# Congruences modulo a prime p

How would you go about showing that (for $a \in \mathbb{Z}$) $x^{2}+a^{2}$ divides $x^{p-1}-1$, modulo a prime $p$, where $p\equiv 1 \mod 4$?

My first thought was to use the fact that there exists a $u$ such that $u^{2}\equiv -1 \mod p$ and factor to get $(x+ua)(x-ua)\equiv x^2 + a^2 \mod p$. Though, I can't seem to relate that to $x^{p-1}-1$.

• Did you mean for $\gcd(a,p) = 1$? – Hurkyl Apr 20 '13 at 21:04

## 3 Answers

Hint $\$ By little Fermat, $\rm\,\pm ua \:$ are roots of $\rm\:f(x) = x^{p-1}\!-1\:$ hence, by the Factor Theorem, $\rm\:f(x),\:$ is divisible by $\rm\:x\!-\!ua,\:$ and $\rm\:x\!+\!ua,\:$ so also by their product $\rm\:x^2\!+a^2,\:$ since the roots are distinct (why?)

Remark $\$ Note that the last inference depends crucially on $\rm\:p\:$ being prime. It may fail otherwise, e.g. $\rm\: mod\ 8\!:\ f(x) = x^2\!-1\:$ has roots $\rm\:x = 1,3\:$ hence $\rm\:f(x)\:$ is divisible by both $\rm\:x-1\:$ and $\rm\:x-3,\:$ but it is not divisible by their product.

• This is less of a hint, and more of a complete solution with a minor point omitted to leave some busy work for the OP. – Hurkyl Apr 20 '13 at 21:03
• @Hurkyl The omitted point is far from "minor" or "busy work", see the Remark. – Math Gems Apr 20 '13 at 21:36
• What if a and p are not coprime? – user70363 Apr 21 '13 at 22:42
• @user70363 If $\rm\,p\mid a\,$ then $\rm\:mod\ p\!:\ x^2\!+a^2\equiv x^2,\:$ which does not divide $\rm\,f(x) = x^{p-1}\!-1\:$ since $\rm\:f(0) = -1\not\equiv 0.\ \$ – Math Gems Apr 21 '13 at 23:11

Hint: by Fermat's little theorem, we have $x^{p-1}\equiv 1\pmod{p}$.

• One needs more than that to give a complete proof - see my answer. E.g does your proposed proof work in non-domains? If not, where did you use that hypothesis? – Math Gems Apr 20 '13 at 20:52
• @MathGems: That's why it's called a "hint", rather than called "a complete proof".... – Hurkyl Apr 20 '13 at 20:59
• @Hurkyl Imo hints should not omit mention of points that are critical to the success of the proof. Hence my comment. – Math Gems Apr 20 '13 at 21:29

If prime $p>2, p$ is odd,

$x^{p-1}=(x^2)^{\frac{p-1}2}=(-a^2)^{\frac{p-1}2}$ (Putting $x^2=-a^2$)

$x^{p-1}=(-1)^{\frac{p-1}2}\cdot a^{p-1}\equiv (-1)^{\frac{p-1}2}\pmod p$ using Fermat's little theorem, $a^{p-1}\equiv1\pmod p$

But $x^{p-1}\equiv1\pmod p$

$\implies (-1)^{\frac{p-1}2}\equiv1\pmod p$

If $\frac{p-1}2$ is odd, if $\frac{p-1}2=2k+1,p=4k+3\equiv3\pmod 4$ for some integer $k,$

$(-1)^{\frac{p-1}2}\equiv-1\pmod p\implies -1\equiv1\pmod p\implies 2$ divides $p$, but $p$ is odd

Similarly, test when $\frac{p-1}2$ is even