Suppose p is an odd prime, 3 Z p1 , and d = 3^ -1 mod p.

(a) Show that for all a Zp: a^3= b (mod p) iff a = b^d (mod p). .

(b) Show that y^2 = x^3 + 1 (mod p) has exactly p + 1 points, including (, ). (Hint: Thus, a has a unique cube root mod p)

Reference:

kAk = the number of elements in set A. (n) =def k{ a Z+ n : gcd(a, n) = 1 }k.

Eulers Theorem: For each n > 1 and a Z n : a (n) = 1 (mod n).

g is a primitive element of Z n iff { g 1 , g 2 , . . . , g (n) } = Z n .

Suppose g is a primitive element of Z n . For a Z n , the discrete log of a to the base g mod p (written: dlogg (a)) is the solution for x of: g x = a (mod n), i.e., g dlogg (a) = a (mod n).

Definition. Suppose a, n Z with n > 1 and a 6= 0. (a) a is a quadratic residue mod n when x 2 a (mod n) has a solution, otherwise a is a nonresidue.

(b) QRn = the quadratic residues mod n.

(c) The Legendre and Jacobi symbols: See 9-2 in Andrews.

(d) Suppose n is the product of two distinct odd primes p and q. QRn = { a : ( a p ) = 1 = ( a q ) } = the pseudo-residues mod n.