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

Order of an integer

  1. Jun 1, 2005 #1
    Two conjectures (or are they?):

    1. The order of an integer 'a' modulo P^m = P^(m-1)*(Order of a mod P); where P
    is an odd prime .

    2. If a, m, and n are elements of Z and (a,mn) = 1, then Order of a mod mn =
    QR/(Q,R); where Q = Order of a mod m and R = Order of a mod n and (Q,R) is the
    greatest common divisor function.

    For example:

    Example 1:Let a =2 and P=7. Then the order of 2 mod 7 = 3 and the order of 2
    mod 7^3 = 7^2(3)= 147.

    Example 2: The Order of 2 mod 11^2 = 11*(Order of 2 mod 11) = 110

    Example 3: The Order of 2 mod (3*7) = (Order of 2 mod 3)*(Order of 2 mod
    7)/(U,V) = 2*3/1 = 6; where U = Order of 2 mod 3 and V = Order of 2 mod 7.

    Are any of these two statements known? If so, could one point me in the
    direction? If not can anyone prove or disprove?
  2. jcsd
  3. Jun 1, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Firstly,in 2. the quantity QR/(Q,R) is commonly called the least common multiple of Q and R.

    In any case the proof of (the correct version of) statement 1 appears in LeVeque fundmentals of number theory 4.4

    Let p be an odd prime, and suppose p does not divide a. Futher suppose that the order of a module p is t, and let s be the largest powe of p dividing a^t-1.

    If s=p then the order of a modulo p^n is still t, otherwise it is tp^n/s

    The second one is, I think, obvious, isn't it?

    If a^t is 1 modulo mn it is 1 modulo m and n thus Q divides t as does R, hence their least common multiple, call that L, divides t. Conversely it suffices to show that a^L=1 modulo mn, but we know a^L=km+1 and jn+1 for some integers k and j, that is km=jn for some choice of integers j and k, hence m divides j and n divides k as n and m are coprime, ie km=nmk' for some integer k' and thus a^L=nmk'+1=1 mod(mn).

    Thus the order is divisible by L and divides L, so they must be equal.
    Last edited: Jun 1, 2005
  4. Jun 1, 2005 #3


    User Avatar
    Science Advisor
    Homework Helper

    I just wanted to point out that this assumption wasn't included in Ben's post, but it is needed.
  5. Jun 1, 2005 #4
    I would just like to clarify this is not for me! And I hadn't really looked at the problem, jsut somebody on another forum pm'd me with it nad at the time I had no time to spare.

    so, anyway thank you a lot guys for doing it for me, and Matt I have LeVeques book - in all its purple and red glory!

  6. Jun 2, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I just blindly assumed I'd read m and n were coprime otherwise the conjecture would have to be false. Or rather it would be unlikely to be true and I'd instantly start to look for a counter example and find one very quickly I imagine eg a=3, m=n=2.

    Sometimes your mind just fills in the blanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook