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$ 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.

  • 1
    $\begingroup$ Yes, it could be possible only with $p=2$, and you suppose $p$ is odd. $\endgroup$ – Bernard Mar 30 at 22:54
  • $\begingroup$ @Bernard Thank you so much. $\endgroup$ – Dima Mar 30 at 22:59
  • $\begingroup$ You're welcome! Always glad to help! $\endgroup$ – Bernard Mar 30 at 23:00
  • 1
    $\begingroup$ 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$. $\endgroup$ – Bernard Mar 30 at 23:10
  • $\begingroup$ " 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. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.