10
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Take $n \in \{ 4, 4+65, 4+65+65 , \dots \} = \{ 4+ 65k : k \ge 0 \}$. All such numbers work, and they are infinitely many. $\endgroup$ – Crostul Mar 19 '16 at 14:12
  • $\begingroup$ 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. $\endgroup$ – fleablood Mar 19 '16 at 22:32

10 Answers 10

4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The answer's great but how did you come to know that adding $65k$ works? $\endgroup$ – TheRandomGuy Mar 19 '16 at 16:20
  • $\begingroup$ 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. $\endgroup$ – robjohn♦ Mar 19 '16 at 17:36
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think you meant $\color{red}61$ in the places where you wrote $51$ $\endgroup$ – J. W. Tanner Sep 4 '19 at 0:02
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – J. W. Tanner Sep 4 '19 at 0:01
  • $\begingroup$ I added a complement to my answer. $\endgroup$ – nguyen quang do Sep 4 '19 at 8:28
  • $\begingroup$ Did you mean $\color{red}-8n+7=65b$? $\endgroup$ – J. W. Tanner Sep 4 '19 at 10:10
  • 1
    $\begingroup$ Yes, sorry. But the final form of b is unchanged although the value of $\beta$ is changed. $\endgroup$ – nguyen quang do Sep 4 '19 at 11:04
  • $\begingroup$ without solving for a you could say 8n=7−65b=7−65(−1+8β)=72−65×8β so n=9−65β $\endgroup$ – J. W. Tanner Sep 4 '19 at 11:25
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The second hint is already given in the question. $\endgroup$ – N.S.JOHN Mar 19 '16 at 14:15
  • 1
    $\begingroup$ @ThomasAndrews So I just go on adding 65? $\endgroup$ – TheRandomGuy Mar 19 '16 at 14:18
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @ThomasAndrews, Sorry I meant this $\endgroup$ – lab bhattacharjee Mar 19 '16 at 14:16
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.