$\operatorname{gcd}(p,a)=1 \Rightarrow \operatorname{gcd}(p,a+1)=1$

Question

How can I show that if $p$ is a prime, $\operatorname{gcd}(p,a)=1$ and $\operatorname{ord}_{p}(a)=3$. then $\operatorname{gcd}(p,a+1)=1$.

I know that $\operatorname{ord}_{p}(a)=3$ means that $a^3 \equiv 1 \pmod p$ but how can I use that to proof the assertion?

Answer 1

Note that

$$a^3 \equiv 1 \iff a^3-1 \equiv 0 \iff (a-1)(a^2+a+1)\equiv 0 \pmod p$$

then

$$p|(a-1) \quad \lor \quad p|(a^2+a+1)$$

but

• $a-1\equiv 0 \iff a \equiv 1\pmod p$ is not possible since $\operatorname{ord}_{p}(a)=3$

then we have

• $a^2+a+1\equiv 0 \pmod p$

then if $\gcd(p,a+1)\neq 1$ we had

• $a^2+a+1\equiv a^2 \equiv 0 \pmod p \implies a^3\equiv 0 \pmod p $

which is a contradiction.

Answer 2

Let $p$ be prime. And $ord_p(a) = 3$.

$\gcd(p,a+1)$ divides $p$ so $\gcd(p,a+1) = 1$ or $p$.

Suppose $\gcd(p,a+1)= p$. Then $p|a+1$ so $a+1 \equiv 0 \mod p$.

So $a \equiv -1 \mod p$.

So $a^3 \equiv -1 \mod p$.

And $a^3 \equiv 1 \mod p$ so

$-1\equiv 1 \mod p$ and so $0 \equiv 2 \mod p$. So $p|2$.

So $p = 2$.

But that would mean $a \equiv-1\equiv 1 \mod p$ and $ord_2(1)=1\ne 3$. So that is a contradiction.

$\gcd(p,a+1) = 1$.

Answer 3

HINT

From $ord_p(a) = 3$ deduce that $p$ divides $1 + a + a^2$. (Remember that $a^2 \not\equiv 1 \mod p$)!

Now assume $p$ divides $1+a$ and deduce $p$ divides $a$.