Results 1 to 3 of 3

Math Help - Dirichlet Principle

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    17

    Dirichlet Principle

    How many pairs of integers (a,b) are necessary to make sure that for two of them, say ({a_1},{b_1}) and ({a_2},{b_2}) it is the case that {a_1} mod 5 = {a_2} mod 5 and {b_1} mod 5 = {b_2} mod 5?
    Last edited by seit; June 6th 2011 at 09:16 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    OK, using Google Translate, I guess the question is the following.

    How many pairs of integers (a, b) are necessary to make sure that for two of them, say (a_1,b_1) and (a_2,b_2) it is the case that a_1\equiv a_2\pmod{5} and b_1\equiv b_2\pmod{5}?

    Dirichlet (or Pigeonhole) Principle talks about pigeons and holes. I suggest considering pairs (a, b) where a,b\in\mathbb{Z} as pigeons and pairs (x, y) where x,y\in\mathbb{Z} and 0\le x, y < 5 as holes. A pigeon (a, b) is in the hole (x, y) if a\equiv x\pmod{5} and b\equiv y\pmod{5}. You have to check that having two pigeons in one hole corresponds to the condition in the problem statement, as well as to find out the number of holes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by seit View Post
    How many pairs of integers (a,b) are necessary to make sure that for two of them, say ({a_1},{b_1}) and ({a_2},{b_2}) it is the case that {a_1} mod 5 = {a_2} mod 5 and {b_1} mod 5 = {b_2} mod 5?
    Let \mathcal{L}=\{0,1,2,3,4\} residues mod 5.
    Use the pairs in \mathcal{L}\times\mathcal{L} to label 'pigeon-holes".
    So we would put the pair (15,-3) into the hole with label (0,2).

    How is this question finished?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Dirichlet characters
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 9th 2010, 09:32 AM
  2. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 08:31 AM
  3. Dirichlet
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 8th 2010, 10:27 PM
  4. Momentum Principle and Energy Principle Problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 4th 2009, 01:42 AM
  5. Dirichlet
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 7th 2008, 04:02 PM

Search Tags


/mathhelpforum @mathhelpforum