Computing $16^{74} \bmod 65$

Question

I have the following problem. I need to calculate $16^{74} \bmod 65$. Is there a way to do this without a calculator? Thank you for your help in advance!

EDIT (M.S.): Notice that this question is linked as an example in one of the answers to the FAQ post: How do I compute $a^b\,\bmod c$ by hand?

Answer 1

$65=2^6+1$ and $$ 16^{74} = 2^{296} = 4\cdot(2^6)^{49} = 4(65-1)^{49}\equiv 4(-1)^{49} \equiv \color{red}{-4}\pmod{65}. $$

Answer 2

Repeatedly raising to as small powers as possible and immediately reducing modulo $65$ we have

$$(16)^{74} = (16^2)^{37} = (256)^{37} = (260 - 4)^{37} \equiv (-4)^{37} = - 4^{37} = -4 \cdot 4^{36} = -4 \cdot (4^4)^9 = \\ -4 \cdot (256)^9 = -4 \cdot (260 - 4)^9 \equiv -4 \cdot (-4)^9 = 4^{10} = 4 \cdot (4^3)^3 = 4 \cdot (64)^3 = 4 \cdot (65 - 1)^3 \equiv \\ 4 \cdot (-1)^3 = -4 \equiv 61 .$$

Answer 3

$$16^3 \bmod 65 = 1 \implies 16^3 = 1 \bmod 65 \implies 16^{3 \times 24} =1^{24} \bmod 65 = 1 \bmod 65 \implies$$

$$16^{72} = 1 \bmod 65 \implies 16^2 \times 16^{72} = 16^2 \bmod 65 = 61 \bmod 65$$

Hence $16^{74} = 61 \bmod 65 \implies 16^{74} \bmod 65 = 61$

Answer 4

Note that we can write $$ 74=1\cdot64+0\cdot32+0\cdot16+1\cdot8+0\cdot4+1\cdot2+0\cdot1. $$ (In other words: $74$ in binary is $0b1001010$.)

We can proceed, then, by writing $$ 16^{74}=16^{64}\cdot16^{8}\cdot16^2 $$ and computing these powers modulo $65$ by repeated squaring.

A pattern quickly emerges in the repeated squaring: $$ \begin{align*} 16^2&=256\equiv61\equiv-4\pmod{65}\\ 16^4&=(16^2)^2\equiv(-4)^2\equiv16\pmod{65}\\ 16^8&=(16^4)^2\equiv16^2\equiv-4\pmod{65}\\ 16^{16}&=(16^8)^2\equiv16\pmod{65}\\ 16^{32}&=(16^{16})^2\equiv-4\pmod{65}\\ 16^{64}&=(16^{32})^2\equiv16\pmod{65} \end{align*} $$ So, we find that $$ 16^{74}\equiv16\cdot(-4)\cdot(-4)\equiv256\equiv-4\pmod{65}. $$

Answer 5

Since $\phi(65)=48$ and $4\cdot74 = 296 \equiv 8 \bmod 48$, we get by Fermat–Euler: $$ 16^{74} = 2^{296} \equiv 2^8 = 256 \equiv 61 \bmod 65 $$

Answer 6

$4^3 = 64 \equiv -1\pmod{65}$

$4^6 = 16^3 \equiv 1\pmod{65}$

$16^{72} \equiv 1\pmod{65}$

$16^{74} \equiv 16^2\equiv 61\pmod{65}$

Answer 7

${\rm mod}\,\ 65\!:\ \color{#c00}{4^{\large 3}\equiv\bf -1}\,\Rightarrow\, 16^{\large 2+3N}\!\equiv\! 4^{\large 4+6N}\!\equiv 4(\color{#c00}{4^{\large 3}})^{\large 1+2N}\!\equiv 4(\color{#c00}{\bf -1})^{\large 1+2N}\!\equiv -4$

Answer 8

$$\begin{cases}16^3=63\cdot65+1\\74=3\cdot24+2\\256==3\cdot65+61\end{cases}\Rightarrow16^{74}\equiv(1)^{24}\cdot16^2\equiv256=3\cdot65+61\equiv \color{red}{61}\pmod{65}$$