270 views

Compute the remainder of $3^{64}$ in the division by $67.$

### 1 comment

$3^{-2} \ 3^{66} \mod 67 = 3^{-2} \mod 67 = 9^{-1} \mod 67$ (By Fermat’s Little theorem )

Using Euclidean algorithm

$67 = 7*9 + 4$ and $9 = 2*4 + 1 \Rightarrow 1 = 9 – 2*(67\ –\ 7*9) \Rightarrow 1 = 15*9\ –\ 2*67$

So, $9^{-1} \mod 67 = 15$

We have $64=2^6.$ Hence
$3^2=9\\ 3^4=9^2=81\equiv 14\; \mod \; (67)\\ 3^8\equiv14^2=196\equiv62\equiv -5 \; \mod \; (67)\\ 3^{16}\equiv (-5)^2=25\; \mod \;(67)\\ 3^{32} \equiv 25^2 =625 \equiv 22 \; \mod \; (67)\\ 3^{64}\equiv 22^2 = 484 \equiv 15 \; \mod \; (67)$

14

(3^64)%67

GROW SLOWLY

(3^2)%67 = 9

(9^2)%67 = 14

(14^2)%67 = -5

((-5)^2)%67 = 25

((25)^2)%67 = 22

((22)^2)%67 = 15