Number Theory: Pigeonhole Principle

  • Thread starter Firepanda
  • Start date
  • #1
430
0
2exmt6c.jpg


What have I done wrong here?

Define f: A -> B

(a,b) -> f(a,b) ≡ a + bc mod p

Let A = {(a,b): a,b integers, 0≤a,b≤√p}

B = {0,1,2,..,p-1}

By pigeonhole principle there are distinct (a1,b1), (a2,b2) in A with f(a1,b1) = f(a2,b2).


=> a1+b1c ≡ a2+b2c mod p

=> (a1-a2) ≡ (b2-b1)c mod p

=> (a1-a2)2 ≡ (b2-b1)2c2 ≡ (b2-b1)2(-2) mod p

Let a = a1 - a2 and b = b1-b2

=> a2 ≡ -2b2 mod p

=> a2+2b2 is a multiple of p

As (a1,b1) ≠ (a2,b2)

(a,b) ≠ (0,0) so a2+b2 > 0

As 0≤a1≤√p and 0≤a2≤√p

then

-√p < a1 - a2 < √p

i.e. -√p < a < √p => a2 < p

Similarly b2 < p => 2b2 < 2p

=> a2+2b2 < p + 2p = 3p

So a2+2b2 is a multiple of p strictly between 0 and 3p

So a2+2b2 = p

OR a2+2b2 = 2p surely?
 

Answers and Replies

Related Threads on Number Theory: Pigeonhole Principle

Replies
2
Views
3K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
12
Views
11K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
17
Views
8K
  • Last Post
Replies
8
Views
824
  • Last Post
Replies
13
Views
10K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
Top