Question 2 - Eulers Toitent Function

Question 1

Definition : Euler totient function

Answer 1

The Euler totient function φ(n) is defined by
φ(n) = |(Z/nZ)^×| = #{x ∈ Z(bar) : 0 ≤ x < n, gcd(x, n) = 1}.

Question 2

Corollary : Z(bar)/nZ(bar) is a field iff n is
prime. (PF ON EXAM)

Answer 2

Let n be a positive integer.
Then Z(bar)/nZ(bar) is a field iff n is
prime.

PROOF:

If n = p is prime, then the number of units is φ(p) = p − 1, so Z(bar)/pZ(bar) is
a field.
If n is not prime, then n has some divisor d such that 1 < d < n, and
gcd(d, n) = d not equal 1, so [d] is a non-zero element of Z(bar)/n(bar) which is not invertible.
That is, [d][n/d] = [n] = [0].

Question 3

Definition : The field of order

Answer 3

Let p be a prime. The field of order p is F(bar)p = Z(bar)/pZ(bar)

Question 4

Theorem : Euler’s Theorem

Answer 4

Let n ≥ 1 and let x ∈ (Z(bar)/nZ(bar))^×. Then x^(φ(n)) = 1.

PROOF:

If G is a group and x ∈ G we have x^(|G|) = 1 by Lagrange’s theorem. Apply this with G = (Z(bar)/nZ(bar))^×.

Question 5

Corollary : Fermat’s Little Theorem

Answer 5

Let p be a prime and let x ∈ Z(bar). Assume x is not divisible by p.
Then x^(p−1) ≡ 1 (mod p).

Question 6

Wilson’s Theorem

Answer 6

Let p be a prime. Then
(p−1)! ≡−1 (mod p)

Question 7

Theorem : Chinese remainder theorem for Z(bar)

Answer 7

Let m_1,…,m_k be pairwise
coprime positive integers and let m= m_1···m_k.
Then Z(bar)/mZ(bar)∼
= Z(bar)/m_1Z(bar) ×···×Z(bar)/m_kZ(bar).
Moreover the map defined by
f(x) = (x mod m_1,…,x mod m_k)
is a ring isomorphism.

Question 8

Lemma Euler coprime

Answer 8

If m,n≥1 are coprime then φ(mn) = φ(m)φ(n)