3. Let p = 34303 (a prime). Find, with proof, all x Z such that x...

 

Transcribed Image Text:

3. Let p = 34303 (a prime). Find, with proof, all x Z such that x = 1 (mod p), without resorting to brute-force enumeration. (a) Let p = 34303. Find all three solutions to the following equation: 23 = 1 (mod p) You may use the fact that g = 17 is a generator for Z. (Hint: Recall that by Fermat's Little Theorem, gP-1 = 1 (mod p).) (b) Prove that these three solutions are the only three solutions to this equation. Recall that by the Fundamental Theorem of Algebra, a polynomial of degree d can have no more than d roots. This theorem holds even modulo p as long as p is prime. 3. Let p = 34303 (a prime). Find, with proof, all x Z such that x = 1 (mod p), without resorting to brute-force enumeration. (a) Let p = 34303. Find all three solutions to the following equation: 23 = 1 (mod p) You may use the fact that g = 17 is a generator for Z. (Hint: Recall that by Fermat's Little Theorem, gP-1 = 1 (mod p).) (b) Prove that these three solutions are the only three solutions to this equation. Recall that by the Fundamental Theorem of Algebra, a polynomial of degree d can have no more than d roots. This theorem holds even modulo p as long as p is prime.