Euler’s ϕ-function %%visits: 2
Find a formula for ϕ(pa)
Explain why ϕ(mn) = ϕ(m)ϕ(n) if gcd(m, n) = 1 (if they are coprime) m, n ∈ ℤ
Euler_functio := Let m be a positive integer. We define
ϕ(m) = |{1 ≤ a ≤ m : gcd(a, m) = 1}|
which is how many integers are coprime to this number.
ϕ(m) = |ℤmx|, ℤmx being the multiplicative group of units of ℤm
ϕ(1) = 1, ϕ(6) = 2 since 1, 2, 3, 4, 5, 6 and only 1, 5 are coprime
ϕ(p) = p − 1 if p is prime.
ϕ(25) since 5 has 2 of the same factors, then we only need to consider the multiples of 5. there are 5 multiples of 5, so 20 other numbers that do not share divisors. The same with ϕ(125)
Generalising this to a lemma, ϕ(pa) = pa − pa − 1.
Let m, n be two coprime positive integers. The ϕ(mn) = ϕ(m)ϕ(n)
Let m be a positive integer. Then $$
_{d= divisors of m greater than 0} (d) = m $$ # Example Take m = 8
∑0 < d|8ϕ(8) = ϕ(1) + ϕ(2) + ϕ(4) + ϕ(8) = 1 + 1 + 2 + 4 = 8
take ∑0 < d|paϕ(d) = ϕ(1) + ϕ(p) + ϕ(p2) + ϕ(p3) + … + ϕ(pa) = 1 + (p − 1) + (p2 − p) + … + (pa − pa − 1) which is a telescoping_series so it equals pa
Proof, for m, n ≥ 1, which are coprime. By the fundamental_theorem_of_arithmetic there is a 1-to-1 correspondence between {d ∈ ℕ : d|mn}
and {(a, b) ∈ ℕ2 : a|m and b|n}
Let F(m) = ∑0 < d|mnϕ(d). Hence, using that ϕ(ab) = ϕ(a)ϕ(b) for gcd(a, b) = 1. $$
F(mn) = {0<d|mn} (d) = {0<a|m \ 0 < b|n}(ab) = {0<a|m} (a) {0<b|m} (b) = F(m)F(n) $$
Writing m = p1a1p2a2…pnan
F(m) = F(p1a1p2a2…pnan) = F(p1a1)F(p2a2)…F(pnan) = p1a1p2a2…pnan = m
Example. ϕ(4) = |{1 ≤ 4 : gcd(a, 4}| Example. $\phi(2^{n}) = \frac{1}{2} 2^{n}$ since it is every odd number Example. ϕ(p) = p − 1
tags :math: