Ch3 Euler’s totient function

Question 1

Definition 3.1.1 (Euler’s totient function)

Answer 1

For n ≥ 1, the totient of n, written ϕ(n), is the number of integers k such that 1 ≤ k ≤ n which are coprime with n
(that is, gcd(k, n) = 1).

(For a positive natural we find the totient of n # of integers in {1,…n} s.t gcd(k,n)=1 coprime to n)

Question 2

Example 3.1.2. *
ϕ(10)
ϕ(1) =
ϕ(p)

Answer 2

ϕ(10)=4
(2,5 and 10 are factors 4,6,8 not coprime)
: the set of numbers between 1 and 10 which are
coprime with 10 is {1, 3, 7, 9};
ϕ(1) = 1
ϕ(p)= p-1 iff p is prime p>2

by the lemma its a multiplicative funct
ϕ(10)=ϕ(5)ϕ(2) = 1*4
ϕ(pqr) = (p-1)(q-1)(r-1) by this too

Question 3

multiplicative functs

Answer 3

ϕ(n) is a multiplicative funct

if two numbers are coprime gcd(p,q)=1
ϕ(pq)=ϕ(p)ϕ(q)
ϕ(pqr) = (p-1)(q-1)(r-1) by this too

Other multiplicative funct:
d(n)~# divisors of n
= sum_{d|n} 1
(for two comprimes its multiplicative)

sigma(n)= sum_{d|n} d
(sum of divisors relates to perfect numbers)
sigma_k is
Möbius function

Question 4

remark multiplicative functs

Answer 4

Remark 3.1.5. A function f : N^{≥1} → N is called multiplicative if f (ab) = f (a) f (b)
whenever a and b are coprime. It is completely multiplicative (or totally multiplicative)
if f (ab) = f (a) f (b) for every a, b. Such functions are ubiquitous in number theory.
Some examples:
(1) d(n) := Σd|n 1: the number of positive divisors of n;
(2) σ(n) := Σd|n d: the sum of the positive divisors of n;
(3) σk(n) := Σd|n d_k: the sum of the k-th powers of the positive divisors of n (note
that d(n) = σ0(n), σ(n) = σ1(n);
(4) the Möbius function
μ(n) =
1 if n = 1
(−1)k if n is a product of k distinct primes
0 otherwise.

Question 5

completely multiplicative

Answer 5

None of those functions is completely multiplicative: for instance d(4) = 3 ̸= d(2)2.
Completely multiplicative functions include instead:
* 1(n) := 1: the constant function 1;
* Id(n) := n: the identity function;
* n → n^k.

Question 6

Remark 3.1.3. totient

Answer 6

The number ϕ(n) is exactly the size of the group
(Z/nZ)×.

Indeed, we are looking at the numbers between 1 and n which are coprime to n;

this is the same as the numbers between 0 and n − 1 which are coprime to n.

This immediately implies that if a is coprime with n, then
a^ϕ(n) ≡ 1 (mod n). We’ll come back to this
taking an element a from the group and raising to the power when gcd(a,n)=1

Question 7

Lemma 3.1.4.
totient function of coprime naturals

Answer 7

If m, n ∈ N are coprime, then ϕ(m)ϕ(n) = ϕ(mn).

“multiplicative function”
“won’t spend too much time on, what that means”

holds only when n,m are coprime not in general

Question 8

PROOF of
If m, n ∈ N are coprime, then ϕ(m)ϕ(n) = ϕ(mn).

Answer 8

Consider mapping:
F : {0, 1, . . . , mn − 1} → {0, 1, . . . , m − 1} × {0, 1, . . . , n − 1}

defined by F(k) = (a, b), where a is the remainder of k
modulo m (congruence class of k mod m k=a mod m)
and
b the remainder of k modulo n. (k=b modn)
k mapped to (a,b)

Since gcd(m,n)=1: By the Chinese Remainder Theorem, the map F is a bijection( onto (because x ≡ a (mod m) and x ≡ b (mod n) has a solution for every a, b) and injective (because the solution is unique modulo mn).

To state this more abstractly, the map Z/mnZ → Z/mZ × Z/nZ defined as above is a bijection

Observe, k is coprime to mn.
IFF
k is coprime to n and k is coprime to m. (not using m and m coprime) (by Corollary 1.1.12)
IFF
a is coprime to n and b is coprime to m s.t (a,b)=F(k)
(whether k is coprime to m dep on when a coprime to m, because k ≡ a (mod m) and k ≡ b (mod n))

The numbers of k’s coprime to mn is ϕ(mn); the numbers of pairs (a, b) where a is coprime to m and b is coprime to n is ϕ(m)ϕ(n). Thus ϕ(mn) = ϕ(m)ϕ(n).

Question 9

Remark 3.1.5.

Answer 9

missed some notes??

Question 10

Thm Eulers product thm 3.2.1

Answer 10

(used for powers of primes using (p^α=pᵃ))

For a prime power p^α
, ϕ(pᵃ) = pᵃ − pᵃ⁻¹ = pᵃ(1 − (1/p))
(from prev thm)

In general, if n = p₁ᵃ¹· · · pₜᵃᵗ , (using ftoa)
where the pᵢ’s are distinct prime factors of n,
then (we can apply the thm as each prime factor is comprime to the others)

ϕ(n) = (pᵃ-¹ - pᵃ-¹⁻¹)· · ·(pᵃ-ᵗ - pᵃ-ᵗ⁻¹)·)
=n(1- (1/pₜ))· · · (1 - (1/pₜ))

Question 11

eulers product thm proof

used for powers of primes using (p^α=pᵃ))

For a prime power p^α
, ϕ(pᵃ) = pᵃ − pᵃ⁻¹ = pᵃ(1 − (1/p))
(from prev thm)

In general, if n = p₁ᵃ¹· · · pₜᵃᵗ , (using ftoa)
where the pᵢ’s are distinct prime factors of n,
then (we can apply the thm as each prime factor is comprime to the others)

ϕ(n) = (pᵃ-¹ - pᵃ-¹⁻¹)· · ·(pᵃ-ᵗ - pᵃ-ᵗ⁻¹)·)
=n(1- (1/pₜ))· · · (1 - (1/pₜ))

