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 e for the
base of the natural logarithms and ii for −1−−−√−1; 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.

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 + 2 – 2 + 3 – 2 + ⋯. Using the infinite series
for sinx, and assuming that it behaved like a finite polynomial, Euler showed that the sum is π2/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.
Euler's Totient Function and Euler's Theorem

• The Euler's totient function, or phi (φ) function is a very important number theoretic function
having a deep relationship to prime numbers and the so-called order of integers. The totient
φ(n) of a positive integer n greater than 1 is defined to be the number of positive integers less
than n that are coprime to n. φ(1) is defined to be 1. The following table shows the function
values for the first several natural numbers:

n φ(n) numbers coprime to n

1 1 1
2 1 1
3 2 1, 2
4 2 1, 3
5 4 1, 2,3,4
6 2 1, 5
7 6 1, 2, 3,4, 5, 6
8 4 1, 3, 5, 7
9 6 1, 2, 4, 5, 7, 8
10 4 1, 3, 7, 9
11 10 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
12 4 1, 5, 7, 11
13 12 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
14 6 1, 3, 5 ,9, 11, 13
15 8 1, 2, 4, 7, 8, 11, 13, 14

• Can you find some relationships between n and φ(n)? One thing you may have noticed is that:
when n is a prime number (e.g. 2, 3, 5, 7, 11, 13), φ(n) = n – 1.
• But how about the composite numbers? You may also have noticed that, for example, 15 = 3*5
and φ(15) = φ(3)*φ(5) = 2*4 = 8. This is also true for 14,12,10 and 6. However, it does not hold for
4, 8, 9. For example, 9 = 3*3 , but φ(9) = 6 ≠ φ(3)*φ(3) = 2*2 =4. In fact, this multiplicative
relationship is conditional:
when m and n are coprime, φ(m*n) = φ(m)*φ(n).
• The general formula to compute φ(n) is the following:
If the prime factorization of n is given by n =p1e1*...*pnen, then φ(n) = n *(1 - 1/p1)* ... (1 - 1/pn).

For example:
9 = 32, φ(9) = 9* (1 − 1/3) = 6
4 =22, φ(4) = 4* (1 − 1/2) = 2
15 = 3*5, φ(15) = 15* (1 − 1/3)*(1 − 1/5) = 15*(2/3)*(4/5) =8
 • Euler’s theorem generalises Fermat’s theorem to the case where the modulus is not prime. It says
that:
if n is a positive integer and a, n are coprime, then aφ(n) ≡ 1 mod n where φ(n) is the Euler's
totient function.
Let's see some examples:
165 = 15*11, φ(165) = φ(15)*φ(11) = 80. 880 ≡ 1 mod 165
1716 = 11*12*13, φ(1716) = φ(11)*φ(12)*φ(13) = 480. 7480 ≡ 1 mod 1716
φ(13) = 12, 912 ≡ 1 mod 13
• We can see that Fermat's little theorem is a special case of Euler's Theorem: for any prime n, φ(n)
= n-1 and any number a 0< a <n is coprime to n. From Euler's Theorem, we can easily get several
useful corollaries. First:
if n is a positive integer and a, n are coprime, then aφ(n)+1 ≡ a mod n.
• This is because aφ(n)+1 = aφ(n)*a, aφ(n) ≡ 1 mod n and a ≡ a mod n, so aφ(n)+1 ≡ a mod n. From here,
we can go even further:
if n is a positive integer and a, n are coprime, b ≡ 1 mod φ(n), then ab ≡ a mod n.
If b ≡ 1 mod φ(n), then it can be written as b = k*φ(n)+1 for some k. Then ab = ak*φ(n)+1 = (aφ(n))k*a.
Since aφ(n) ≡ 1 mod n, (aφ(n))k ≡ 1k ≡ 1 mod n. Then (aφ(n))k*a ≡ a mod n. This is why RSA works.
Euler’s Theorem
• Let be Euler's totient function. If is a positive integer, is the number of integers in
the range which are relatively prime to . If is an integer and is a positive
integer relatively prime to ,Then .
Credit
• This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which
specifies that is prime. For this reason it is also known as Euler's generalization or the Fermat-
Euler theorem.
Four Properties of the Euler Phi Function
1. Prove that the Euler Phi-function is Multipilcative.
• Suppose t = mn where m, n are coprime, then the Chinese Remainder Theorem states that (a, t)
= 1 if and only if (a, m) = 1 and (a, n) = 1. Now the number of positive integers not greater than t
and coprime with t is precisely (t), but it is also the number of pairs (u, v) where u is not greater
than m and coprime with m and v not greater than n and coprime with n, (mn) = (m) (n)

2. For any positive integers m and n, prove that (mn) = (m)• (n) •(d/(d)), where d is the gcd
of m and n.
• The multiplicative nature makes the m and n parts doable, what happens with d/(d)? Note that
the case d = 1 is equivalent to the first property.

3. For any positive integer m and n, prove that (m) • (n) = (gcd(m, n)) • (lcm(m, n))
• It might be possible to use the fact that gcd(m, n) lcm(m, n) = mn or does that move away from
the multiplicativity? As a last resort, the prime factorization of m and n could be used.

4. Take n to be a positive integer greater than 1. Prove that the sum of the integers m with 1 < m <
n that are coprime with n is (n • (n)/2.
• If m is coprime with n, what can you say about n – m and n? They are also coprime?

➢ When something is known about Zn, it is frequently fruitful to ask whether something
comparable applies to Un. Here we look at Un 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 nn.

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 Un, 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 ϕ(pa)=pa−pa−1.

Proof: We want to calculate the number of non-negative integers less than n=pa 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, …, pa−1; there are pa of them. The numbers that have a
common factor with pa (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 pa/p=pa−1 numbers
in this list, so ϕ(pa)=pa−pa−1.

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

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

Corollary 3.8.8: Suppose n = ab, with a and b relatively prime. For x = 0, 1, …, n−1, if [x] ∈ Un,
associate [x] with ([x],[x]) ∈ Za × Zb. This gives a one-to-one correspondence between Un and Ua
× Ub.

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

Example 1: ϕ(200)=ϕ(25) ϕ(8)=(25−5)(8−4) = 80

Theorem 3.8.11: If n is a positive integer with prime

factorization pe1pe2⋯pekkp1e1p2e2⋯pkek, then
ϕ(n)=(pe11−pe1−11)(pe22−pe2−12)⋯(pekk−pek−1k).ϕ(n)=(p1e1−p1e1−1)(p2e2−p2e2−1)⋯(pk
ek−pkek−1).