Euler’s function - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

When something is known about Z_n, it is frequently fruitful to ask whether something comparable applies to U_n. Here we look at U_n in the context of the previous section. To aid the investigation, we introduce a new quantity, the Euler phi function, written ϕ(n), for positive integers n.

Definition 3.8.1 ϕ(n) is the number of non-negative integers less than n that are relatively prime to n. In other words, if n>1 then ϕ(n) is the number of elements in U_n, and ϕ(1)=1.

Example 3.8.2 You can verify readily that ϕ(2)=1, ϕ(4)=2, ϕ(12)=4 and ϕ(15)=8.

Example 3.8.3 If p is a prime, then ϕ(p)=p−1, because 1, 2, …, p−1 are all relatively prime to p, and 0 is not.

For any number n, ϕ(n) turns out to have a remarkably simple form; that is, there is a simple formula that gives the value of ϕ(n). We've already seen how simple it is for primes. As is typical of many results in number theory, we will work our way gradually to any n, looking next at powers of a single prime.

Theorem 3.8.4 If p is a prime and a is a positive integer, then

ϕ(p^a)=p^a−p^a−1

Proof.

We want to calculate the number of non-negative integers less than n=p^a that are relatively prime to n. As in many cases, it turns out to be easier to calculate the number that are not relatively prime to n, and subtract from the total. List the non-negative integers less than pa: 0, 1, 2, …, p^a−1; there are p^a of them. The numbers that have a common factor with p^a (namely, the ones that are not relatively prime to n) are the multiples of p: 0, p, 2p, …, that is, every pth number. There are thus p^a/p=p^a−1 numbers in this list, so ϕ(p^a)=p^a−p^a−1.

□
Example 3.8.5 ϕ(32)=32−16=16, ϕ(125)=125−25=100.

Now we want to extend our formula to handle any positive integer n. Consider an example first:

Example 3.8.6 Since

U₂₀={[1],[3],[7],[9],[11],[13],[17],[19]},

U₄ ={[1],[3]},

U₅ ={[1],[2],[3],[4]}

both U₂₀ and U₄�U₅ have 8 elements. In fact, the correspondence discussed in the Chinese Remainder Theorem between Z₂₀ and Z₄�Z₅ is also a 1-1 correspondence between U₂₀ and U₄�U₅:

[1] ↔ ([1],[1]) [11] ↔ ([3],[1])

[3] ↔ ([3],[3])   [13] ↔ ([1],[3])

[7] ↔ ([3],[2])     [17 ↔ ([1],[2])

[9] ↔([1],[4])  [19]  ↔ ([3],[4])

Using the Chinese Remainder Theorem we can prove that this is true in general.

Theorem 3.8.7 If a and b are relatively prime and n=ab, then ϕ(n)=ϕ(a)ϕ(b).

Proof.
We want to prove that |U_n|=|U_a|⋅|U_b|. As indicated in the example, we will actually prove more, by exhibiting a one to one correspondence between the elements of U_n and U_a�U_b. We already have a one to one correspondence between the elements of Z_n and Z_a�Z_b. Again as indicated by the example, we just have to prove that this same correspondence works for U_n and U_a�U_b. That is, we already know how to associate any [x] with a pair ([x],[x]); we just need to know that [x]∈U_n if and only if ([x],[x])∈U_a�U_b. After a long-winded build up, here's the proof: [x] is in U_n if and only if (x,n)=1 if and only if (x,a)=1 and (x,b)=1 if and only if ([x],[x])∈U_a�U_b.

Corollary 3.8.8 Suppose n=ab, with a and b relatively prime. For x=0,1,…,n−1, if [x]∈U_n, associate [x] with ([x],[x])∈Z_a�Z_b. This gives a one-to-one correspondence between U_n and U_a�U_b.

Proof.
We proved this already in the proof of the previous theorem, but it deserves its own statement.

Now we know enough to compute ϕ(n) for any n.

Example 3.8.9    ϕ(200)=ϕ(25)ϕ(8)=(25−5)(8−4)=80.

Example 3.8.10

ϕ(2³3⁴7²)=ϕ(2³)ϕ(3⁴7²)=ϕ(2³)ϕ(3⁴)ϕ(7²)=(2³−2²)(3⁴−3³)(7²−7)

We can express this as a formula once and for all:

Theorem 3.8.11 If n is a positive integer with prime factorization  , then

Proof.

The proof by induction is left as an exercise.

Leonhard Euler. Euler (pronounced "oiler'') was born in Basel in 1707 and died in 1783, following a life of stunningly prolific mathematical work. His complete bibliography runs to nearly 900 entries; his research amounted to some 800 pages a year over the whole of his career. He continued doing research right up until his sudden death while relaxing with a cup of tea. For almost all of the last 17 years of his life he was totally blind.

The breadth of Euler's knowledge may be as impressive as the depth of his mathematical work. He had a great facility with languages, and studied theology, medicine, astronomy and physics. His first appointment was in medicine at the recently established St. Petersburg Academy. On the day that he arrived in Russia, the academy's patron, Catherine I, died, and the academy itself just managed to survive the transfer of power to the new regime. In the process, Euler ended up in the chair of natural philosophy instead of medicine.

Euler is best remembered for his contributions to analysis and number theory, especially for his use of infinite processes of various kinds (infinite sums and products, continued fractions), and for establishing much of the modern notation of mathematics. Euler originated the use of ee for the base of the natural logarithms and ii for  the symbol ππ has been found in a book published in 1706, but it was Euler's adoption of the symbol, in 1737, that made it standard. He was also responsible for the use of ∑ to represent a sum, and for the modern notation for a function, f(x).

Euler's greatest contribution to mathematics was the development of techniques for dealing with infinite operations. In the process, he established what has ever since been called the field of analysis, which includes and extends the differential and integral calculus of Newton and Leibniz. For example, by treating the familiar functions sinx, cosx and ex analytically (as infinite series), Euler could easily establish identities that became fundamental tools in analysis. One such is the well-known e^ix=cosx+isinx; substituting x=π gives e^iπ=−1 or e^iπ+1=0, a remarkable equation containing perhaps the five most important constants in analysis.

Euler used infinite series to establish and exploit some remarkable connections between analysis and number theory. Many talented mathematicians before Euler had failed to discover the value of the sum of the reciprocals of the squares: 1⁻²+2⁻²+3⁻²+⋯. Using the infinite series for sinx, and assuming that it behaved like a finite polynomial, Euler showed that the sum is π²/6. Euler's uncritical application of ordinary algebra to infinite series occasionally led him into trouble, but his results were overwhelmingly correct, and were later justified by more careful techniques as the need for increased rigor in mathematical arguments became apparent. We'll see Euler's name more than once in the remainder of the chapter.

The information here is taken from A History of Mathematics, by Carl Boyer, New York: John Wiley & Sons, 1968.