Proving non-existence of integer solutions by reducing mod p


by Poopsilon
Tags: integer, nonexistence, proving, reducing, solutions
Poopsilon
Poopsilon is offline
#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
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Hurkyl
Hurkyl is offline
#2
Jan4-12, 05:46 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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
Poopsilon is offline
#3
Jan4-12, 05:52 PM
P: 294
Ah yes, that makes sense, thanks =].

TylerH
TylerH is offline
#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
Deveno is offline
#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
TylerH is offline
#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