Register to reply

Proving non-existence of integer solutions by reducing mod p

Share this thread:
Poopsilon
#1
Jan4-12, 05:01 PM
P: 294
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?
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
Hurkyl
#2
Jan4-12, 05:46 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Quote Quote by Poopsilon View Post
that it has no integer solutions mod 5 to conclude the original equation has no integer solutions, correct?
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.


Also does this only work modulo a prime, or can I do this modulo any natural number?
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
#3
Jan4-12, 05:52 PM
P: 294
Ah yes, that makes sense, thanks =].

TylerH
#4
Jan5-12, 12:23 AM
P: 737
Proving non-existence of integer solutions by reducing mod p

Would someone mind showing the steps to reducing that? (a^2-10b^2=2 to a^2 = 2 mod 5)
Deveno
#5
Jan5-12, 01:09 AM
Sci Advisor
P: 906
Quote Quote by TylerH View Post
Would someone mind showing the steps to reducing that? (a^2-10b^2=2 to a^2 = 2 mod 5)
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][b]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).
TylerH
#6
Jan6-12, 06:58 PM
P: 737
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.


Register to reply

Related Discussions
Find all integer solutions to ... Calculus & Beyond Homework 1
Proving the existence, or non-existence, of unbiased estimators Set Theory, Logic, Probability, Statistics 0
Proving that a^2-2b^2-4c^2 = 0 has no positive integer solutions Calculus & Beyond Homework 3
Integer solutions Linear & Abstract Algebra 15
Proving an integer is prime Introductory Physics Homework 5