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.

(In reply to

Modular arithmetic by Brian Smith)

Brian:

This is great work, but you got stuck, I think, because of a mistake on your last step:

"At this point N is a multiple of 8 and either a multiple of 7 or two more than a multiple of 7". So far you are OK.

But then you err with the statement ", aka N=56x or 56x+2". Well 56x + 2 is not a multiple of 8.

I don't know how to finish it up, though.

N = 56x or 8(7x+2)*y; aka 56x or (56xy+16y).

Assume N= 56xy + 16y, but is not of the form 56z

Then 3N + 1 = 168xy + 48y +1

4N + 1 = 224xy + 64y + 1

Mod 7, 168xy + 48y + 1 = 1-y, must equal 0,1,2, or 4

so y must equal 0,6,5, or 3 mod 7

Mod 7, 224xy + 64y + 1 = 1+ y, must equal 0,1,2 or 4,

so y must equal 6, 0, 1, or 3 mod 7

So, y must equal 0, 3 or 6 mod 7

0 just defaults to the previous form (56x), so assume y = 3 or 6 mod 7.

Then N = 8*(7x+2)*(7z+3) or 8*(7x+2)*(7z+6)

And where do we go from here?