Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
I have made no further progress. Please help me find the solution. Thanks.
$$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'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$.
$$ \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} $$
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.
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$.
$$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
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.
