Module 77

• Mar 26th 2008, 12:16 PM
Module 77
Evalute $2^{100000}$ in mod 77.

I know that $2^{76} \equiv 1 \ (mod \ 77)$, but how should I continue? Thanks.
• Mar 26th 2008, 12:32 PM
topsquark
Quote:

Evalute $2^{100000}$ in mod 77.

I know that $2^{76} \equiv 1 \ (mod \ 77)$, but how should I continue? Thanks.

Sorry, but I'm getting $2^{76} \equiv 9 \text{ (mod 77)}$.

There may be a more elegant way to do this but
Note that $2^{30} \equiv 1 \text{ (mod 77)}$

So
$2^{100000} \equiv 2^{30 \cdot 3333 + 10} \equiv \left ( 2^{30} \right ) ^{3333} \cdot 2^{10} \text{ (mod 77)}$

$\equiv 2^{10} \text{ (mod 77)}$
which is easy to finish off.

-Dan
• Mar 26th 2008, 01:49 PM
Moo
Quote:

Evalute $2^{100000}$ in mod 77.

I know that $2^{76} \equiv 1 \ (mod \ 77)$, but how should I continue? Thanks.

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 :

$\forall a \ < n, \ a^{\varphi(n)} \equiv 1 \ (mod \ n)$

With $\varphi(n)$ the Euler's totient function, defined as :

(p designing prime numbers)

$\varphi(p)=p-1$

$\varphi(p^n)=p^{n-1}(p-1)$ (the first one can be a deduction of this one)

$\varphi(p^n q^r)=\varphi(p^n) \varphi(q^r)$ (with q a prime number)

As 77 is 11x7, $\varphi(77)=(11-1)(7-1)=60$

=> $2^{60}\equiv 1 (mod \ 77)$
• Mar 26th 2008, 02:22 PM
I actually got to this point with Euler, but then I'm stuck here.
• Mar 26th 2008, 02:30 PM
Moo
Well,

Division of 100.000 by 60.

i'll say that 100 is 60x16+40

So 100.000 is 60x16000+40.000

$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 :D)