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.

  • 4
    $\begingroup$ what are successive numbers of the form $n^2+3$.. Give some examples.. $\endgroup$ – kk lm Feb 1 '16 at 17:28
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Feb 1 '16 at 17:40
  • $\begingroup$ @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. $\endgroup$ – fleablood Feb 1 '16 at 17:45

We apply the euclidean algorithm on the polynomials:


We get:




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

  • $\begingroup$ "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.... $\endgroup$ – fleablood Feb 1 '16 at 18:04
  • $\begingroup$ @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$ $\endgroup$ – Ross Millikan Feb 6 '16 at 23:24

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.


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


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.