We present a formula for Euler’s function.
Relatively Prime Two natural numbers and are called relatively prime if their
greatest common divisor is 1, i.e.,
example 1 The numbers 64 and 81 are relatively prime since the only natural number
that divides evenly into both is 1, i.e., .
Fundamental Theorem of Arithmetic Every natural number greater than 1 has a
unique prime factorization, i.e., for , there exists a unique list of distinct primes and
a unique list of positive integers such that
example 2 Find the prime factorization of 2345.
Since the number 2345 ends in 5, it must be divisible by 5. Hence . Now note that 469 is divisible by 7, and we have . Since 47 is prime, this is the unique prime factorization of 2345.
Since the number 2345 ends in 5, it must be divisible by 5. Hence . Now note that 469 is divisible by 7, and we have . Since 47 is prime, this is the unique prime factorization of 2345.
Euler’s function For each natural number , we define Euler’s function (sometimes
called the totient function) to be the number of natural numbers less than which are
relatively prime to .
example 3 Find .
Among the natural numbers less than 10 the following are relatively prime to 10:
Among the natural numbers less than 10 the following are relatively prime to 10:
Since there are 4 such numbers, .
We now state the main proposition of this section, whose proof utilizes the Inclusion-Exclusion Principle.
- Proof
- If is a natural number less than which is relatively prime to , then
none of the primes will divide . For each , define to be the subset of consisting
of the multiples of the prime . Then
Now, we use the Inclusion-Exclusion Principle to compute : \begin{align*} \phi (n) &= |A_1^c \cap A_2^c \cap \cdots \cap A_r^c|\\ &= |(A_1 \cup A_2 \cup \cdots \cup A_r)^c|\\ &= |S| - |A_1 \cup A_2 \cup \cdots \cup A_r|\\ &= |S| - \sum |A_i| + \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| + \cdots + (-1)^r|A_1 \cap A_2 \cap \cdots \cap A_r|\\[7pt] &= n - \sum \frac{n}{p_i} + \sum \frac{n}{p_ip_j} - \sum \frac{n}{p_ip_jp_k} + \cdots + (-1)^r \frac{n}{p_1p_2 \cdots p_r}\\[7pt] &= n\left (1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_ip_j} - \sum \frac{1}{p_ip_jp_k} + \cdots + (-1)^r \frac{1}{p_1p_2 \cdots p_r} \right )\\[7pt] &= n \prod _{i = 1}^r \left (1 - \frac{1}{p_i}\right ) \end{align*}
- Proof
- Let the prime factorizations of and be Since and are relatively prime, the prime factorization of is given by According to the proposition, and It is now clear that .
example 4 Use the proposition to compute and and then use the corollary to
compute .
Since , the proposition gives and since , the proposition gives Finally, since , the corollary gives
Since , the proposition gives and since , the proposition gives Finally, since , the corollary gives
(problem 4b) Use the proposition to establish a formula for where is any prime and
is a positive integer.
The proof of the proposition uses a factorization theorem. We explore this theorem in the next example and problem.
example 5 Multiply and use this to validate the factorization in the last
step of the proof of the proposition in the case that has 3 distinct prime
factors.
The FPC tells us that there will be terms. Further, we can group these terms according to how many of the variables are present. We have Referring back to the proof of the proposition, suppose had three distinct prime factors, . Then the Inclusion-Exclusion Principle gives If we expand these sums, we obtain Noting that the expression in the brackets has the same form as the expansion of with and , we have
The FPC tells us that there will be terms. Further, we can group these terms according to how many of the variables are present. We have Referring back to the proof of the proposition, suppose had three distinct prime factors, . Then the Inclusion-Exclusion Principle gives If we expand these sums, we obtain Noting that the expression in the brackets has the same form as the expansion of with and , we have
(problem 5a) Multiply and use this to validate the factorization in the last
step of the proof of the proposition in the case that has 4 distinct prime
factors.
2024-09-27 14:05:17