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.
On
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$.
On
$$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
On
$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$.
On
$$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}\}.$$
On
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.
On
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....$
$$ \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} $$