El primer divide $n^2 + 1 \Rightarrow$ prime no divide $n$

Question

¿Cómo puedo demostrar que si un prime $p$ divide $$n^2 + 1$$ then it doesn't divide $n$?

Answer 1

Podemos utilizar la Identidad de Bezout para mostrar que $\left(n^2+1,n\right)=1$. Es decir, $$ \left(n^2+1\right)\cdot1-n\cdot n=1 $$ Por lo tanto, el máximo común divisor de a$n^2+1$$n$$1$.

Es decir, si cualquier número dividido tanto en$n^2+1$$n$, también se dividen $(n^2+1)-n\cdot n=1$.

Answer 2

Una prueba por contradicción: suponga $n\equiv 0\mod p$$p>1$, luego $$n^2\equiv 0\pmod p$$ also. But $$n^2\equiv -1\pmod p$$ lo que contradice, por lo tanto $$n^2+1\equiv 0\pmod p\Rightarrow n\not\equiv 0\pmod p$$

Answer 3

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[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{\mitad}{{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}{\parcial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

A continuación, todos los 'leters variables' $\ds{n,s,p}$ son enteros $\ds{\pars{~p\ \mbox{is a}\ \ul{prime\ number}~}}$:

• $\ds{{n \sobre p} = s\quad\imp\quad n = sp\quad\imp\quad{n^{2} + 1 \sobre p} = {s^{2}p^{2} + 1 \sobre p} = s^{2} p + {1 \over p}\ !!!}$

  ---

• $\ds{{1 \over p}\ \ul{\mbox{no}}\ \mbox{un entero porque}\ p > 1 \pars{~p\ \mbox{es un número primo}~}}$

  ---

• $\pars{\vphantom{\LARGE A}% p \mediados n \imp p \no\mid \pars{n^{2} + 1}}\ \mbox{es equivalente a}\ \pars{\vphantom{\LARGE A}% p \mid \pars{n^{2} + 1} \imp p \no\mediados n}$

Answer 4

Si $p=2 $ and $2\mediados de 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{casos}$$ y esto es absurdo.

Answer 5

Quiere probar que la declaración de $\color\red{p|n^2+1}\implies\color\green{p\not|n}$.

En su lugar, usted puede probar la declaración equivalente $\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})$.

Por CIERTO, esta declaración tiene no sólo para cada prime $p$, pero también para cada entero $p>1$.