Proving nonexistence of integer solutions by reducing mod pby Poopsilon Tags: integer, nonexistence, proving, reducing, solutions 

#1
Jan412, 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?




#2
Jan412, 05:46 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

If there was an integer solution, that would also be a solution to the reducedmodulo5 version. And since there isn't a solution to the reducedmodulo5 version, there isn't an integer solution. A (polynomial) equation doesn't have a solution modulo 6 if and only if at least one of the following is true:Incidentally, it's fairly common that 4 and 8 are more useful to consider than 2. 



#3
Jan412, 05:52 PM

P: 294

Ah yes, that makes sense, thanks =].




#4
Jan512, 12:23 AM

P: 737

Proving nonexistence of integer solutions by reducing mod p
Would someone mind showing the steps to reducing that? (a^210b^2=2 to a^2 = 2 mod 5)




#5
Jan512, 01:09 AM

Sci Advisor
P: 906

[13] = [3]. a^{2}  10b^{2} = 2 (given equation to solve) [a^{2}  10b^{2}] = [2] (reducing both sides modulo 5) [a^{2}]  [10b^{2}] = [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 "oldfashioned method": let a = a' + 5k let b = b' + 5m then a^{2}  10b^{2} = (a' + 5k)^{2}  10(b' + 5m)^{2} = (a')^{2} + 10a'k + 25k^{2}  10(b')^{2}  100b'm + 250m^{2} collecting all obvious multiples of 5, we get: = a'^{2} + 5(2a'k + 5k^{2}  2b'^{2}  20b'm  50m^{2}) let n = 2a'k + 5k^{2}  2b'^{2}  20b'm  50m^{2}, then we have: a'^{2} + 5n = 2, that is: a^{2} = a'^{2} = 2 (mod 5). 



#6
Jan612, 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 nonexistence, of unbiased estimators  Set Theory, Logic, Probability, Statistics  0  
proving that a^22b^24c^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 