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!

Homework Help: Primes, pigeon holes, modular arithmetic

  1. Nov 27, 2012 #1
    1. The problem statement, all variables and given/known data


    3. The attempt at a solution

    Don't have a clue how to even start this one, sorry.
  2. jcsd
  3. Nov 27, 2012 #2


    User Avatar
    Homework Helper

    I don't have much time to help with this one. Do you recall what the pigeonhole principle states?

    The n elements of a set get mapped to n-1 elements of another set, so no matter what, there are elements ai and aj which get mapped to the same element or the same 'hole'.
  4. Nov 27, 2012 #3
    Yeah I'm happy with the pigeon hole principle, although I can't quite see how it applies as a can be any natural number or 0, so surely the size of set A is infinite?
  5. Nov 27, 2012 #4
    That can't be meant, because the pigeonhole principle can only be used if ##\mathcal A## is finite. So ##0\leq a,b<\sqrt p## probable means ##(0\leq a<\sqrt p)## and ##(0\leq b<\sqrt p)##. This would give you ##|\mathcal A| < (\sqrt p+1)^2 = p+2\sqrt p+1##.

    Now I'd look at the function ##f(x,y)=x^2+2y^2## for all pairs ##(x,y)\in\mathcal A##.
  6. Nov 27, 2012 #5
    Ah right yeah I thought they were too separate inequalities which really messed me up. Quite simple now.

    Got down to this..

    (b-b')^2 + 2(a-a')^2 = pk

    for some integer k.

    I'm having a little struggle getting rid of the k (so to speak).

    a, b, a', b' are all < sqrt(p)


    (b-b')^2 + 2(a-a')^2 < 3p

    so k < 3

    if k = 1 we're fine, no worries.

    but what about the k = 2 case? I feel like I should return to the x^2 = -2 (mod p) to get some fact about p I could use...?

    Thanks for the help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook