Math 110 Problem Set 2 Solutions - Stanford University

1 Math 110 Problem Set 2 3 be prime. Show that the only Solutions tox2 1 (modp) arex 1 (modp).Solution:Note that we have(x+ 1) (x 1) x2 1 0 (modp)Thus, by Exercise 7(a), we have that eitherx 1 0 (modp) orx+ 1 0(modp) so we havex 1 (modp) as 2 (mod 7) andx 3 (mod 10). What isxcongruent to mod70?Solution:This is easiest to do by trial and error. The 2nd condition meansthatxis 3, 13, 23, 33, 43, 53, or 63 modulo 70. Checking, we see that the onlyone of these which is 2 modulo 7 is 23, soxmust be 23 (mod 70). Note thatthe Chinese remainder Theorem guarantees that there is a unique answer tothe prime.

2 Show thatap a(modp) for :Let us consider two cases:pdividesa, andpdoes not dividea. Ifpdividesa, then both sides are 0 modulop. Ifpdoes not dividea, by Fermat sLittle Theorem,ap 1 1 (modp) ap a(modp)Thus, in either case,ap a(modp) 210203by 101. What is the remainder ?Solution:Note that by Fermat s Little Theorem, 2100 1 (mod 101). Thus,we have that for any integern, 2100n 1 (mod 101), raising both sides to thepower ofn. Hence, we have that 210200 1 (mod 101), so we conclude that210203 23 210200 8 (mod 101)Thus, the remainder from the division is (a) Compute (d) for all of the divisors of 10 (namely, 1, 2, 5, 10) and find thesum of all these (d).

3 (b) Repeat part (a) for all the divisors of 12.(c) Letn 1. Conjecture the value of (d), where the sum is over thedivisors :(a) We calculate: (1) = 1 (2) = 2 1 = 1 (5) = 5 1 = 4 (10) = (2) (5) = 1 4 = 4 Here we have used the fact that (p) =p 1 for a primepand the formula for (n) in the textbook. Thus, we have that the sum of all these is 1+1+4+4 = 10.(b) We calculate: (1) = 1 (2) = 2 1 = 1 (3) = 3 1 = 2 (4) = 4 (1 12) = 2 (6) = (2) (3) = 1 2 = 2 (12) = 12 (1 12)(1 13) = 2 2 = 4 Thus, we have that the sum of all these is 1 + 1 + 2 + 2 + 2 + 4 = 12.(c) The previous two examples suggest that this sum (a) Show that every nonzero congruence class mod 11 is a power of 2, andtherefore 2 is a primitive root mod 11.

4 (b) Note that 23 8 (mod 11). Findxsuch that 8x 2 (mod 11).(c) Show that every nonzero congruence class mod 11 is a power of 8, andtherefore 8 is a primitive root mod 11.(d) Letpbe prime and letgbe a primitive root modp. Leth gy(modp)with gcd(y, p 1) = 1. Letxy 1 (modp 1). Show thathx g(modp).(e) Letpandhbe as in part (d). Show thathis a primitive root :(a) Let us calculate the powers of 2 modulo 11:2 2 (mod 11)22 4 (mod 11)23 8 (mod 11)24 16 5 (mod 11)25 2 24 2 5 10 (mod 11)26 2 25 2 10 9 (mod 11)227 2 26 2 9 7 (mod 11)28 2 27 2 7 3 (mod 11)29 2 28 2 3 6 (mod 11)210 2 29 2 6 1 (mod 11)Thus, we see that every congruence class mod 11 appears, so 2 is a primitiveroot mod 11.

5 (b) Note that the inverse of 3 (mod 10) is 7 (mod 10). Now, by Fermat sLittle Theorem, 210 1 (mod 11). Thus,23 8 (mod 11) (23)7 87(mod 11) 87 221 2 (mod 11)Thus, thexwe want is 7.(c) Letcbe a congruence class mod 11. By (a), there existsxsuch that 2x c(mod 11). Applying the formula from (b), we have that 87x c(mod 11). Thusevery nonzero congruence class mod 11 is a power of 8.(d) Sincexy 1 (modp 1), by Fermat s Little Theorem,gxy g(modp) hx (gy)x gxy g(modp)(e) Letcbe a congruence class modp. Then, sincegis a primitive root modp,there existsasuch thatga c(modp). Thus, we have thathax c(modp),so every nonzero congruence class modpis a power ofh.

6 Hencehis a primitiveroot