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$].
Is that true, please?
Thank you.
Best Answer
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