Can 40 divide n with the following conditions

Question

If $2n+1$ and $3n+1$ are both perfect squares then prove that $40$ divides $n$.

I tried to solve the problem by taking $a$'s values as multiples of $40$. But the number of such cases would not ever end. So, Probably I need to use some theory- how should I approach this problem?

Answer 1

If $x$ is a square mod 8, then $x$ is 0, 1, or 4 mod 8.

If $x$ is a square mod 5, then $x$ is 0, 1, or 4 mod 5.

So if $x$ is a square mod 40, then $x$ is 0, 1, 4, 9, 16, 20, 24, 25, or 36 mod 40.

$2n+1$ is odd, so if it's a square, then it's 1, 9, or 25 mod 40, and that means that $n$ is 0, 4, or 12 mod 20, and that means that $3n+1$ is 1, 13, or 17 mod 20, so $3n+1$ is 1, 13, 17, 21, 33, or 37 mod 40.

But looking at our list of squares mod 40, $3n+1$ must be 1 mod 40, so $n$ is a multiple of 40.

Answer 2

Brute force search seem to be in agreement with the statement ($n<10^8$)

       0 = 40 * 0
      40 = 40 * 1
    3960 = 40 * 99
  388080 = 40 * 9702
38027920 = 40 * 950698

By parity if $a^2=2n+1$ then $a$ is odd, so let's have $a=2p+1$

$2n=a^2-1=(a-1)(a+1)=2p(2p+2)=4p(p+1)\iff n=2p(p+1)$ which is divisible by $4$.

So let's have $n=4k$

$3n=12k=b^2-1=(b-1)(b+1)$ so $b$ is also odd. Let's have $b=2q+1$.

$12k=4q(q+1)\iff 3k=q(q+1)$ and since $3$ is prime, it divises either $q$ or $q+1$.

• If $q=3u$ then $k=u(3u+1)$ which is even, thus $2\mid k$ and $n$ is divisible by $8$.

• If $q+1=3u$ then $k=u(3u-1)$ which is even too, thus $2\mid k$ and $n$ is divisible by $8$.

$n$ is divisible by $8$

Now we want to show that $n$ is also divisible by $5$.

$n=(3n+1)-(2n+1)=b^2-a^2=(b-a)(b+a)$

For now, I'm stuck here...

Answer 3

Let $2n+1 = a^2$ and $3n+1 = b^2$, then we see that $2b^2 = 6n+2$ and $3a^2 = 6n+3$. Subtracting, $3a^2-2b^2 = 1$, which then gives $b = \sqrt{\frac{3a^2-1}2}$.

Hence, it's essentially enough to find when $b$ is an integer. For example, when $a=9$, then $b = 11$, so this gives $n = 40$.

Theory is a must, as you said. So I quote this nice result:

Given an initial soln $\{p,q\}$ to $mp^2-nq^2 = c$, then $mx^2-ny^2 = c$ where, $x = {pu^2+2nquv+mnpv^2}, y = {qu^2+2mpuv+mnqv^2}$ and $u,v$ are chosen to satisfy $u^2 - mnv^2 = \pm 1$. You can repeat this by putting $p=x,q=y$, and the catch is that the numbers coming out of this procedure are all the solutions.

This can be algebraically verified. These all appear in a family of identities related to the Pell equations, which were investigated by Euler.

In our case, we have $m=3,n=2,c=1$. So we have to find $u,v$ satisfying $u^2 - 6v^2 = \pm 1$.

Note that $-1$ is not a square mod $6$ (since the values are $0,1,4,9,16,25$, which leave remainders of $0,1,4,3,4,1$ mod $6$), hence $x^2 + 1 = 6y^2 \equiv 0 (6)$ cannot happen. Hence, we need to only find some positive solution of $u^2 - 6v^2 = 1$.

Then, we see that $u=5,v=2$ works out.

So given a solution $p,q$, the numbers $x = 49p + 40q$, $y = 49q+60p$ also satisfy the equation, with $n = \frac{2401p^2 - 1}{2} + 800q^2 + 1960pq$. For example, if $p=9,q=11$ (the initial solution), then $x= 881, y = 1079$, and these satisfy the equation, with $n = 388080$ being a multiple of $40$.

The question you asked was : when is $n$ a multiple of $40$. Well, note that if $2401p^2 - 1$ is a multiple of $80$, we are done, since the other terms are anyway all multiples of $40$. If we are proceeding inductively (base case done with $p=9,q=11,n=40$), then $40$ is a multiple of $\frac{p^2-1}{2}$, hence $80$ is a multiple of $p^2-1$, hence of $2401p^2 - 2401$, hence of $2401p^2 - 1$.

So by induction, we have that $40$ divides $n$ for all $n$ such that $2n+1,3n+1$ are squares.

Sister(brother,sister-in-law,etc.) results do exist. You can show that if $3n+1$ and $4n+1$ are squares, then $n$ is a multiple of $56$.

Definitely, this was a harder result than you(and $I$) imagined at first.