12. Let p and q be prime numbers. (a) Prove that (p q) = (p -...

12. Let p and q be prime numbers.

(a) Prove that φ(p ⋅ q) = (p - 1) ⋅ (q - 1).

(b) Let n = p ⋅ q and x ∈ Z. Define x0 i ≥ 0.

def

= x² mod n and xi+1 = x² mod n for all

(i) Use mathematical induction on *i* to show that x*_i* = x ₀²ⁱ mod *n*.
(ii) Use the facts from Exercises 11 and 12

(a) to show that x₀²ⁱ mod *n* = x₀^a_i mod *n*, where a_i = 2ⁱ mod (p-1) (q-1).
(iii) Conclude that x_i = x₀^a_i mod *n* for all *i* ≥ 0.