1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory: Modulus and Divisibility problem

  1. May 12, 2013 #1
    1. The problem statement, all variables and given/known data

    Prove that if gcd(a, 133) = 1, then 133 divides (a^18 - 1).



    3. The attempt at a solution

    This is an old homework question as I'm going over the homeworks to review for the test, but can't seem to get this right. Which is annoying because I remember I did it fine back in the course when this homework was actually due.

    So, I know gcd(a, 133) = 1 implies 133 divides a^phi(133) -1 = a^108 -1. So I assume I'd want to factor that out so that I get a product of polynomials, one of the form (a^18 - 1), and show that the other polynomial factors aren't divisible by 133 by appealing to their modulus form. But that doesn't seem to be working out.
     
  2. jcsd
  3. May 12, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Can you show where exactly you run into problems? The approach looks good, I think.
     
  4. May 13, 2013 #3
    It just doesn't factor easily, and generally in this class the problems have been computationally simple once you know the right approach to take, so that's making me think it can't be right. I mean, I'd want to factor it so I get a product of (a^x -1)(a^y + 1) .... (a^z +1) etc so that I can easily show that none of the other factors are divisible, but it doesn't seem like it'll break up like that:

    I can get (a^108 - 1) = (a^54 -1)(a^54 +1) = (a^27 - 1)(a^27+1)(a^54 + 1) etc. I think I need to factor it into forms like that to get a product of factors only of the form I can convert into modulus representations. But it doesn't seem I can do that.
     
  5. May 13, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    [tex]a^{108-1} = (a^{18})^6-1 = (a^{18}-1)(...)[/tex]

    I think you can show that a^18=1 mod 7 and/or a^18=1 mod 19 is the only way to solve this (so the other expression cannot be 0 mod 133).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Number theory: Modulus and Divisibility problem
Loading...