Fermat's Little Theorem says that if a, pZ with p prime and a not divisible by...

 

Transcribed Image Text:

Fermat's Little Theorem says that if a, pЄZ with p prime and a not divisible by p then a²-1=1 mod p. In the question below, it will be helpful for you to remember the notion of order of an element a E Fo and how it is an integer (dividing 10091) depending on a. 1009, (a) Assuming Fermat's Little Theorem, and assuming xEZ, please find a simple character- ization for when 11ª = 114 mod 1009. Hint: Could it be a congruence involving x? If so, what would the modulus be? (b) Please find a simple characterization for when 121 1214 mod 1009. (c) If you consider x € {0,..., 1007} which happens more often: 11 = 114 mod 1009 or Fermat's Little Theorem says that if a, pЄZ with p prime and a not divisible by p then a²-1=1 mod p. In the question below, it will be helpful for you to remember the notion of order of an element a E Fo and how it is an integer (dividing 10091) depending on a. 1009, (a) Assuming Fermat's Little Theorem, and assuming xEZ, please find a simple character- ization for when 11ª = 114 mod 1009. Hint: Could it be a congruence involving x? If so, what would the modulus be? (b) Please find a simple characterization for when 121 1214 mod 1009. (c) If you consider x € {0,..., 1007} which happens more often: 11 = 114 mod 1009 or

Answer rating: 100% (QA)

ANSWER a Since 1009 is prime we can apply Fermats Little Theorem to obtain 111008 1 mod 1009 Now we ... View the full answer