Suppose we have p is a prime, a > 1, and gcd(a,p) = 1

1.) Prove that a^(ord_(p)a - 1) + a(ord_(p)a - 2) + ... + a^1 + 1 = 0 (mod p)

2.) Prove that if a has order 3 (mod p), then a + 1 has ord 6 (mod p).

Printable View

- Apr 16th 2007, 01:58 PMfifthrapiersOrder of Integer Proof
Suppose we have p is a prime, a > 1, and gcd(a,p) = 1

1.) Prove that a^(ord_(p)a - 1) + a(ord_(p)a - 2) + ... + a^1 + 1 = 0 (mod p)

2.) Prove that if a has order 3 (mod p), then a + 1 has ord 6 (mod p). - Apr 16th 2007, 05:14 PMThePerfectHacker
We know that,

a^k = 1 (mod p) where k is ord_p(a).

If and only if,

a^k - 1 = 0 (mod p)

Factorize,

(a-1)(a^{k-1}+a^{k-2}+...+a^1+1)=0 (mod p)

Since,

a-1 != 0 (mod p ) unless a=1 (but then proof is trivial).

That means, (division)

a^{k-1}+a^{k-2}+...+a^1+1 =0(mod p) - Apr 16th 2007, 06:45 PMThePerfectHacker
Let us first show that if gcd(a,p)=1 then gcd(a+1,p)=1. Meaning, we want to show that the order modulo p is defined (because if gcd(a+1,p)=p then the order is not defined!)

Say, it is not, gcd(a+1,p)=1 that is a+1=pn. Hence, a=pn-1.

But then a = pn -1 = -1 (mod p) meaning the order is 2 not 3, a contradiction.

Thus, this problem does not lead to an undefined operation.

Now we can solve this problem, gaze below.