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

Quote:

---

Originally Posted by fifthrapiers

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)

---

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)

Quote:

---

Originally Posted by fifthrapiers

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

---

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.