Proving non-existence of integer solutions by reducing mod p

  1. 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. jcsd
  3. Hurkyl

    Hurkyl 16,089
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. Ah yes, that makes sense, thanks =].
     
  5. Would someone mind showing the steps to reducing that? (a^2-10b^2=2 to a^2 = 2 mod 5)
     
  6. Deveno

    Deveno 906
    Science Advisor

    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).
     
  7. 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.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?