# Primes, pigeon holes, modular arithmetic

by HmBe
Tags: arithmetic, holes, modular, pigeon, primes
 P: 43 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.
 P: 1,258 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'.
 P: 43 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?
P: 181

## 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##.
 P: 43 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.

 Related Discussions Calculus & Beyond Homework 3 Calculus & Beyond Homework 2 Linear & Abstract Algebra 11 Calculus & Beyond Homework 2 General Math 17