# Modular arithmetic - remainders

I'm unsure on the method regarding finding remainders of large numbers using modular arithmetic, for example $$\frac{5^{64}}{41}$$ Is this equivalent to finding $5^{64} \pmod{41}$? It would make sense as this would yield a number between $0$ and $40$ but I'm unsure as to why it would give you the remainder? I feel like I'm missing something fundamental here so any help would be appreciated!

• the answer is $10$ – Dr. Sonnhard Graubner Nov 29 '15 at 14:13
• @Dr.SonnhardGraubner Yes but why? – the man Nov 29 '15 at 14:16

Yes, this is equivalent to finding $5^{64} \pmod {41}$. In fact, $5^{64} \pmod {41}$ is by definition the remainder upon dividing $5^{64}$ by $41$. For this particular problem you will probably want to use Fermat's Little Theorem: if $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1}\equiv 1 \pmod p$. Since $41$ is prime, and $5$ is not divisible by $41$, $$5^{64}\pmod {41} \equiv 5^{40} \cdot 5^{24} \pmod{41} \equiv 1 \cdot 5^{24} \pmod {41}.$$ Fermat's Little Theorem is no longer useful since the exponent is less than $40$. Now we can break down the exponent into smaller ones to reduce the problem. $5^2=25<41$, so we can't reduce this modulo $41$. But $5^3=125 \equiv 2 \pmod{41}$. So we get $$5^{24} \pmod {41} \equiv (5^3)^8 \pmod {41} \equiv 2^8 \pmod{41}.$$ Now it's easy enough to just compute: $2^8=256= 6 \cdot 41 + 10$, so $2^8 \equiv 10 \pmod{41}$, and thus $5^{64} \equiv 10 \pmod{41}$.
Another method is repeated squaring, which is particularly appropriate given the exponent $64$ since it is a power of $2$. We have:
$$5^2 \equiv 25 \pmod {41}$$ $$5^4 \equiv (5^2)^2 \equiv 25^2 \equiv 10 \pmod {41}$$ $$5^8 \equiv (5^4)^2 \equiv 10^2 \equiv 18 \pmod {41}$$ $$5^{16} \equiv \ldots$$
$$5^3\equiv2\pmod{41} \implies5^{64}=5\cdot2^{21}$$
$$2^5\equiv-9\implies2^{10}\equiv(-9)^2\equiv-1\implies2^{20}\equiv(-1)^2\equiv1$$
$$\implies5^{64}\equiv10\cdot1$$