Proving non-existence of integer solutions by reducing mod p

Poopsilon

Say I have the equation a^2 - 10b^2 = 2. So even though this is an equation in two variables and not one, I can still reduce mod P to a^2 = 2 (mod 5) and use the fact that it has no integer solutions mod 5 to conclude the original equation has no integer solutions, correct? Also does this only work modulo a prime, or can I do this modulo any natural number?

Hurkyl

Correct.

If there was an integer solution, that would also be a solution to the reduced-modulo-5 version.

And since there isn't a solution to the reduced-modulo-5 version, there isn't an integer solution.


Any natural number. But via the Chinese Remainder Theorem, you only really need to deal with prime powers -- e.g. reducing modulo 6 tells you the exact same information as considering reducing modulo 2 and reducing modulo 3 separately. For example, there's the theorem:

A (polynomial) equation doesn't have a solution modulo 6 if and only if at least one of the following is true:

• The equation doesn't have a solution modulo 2
• The equation doesn't have a solution modulo 3

Incidentally, it's fairly common that 4 and 8 are more useful to consider than 2.

Poopsilon

Ah yes, that makes sense, thanks =].

TylerH

Would someone mind showing the steps to reducing that? (a^2-10b^2=2 to a^2 = 2 mod 5)

Deveno

to indicate a number modulo 5, i will write [n] instead of n, so

[13] = [3].

a² - 10b² = 2 (given equation to solve)
[a² - 10b²] = [2] (reducing both sides modulo 5)
[a²] - [10b²] = [2] (because mod 5, [x+y] = [x] + [y])
[a]² - [10][b]² = [2] (because mod 5, [xy] = [x][y])
[a]² = [2] (because [10] = [0] mod 5)

one can explicitly compute [a]², for a = 0,1,2,3, and 4:

[0][0] = [0]
[1][1] = [1]
[2][2] = [4]
[3][3] = [9] = [4]
[4][4] = [16] = [1]

or, using an "old-fashioned method":

let a = a' + 5k
let b = b' + 5m

then a² - 10b² = (a' + 5k)² - 10(b' + 5m)²

= (a')² + 10a'k + 25k² - 10(b')² - 100b'm + 250m²

collecting all obvious multiples of 5, we get:

= a'² + 5(2a'k + 5k² - 2b'² - 20b'm - 50m²)

let n = 2a'k + 5k² - 2b'² - 20b'm - 50m², then we have:

a'² + 5n = 2,

that is: a² = a'² = 2 (mod 5).

TylerH

Oh, that makes sense. I actually did some of those, using the "old fashioned method," in my proof class, but only of a single variable. It was the second variable that threw me off. Thanks for the great explanation.