I just finished reading about Euler's Totient theorem, Fermat's little theorem, and the Chinese Remainder theorem, so I decided to test what I learned with a small problem that I came up with for myself. The question was to find the remainder of $7^{27}$ when divided by $11$. Here is how I started:
$$7^{27}=7^{11}\cdot 7^{11}\cdot 7^5\equiv 7\cdot 7\cdot 7^5\mod 11\equiv 5\cdot 7^5\mod 11 \tag{via Flt}$$
Here is where I ran into some problems. I noticed that $7^{31}\equiv 5\mod 11$ via Euler's Totient theorem and that $7^5\equiv 2\mod 5$ via Flt, but I had to deduce that $7^7\equiv 10\mod 11$ via the following method, which I am pretty sure is correct using the fact that $ab\mod n=(a\mod n) \cdot (b\mod n)$ :
$$\begin{align*} 5\cdot 7^5\mod 11&\equiv(5\pmod {11})\cdot (7^2\pmod {11})^2\cdot(7\pmod{11})\\&\equiv (5\pmod{11})^3\cdot(7\pmod{11})\\&\equiv (125\pmod{11})\cdot(7\pmod {11})\\&\equiv (4\pmod {11})\cdot(7\pmod{11})\\&\equiv (28\pmod {11})\\&\equiv 6\pmod{11} \end{align*}$$
Is there a faster way of going about this? Thanks.
Best Answer
Fermat's Little Theorem implies $7^{11} \equiv 7 \pmod{11}$, which was your mistake (before you edited the question). Since $7$ is not divisible by $11$, $7^{10} \equiv 1 \pmod{11}$. Observe that $$7^2 \equiv 49 \equiv 5 \pmod{11} \implies 7^3 \equiv 7 \cdot 5 \equiv 35 \equiv 2 \pmod{11}$$ Hence, \begin{align*} 7^{27} & \equiv (7^{10})^2 \cdot 7^7 \pmod{11}\\ & \equiv 7^7 \pmod{11}\\ & \equiv (7^3)^2 \cdot 7 \pmod{11}\\ & \equiv 28 \pmod{11}\\ & \equiv 6 \pmod{11} \end{align*}