# Use Fermat's Little Theorem [duplicate]

Find a number $$0 \leq a < 73$$ with $$a≡9^{794}\mod 73$$.

I know that $$a$$ and $$73$$ are relatively prime and $$a^{72}≡1 \mod73$$. But I couldn't use the theorem.

• Don't focus on powers of $a$. You're not asked to calculate powers of $a$. You're asked to calculate powers of $9$, in a very roundabout way. – Arthur May 26 at 14:37
• Just use the theorem. $73$ is prime so $9$ is relatively prime to $73$ so $9^{72}\equiv 1\pmod {73}$. And If $9^{72}\equiv 1 \pmod {73}$ then $9^{72*11 + 2} \equiv (9^{72})^{11} *9^2 \equiv 1^{11}*9^2 \equiv 1*9^2\equiv 9^2 \pmod {73}$. – fleablood May 26 at 14:50
$$a\equiv9^{794}\equiv9^{72\times11+2}\equiv(\color{blue}{9^{72}})^{11}9^2\equiv(\color{blue}1)^{11}9^2\equiv81\bmod73$$.