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.
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]
Modular arithmetic
