Register to reply

Primes, pigeon holes, modular arithmetic

by HmBe
Tags: arithmetic, holes, modular, pigeon, primes
Share this thread:
HmBe
#1
Nov27-12, 09:30 AM
P: 45
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.
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
Zondrina
#2
Nov27-12, 09:41 AM
P: 1,460
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'.
HmBe
#3
Nov27-12, 09:53 AM
P: 45
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
#4
Nov27-12, 10:14 AM
P: 181
Primes, pigeon holes, modular arithmetic

Quote Quote by HmBe View Post
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
#5
Nov27-12, 08:38 PM
P: 45
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.


Register to reply

Related Discussions
Modular arithmetic Calculus & Beyond Homework 3
Modular arithmetic Calculus & Beyond Homework 2
Modular arithmetic Linear & Abstract Algebra 11
Modular Arithmetic Calculus & Beyond Homework 2
Help: modular arithmetic General Math 17