Primes, pigeon holes, modular arithmetic

[HmBe]

Homework Statement

The Attempt at a Solution

Don't have a clue how to even start this one, sorry.

 

[STEMucator]

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 a_i and a_j which get mapped to the same element or the same 'hole'.

 

[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?

 

[Michael Redei]

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

 

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