Exercises - Fast Exponentiation and Fermat's Little Theorem

  1. Find a number $a$ where $0 \le a \lt 73$ and $a \equiv 9^{794}\pmod{73}$  

  2. Solve $x^{86} \equiv 6 \pmod{29}$  

  3. Solve $x^{39} \equiv 3 \pmod{13}$

  4. The statement $7^{1734250} \equiv 1660565\pmod{1734251}$ is true. Can you conclude 1734251 is a composite number?  

  5. Verify using fast exponentiation that the congruence $$129^{64026} \equiv 15179\pmod{64027}$$ is true. Can you conclude 64027 is a composite number?  

  6. Verify using fast exponentiation that the congruence $$2^{52632} \equiv 1\pmod{52633}$$ is true. Can you conclude 52633 is a prime number?  

◆ ◆ ◆