# $ord_p(a)=2 \iff a\equiv -1 \mod p$

a) Let $$p$$ be an odd prime. Prove that:

$$\text{ord}_p(a)=2 \iff a\equiv -1 \mod p$$

My attempt:

Assume that $$\text{ord}_p(a)=2$$, then

$$a^2\equiv 1 \mod p$$

$$p\mid a^2-1$$

$$p\mid(a-1)(a+1)$$

$$p\mid a-1$$ or $$p\mid a+1$$

If $$p\mid a-1$$ then $$a\equiv 1 \mod p$$

Which contradicts that $$\text{ord}_p(a)=2$$

Therefore, we must have $$a\equiv -1 \mod p$$.

Now, assume that $$a\equiv -1 \mod p$$

Then $$a^2 \equiv 1 \mod p$$. Now, I think we must show that $$2$$, is the least positive integer satisfying the last congruence. This is equivalent to showing, that $$a\not \equiv 1 \mod p$$. Since $$a\equiv -1 \mod p$$, then $$a\not \equiv 1 \mod p$$. Is that true, please?

b) Suppose that $$\text{ord}_n (a)=n-1$$, prove that n is a prime number.

My attempt:

$$\text{ord}_n (a)=n-1 \implies a^{n-1} \equiv 1 \mod n$$

Then and by the converse of the Fermat’s little theorem, we have that $$n$$ is a prime number. [notice that $$(a,n)=1$$].

Thank you.

• Yes, it could be possible only with $p=2$, and you suppose $p$ is odd. – Bernard Mar 30 at 22:54
• @Bernard Thank you so much. – Dima Mar 30 at 22:59
• You're welcome! Always glad to help! – Bernard Mar 30 at 23:00
• B.t.w., non-prime numbers which satisfy that $a^{n-1}\equiv 1$ for all $a$ coprime to $n$ are called *Carmichael numbers. The smallest Carmichael number is $561=3\cdot 11\cdot 17$. – Bernard Mar 30 at 23:10
• " Now, I think we must show that 2, is the least positive integer satisfying the last congruence." uh.... he only positive integer smaller is $1$.... Sometimes one of the directions in an if and only if proof is self evident. This is one of those times. – fleablood Mar 31 at 1:10

Hint For $$b)$$ your approoach is not working since the converse to FLT is not true.
Try instead the following: $$\text{ord}_n (a)=n-1$$ implies that $$a, a^2,... , a^{n-1}$$ are distinct elements modulo n, in the set $$\{1, 2, .., n-1\} \pmod{n}$$.
Deduce that $$1, 2,.., n-1$$ are all invertible modulo n