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$? 
 A: 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$.
A: 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$$
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

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}$

A: 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.
A: 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$.
