Big Division Remainder

According to Fermat's Little Theorem , $a^{p-1}-1$ is always an integer multiple of $p,$ i.e. $a^{p-1} \equiv 1 \pmod{p}.$ By applying Fermat's little theorem, we know that ${7}^{10} \equiv 1 \pmod{11}.$ Hence, we have ${7}^{88} \equiv ({7}^{10})^{8} \cdot {7}^8 \equiv {7}^8 \equiv {49}^4 \equiv {5}^4 \equiv 625 \equiv 9 \pmod{11}.$ Therefore, the remainder of ${7}^{88}$ upon division by $11$ is $9.$

It's known that:

$7^3 \equiv 2 \quad (mod \quad 11)$

$7^2 \equiv 5 \quad (mod \quad 11)$

This gives:

$7^2 \cdot 7^3 = 7^5 \equiv 10 \equiv -1 \quad (mod \quad 11)$

$7^{88}$ can be written as: $(7^5)^{17} \cdot 7^3$

Take modulo 11:

$(7^5)^{17} \cdot 7^3 \equiv (-1)^{17} \cdot 2 \equiv -2 \equiv \boxed{9} \quad (mod \quad 11)$

Without remembering Fermat's Little Theorem, and without jumping straight to the result with an arbitrary precision calculator, I tried to spot a pattern in:

• 7^0 % 11 = 1
• 7^1 % 11 = 7
• 7^2 % 11 = 5
• 7^3 % 11 = 2
• 7^4 % 11 = 3
• 7^5 % 11 = 10
• 7^6 % 11 = 4
• 7^7 % 11 = 6
• 7^8 % 11 = 9
• 7^9 % 11 = 8
• 7^10 % 11 = 1
• 7^11 % 11 = 7

where a % b represents the remainder of a divided by b.

Turns out that the repeating pattern seems 1, 7, 5, 2, 3, 10, 4, 6, 9, 8 (I didn't verify it mathematically) and then it becomes trivial to extrapolate what 7^88 will be.

Notice that $\gcd(7;\:11)=1$ , so we may use Euler's Theorem . We also note $7\cdot (\red{-3})\equiv 1\mod 11$ : $\begin{aligned} \text{Euler's Theorem:}&&7^{10}&\equiv 1\mod 11&&&\Rightarrow&&&&7^{88}\equiv7^{90}\cdot (\red{-3})^2\equiv 1^9\cdot (-3)^2\equiv\boxed{9}\mod 11 \end{aligned}$