Proving that m^270300 = 1 (mod 3121)

[TwilightTulip]

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! :)

 

[robert Ihnot]

What is m? If m represents any integer relataively prime to the modulus, you are wrong since you show a factor of 4.

 

[TwilightTulip]

What is m? If m represents any integer relataively prime to the modulus, you are wrong since you show a factor of 4. However, also, you have not correctly found the phi function of 11113121.

Thank you for the reply. Yes, m is anything relatively prime to 1113121. I believe my calculations are correct.

Phi(1113121) = Phi(101)Phi(103)Phi(107)
= 100*102*106=1,081,200 =2^4 * 3 * 5^2 * 17 * 53 = 4*270300

edit: I see that I have placed an extra 1 in the title, but there are three leading 1's in the modulous. That is likely what the confusion is?

 

[Mensanator]

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.

That's usually what "theorem" means.

For a while I had thought the conjecture, in general, was incorrect,

Why would you think that?

but I did this with a brute force algorithm to find no counter examples.

Duh.

Can anyone help?

No need to, it's a THEOREM.

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

No need to, Euler already did the work.

Thanks! :)

Thank Euler.

 

[TwilightTulip]

That's usually what "theorem" means.

Why would you think that?

Duh.

No need to, it's a THEOREM.

No need to, Euler already did the work.

Thank Euler.

Clearly the above poster can't read, as he/she thinks I am trying to prove Euler's theorem. Thanks for trying to make me feel like an idiot and failing horribly.

I have proved WHAT I am trying to do with the aid of a simple brute force approach. I tested all primes p except 101, 103, 107 and verified it was true. Then I wrote m in its prime factorization and two lines of algebra provided my answer.

I would still like to know if there were a purely (relatively simple) algebraic way to handle this.

 

[Mensanator]

Clearly the above poster can't read, as he/she thinks I am trying to prove Euler's theorem. Thanks for trying to make me feel like an idiot and failing horribly.

I have proved WHAT I am trying to do with the aid of a simple brute force approach. I tested all primes p except 101, 103, 107 and verified it was true. Then I wrote m n its prime factorization and two lines of algebra provided my answer.

I would still like to know if there were a purely (relatively simple) algebraic way to handle this.

Don't you think Euler would have noticed?

 

[robert Ihnot]

There ought to be a relatively simple way to handle this, as you suggest.

Now for 3x5=15, phi(15)=8, but we only need consider for all cases m^4==1, Mod 15; so that we might think that we need go no more than the highest power of 2--here found in phi(5) =4. Similarly in the case you present the highest power of 2 is 4 found in Phi(101). (In the total phi sum the highest power is 16.)

Now take the case of 3,5,17 = 255. Phi(255) = 128. Here we find that x^16==1 Mod 17. And that is needed for m=7 Mod 255. This follows the same pattern.
So there seems to be a theorem here.

 

[TwilightTulip]

There ought to be a relatively simple way to handle this, as you suggest.

Now for 3x5=15, phi(15)=8, but we only need consider for all cases m^4==1, Mod 15; so that we might think that we need go no more than the highest power of 2--here found in phi(5) =4. Similarly in the case you present the highest power of 2 is 4 found in Phi(101). (In the total phi sum the highest power is 16.)

Now take the case of 3,5,17 = 255. Phi(255) = 128. Here we find that x^16==1 Mod 17. And that is needed for m=7 Mod 255. This follows the same pattern.
So there seems to be a theorem here.

Thanks for the reply, I think I figured it out. Its amazing, waking up in the morning and realizing what was right in your face the whole time. Perhaps it was all the code-writing, but here's my argument:

If p is an arbitrary prime between 1 and 1113121=101*103*107 (except these primes specifically), we note that Phi applied to each of these prime factors of 1113121 divide 270300. The gcd of p with any of these prime factors is 1 =>

270300 = 0 (mod Phi(101)) => p^270300 = 1 (mod 101)
270300 = 0 (mod Phi(103)) => p^270300 = 1 (mod 103)
270300 = 0 (mod Phi(107)) => p^270300 = 1 (mod 107)

From which we notice the obvious fact that these factors are relatively prime and can conclude from the Chinese Remainder Theorem:

p^(270300) = 1 (mod 1113121)

Then we break m into its prime factorization (which by assumption does not contain 101,103,107) and apply the above lemma. The last step is simple congruence arithmetic and we have the result.

 

[IB1]

There are Algebraic Methods. But I simply do not recommend them to you or to anyone else. Is far much simpler to know Euler's Function, or even some elementary abstract algebra knowledge would do the work. If you want to learn these methods to use them in Mathematical Olympiads, then I prefer you that you write solutions using group properties, since university teachers who mark the papers really like to see applications of group theory and therefore may give you more marks. :P

 

[lab_b]

Using Fermat's_little_theorem (http://en.wikipedia.org/wiki/Fermat's_little_theorem),

m^100=1(mod 101), m^102=1(mod 103), m^106=1(mod 107),

Using a=b(mod M)=>a^n=b^n(mod M)
m^270300 = 1 (mod 101) , m^270300 = 1 (mod 103), m^270300 = 1 (mod 107)

Using a=b(mod M1),a=b(mod M2) and a=b(mod M3) =>a=b(mod lcm(M1.m2,M3))
m^270300 = 1 (mod lcm(101,103,107))
=>m^270300 = 1 (mod 101*103*107) as 101,103,107 are pair-wise co-prime.

Thanks
Lab