Gauss Problem 4 A positive integer n is such that number 2n plus 1 and 3n plus 1 are perfect squares. Prove that n is divisible by 8?

Answer 1

This proof uses modular arithmetic. If you are unfamiliar with this, the basic principle is that if we have integers a, b, and a nonzero integer c, then a = b (mod c) if a/c and b/c have the same remainder. For example, 8 = 2 (mod 3), because 8/3 and 2/3 have remainder 2.

One property of this relation is that for any integer x and for any nonzero integer y, there exists a unique integer z such that x = z (mod y) and z is between 0 and y inclusive. The upshot of this is that, in most cases, if you know how your relation behaves with all integers between 0 and y, you know how it behaves for all integers.

Consider the quadratic residues mod 8; that is, find all possible values of c if 0 <= c < 8 and x2 = c (mod 8) for some integer x. Plugging in all values from 0 to 7 for x, the only possible values of c are 0, 1, and 4.

Now consider 2n + 1 (mod 8). We know that 2n + 1 is a perfect square, so we know that 2n + 1 = 0, 1, or 4 (mod 8). Thus, 2n = -1, 0, or 3 (mod 8). Since 2n is an even number, and 8 is an even number, 2n can only be congruent to an even number mod 8. Therefore, 2n = 0 (mod 8), and therefore n = 0 (mod 4).

Finally, consider 3n + 1 (mod 8). As before, we note that 3n = -1, 0, or 3 (mod 8). We know that n = 0 (mod 4), so we know that n = 4k for some integer k. Therefore, n is even. Since 8 is also even, we know that n = 0 (mod 8). Therefore, n is divisible by 8. QED.