3
$\begingroup$

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!

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

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}$.

$\endgroup$
2
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

$$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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.