Answer 11

Take a prime power pᵃ . Since p is prime, the only numbers not coprime with pᵃ are the multiples of p; below pᵃ {p,2p,3p,…,p²,…,p^n} so there are pᵃ/p of them= pᵃ⁻¹

Eg multiples of prime until prime to the power of alpha minus one

ϕ(pᵃ)= # coprime to p below pᵃ are pᵃ-pᵃ⁻¹ many.

(when n is the power of a single prime)
For general n, just use that ϕ is multiplicative and combine the above result. As long as factors are pairwise coprime, distinct factors taken as fundamental thm of arithmetic.
ϕ(n) = (pᵃ-¹ - pᵃ-¹⁻¹)· · ·(pᵃ-ᵗ - pᵃ-ᵗ⁻¹)·)
=n(1- (1/pₜ))· · · (1 - (1/pₜ))

Question 12

ϕ(m) link to group

Answer 12

ϕ(m) is also the cardinality of the multiplicative group {z/mz}*

Question 13

Example 3.2.2. ϕ(2560)=

Answer 13

3.2.2. ϕ(2560) = ϕ(2^9 · 5)
= 2560(1 − 1/2)(1 − 1/5)
= 1024.

Question 14

Extra.We can also verify manually that ϕ(2560) = 1024.

Answer 14

Indeed, the numbers not coprime
with 2560 are the numbers divisible by 2 and the numbers divisible by 5. There are 2560/2 = 1280
numbers below 2560 that are divisible by 2; and 2560/5 = 512 are divisible by 5; we are counting twice the numbers that are multiple of 10, and there are 256 of those.
Thus, the numbers not coprime with 2560 are 1280 +512 −256 = 1536; so the numbers coprime
with 2560 are 2560 − 1536 = 1024.

Question 15

Theorem 3.2.3 (Euler / Euler-Fermat theorem (Euler, 1763))

Answer 15

If a is coprime with n,
then aᵠ⁽ⁿ⁾ ≡ 1 (mod n).

Question 16

Group-theoretic proof.

Theorem 3.2.3 (Euler / Euler-Fermat theorem (Euler, 1763))
If a is coprime with n,
then aᵠ⁽ⁿ⁾ ≡ 1 (mod n).

Answer 16

By Lagrange’s theorem, because ϕ(n) is the size of the group
(Z/nZ)×.

any element multiplied by itself this many times links to cardinality

Question 17

Combinatorial proof.

(Similar to FLittleThm)

Theorem 3.2.3 (Euler / Euler-Fermat theorem (Euler, 1763))
If a is coprime with n,
then aᵠ⁽ⁿ⁾ ≡ 1 (mod n).

Answer 17

Same as proof for Fermat’s little theorem:

let r₁, . . . , rᵩ₍ₙ₎ be the numbers between 0 and n − 1 that are coprime with n.

Then ar₁, . . . , arᵩ₍ₙ₎ are pairwise non congruent to each other (mod m). Because if a coprime with m we have the cancellation showing the left overs are also coprime. So in this case we don’t have this.

I can shuffle them around.

By lemma 2.1.8, the congruence classes of ar₁, . . . , arᵩ₍ₙ₎ are just a permutation of the classes of r₁, . . . , rᵩ₍ₙ₎. Therefore products
(ar₁) . . . (arᵩ₍ₙ₎)≡ r₁ . . . rᵩ₍ₙ₎≡ (mod n)

=aᵠ⁽ⁿ⁾ product rᵢ from i=1 to rᵢ
thus, after cancelling the rᵢ’s (which we can do, because gcd(rᵢ, n) = 1 so their product is also coprime to n), we find that
aᵠ⁽ⁿ⁾ ≡ 1 (mod n).

Question 18

Example 3.2.4. Take n = 18, a = 7.

