Evalute $\displaystyle 2^{100000} $ in mod 77.
I know that $\displaystyle 2^{76} \equiv 1 \ (mod \ 77) $, but how should I continue? Thanks.
Sorry, but I'm getting $\displaystyle 2^{76} \equiv 9 \text{ (mod 77)}$.
There may be a more elegant way to do this but
Note that $\displaystyle 2^{30} \equiv 1 \text{ (mod 77)}$
So
$\displaystyle 2^{100000} \equiv 2^{30 \cdot 3333 + 10} \equiv \left ( 2^{30} \right ) ^{3333} \cdot 2^{10} \text{ (mod 77)}$
$\displaystyle \equiv 2^{10} \text{ (mod 77)}$
which is easy to finish off.
-Dan
Hello,
I guess you wanted to use Fermat's little theorem. Unfortunately, this only works if 77 is a prime number.
Otherwise, you can use Euler's theorem which states that :
$\displaystyle \forall a \ < n, \ a^{\varphi(n)} \equiv 1 \ (mod \ n)$
With $\displaystyle \varphi(n)$ the Euler's totient function, defined as :
(p designing prime numbers)
$\displaystyle \varphi(p)=p-1$
$\displaystyle \varphi(p^n)=p^{n-1}(p-1)$ (the first one can be a deduction of this one)
$\displaystyle \varphi(p^n q^r)=\varphi(p^n) \varphi(q^r)$ (with q a prime number)
As 77 is 11x7, $\displaystyle \varphi(77)=(11-1)(7-1)=60$
=> $\displaystyle 2^{60}\equiv 1 (mod \ 77)$
Well,
Division of 100.000 by 60.
i'll say that 100 is 60x16+40
So 100.000 is 60x16000+40.000
$\displaystyle 2^{60 \times 16000}=(2^{60})^{16000} \equiv 1^{16000}[77]$
So you can throw off this term...
There is 40.000 remaining : find the remain of 40.000 in the division by 60 (i've shown steps above, because i'm too lazy to take a calculator )