A. Student

Math 124 Problem Set 4

1. (\frac{3}{97}) = (−1)^{48} · (\frac{97}{3}) = (\frac{1}{3}) = 1; (\frac{5}{389}) = (−1)^{2} · (\frac{389}{5}) = (\frac{4}{5}) = 1; (\frac{2003}{11}) = (\frac{1}{11}) = 1; (\frac{5!}{7}) = (\frac{120}{7}) = (\frac{1}{7}) = 1;

2. By quadratic reciprocity (\frac{3}{p}) = (−1)^{\frac{p−1}{2}} · (\frac{p}{3}). There are four cases: Case 1: p ≡ 1(mod 3), p ≡ 1(mod 4): Then p ≡ 1(mod 12) and (−1)^{\frac{p−1}{2}} · (\frac{1}{3}) = 1 · 1 = 1. Case 2: p ≡ 1(mod 3), p ≡ −1(mod 4): Then p ≡ 7(mod 12) and (−1)^{\frac{p−1}{2}} · (\frac{1}{3}) = −1 · 1 = -1. Case 3: p ≡ 2(mod 3), p ≡ 1(mod 4): Then p ≡ 5(mod 12) and (−1)^{\frac{p−1}{2}} · (\frac{−1}{3}) = 1 · −1 = -1. Case 4: p ≡ 2(mod 3), p ≡ −1(mod 4): Then p ≡ 11(mod 12) and (−1)^{\frac{p−1}{2}} · (\frac{−1}{3}) = −1 · −1 = 1. (We solve the systems with the Chinese Remainder Theorem).

3. It is sufficient to give two distinct elements a, b in Z_{n}^{∗} of order 2, for if there was a primitive root g, then g^{ϕ(2^{m})/2} = g^{2^{m−2}} cannot simultaneously be congruent to a and b modulo n. Put a = −1; since n > 2, −1 has order 2 in Z_{n}^{∗}. Set b = 2^{m−1} − 1; then

b^{2} = (2^{m−1} − 1)^{2} ≡ 2^{2m−2} − 2 · 2^{m−1} + 1 ≡ 1(mod 2^{m}).

Now b is distinct from a, since their difference, 2^{m−1}, is less than 2^{m}. Furthermore, b ≠ 1, since m > 2. Therefore a and b are distinct elements of order 2 in Z_{n}^{∗}.

4. Let g_{0} be a primitive root modulo p. We will construct an element g of Z_{p^{2}}^{∗} with order ϕ(p^{2}) = p(p−1). Let g = g_{0} + pt for some t to be determined. Then by the binomial theorem

g^{p−1} ≡ g_{0}^{p−1} + (p − 1)pg_{0}^{p−2}t ≡ (1 + kp) + p(p − 1)g_{0}^{p−2}t (mod p^{2}),

for some k, since g_{0}^{p−1} ≡ 1(mod p). Now choose t such that n = k + (p − 1)g_{0}^{p−2}t is nonzero modulo p. We can do this because p − 1 and g_{0}^{p−2} are both elements of Z_{p}^{∗}. Then g^{p−1} ≡ 1 + np (mod p^{2}), p ∤ n. Therefore the order of g in Z_{p^{2}}^{∗} does not divide p − 1. But it divides p(p − 1), and p is prime, so the order of g must be p(p − 1). Thus g is a primitive root modulo p^{2}.

5. Let g be a primitive root modulo p. Since p ≡ 1(mod 3), c = g^{(p−1)/3} has order 3. Therefore c is a solution to x^{3} − 1 = (x − 1)(x^{2} + x + 1) = 0 modulo p. Since c ≠ 1 and we are in a domain, c^{2} + c + 1 = 0. Now note that 4c^{2} + 4c + 4 = (2c + 1)^{2} + 3 = 0; therefore (2c + 1)^{2} = −3, so (\frac{−3}{p}) = 1.

6. The proof is almost identical to the one above. Let c in Z_{p}^{∗} be an element of order 5. Then c^{5} − 1 = (c − 1)(c^{4} + c^{3} + c^{2} + c + 1) = 0 and c ≠ 1 implies that c^{4} + c^{3} + c^{2} + c + 1 = 0. Now

(c + c^{4})^{2} + (c + c^{4}) − 1 = c^{2} + c^{8} + 2c^{5} + c + c^{4} − 1 = c^{4} + c^{3} + c^{2} + c + 1 = 0.

Therefore (2(c + c^{4}) + 1)^{2} = 4((c + c^{4})^{2} + (c + c^{4}) − 1) + 5 = 5, so (\frac{5}{p}) = 1.

7. All odd primes. Let p be an odd prime and g a primitive root modulo p. Rewrite the sum as:

∑_{a=1}^{p−1} (\frac{a}{p}) = ∑_{i=1}^{p−1} (\frac{g^{i}}{p} ) = ∑_{j=1}^{\frac{p−1}{2}} (\frac{g^{2j}}{p} )+∑_{j=1}^{\frac{p−1}{2}} (\frac{g^{2j+1}}{p} ) = ∑_{j=1}^{\frac{p−1}{2}} (\frac{g^{2j}}{p} )+(\frac{g}{p}) ∑_{j=1}^{\frac{p−1}{2}} (\frac{g^{2j}}{p} ) = \frac{p − 1}{2} (1 + (\frac{g}{p})) .

Now (\frac{g}{p}) = −1, for if (\frac{g}{p}) = 1 then g^{\frac{p−1}{2}} = 1, and g would not be primitive. Therefore ∑_{a=1}^{p−1} (\frac{a}{p}) = 0.

8. A good guess seems to be C ≈ .374. In PARI, we can write a program to check the first n primes to see if 2 is a primitive root, and divide this total by n to see the behavior of the ratio: g0(n)=numRoot=0; lPr=prime(2);

for(j=2,n,(if(znorder(Mod(2,lPr))==lPr-1,numRoot++)); lPr=prime(j+1)); tPr=n;

return(numRoot/(1.0*n)); Using this, we have g0(41560) ≈ .37377. This exhausts PARI’s list of primes, so we can write another program to continue testing:

g(n)=lPr=nextprime(lPr+1);

for(j=1,n,(if(znorder(Mod(2,lPr))==lPr-1,numRoot++));tPr++;lPr=nextprime(lPr+1));

return(numRoot/(1.0*tPr)); With this program, we can check the first n primes (according to PARI’s nextprime function). For the first 81,560 primes, we have C ≈ .373725; For the first 101,560 primes, we have C ≈ .374714. Finally, for the first 200,000 primes, we have C ≈ .374075.