18.781 Solutions to Problem Set 4 (Part 1)

18.781 Solutions to Problem Set 4, Part 1 1. (a) If x is a cube root of 1 then x3 ≡ 1 (mod 1024). Obviously x must be coprime to 1024, so xφ(1024) = x512 ≡ 1 (mod 1024) by Fermat. Since 3 and 512 are coprime, and the order of x mod 1024 divides both, it must be 1. Therefore x ≡ 1 (mod 1024). (b) By part (a), if a cube root of −3 exists, it must be unique (if x, y are both cube roots of −3 mod 1024, then (xy −1 )3 ≡ 1 (mod 1024) so x ≡ y). Now 53 = 125 ≡ −3 (mod 128). Note that the derivative of x3 + 3 is 3x2 , and 3 · 52 6≡ 0 (mod 2). We have f (5) = (3 · 52 )−1 ≡ 1 (mod 2). Lifting to a cube root mod 256, we get 5 − 128 ≡ 5 + 128 ≡ 133 (mod 256). Now 1333 = (5 + 128)3 ≡ 53 + 3 · 52 · 128 ≡ −3 + 76 · 128 ≡ −3 (mod 512), so we don’t need to modify 133 mod 512. Mod 1024, we have 1333 ≡ −3 + 76 · 128 ≡ −3 + 39 · 512 ≡ −3 + 512 (mod 1024), so the solution is 133 − 512 ≡ 133 + 512 ≡ 645 (mod 1024). (c) First, working mod 3, it’s easy to see that the only solution is x ≡ 1 (mod 3). Now f 0 (1) = 5 + 4 ≡ 0 (mod 3), so it’s not a nonsingular solution and we can’t apply Hensel’s lemma. But the proof of Hensel’s lemma (by Taylor series expansion) tells us that mod 9, all the lifts of 1 (i.e., 1, 4, 7) will have the same value when plugged into f mod 9. We also know that any solution mod 9 must be a solution mod 3. Since f (1) = 3 6≡ 0 (mod 9), there is no solution mod 9, and thus none mod 81. 2. See gp file for the code. The factor 531793 is found. (Some other factors obtained from running Pollard rho on the quotient are 5684759 and 18207494497.) 3. If we know N = pq and φ(N ) = (p − 1)(q − 1), then we know p + q = N − φ(N ) − 1. So p and q are the roots of x2 − M x + N for some integer M , which we can solve by the quadratic formula. 4. Let f (a) = tpj where t is an integer. Then, by the Taylor series expansion, f (b) = f (a − tpj f 0 (a)) = f (a) − tpj f 0 (a)f 0 (a) + f 00 (a) j 0 (tp f (a))2 + · · · 2 Since the coefficients f 00 (a)/2, etc. are all integers, f (b) ≡ f (a) − tpj f 0 (a)f 0 (a) ≡ tpj − tpj f 0 (a)f 0 (a) ≡ tpj (1 − f 0 (a)f 0 (a)) (mod p2j ). Now by definition, f 0 (a)f 0 (a) ≡ 1 (mod pj ). So the product on the RHS is divisible by p2j . Therefore f (b) ≡ 0 (mod p2j ), as desired. 1 5. (a) Remember that we have xp−1 − 1 ≡ (x − 1)(x − 2) · · · (x − p + 1) =x p−1 − σ1 x p−2 + σ2 x p−3 (mod p) − · · · − σp−2 x + σp−1 . So since the coefficients of x, x2 , . . . , xp−2 on the LHS are all 0, we must have that σ1 , σ2 , . . . , σp−2 are all congruent to 0 mod p. (b) Plugging x = p into (x − 1) · · · (x − p + 1) = xp−1 − σ1 xp−2 + · · · + σp−1 , we get (p − 1)! = pp−1 − σ1 pp−2 + · · · + σp−3 p2 − σp−2 p + σp−1 . Now σp−1 = (p − 1)!, the product of the roots. So we cancel it with the (p − 1)! from the LHS and divide by p to get 0 = pp−2 − σ1 pp−3 + · · · + σp−3 p − σp−2 . Since p ≥ 5 and σ1 , . . . , σp−3 are all divisible by p by part (a), we see that p2 divides all the terms on the RHS except possibly σp−2 . But since the terms sum to zero, it follows that p2 divides σp−2 as well. 6. Consider the p − 1 congruence classes 1, g, . . . , g p−2 mod p. These are all distinct, or else we would have g i ≡ g j for some 0 ≤ i < j ≤ p − 2 and then g j−i ≡ 1 (mod p), contradicting the fact that g is a primitive root. Furthermore, they are all coprime to p. So they must be 1, 2, . . . , p − 1 in some order. Therefore Sk = 1k + · · · + (p − 1)k = 1k + g k + g 2k + · · · + g (p−2)k . If p − 1 divides k then each term is congruent to 1, so the sum is congruent to p − 1. Otherwise Sk = g (p−1)k − 1 ≡0 gk − 1 (mod p), since the numerator is g (p−1)k − 1 ≡ 1k − 1 ≡ 0 (mod p), but the denominator is g k − 1 6≡ 0 (mod p), since g has order p − 1 and by assumption p − 1 6 |k. So ( −1 if p − 1|k 1k + 2k + · · · + (p − 1)k ≡ 0 if p − 1 6| k. 7. (a) We know xp − x ≡ x(x − 1) · · · (x − p + 1) (mod p), so σ1 , . . . , σp−2 , σp ≡ 0 (mod p) while σp−1 ≡ −1 (mod p). It can be easily shown by induction that for k = 1, . . . , p − 2, Sk ≡ 0 (mod p). (The inductive step is using Newton’s identity kσk = S1 σk−1 − S2 σk−2 + · · · + (−1)k−2 Sk−1 σ1 + (−1)k Sk and noting that all terms on the LHS and RHS except for (−1)k Sk are congruent to 0). Then, for k = p − 1, we get (p − 1)σp−1 ≡ 0 + · · · + 0 + (−1)p−2 Sp−1 , so Sp−1 ≡ −1 (mod p). Indeed, this checks with Fermat since 0p−1 + 1p−1 + · · · + (p − 1)p−1 ≡ 0 + 1 + · · · + 1 | {z } p−1 times ≡p−1 ≡ −1 (mod p). Finally, for k = p, we get pσp = S1 σp−1 + 0 + · · · + 0 + (−1)p−1 Sp . So Sp ≡ 0 (mod p) as well. These results agree with Problem 6. 2 (b) Let x1 , . . . , xn be the n variables. Suppose that for some values of x1 , . . . , xn , we have f (x1 , . . . , xn ) ≡ 0. Then 1 − f (x1 , . . . , xn )p ≡ 1 (mod p). On the other hand, if f (x1 , . . . , xn ) 6≡ 0 (mod p), then by Fermat’s Little Theorem f (x1 , . . . , xn )p−1 ≡ 1 (mod p), so 1 − f (x1 , . . . , xn )p−1 ≡ 0 (mod p). Therefore, the function 1 − f (x)p−1 equals 1 if x is a root, 0 mod p if x is not a root. So the number of roots, mod p, is X X [1 − f (a1 , . . . , an )p−1 ] = pn − f (a1 , . . . , an )p−1 a1 ,...,an a1 ,...,an ≡− X f (a1 , . . . , an )p−1 (mod p). a1 ,...,an T number of roots is equivalent to 0 (mod p), it’s enough to see that this sum Po show that the f (a1 , . . . , an )p−1 vanishes mod p. Now f has total degree d < n, i.e., each monomial of f has degree d < n. So for each monomial xe11 · · · xenn of f p−1 , we have e1 + · · · + en < (p − 1)n. This implies that some ei must be less than p − 1. Now, if we can show that for any monomial M appearing in f p−1 , X M (a1 , . . . , an ) ≡ 0 (mod p), a1 ,...,an then we’re done by linearity. But we have X M (a1 , . . . , an ) = a1 ,...,an X ae11 · · · aenn a1 ,...,an = n Y X i=1 ! aei i , ai where P ei the sum runs from 0 through Q Pp − 1 for each i. Now if some ei < p − 1 then by Problem 6, ai ≡ 0 (mod p). Therefore ( aei i ) ≡ 0 (mod p) for every monomial, proving our result. When f has no constant term, the number of roots is a multiple of p, and it is positive since (0, . . . , 0) is a root. So there are at least p roots. This implies there must be a nontrivial root as well. 3