Results 1 to 2 of 2

Math Help - 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

    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.
    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: March 23rd 2010, 06:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 10:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 28th 2010, 06:44 AM
  4. Replies: 2
    Last Post: August 28th 2009, 03:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 30th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum