0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – AlexR Oct 31 '14 at 16:47
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

As $(n,n^2+1)=(n,n^2+1-n\cdot n)=(n,1)=1$ and $p\mid(n^2+1),(n,p)=1$

then apply the little Theorem

$\endgroup$

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.