After seeing and doing a bunch of proofs like "For all $a$ in the natural numbers, then if $7$ does not divide $a$, then $7$ divides $a^3+1$ or $a^3-1$," I conjectured the following, but got stuck in proving it. I'd like to know if it has an actual name, or whether this is just something rather trivial and pointless.

Given a prime $p$ of the form $2n+1$, for all $a$ in the natural numbers if $p$ does not divide $a$, then $p$ divides $a^n+1$ or $a^n-1$.

*Assume non-trivial $a$

Thanks very much.

  • $\begingroup$ Every odd prime number is of the form $2n+1$, by the way. So it's every prime number except $2$. $\endgroup$ – Asaf Karagila May 5 '13 at 20:18
  • 2
    $\begingroup$ Fermat's little theorem. $\endgroup$ – Ma Ming May 5 '13 at 20:19
  • $\begingroup$ @AsafKaragila I was trying to make it clear. Stating it as an odd prime means I have to waste a sentence with defining n. But if there's a more elegant way of stating this, I'm all ears. $\endgroup$ – Thoth19 May 5 '13 at 20:41

This is well known. Let $p = 2n + 1$ be an odd prime. Then, it is known that if $\gcd(a,p) = 1$, then $a^{p-1} = a^{2n} \equiv 1 \pmod{p}$, by Fermat's Little Theorem. Hence, $(a^n)^2 \equiv 1 \pmod{p}$ so that $a^n \equiv \pm 1 \pmod{p}$.

You do need to know that $x^2 \equiv 1 \pmod{p}$ has exactly two solutions when $p > 2$ is prime, but this is a consequence of $\mathbb{Z}_p$ (The integers mod $p$) being a (finite) field. When $p = 2$, we have $1 \equiv -1 \pmod{2}$ so that $x^2 \equiv 1 \pmod{p}$ has only one solution in this case.

  • $\begingroup$ Thank you. I haven't used that one often enough or recently enough to recognize it. $\endgroup$ – Thoth19 May 5 '13 at 20:43

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.