Module 77

**tttcomrader** · March 26th 2008, 11:16 AM

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

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

**topsquark** · March 26th 2008, 11:32 AM

Originally Posted by tttcomrader

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

**Moo** · March 26th 2008, 12:49 PM

Originally Posted by tttcomrader

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

**tttcomrader** · March 26th 2008, 01:22 PM

I actually got to this point with Euler, but then I'm stuck here.

**Moo** · March 26th 2008, 01:30 PM

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

)

Thread: Module 77

LinkBack

Thread Tools

Display

Module 77

Similar Math Help Forum Discussions

a singular module is the quotient of a module and its essential submodule

Module Help

About some module over a DVR

k[x]-module

R-module

Search Tags