1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory: Pigeonhole Principle

  1. Jun 4, 2009 #1

    What have I done wrong here?

    Define f: A -> B

    (a,b) -> f(a,b) ≡ a + bc mod p

    Let A = {(a,b): a,b integers, 0≤a,b≤√p}

    B = {0,1,2,..,p-1}

    By pigeonhole principle there are distinct (a1,b1), (a2,b2) in A with f(a1,b1) = f(a2,b2).

    => a1+b1c ≡ a2+b2c mod p

    => (a1-a2) ≡ (b2-b1)c mod p

    => (a1-a2)2 ≡ (b2-b1)2c2 ≡ (b2-b1)2(-2) mod p

    Let a = a1 - a2 and b = b1-b2

    => a2 ≡ -2b2 mod p

    => a2+2b2 is a multiple of p

    As (a1,b1) ≠ (a2,b2)

    (a,b) ≠ (0,0) so a2+b2 > 0

    As 0≤a1≤√p and 0≤a2≤√p


    -√p < a1 - a2 < √p

    i.e. -√p < a < √p => a2 < p

    Similarly b2 < p => 2b2 < 2p

    => a2+2b2 < p + 2p = 3p

    So a2+2b2 is a multiple of p strictly between 0 and 3p

    So a2+2b2 = p

    OR a2+2b2 = 2p surely?
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted