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.)
Solution Solution (Spoiler) | Comment 11 of 14 |
Let        3N + 1 = a2       and       4N + 1 = b2                   (1)

If N = 8n + k  where n and k are integers with k = 0..7,  then

24n + 3k + 1 = a2          and       32n + 4k + 1 = b2

Working modulo 8 ( in which squares can only have the value 0, 1, or 4)
            3k + 1 = 0, 1 or 4          giving    k = 0 or 1                      (mod 8)
            4k + 1 = 0, 1 or 4          giving    k = 0, 2, 4, 6 or 8          (mod 8)

k = 0 is the only common solution, giving N = 8n, so 8 is a factor of N

Equations (1) also give   4a2 - 3b2 = 1      which can be written in the form of Pellís Equation as:
                                    (2a)2 - 3b2 = 1

All possible values of 2a and b are therefore given by the numerators and denominators of appropriate convergents of sqrt(3) when written as a continued fraction. Convergents of sqrt(3) that satisfy X2 - 3b2 = 1 are as follows:
X/b :     2/1, 7/4, 26/15, 97/56, 362/209, 1351/780, 5042/2911, ....

Only alternate convergents provide the even numerator required to fit X = 2a, so we are left with the following possibilities:

a                      1,         13,        181,      2521,    35113,  489061, ......
b                      1,         15,        209,      2911,    40545,  564719, ......
b - a                 0,         2,         28,        390,      5432,    75658,  ......
b + a                2,         28,        390,      5432,    75658,  1053780, ......

From (1):          N = b2 - a2 = (b - a)(b + a),  so the last two lines above give the sequence of N values as:
            0*2,      2*28,   28*390,     390*5432,     5432*75658, 75658*1053780,
i.e. N = 0,         56,        10920,      2118480,       410974256,  79726887240, ...

Note that successive pairs share a common factor which is always divisible by 7 (i.e. 28, 5432, 1053780 ....) which means that 7 is a factor of all values of N. Both results together show that N is always divisible by 56.
________________________________________________________________
For more rigour....

The first four sequences shown above satisfy the same Pell recurrence relation:

viz.       u[r] = 14u[r - 1] - u[r - 2]

Thus N[r] = b[r]2 - a[r]2
= (14b[r-1] - b[r-2])2 - (14a[r-1] - a[r-2])2
= 196(b[r-1]2 - a[r-1]2) - 28(b[r-1]b[r-2] - a[r-1]a[r-2]) + (b[r-2]2 - a[r-2]2)

N[r] = 196N[r-1] - 28(b[r-1]b[r-2] - a[r-1]a[r-2]) + N[r-2]

Thus, if N[r-2] is divisible by 7 then N[r] will also be divisible by 7. Since 56 and 10920 are divisible by 7, by induction, all subsequent values of N will also be.

  Posted by Harry on 2010-04-04 00:18:59
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