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$.
 A: Hint: by Fermat's little theorem, we have $x^{p-1}\equiv 1\pmod{p}$.
A: 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.
A: 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 
