# Math Help - prove

1. ## prove

if 3n+1 and 4n+1 are perfect squares then prove that n is divisible by 56.

2. Let

$3n+1\ =\ a^2$

$4n+1\ =\ b^2$

The second equation implies $b$ is odd. Hence $n$ is even (if $n$ were odd, then $4n+1\equiv5\,(\bmod\,8)$ which is not possible because perfect squares cannot be congruent to 5 modulo 8). So $a$ is odd.

Subtracting the equations gives $n\,=\,b^2-a^2\,=\,(b-a)(b+a).$ Since $b-a$ and $b+a$ are both even, $n$ is divisible by 4. In fact, one of $b-a$ and $b+a$ must be divisible by 4. For, suppose $b-a$ is not divisible by 4. Then $b-a\equiv2\,(\bmod\,4)$ and $2a\equiv2\,(\bmod\,4)$ (since $a$ is odd) and so $b+a=(b-a)+2a\equiv0\,(\bmod\,4).$ Hence $n$ is divisible by 8.

It remains to show that $n$ is divisible by 7. There may be a simple way but the only way I can do it is by contradiction. Now, by checking $1^2,\,2^2,\,\ldots,\,6^2$ in turn, observe that a perfect square cannot be congruent to 5 or 6 modulo 7. If $n\equiv1,3,4,6\,(\bmod\,7),$ then one of $3n+1$ and $4n+1$ would be congruent to 5 or 6 mod 7, so we can eliminate these. We are left with $n\equiv\pm2\,(\bmod\,7).$ In this case, one of $3n+1$ and $4n+1$ is divisible by 7, and so their product is divisible by 7 and must be a perfect square. Hence

$12n^2+7n+1-m^2\ =\ 0$

for some integer $m$ divisible by 7. The discriminant of this quadratic in $n$ must be a perfect square; this is $49-48(1-m^2)=48m^2-1.$ But if $m$ is divisible by 7, then $48m^2-1\equiv6\,(\bmod\,7)$ which is impossible. Thus $n$ must be divisible by 7.