5
$\begingroup$

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

$\endgroup$
7
  • 8
    $\begingroup$ If p divides n then it must divide n^2. No number other than 1 can divide two consecutive numbers. $\endgroup$
    – fleablood
    Jul 6 '16 at 2:25
  • $\begingroup$ Dang auto correct. And that was a weird one. Can not understand it. $\endgroup$
    – fleablood
    Jul 6 '16 at 2:28
  • $\begingroup$ Try proving the contrapositive, it's easier to think about. $\endgroup$ Jul 6 '16 at 2:29
  • 1
    $\begingroup$ @fleablood Maybe cutie numbers are like friendly numbers and lucky numbers at the same time? $\endgroup$
    – user296602
    Jul 6 '16 at 2:29
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 6 '16 at 3:35
7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ For every integer $k\ge 1$, $(n^k+1)\cdot 1-n\cdot n^{k-1}=1$. $\endgroup$
    – Woria
    Jul 6 '16 at 10:27
  • $\begingroup$ Indeed. $\left(n^k+1,n\right)=1$ for $k\ge1$. $\endgroup$
    – robjohn
    Jul 6 '16 at 12:12
  • $\begingroup$ @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). $\endgroup$ Aug 4 '16 at 2:51
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Aug 4 '16 at 2:54
1
$\begingroup$

$\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}$
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\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.