# Congruence Proof Involving Fermat's Little Theorem

Let $n \in\mathbb N$. Use Fermat’s little Theorem to show that if a prime $p$ divides $n^2 + 1$, then $n^{p−1} \equiv 1 \pmod p$.

So far, I have written that I need to show $n^2 \equiv -1 \pmod p$. What I have to work with is $n^2+1 = pk$ for some $k \in\mathbb Z$.

I'm not not quite sure what to do from here.

• Welcome to Math.SE. You may want to take a look at math.stackexchange.com/help/notation to see how to use MathJax on this site. I've applied MathJax formatting to your post this time. – AlexR Oct 31 '14 at 16:47

$p \mid n^2+1 \implies \operatorname{gcd}(n,p)=1 \implies n^{p-1}\equiv 1 \pmod p$
As $(n,n^2+1)=(n,n^2+1-n\cdot n)=(n,1)=1$ and $p\mid(n^2+1),(n,p)=1$