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

Order of an integer mod P^k

Expand Messages
  • cemmanu@yahoo.com
    We know that the order of r modulo p^2 = p(p-1), where r is a primitive root of p and p is a prime greater than 2.  Now, are equations 1 and 2 below known? 
    Message 1 of 1 , May 9, 2009
      We know that the order of r modulo p^2 = p(p-1), where r is a primitive root of p and p is a prime greater than 2.  Now, are equations 1 and 2 below known?  If not, is my proof sufficient?...


      ___________________________________________________________________________
      Let a,i,k,n,m, x, and y be elements of Z and p be a prime >2. 

      Let n be the order of 'a' mod p,

      then
      order of 'a' mod p^2 = pn  ----------------------------------------------------------------> (Eq.1)

      In general,
      order of a mod p^k = (p^(k-1))*(order of a mod p)  ---------------------------->(Eq. 2)

      PROOF (for the case of k = 2):
      Since a^n = 1 mod p, let a^n = x + 1, therefore p divides x

      (a^n)^m = 1 mod p for m = 1,2,3, ... and m < p

      (a^n)^m = the product of [C(m,i)* x^(m-i)], where C(m,i) is the combination m choose i, for i = 0 to m. 

      Therefore
      (a^n)^m = (x+1)^m = [C(m,0)]*x^m + [C(m,1)]*x^(m-1) + [C(m,2)]*x^(m-2) + .  .  .
      + [C(m,m-2)]*x^2 + C(m,m-1)*x + 1    -------------------------------------------------->(Eq. 3)

      Which is equal to
      x^m + mx^(m-1) + (m(m-1)/2)*x^(m-2) + .  .  . + (m(m-2)/2)x^2 + mx + 1 -->(Eq. 4)

      Equation 1 is equal to mx + 1 mod p^2, which is not congruent to 1 mod p^2

      But if we let m = p then equation 4 becomes
      x^p + px^(p-1) + (p(p-1)/2)*x^(p-2) + .  .  . + (p(p-2)/2)x^2 + px + 1 ----------->(Eq. 5)

      And since p divides x, then equation 5 is congruent to 1 mod p^2.

      This proves equation 1.  Equation 2 can be proven by induction.
      _______________________________________________________________________

      ---Cletus






      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.