ϕ(18)

Answer 18

didnt go through but relates to prev thm

The numbers coprime with 18 are {1, 5, 7, 11, 13, 17},
and so ϕ(18) = 6.

Modulo 18, we have
7 · 1 ≡ 7, 7 · 5 ≡ 17, 7 · 7 ≡ 13, 7 · 13 ≡ 7 · (−5) ≡ 1, 7 · 17 ≡ 11 (mod 18).
Thus
76 · (1 · 5 · 7 · 11 · 13 · 17) ≡ 7 · 17 · 13 · 5 · 1 · 11 (mod 18),

so 7⁶ ≡ 1 (mod 18).

We can also verify 7⁶ ≡ 1 directly:
7⁶ ≡ (13)³ ≡ (−5)³ = (−5) · 25 ≡ (−5) · 7 ≡ −(−1) = 1 (mod 18).

Question 19

Example 3.2.5. Compute the last three digits of
3²⁰²⁴ without using a calculator.

Answer 19

(computing the last digits we compute remainder mod 10; last 3 then mod 1000) This means computing the remainder of 3²⁰²⁴ modulo 1000. First of all,
ϕ(1000) = 1000 ·(1 −1/2)(1 −1/5) = 400. (by Euler’s)

Since 3 is coprime with 1000, we have (by Euler-Fermat)
3⁴⁰⁰ ≡ 1 (mod 1000). Thus
3²⁰²⁴ = (3⁴⁰⁰ )· 3²⁴ ≡ 3²⁴ (mod 1000).

The exponent is still quite large, so we try to be clever. Write
3²⁴ = 9¹² = (10 − 1)¹².
We also have
(10 − 1)¹² =
10¹²−(12)10¹¹ + · · · + (12) 10² - (12)10+1
(1) (10) (11)

(note the negative terms)

When we divide modulo 1000, we can discard the high powers of 10, and we are left
with
3²⁰²⁴ ≡ 3²⁴ = 9¹² ≡
(12) 10² - (12) 10 +1
(10) (11)
= 6600 − 120 + 1 ≡ 481 (mod 1000).

(Now double check with a calculator that 3²⁴ does end with 481.)

Question 20

Theorem 3.3.1 (Gauss, 1801 (art. 39))

Answer 20

Let n ∈ N≥¹

Then Σ_{d|n} ϕ(d) = n.

*we have a formula to compute ϕ(d) already
*thm says if for every divisor of n; all naturals s.t d|n of ϕ(d) ;

for every divisor I take the all the numbers coprime to d between 1 and d and I count how many there are, and I take the sum

Question 21

Proof
thm 3.3.1 Gauss

Let n ∈ N≥¹

Then Σ_{d|n} ϕ(d) = n

Answer 21

For each positive divisor d of n, let
S_d := {m : 1 ≤ m ≤ n, gcd(m, n) = d}.
Clearly a partition of the set {1, . . . , n}, namely
S_d ∩ S_e = ∅ when d ̸= e
and
U_{d|n} S_d = {1, . . . , n}.
(e.g S_1={1,…,n}}

Therefore, Σ_{d|n} |S_d| = n. (size of set n is equal to sum of sizes of the partition sets)

On the other hand,
m ∈ S_d IFF
d | m (its the gcd of n and m) and gcd(m/d, n/d) = 1 (by Corollary 1.1.12, again).
(from the exercises)
This means that |S_d| = ϕ(n/d).
Explanation:
(counting # possible choices for n # things coprime to n/d between 1 and n/d)
S_d is made of divisors, dividing every member by d
S_d= d E_d
E_d=[m/d for m∈ S_d]
=[ k 1<k<n/d and gcd(k,n/d)=1]
|E_d|=ϕ(n/d

To conclude, note that
d divides n IFF
n/d divides n.
Thus we may reindex the sum and discover that
n =Σ_{d|n} |S_d|
=Σ_{d|n} |S_{n/d}| another divisor just reorders sum
=Σ_{d|n} ϕ(d).

Question 22

Example 3.3.2. Take n = 12.

Form sets S_d to show the totient function of n/divisor forms a partition

Answer 22

d| S_d | ϕ( 12/d )
1 |S₁ = {1, 5, 7, 11} |ϕ(12) = 12(1 − 1/2 )(1 − 1/3 ) = 4
2 |S₂ = {2, 10} |ϕ(6) = 2
3 |S₃ = {3, 9} |ϕ(3) = 2
4 |S₄ = {4, 8} |ϕ(4) = 2
6 |S₆ = {6} |ϕ(2) = 1
12 |S₁₂ = {12} | ϕ(1) = 1
Indeed, Σ_{d|12} ϕ(d)
= Σ_{d|12} |S_d|
= 4 + 2 + 2 + 2 + 1 + 1 = 12.

method:
divisors of 12 {1,2,3,4,6,12} which are coprime
S_2 are all# s.t have gcd 2 (so not divisible by 3,4,6 etc)forming a partition and sums agree