Congruences mod Primes, Order, Primitive Roots

Lecture 7 Congruences mod Primes, Order, Primitive Roots Continuation of Proof of Hensel’s Lemma. By lemma, f (a + tpj ) ≡ f (a) + tpj f ' (a) (mod pj+1 ) Now we want to have the right hand side ≡ 0 mod pj+1 . f (a) + tpj f ' (a) ≡ 0 mod pj+1 ↔ tf ' (a) + f (a) ≡0 pj mod p this has a unique solution t≡− f (a) 1 pj f ' (a) mod p • Direct formula - start with solution a of f (x) ≡ 0 mod p, and we want a solution mod p∗ . Set a1 = a. aj+1 = aj − f (aj )f ' (a) (mod pj+1 ) where f ' (a) is an integer chosen once at the beginning of the algorithm, which only matters mod p. It’s chosen such that f ' (a)f ' (a) ≡ 1 mod p. Then f (aj ) ≡ 0 mod pj for j ≥ 1 as long as f ' (a) ≡ 0 mod p. Eg. Solve the congruence x2 ≡ −1 mod 125. (f (x) = x2 + 1, f ' (x) = 2x). Mod 5: 22 ≡ −1 mod 5, so set a = 2. f ' (a) ≡ 4 mod 5, so can choose f ' (a) = −1. a1 = 2 (mod 5) a2 = a1 − f (a1 )f ' (a) (mod 25) = 2 − (5)(−1) (mod 25) = 7 (mod 25) a3 = a2 − f (a2 )f ' (a) (mod 125) = 7 − (50)(−1) (mod 125) = 57 (mod 125) Congruences to prime modulus: Assume that all the coefficients of f (x) = an xn + an−1 xn−1 · · · + a0 are reduced mod p and also that an ≡ 0 mod p. By dividing out by an , can assume that f (x) is monic (ie., highest coefficient is 1). We can also assume degree n of f is less than p. If not, can divide f by xp − x to get f (x) = g(x)(xp − x) + r(x) with deg(r(x)) < p f (a) = g(a)(ap − a) + r(a) ≡ r(a) mod p by Fermat so roots of f (x) mod p are the same as the roots of r(x) mod p. 1 Theorem 28. A congruence f (x) ≡ 0 mod p of degree n has at most n solutions. Proof. (imitates proof that polynomial of degree n has at most n complex roots) Induction on n: congruences of degree 0 and 1 have 0 and 1 solutions, trivially. Assume that it holds for degrees < n (n ≥ 2) If it has no roots, then we’re done. Otherwise, suppose it does have a root α. Dividing f (x) by x − α, we get g(x) ∈ Z[x] and a constant r such that f (x) = g(x)(x − α) + r. Now if we plug in α we get f (α) = (α − α)g(α) + r = r, which means that f (α) = r and f (x) = (x − α)g(α) + f (α). We know that f (α) ≡ 0 mod p. If β is any other root of f (x) then we plug β into the equation to get f (β) = (β − α)g(β) + f (α). Mod p, f (β) ≡ (β − α)g(β) mod p, so 0 ≡ (β − α)g(β). We also assume that β ≡ α, so g(β) ≡ 0 mod p. So β is a root of g(x) as a solution of g(x) ≡ 0 mod p. We know that g(x) has degree n − 1, so by induction hypothesis g(x) ≡ 0 mod p has at most n − 1 solutions, which by including α gives f (x) at most n solutions. • Corollary 29. If an xn + an−1 xn−1 + · · · + a0 ≡ 0 mod p has more than n solutions, then all ai ≡ 0 mod p. Theorem 30. Let f (x) = xn + an−1 xn−1 + · · · + a0 . Then f (x) ≡ 0 mod p has exactly n distinct solutions if and only if f (x) divides xp − p mod p. Ie., there exists g(x) ∈ Z[x] such that f (x)g(x) = xp − x mod p as polynomials (all coefficients mod p) Proof. Suppose f (x) has n solutions. Then n ≤ p because only p possible roots mod p (ie., deg(f ) ≤ deg(xp − x)). Divide xp − x by f (x) to get xp − x = f (x)g(x) + r(x), deg(r) < deg(f ) = n Now note, if α is a root of f (x) mod p then plug in to get αp − α = f (α)g(α) + r(α) ≡ 0g(α) + r(α) ≡ r(α) mod p so α must be a solution to r(x) ≡ 0 mod p. Since f (x) has distinct roots, we see that r(x) ≡ 0 mod p has n distinct solutions. But deg(r) < n. So by corollary we must have r(x) ≡ 0 mod p as a polynomial (each coefficient is 0 mod p.) Ie., xp − p = f (x)g(x) mod p, and so f (x) divides xp − x. Now suppose f (x)|xp − x mod p. Write xp − x ≡ f (x)g(x) mod p, where f (x) is a monic of degree n and g(x) is a monic of degree p − n. We want to show that f (x) has n distinct solutions. 2 By previous theorem, g(x) has at most p − n roots mod p. If α ∈ 0, 1, . . . p − 1 is not a root of g(x) mod p then αp − α ≡ f (α)g(α) mod p, which by Fermat ≡ 0. Since g(α) ≡ 0 mod p, f (α) ≡ 0 mod p. So since there are at least p − (p − n) such α, we see that f (x) has at least n distinct roots mod p. By the theorem, f (x) has at most n roots mod p ⇒ f (x) has exactly n distinct roots mod p. • Corollary 31. If d|p − 1 then xd ≡ 1 mod p has exactly d distinct solutions mod p. Proof. d|p − 1, so xd−1 − 1|xp−1 − 1 as polynomials. p − 1 = kd, so xkd − 1 = (xd − 1)(x(k−1)d · · · + 1). So xd − 1|x(xp−1 − 1) = xp − x. So has d solutions. • Corollary 32. Another proof of Wilson’s Theorem Proof. Let p be an odd prime. Let f (x) = x(x − 1)(x − 2) . . . (x − p + 1). This has deg p and p solutions mod p, so it must divide xp − x mod p. Both polynomials are monic of the same degree (p), so must be equal mod p. x(x − 1) . . . (x − (p − 1)) ≡ xp − x mod p Coefficient of x on the LHS is just (−1)(−2) . . . (−(p − 1)) = (−1)p−1 (p − 1)! = (p − 1)! since p is odd, and so (p − 1)! ≡ −1 mod p (coefficient on RHS). • This tells us much more as well - eg., 1 + 2 + · · · + p − 1 ≡ 0 mod p for p ≥ 3, and (1)(2) + (1)(3) + . . . (2)(3) · · · + (p − 1)(p − 2) ≡ 0 mod p for p ≥ 5. If we have a product f (x) = (x − α1 ) . . . (x − αn ) then f (x) = xn − σ1 xn−1 + σ2 xn−2 + . . . (−1)n σn . σi are elementary symmetric polynomials. σ1 = αi σ2 = αi αj i 0, contradicts minimality of h, which means that r = 0, and k is multiple of h. • Lemma 34. If h = ordm (a) then ak has order k (k,h) mod m. Proof. akj ≡ 1 mod m ↔ h|kj h k ↔ | j (h, k) (h, k) h ↔ |j (h, k) So smallest such positive j = h (h,k) . • Lemma 35. If a has order h mod m and b has order k mod m, and (h, k) = 1, then ab has order hk mod m. Proof. We know (ab)hk ≡ (ah )k (bk )h ≡ 1k 1h ≡ 1 mod m Conversely suppose that r = ordm (ab). (ab)r ≡ 1 rh mod m (ab) ≡1 h r rh ≡ 1 mod m rh ≡ 1 mod m (a ) b b mod m so k|rh ⇒ k|r (since (k, h) = 1), and similarly h|r. So hk|r, and so hk = • ordm (ab). (Definition) Primitive Root: primitive root mod m. If a has order φ(m) mod m, we say that a is a Eg. mod 7: 4 1 2 3 4 5 6 has order has order has order has order has order has order 1 3 6 3 6 2 . (23 ≡ 1 mod 7) (φ(7) = 6) . (φ(7) = 6) Lemma 36. Let p be prime and suppose q e ||p − 1 for some other prime q. Then there’s an element mod p of order q e . Assuming Lemma... p − 1 = q1e1 q2e2 . . . qrer Lemma says that ∃ g1 with ordp (g1 ) = q1e1 , g2 with ordp (g2 ) = q2e2 , etc. Set g = g1 g2 . . . gr . So by previous lemma above, g has order q1e1 q2e2 . . . qrer = p − 1 because all qi are coprime in pairs. p − 1 = φ(p), so g is a primitive root mod p. e e Proof. Consider solutions of xq ≡ 1 mod p. Because q e |p − 1, xq − 1 has exactly q e roots mod p. If α is any such root, then ordp (α) must divide q e . So if it’s not equal to q e , it must divide q e−1 . Then α would have to be root of e−1 xq − 1 ≡ 0 mod p, which has exactly q e−1 solutions. Since q e − q e−1 > 0, there exists α such that ordp (α) = q e . • 5