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:
$\displaystyle 72^{5712} mod 101$ is,

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

$\displaystyle 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:
$\displaystyle 72^{5712} mod 101$ is,

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

$\displaystyle 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

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

This gives

$\displaystyle (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

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

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

Using this we get

$\displaystyle 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 $\displaystyle 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 $\displaystyle P=101$ is prime $\displaystyle 72$ and 101 are coprime and Euler's theorem reduces to Fermat's little theorem. The proof should be identical!