# 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?

◆ ◆ ◆