All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Perfect Square To Divisibility By 56 (Posted on 2010-04-01) Difficulty: 4 of 5
N is a positive integer such that each of 3*N + 1 and 4*N + 1 is a perfect square.

Is N always divisible by 56?

If so, prove it. Otherwise, give a counterexample.

See The Solution Submitted by K Sengupta    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips Modular arithmetic | Comment 8 of 14 |

First assume N is odd: N=2x+1.  Then 4N+1=8x+5.  Perfect squares mod 5 are 0, 1, or 4.  Therefore N is even.

Now assume N is singly even (even but not multiple of 4): N=4x+2.  Then 3N+1=12x+7.  Perfect squares mod 12 are 0, 1, 4, or 9.  Therefore N is a multiple of 4.

Now go one power higher, assume N=8x+4 (mult 4 but not mult 8): Then 3N+1=24N+13.  Perfect squares mod 24 are 0, 1, 4, 9, 12, or 16.  Therefore N is a multiple of 8.

Now try forms of 7: N=7x+k for k=0 to 6.  Then 3N+1=21x+{1, 4, 7, 10, 13, 16, or 19}.  Perfect squares mod 21 are 0, 1, 4, 7, 9, 15, 16, or 18.  There are four matches: 1, 4, 7, 16 corresponding to k=0, 1, 2, 4.

Now try those four forms (7x, 7x+1, 7x+2, 7x+4) with 4N+1=28x+{1, 5, 9, or 17}.  Perfect squares mod 24 are 0, 1, 4, 9, 10, 16, 21, or 25.  There are two matches: 1 and 9 corresponding to k=0 or 2.

At this point N is a multiple of 8 and either a multiple of 7 or two more than a multiple of 7, aka N=56x or 56x+2.

Also, the sequence of possible N is Sloane A059989.  The values form a multiplicative recursion of t[n] = t[n-1]*(t[n-1]-56)/t[n-2] 


  Posted by Brian Smith on 2010-04-02 23:05:04
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information