1. ## a^n in mod

Hey

It's been a while since I posted here, but here goes:

I have to (in basic terms) work out what:
$72^{5712} mod 101$ is,

I've started by applying Euler's theorem and moved it down to:

$72^{100x57 +12}$

but I'm stuck, as I'm not sure how this is going to give me a final result.

2. Originally Posted by ramdrop
Hey

It's been a while since I posted here, but here goes:

I have to (in basic terms) work out what:
$72^{5712} mod 101$ is,

I've started by applying Euler's theorem and moved it down to:

$72^{100x57 +12}$

but I'm stuck, as I'm not sure how this is going to give me a final result.
You have a good start by Fermat's little theorem we get that

$72^{100} \equiv 1 \text{mod}(101)$

This gives

$(72^{100})^{57}72^{12} \text{mod}(101)\equiv 72^{12} \text{mod}(101) \equiv 3^{24}\cdot 2^{36} \text{mod}(101)$

Now further note that

$2^9 \text{mod}(101)\equiv 7 \text{mod}(101)$ and

$3^6 \text{mod}(101)\equiv 22 \text{mod}(101)$

Using this we get

$3^{24}\cdot 2^{36} \text{mod}(101)\equiv 22^4\cdot7^4 \text{mod}(101)\equiv (154)^4 \text{mod}(101)\equiv (53)^4 \text{mod}(101)$

Now just multiply it out and divide by 101 to find the remainder

I end up with $58$

3. An interesting approach, thanks a lot

I'm still trying to approach it by Euler's, but at least I have some idea what the end result will be.

4. Originally Posted by ramdrop
An interesting approach, thanks a lot

I'm still trying to approach it by Euler's but at least I have some idea what the end result will be.
Just FYI Euler's theorem is a generalization of Fermat's little theorem.

Since Sine $P=101$ is prime $72$ and 101 are coprime and Euler's theorem reduces to Fermat's little theorem. The proof should be identical!