prove

**newtoinequality** · July 14th 2009, 05:14 AM

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

**TheAbstractionist** · July 14th 2009, 10:15 AM

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.

Thread: prove

LinkBack

Thread Tools

Display

prove

Similar Math Help Forum Discussions

Prove a/b and a/c then a/ (3b-7c)

prove,,,

Prove |w + z| <= |w| +|z|

prove that if sequence (an) converges, use def of limit of sequence to prove...

How to prove that n^2 + n + 2 is even??

Search Tags