Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Order of an integer

Expand Messages
  • Sarad AV
    Hello, ... Thankyou for providing counter examples,a special case of this conjecture is proved to be true as follows: If p is an odd prime and p(doesnot divide
    Message 1 of 3 , Jun 1, 2005
    • 0 Attachment
      Hello,

      --- Peter Kosinar <goober@...> wrote:

      > 1. The order of an integer 'a' modulo P^m =
      > P^(m-1)*(Order of a mod P);
      > where P is an odd prime .
      >
      > This conjecture doesn't seem to be valid.

      Thankyou for providing counter examples,a special case
      of this conjecture is proved to be true as follows:

      If p is an odd prime and p(doesnot divide k), then
      p^(m-1) is the order of a = 1+kp (mod p^m).

      The proof can be found on page 43, A classical
      introduction to modern number theory, Kenneth Ireland
      and Michael Rosen, Second Edition, Springer

      > 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.

      The proof of this has been given by Maverick as
      follows:

      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 modulo p is t,
      and let s be the largest power 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

      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.

      This must be acknowlodged to mattgrime @ physicsforums


      Cheers.




      __________________________________
      Yahoo! Mail
      Stay connected, organized, and protected. Take the tour:
      http://tour.mail.yahoo.com/mailtour.html
    Your message has been successfully submitted and would be delivered to recipients shortly.