189-346/377B: Number Theory Assignment 3

Due: Monday, February 12

1. Find the remainder in the division of 3^{10000001} by 707, i.e., the unique r ∈ Z such that

3^{10000001} = 707q + r, 0 ≤ r ≤ 706.

2. Solve completely the following congruence equations. More precisely, given the equation f(x) ≡ 0 (mod N), list all the solutions between 0 and N − 1. (You may use a computer to help yourself with the intermediate calculations if they get too lengthy, but you should justify the steps of the calculation.)

a) 3x + 2 ≡ 0 (mod 3^{11}).

b) 3x + 3 ≡ 0 (mod 3^{11}).

c) x^{2} + 1 ≡ 0 (mod 65).

d) x^{3} + x + 1 ≡ 0 (mod 11^{5}).

3. Show that the polynomial x^{d}−1 has a root in the field Q_{p} of p-adic numbers if and only if d divides (p − 1), and that in that case, the polynomial x^{d} − 1 has d distinct roots in Q_{p}.

4. Let p be an odd prime. Let j be an element of Z/pZ, and consider the polynomials in Z/pZ[x], depending on a parameter j ∈ Z/pZ and defined by

f_{j} = (x − j)^{\frac{p−1}{2}} − 1, g_{j} = (x − j)^{\frac{p−1}{2}} + 1.

Show that

x^{p} − x = (x − j)f_{j}(x)g_{j}(x).

Conclude that the roots of f_{j} and g_{j} are disjoint subsets A_{j} and B_{j} of Z/pZ satisfying

A_{j} ∪ B_{j} = Z/pZ − {j}.

Give a simple description of A_{j} and B_{j}.

5. List all the primitive roots modulo p = 37 and modulo 25.

6. Let g be the smallest positive integer that is a primitive root modulo 37. Compute the mod 37 discrete logarithm log_{g}(12).

7. Let a be an element of order t in (Z/pZ)^{×}. Show that a+a^{2} +⋯+a^{t−1} = −1 in Z/pZ.

8. Let g be a primitive root modulo an odd prime p. Show that −g is also a primitive root modulo p if and only if 4 divides p − 1.

9. Let p be an odd prime. Show that, for all N ≥ 1, (1 − 2p) = (1 − p)^{j} (mod p^{N}),

where

j = \frac{(2p) + (2p)^{2}/2 + (2p)^{3}/3 + ⋯ + (2p)^{N}/N}{p + p^{2}/2 + p^{3}/3 + ⋯ + p^{N}/N} .

Can you formulate this as an identity between p-adic numbers? The following problems are optional for Math 346

10. Using the notations of Problem 4, show that for any polynomial h(x) in Z/pZ[x],

gcd(h(x), f_{j}(x)) = ∏_{h(a)=0^{a∈A_{j}}}(x − a), gcd(h(x), g_{j}(x)) = ∏_{h(b)=0^{b∈B_{j}}}(x − b).

Given that h(x) has r distinct roots in Z/pZ, and that j is chosen at random, estimate the likelihood that both these factors of h(x) are different from 1.

11. Using the outcome of problems 4 and 10, describe an efficient probabilistic algorithm for finding the roots of a polynomial over Z/pZ.