a^n in mod

**ramdrop** · March 30th 2011, 05:30 AM

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.

**TheEmptySet** · March 30th 2011, 06:02 AM

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$

**ramdrop** · March 30th 2011, 06:09 AM

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.

**TheEmptySet** · March 30th 2011, 06:39 AM

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!

Thread: a^n in mod

LinkBack

Thread Tools

Display

a^n in mod

Search Tags