Prove that if $2n+1$ and $3n+1$ are both perfect squares then $40|n$.
First, I took
$$2n+1 \equiv x^2 \equiv 0, 1 \pmod 4$$
which showed that $n$ was even.
Now,
$$3n + 1 \equiv y^2 \equiv 0, 1, 4 \pmod 8$$ But since $n$ is even, we get that $8|n$.
So, now any square $\equiv 0, 1, 4, 5, 6, 9 \pmod{10}$. So, I tested $2n+1$ and $3n+1$ for all numbers from 0 to 9. For only two, 0 and 5, were both of them ending with the residues above mentioned. So, I finally proved that $5|n$.
So, $40|n$.
Is my proof correct?
Also, my proof is too roundabout and lengthy. I had to write many programs to take different modulos. Can anyone suggest a more elegant proof especially for the second part when I have to show that $5|n$?
Thanks.
Best Answer
You basically have the idea - note that the quadratic residues $\mod{5},\mod{8}$ are both $\{0,1,4\}$, and you need to find $n$ such that $(2n+1),(3n+1)$ are both amongst these for each modulus.
Checking cases gives that $(2n+1)\mod{5}$ and $(3n+1)\mod{5}$ are both in $\{0,1,4\}$ only when $n=0\mod{5}$, and the same calculations $\mod{8}$ tell you that $n$ must be $0\mod{8}$.
Thus, $n$ is a multiple of $5$ and $8$, which are coprime, hence $n$ is a multiple of $5\times8=40$.