# Prime divides $n^2 + 1 \Rightarrow$ prime doesn't divide $n$

How can I show that if a prime $p$ divides $$n^2 + 1$$ then it doesn't divide $n$?

• If p divides n then it must divide n^2. No number other than 1 can divide two consecutive numbers. Jul 6 '16 at 2:25
• Dang auto correct. And that was a weird one. Can not understand it. Jul 6 '16 at 2:28
• Try proving the contrapositive, it's easier to think about. Jul 6 '16 at 2:29
• @fleablood Maybe cutie numbers are like friendly numbers and lucky numbers at the same time?
– user296602
Jul 6 '16 at 2:29
• Applying Euclid's algorithm $\,(n^k\!+1,n) = (1,n) = 1\,$ by $\,n^k\!+1\equiv 1\pmod n\,$ for $\,k\ge 1.\,$ Since their gcd $= 1,\,$ they have no nontrivial common divisor. Jul 6 '16 at 3:35

We can use Bezout's Identity to show that $\left(n^2+1,n\right)=1$. That is, $$\left(n^2+1\right)\cdot1-n\cdot n=1$$ Therefore, the greatest common divisor of $n^2+1$ and $n$ is $1$.

That is, if any number divided both $n^2+1$ and $n$, it would also divide $(n^2+1)-n\cdot n=1$.

• For every integer $k\ge 1$, $(n^k+1)\cdot 1-n\cdot n^{k-1}=1$. Jul 6 '16 at 10:27
• Indeed. $\left(n^k+1,n\right)=1$ for $k\ge1$.
– robjohn
Jul 6 '16 at 12:12
• @Woria Special case $\, j = n^{k-1}\,$ of $\,(1\!+\!nj,\,n) = 1\$ by $\ 1= 1\!+\!nj-n(j)\ \$ (or by one step of Euclid's algorithm - see my comment on the question). Aug 4 '16 at 2:51

A proof by contradiction: assume $n\equiv 0\mod p$ with $p>1$, then $$n^2\equiv 0\pmod p$$ also. But $$n^2\equiv -1\pmod p$$ which contradicts, therefore $$n^2+1\equiv 0\pmod p\Rightarrow n\not\equiv 0\pmod p$$

• i.e. if $\,p\mid n,\color{#c00}{n^2\!+\!1}\,$ then $\,{\rm mod}\ p\!:\ n\equiv 0\,\Rightarrow\, 0\equiv \color{#c00}{n^2\equiv -1}\,\Rightarrow\, p\mid 1,\,$ contradiction Aug 4 '16 at 2:54


Below, all 'leters variables' $\ds{n,s,p}$ are integers $\ds{\pars{~p\ \mbox{is a}\ \ul{prime\ number}~}}$:

• $\ds{{n \over p} = s\quad\imp\quad n = sp\quad\imp\quad{n^{2} + 1 \over p} = {s^{2}p^{2} + 1 \over p} = s^{2} p + {1 \over p}\ !!!}$
• $\ds{{1 \over p}\ \ul{\mbox{is not}}\ \mbox{an integer because}\ p > 1 \pars{~p\ \mbox{is a prime number}~}}$
• $\pars{\vphantom{\LARGE A}% p \mid n \imp p \not\mid \pars{n^{2} + 1}}\ \mbox{is equivalent to}\ \pars{\vphantom{\LARGE A}% p \mid \pars{n^{2} + 1} \imp p \not\mid n}$

If $p=2$ and $2\mid n$ we have that $n^{2}$ is even and so $n^{2}+1$ is odd. Now assume that $p$ is odd. We can use the Legendre symbol. If we assume that $n\equiv0\mod p$ we have $n^{2}\equiv0 \mod p$. So $$\left(\frac{n^{2}}{p}\right)=0$$ but since $n^{2}\equiv-1 \mod p$ we also have, by the law of quadratic reciprocity $$\left(\frac{n^{2}}{p}\right)=\left(\frac{-1}{p}\right)=1^{\frac{p-1}{2}}=\begin{cases} 1 & p\equiv1\,\mod\,4\\ -1 & p\equiv3\,\mod\,4 \end{cases}$$ and this is absurd.

You want to prove the statement $\color\red{p|n^2+1}\implies\color\green{p\not|n}$.

Instead, you can prove the equivalent statement $\neg(\color\green{p\not|n})\implies\neg(\color\red{p|n^2+1})$:

$\small\neg(\color\green{p\not|n})\implies{p|n}\implies{p|n^2}\implies{\forall_{k\in(0,p)}:p\not|n^2+k}\implies{p\not|n^2+1}\implies\neg(\color\red{p|n^2+1})$.

BTW, this statement holds not only for every prime $p$, but also for every integer $p>1$.