- #1

TwilightTulip

- 24

- 0

**Proving that m^270300 = 1 (mod 11113121)**

I have been fighting with this problem for much too long, can anyone help? I am assuming gcd(m,1113121)=1.

I wrote a program to discover Phi(1113121) = 4*270300, and I have been playing with Euler's theorem:

m^Phi(1113121) = (m^270300)^4 = 1 (mod 1113121).

So that I know is true. For a while I had thought the conjecture, in general, was incorrect, but I did this with a brute force algorithm to find no counter examples.

To save time, here's a bit more info:

1113121=101*103*107

270300= 2^2 * 3 * 5^2 * 17 * 53

Phi(1113121) = 2^4 * 3 * 5^2 * 17 * 53

Can anyone help? It seems like a straight-forward algebra/number-theory problem, but I can't figure it out.

Thanks! :)