## Primes, pigeon holes, modular arithmetic

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.
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 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'.
 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?

## Primes, pigeon holes, modular arithmetic

 Quote by HmBe 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?
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##.
 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) so (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.

 Similar discussions for: Primes, pigeon holes, modular arithmetic Thread Forum Replies Calculus & Beyond Homework 3 Calculus & Beyond Homework 2 Linear & Abstract Algebra 11 Calculus & Beyond Homework 2 General Math 17