Register to reply 
Primes, pigeon holes, modular arithmetic 
Share this thread: 
#1
Nov2712, 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. 


#2
Nov2712, 09:41 AM

P: 1,591

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


#3
Nov2712, 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?



#4
Nov2712, 10:14 AM

P: 181

Primes, pigeon holes, modular arithmetic
Now I'd look at the function ##f(x,y)=x^2+2y^2## for all pairs ##(x,y)\in\mathcal A##. 


#5
Nov2712, 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.. (bb')^2 + 2(aa')^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 (bb')^2 + 2(aa')^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 