Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving that m^270300 = 1 (mod 3121)

  1. Mar 31, 2010 #1
    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:
    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!!! :)
  2. jcsd
  3. Mar 31, 2010 #2
    Re: Proving that m^270300 = 1 (mod 11113121)

    What is m? If m represents any integer relataively prime to the modulus, you are wrong since you show a factor of 4.
    Last edited: Mar 31, 2010
  4. Mar 31, 2010 #3
    Re: Proving that m^270300 = 1 (mod 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?
  5. Mar 31, 2010 #4
    Re: Proving that m^270300 = 1 (mod 11113121)

    That's usually what "theorem" means.
    Why would you think that?
    No need to, it's a THEOREM.
    No need to, Euler already did the work.
    Thank Euler.
  6. Mar 31, 2010 #5
    Re: Proving that m^270300 = 1 (mod 11113121)

    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.
  7. Mar 31, 2010 #6
    Re: Proving that m^270300 = 1 (mod 11113121)

    Don't you think Euler would have noticed?
  8. Apr 1, 2010 #7
    Re: Proving that m^270300 = 1 (mod 11113121)

    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.
  9. Apr 1, 2010 #8
    Re: Proving that m^270300 = 1 (mod 11113121)

    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.
  10. Apr 6, 2010 #9


    User Avatar

    Re: Proving that m^270300 = 1 (mod 11113121)

    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
  11. May 26, 2010 #10
    Re: Proving that m^270300 = 1 (mod 11113121)

    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.

    Last edited: May 26, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook