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

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.

• what are successive numbers of the form $n^2+3$.. Give some examples.. – kk lm Feb 1 '16 at 17:28
• A start: We are looking for common divisors of $n^2+3$ and $(n+1)^2+3$, that is, $n^2+2n+4$. Any such common divisor must divide their difference $2n+1$. – André Nicolas Feb 1 '16 at 17:40
• @kklm 13 divides both 39 and 52 which are two consecutive integers of the form. I took me a while to realize the OP did meant "ass" of the form but that there exists at least one pair of consecutive integers of the form. – fleablood Feb 1 '16 at 17:45

## 3 Answers

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

• "the d divides -n + 6" so if n = 19... $19^2 + 3 = 28*13$ and $20^2 + 3 = 31*13$. Cool! And if n = 32......$32^2 + 3 = 79*13$ $33^2 + 3 = 84*13$. Neat.... – fleablood Feb 1 '16 at 18:04
• @fleablood: in fact, $(13k+6)^2+3=169k^2+156k+39$ is divisible by $13$, as is $(13k+7)^2+3=169k^2+182k+52$ – Ross Millikan Feb 6 '16 at 23:24


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.

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