The only positive integers that divide successive numbers of the form $n^2+3$ are $1$ and $13$

Question

I stuck with this problem, I don't know how to start with. Prove that the only positive integers that can divide successive numbers of the form $n^2+3$ are 1 or 13.

Answer 1

We apply the euclidean algorithm on the polynomials:

$n^2+3,(n+1)^2+3$

We get:

$(n+1)^2+3=(n^2+3)+(2n+1)$

$2(n^2+3)=n(2n+1)+(-n+6)$

$2n+1=-2(-n+6)+13$

From here:

If $d$ divides $(n+1)^2+3$ and $(n^2+3)$ then $d$ divides $2n+1$.

If $d$ divides $n^2+3$ and $(2n+1)$ then $d$ divides $(-n+6)$.

If $d$ divides $2n+1$ and $-n+6$ then $d$ divides $13$.

Putting it all together we have that if $d$ divides $n^2+3$ and $(n+1)^2+3$ then $d$ divides $13$.

Answer 2

Let $p$ be a prime such that $p$ divides the GCD of $n^2+3$ and $(n+1)^2+3$.

It follows $$2n+1=Np\iff n=\frac{Np-1}{2}$$ Hence $$\left(\frac{Np-1}{2}\right)^2+3=Rp\iff N^2p^2-2Np+1+12=4Rp$$ Consequently $p=13$, only possibility for primes $p$, the other factor being the trivial one $1$.

We must, of course, see at the other condition $(n+1)^2+3$ in order to verify compatibility.It gives immediately, $p|13$ also.

An easy calculation gives the numbers in question: $$\color{red}{n=13N+6}$$

Answer 3

This answer is essentially the same as the first answer, by dREaM, but written down in a different form which I personally find easier to understand. (In this answer, all variables range over the integers.)$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} \newcommand{\divides}{\mid} \newcommand{\abs}[1]{\lvert #1 \rvert} $

The mechanism which we will use here is the basic step of Euclid's algorithm for calculating the greatest common divisor of two numbers: for any $\;a,b,c,d\;$, $$ \tag{0} d \divides a \;\;\land\;\; d \divides b \;\;\equiv\;\; d \divides a \;\;\land\;\; d \divides b + c\cdot a $$ where often $\;a<b\;$ and $\;c<0\;$. (Of course $\;\divides\;$ stands for "divides". I've chosen to avoid confusing extra brackets by giving this relation lower precedence than arithmetical operators, but a higher precedence than logical operators.)

Armed with this, for any $\;n,d\;$ where $\;d\;$ is positive, let's calculate which $\;d\;$ satisfy the stated condition:

$$\calc d \divides n^2 + 3 \;\;\land\;\; d \divides (n+1)^2 + 3 \op=\hints{a 'Euclid step': subtract LHS from RHS, i.e., $\ref{0}$ with $\;c := -1\;$} \hint{-- to get rid of the square on the RHS} d \divides n^2 + 3 \;\;\land\;\; d \divides ((n+1)^2 + 3) - (n^2 + 3) \op=\hint{simplify RHS} d \divides n^2 + 3 \;\;\land\;\; d \divides 2n+1 \op\then\hint{LHS: property of $\;\divides\;$} d \divides 2(n^2 + 3) \;\;\land\;\; d \divides 2n+1 \op=\hints{a 'Euclid step': subtract $\;n\;$ times RHS from LHS, i.e., $\ref{0}$ with $\;c := -n\;$} \hint{-- to get rid of the square on the LHS} d \divides 2(n^2 + 3) - n(2n+1) \;\;\land\;\; d \divides 2n+1 \op=\hint{simplify LHS} d \divides 6 - n \;\;\land\;\; d \divides 2n+1 \op=\hints{a 'Euclid step': add 2 times LHS to RHS, i.e., $\ref{0}$ with $\;c := 2\;$} \hint{-- to get rid of the $\;n\;$ on the RHS} d \divides 6 - n \;\;\land\;\; d \divides (2n+1) + 2(6-n) \op=\hint{simplify RHS} d \divides 6 - n \;\;\land\;\; d \divides 13 \op\then\hint{logic: weaken} d \divides 13 \op=\hint{13 is a prime number; $\;d\;$ is positive} d = 1 \;\;\lor\;\; d = 13 \endcalc$$

This proves that at most $1$ and $13$ satisfy the condition.