# Proving non-existence of integer solutions by reducing mod p

1. Jan 4, 2012

### 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?

2. Jan 4, 2012

### Hurkyl

Staff Emeritus
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.

3. Jan 4, 2012

### Poopsilon

Ah yes, that makes sense, thanks =].

4. Jan 5, 2012

### TylerH

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

5. Jan 5, 2012

### Deveno

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

[13] = [3].

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

one can explicitly compute [a]2, 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 a2 - 10b2 = (a' + 5k)2 - 10(b' + 5m)2

= (a')2 + 10a'k + 25k2 - 10(b')2 - 100b'm + 250m2

collecting all obvious multiples of 5, we get:

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

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

a'2 + 5n = 2,

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

6. Jan 6, 2012

### 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.