## Order of an integer mod P^k

Expand Messages
• 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.