Browse Groups

• 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.