# Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$.

This can be written as: $$65k = (2n)^2 + 1$$ It's clear that $k$ will always be odd. Now I am stuck. I wrote a program to find the first few $n$'s. They are $4, 9$.

$n$ can only end with $4, 6, 8, 9$ if I'm correct in my deductions.

• Take $n \in \{ 4, 4+65, 4+65+65 , \dots \} = \{ 4+ 65k : k \ge 0 \}$. All such numbers work, and they are infinitely many. – Crostul Mar 19 '16 at 14:12
• If n = 5m - 1 then 4(5m-1)^2 + 1 = 100m^2 - 40m + 5 is divisible by 5. If n = 13m + 4 then 4(13m + 4) ^2+ 1 = 4*169m^2 + 4*4*13m + 4*16 + 1 = (4*169m^ + 16*13m) + 65 is divisible by 13. So if n = 65m + 4 = 13(5m) + 4 = 5(13m + 1) - 1 so n is divisible by 13 and 5. – fleablood Mar 19 '16 at 22:32

\begin{align} 4(4+65k)^2+1 &=4\left(4^2+2\cdot4\cdot65k+(65k)^2\right)+1\\ &=65\left(1+32k+260k^2\right) \end{align}

• The answer's great but how did you come to know that adding $65k$ works? – TheRandomGuy Mar 19 '16 at 16:20
• The Binomial Theorem says $$\color{#00A000}{(x+65)^k-x^k}=\color{#C00000}{65}\sum_{k=1}^n\binom{n}{k}x^{n-k}65^{k-1}$$ If $P(x)=\sum\limits_{k=0}^na_kx^k$ is a polynomial with integer coefficients, then $$P(x+65)-P(x)=\sum_{k=0}^na_k\left(\color{#00A000}{(x+65)^k-x^k}\right)$$ where each term is divisible by $\color{#C00000}{65}$. See Modular Arithmetic. – robjohn Mar 19 '16 at 17:36

$$4n^2 + 1 \equiv 0 \pmod{13} \iff n^2 \equiv 1 \pmod 5 \iff n \equiv \pm 1 \pmod 5$$

and

$$4n^2 + 1 \equiv 0 \pmod{13} \iff n^2 \equiv 3 \pmod{13} \iff n \equiv \pm 4 \pmod{13}.$$

In conclusion, $$4n^2 + 1 \equiv 0 \pmod{65} \iff n \pmod{65} \in \{4, 9, 51, 56\}.$$

The solutions are $$\{4 + 36k, 9 + 36k, 51 + 36k, 56 + 36k | k \in \mathbb{Z}\}.$$

• I think you meant $\color{red}61$ in the places where you wrote $51$ – J. W. Tanner Sep 4 '19 at 0:02

I'm surprised no one has mentioned the OEIS, since this was available at the time this question was asked:

A203464 Numbers $$n$$ such that $$65$$ divides $$4n^2 + 1$$; alternately, numbers which are $$4, 9, 56$$, or $$61 \bmod 65$$.

$$4, 9, 56, 61, 69, 74, 121, 126, 134, 139, 186, \ldots$$

The sequence is infinite, since every number of the form $$65k + 56$$ is a member. - Arkadiusz Wesolowski, Oct 29 2013

And there isn't the "fini" keyword anywhere to be seen.

Don't just take Mr. Wesolowski's word for it, though. Verify that $$(65k + 56)^2 = 4225k^2 + 7280k + 3136$$. Doubling twice, we obtain $$16900k^2 + 29120k + 12544$$. Clearly $$16900k^2$$ and $$29120k$$ are both multiple of $$65$$. But $$12544$$ is not. In fact, it's $$1$$ short of a multiple of $$65$$. Q.E.D.

Of course this doesn't account for all the numbers listed. But it is sufficient to prove the sequence is infinite.

$$n = 13 \times 10^k + 4$$ implies $$4n^2 + 1 = 4(13^2 \times 10^{2k} + 8 \times 13 \times 10^k + 16) + 1$$, which in turn is $$4 \times 13^2 \times 10^{2k} + 32 \times 13 \times 10^k + 65$$. It is clear that all terms are multiples of $$13 \times 5 = 65$$.

Brooks's answer suggests an even easier answer by working in $$\mathbb Z_{65}$$. Set $$n = 4$$. Then $$4n^2 = 64$$ and $$4n^2 + 1 = 0 \pmod{65}$$.

Going back to $$\mathbb Z$$, this means that any $$n$$ of the form $$65k + 4$$ will give $$4n^2 \equiv -1 \pmod{65}$$ and thus $$4n^2 + 1 \equiv 0 \pmod{65}$$. e.g., $$4 \times 69^2 + 1 = 19045 = 65 \times 293$$, $$4 \times 134^2 + 1 = 71825$$ $$= 65 \times 1105$$, $$4 \times 199^2 + 1 = 158405 = 65 \times 2437$$.

You already found 9. Note that $$9^2 = 81 \equiv 16 \pmod{65}$$, and obviously $$4 \times 16 = 64$$. Also note that $$-61 \equiv 4 \pmod{65}$$ and $$-56 \equiv 9 \pmod{65}$$.

Rather than staying in $$\textbf Z$$, it is more convenient to work in the ring of Gaussian integers $$\textbf Z[i]$$, which is a principal domain.

Since $$5 = 1 + 4$$ and $$13 = 1 + 12$$, these two primes are totally decomposed in $$\textbf Z[i]$$ thus: $$5 = (1 + 2i)(1 - 2i)$$ and $$13 = (3 + 2i)(3 – 2i)$$. If $$2n + i$$ belongs to the principal ideal generated in $$\textbf Z[i]$$ by, say, $$(1 + 2i)(3 - 2i) = 7 + 4i$$, then taking norms will give that $$4 n^2 + 1$$ is a multiple of $$65$$ in $$\textbf Z$$, i.e. a common multiple of $$5$$ and $$13$$.

The complex equation $$2n + i = (a + bi)(7 + 4i)$$ is equivalent to the system of two linear diophantine equations $$2n = 7a - 4b$$ and $$1 = 7b + 4a$$. Eliminating $$a$$, one readily gets $$-8n + 7 = 65b$$, which can be written as a congruence $${65b} \equiv 7 \pmod8$$, or $$b \equiv{-1} \pmod8$$, or $$b = -1 + 8 \beta$$. It follows that $$4a + 56 \beta = 8$$, or $$a = 2 - 14\beta$$, hence $$n = 9 - 65 \beta$$. This shows what is wanted.

• there are infinitely many solutions to $b\equiv-1\pmod8$, but it's not true for all of them that $(a+bi)$ divides $2n+i,$ correct? – J. W. Tanner Sep 4 '19 at 0:01
• I added a complement to my answer. – nguyen quang do Sep 4 '19 at 8:28
• Did you mean $\color{red}-8n+7=65b$? – J. W. Tanner Sep 4 '19 at 10:10
• Yes, sorry. But the final form of b is unchanged although the value of $\beta$ is changed. – nguyen quang do Sep 4 '19 at 11:04
• without solving for a you could say 8n=7−65b=7−65(−1+8β)=72−65×8β so n=9−65β – J. W. Tanner Sep 4 '19 at 11:25

Hint: In general, if $g$ is an integer polynomial and $g(n)$ is divisible by $D$ then $g(n+D)$ is divisible by $D$.

And a number is divisible by $13$ and $5$ if and only if it is divisible by $13\cdot 5=65$.

• The second hint is already given in the question. – N.S.JOHN Mar 19 '16 at 14:15
• @ThomasAndrews So I just go on adding 65? – TheRandomGuy Mar 19 '16 at 14:18

$$4n^2+1\equiv0\pmod{13}\iff4n^2\equiv-1+65$$

As $(4,13)=1,4n^2\equiv64\iff n^2\equiv16\iff n\equiv\pm4\pmod{13}$

Similarly, $n\equiv\pm4\pmod5$

Now use Chinese Remainder Theorem

• @ThomasAndrews, Sorry I meant this – lab bhattacharjee Mar 19 '16 at 14:16

Okay. The simplest way to "see" this is to realize that $$n = 65m + k$$ will yield $$4(65m + k)^2 + 1 = 65^2*4m^2 + 65*2*4mk + 4k^2 + 1 = 65*M + (4k^2 + 1)$$ which is divisible by 65 whenever $$4k^2 + 1$$ is divisible by 65.

Setting $$4k^2 + 1 = 65$$ we get $$k = 4$$ so any $$n=65m + 4$$ will yield $$4n^2 + 1$$ is divisible by 65.

Thus for $$m = 0,1,2...$$ we have $$n = 4, 69, 134....$$

As soon as you find a single $$n$$ such that $$4n^2+1\equiv0$$ mod $$65$$, then $$4m^2+1\equiv0$$ mod $$65$$ for all $$m\equiv n$$ mod $$65$$. And it's easy to see that $$n=4$$ is such a value.

Remark: This answer differs from robjohn's answer mainly in presentation. The key idea, from modular arithmetic, is that a residue class is an infinite set of integers. Note, we have not found all numbers $$n$$ such that $$65$$ divides $$4n^2+1$$, just one infinite family. But that's all the problem asks for.