Results 1 to 2 of 2

Thread: prove

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    13

    prove

    if 3n+1 and 4n+1 are perfect squares then prove that n is divisible by 56.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Let

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

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

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

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

    It remains to show that $\displaystyle 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 $\displaystyle 1^2,\,2^2,\,\ldots,\,6^2$ in turn, observe that a perfect square cannot be congruent to 5 or 6 modulo 7. If $\displaystyle n\equiv1,3,4,6\,(\bmod\,7),$ then one of $\displaystyle 3n+1$ and $\displaystyle 4n+1$ would be congruent to 5 or 6 mod 7, so we can eliminate these. We are left with $\displaystyle n\equiv\pm2\,(\bmod\,7).$ In this case, one of $\displaystyle 3n+1$ and $\displaystyle 4n+1$ is divisible by 7, and so their product is divisible by 7 and must be a perfect square. Hence

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

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

Similar Math Help Forum Discussions

  1. Prove a/b and a/c then a/ (3b-7c)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 23rd 2010, 05:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 1st 2010, 09:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Feb 28th 2010, 05:44 AM
  4. Replies: 2
    Last Post: Aug 28th 2009, 02:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Nov 30th 2008, 01:24 PM

Search Tags


/mathhelpforum @mathhelpforum