Homework Help: Primes, pigeon holes, modular arithmetic

1. Nov 27, 2012

HmBe

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. Nov 27, 2012

Zondrina

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'.

3. Nov 27, 2012

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?

4. Nov 27, 2012

Michael Redei

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$.

5. Nov 27, 2012

HmBe

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.