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.

Let        3N + 1 = a²       and       4N + 1 = b²                   (1)

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

24n + 3k + 1 = a²          and       32n + 4k + 1 = b²

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   4a² - 3b² = 1      which can be written in the form of Pell’s Equation as:
                                    (2a)² - 3b² = 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 X² - 3b² = 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 = b² - a² = (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]² - a[r]²
= (14b[r-1] - b[r-2])² - (14a[r-1] - a[r-2])²
= 196(b[r-1]² - a[r-1]²) - 28(b[r-1]b[r-2] - a[r-1]a[r-2]) + (b[r-2]² - a[r-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