A positive integer n is such that numbers 2n+1 and 3n+1 are perfect squares. Prove that n is divisible by 8.
thanks
I sort of "cheated" by running a quick computer program.
in the first 1 million values of n
I found only 3 values of n that satisfied your condition.
they were 40, 3960, and 388080
All 3 are divisible by 8
I can't think of a "mathematical" way to do you question.
Modulo 8, a square can only be 0, 1 or 4:
0^2 = 0
1^2 = 1
2^2 = 4
3^2 = 1
4^2 = 0
The squares of 5, 6 and 7 are the same as the squares of 3, 2 and 1.
Since 2n + 1 is odd and is a square, it must be 1 modulo 8. So, Mod 8 we have:
2 n + 1 = 1 ------>
2 n = 0
So, we know that n is a multiple of 4, so we can be sure that n is even. But this means that 3n + 1 must be odd. Because 3 n + 1 is a square, it follows that 3 n + 1 Modulo 8 equals 1. So, Modulo 8 we have:
2 n + 1 = 1
3 n + 1 = 1
Subtracting gives (Modulo 8):
n = 0
So, n is a multiple of 8.
To prove that n is divisible by 8, we will use contradiction. We assume that n is not divisible by 8 and show that this leads to a contradiction.
Let's express 2n+1 and 3n+1 as perfect squares. We can write:
2n + 1 = x^2 ...(1)
3n + 1 = y^2 ...(2)
where x and y are positive integers.
From equation (1), we can rewrite n as:
n = (x^2 - 1)/2
Since n is an integer, x^2 - 1 must be even. This implies that x^2 is odd, and hence x is also odd (as the square of an odd number is always odd).
Substituting this value of n into equation (2):
3((x^2 - 1)/2) + 1 = y^2
Simplifying, we get:
3x^2/2 - 3/2 + 1 = y^2
3x^2 - 3 + 2 = 2y^2
3x^2 + 2 = 2y^2 ...(3)
Now, let's consider the equation modulo 4:
3x^2 + 2 ≡ 2y^2 (mod 4)
Since x is odd, x^2 ≡ 1 (mod 4)
Substituting this into equation (3):
3(1) + 2 ≡ 2y^2 (mod 4)
5 ≡ 2y^2 (mod 4)
This implies that 2y^2 is congruent to either 1 or 5 modulo 4.
However, considering the possible remainders when squaring even integers modulo 4, we find that 2y^2 can only be congruent to 0 or 2 modulo 4 due to the fact that y must be odd.
Hence, we have reached a contradiction. Our assumption that n is not divisible by 8 is incorrect.
Therefore, we can conclude that if 2n+1 and 3n+1 are perfect squares, n must be divisible by 8.
To prove that n is divisible by 8, we need to show that it leaves a remainder of 0 when divided by 8.
Let's start by assuming that 2n+1 and 3n+1 are perfect squares. We can express them as follows:
2n+1 = x^2 (1)
3n+1 = y^2 (2)
where x and y are positive integers.
From equation (1), we can rearrange it as follows:
2n = x^2 - 1
n = (x^2 - 1)/2
We can observe that n is an integer if x^2 is an odd number (because the difference of two odd numbers is always an even number). Therefore, x must be an odd number, which we can express as x = 2k + 1, where k is a positive integer.
Plugging this value of x into equation (1), we have:
n = ((2k + 1)^2 - 1)/2
n = (4k^2 + 4k + 1 - 1)/2
n = (4k^2 + 4k)/2
n = 2k^2 + 2k
Now, let's consider equation (2):
3n+1 = y^2
Substituting the value of n from the previous equation, we have:
3(2k^2 + 2k) + 1 = y^2
6k^2 + 6k + 1 = y^2
We can notice that the left side of the equation is congruent to 1 modulo 3. Therefore, y^2 must also be congruent to 1 modulo 3, which means y must be an odd number. We can express it as y = 2m + 1, where m is a positive integer.
Substituting this value of y back into the equation, we get:
6k^2 + 6k + 1 = (2m + 1)^2
6k^2 + 6k + 1 = 4m^2 + 4m + 1
6k^2 + 6k = 4m^2 + 4m
Now, let's consider the parity of k. If k is a positive even integer, we can express it as k = 2p, where p is a positive integer.
Substituting this value of k into the equation, we have:
6(2p)^2 + 6(2p) = 4m^2 + 4m
24p^2 + 12p = 4m^2 + 4m
6p^2 + 3p = m^2 + m
Now, let's consider the left side of the equation. Since p is an even number, we can express it as p = 2q, where q is a positive integer.
Substituting this value of p into the equation, we get:
6(2q)^2 + 3(2q) = m^2 + m
24q^2 + 6q = m^2 + m
We can observe that the left side of the equation is congruent to 0 modulo 3. Therefore, m^2 + m must also be congruent to 0 modulo 3, which means m must be an even number.
Substituting the value of m = 2r, where r is a positive integer, back into the equation, we have:
24q^2 + 6q = 4(2r)^2 + 4(2r)
24q^2 + 6q = 16r^2 + 8r
12q^2 + 3q = 8r^2 + 4r
Now, let's consider the parity of q. If q is an even number, we can express it as q = 2s, where s is a positive integer.
Substituting this value of q into the equation:
12(2s)^2 + 3(2s) = 8r^2 + 4r
48s^2 + 6s = 8r^2 + 4r
We can observe that the left side of the equation is congruent to 0 modulo 3. Therefore, the right side of the equation must also be congruent to 0 modulo 3. This can only happen if r is an even number.
So, we have shown that k, m, and r are all even numbers: k = 2p, m = 2r, and q = 2s.
Substituting these values back into the expressions for n and x, we have:
n = 2k^2 + 2k = 2(2p)^2 + 2(2p) = 8p^2 + 4p
We can see that n is indeed divisible by 8, which completes the proof.
Therefore, if 2n+1 and 3n+1 are perfect squares, n must be divisible by 8.