1
$\begingroup$

I have a homework question that asks the following:

How many order pair of integers (a,b) are needed to guarantee that there are two ordered pairs (a1,b1) and (a2,b2)such that such that a1 mod 5= a2 and b1 mod 5= b2?

I know that this is a pigeonhole principle question and I searched for the question online, but I didn't quite understand the answer. My question is: what does it mean for integers such as k and q, such that k mod 5= q mod 5? And can someone explain how to solve this? I just want to understand; I don't care about getting the answer us much as I care about learning how to do this.

$\endgroup$
  • 3
    $\begingroup$ It means that $k-q$ is divisible by $5$, or equivalently, $k$ and $q$ have the same remainder when divided by $5$. $\endgroup$ – Minus One-Twelfth Apr 6 '19 at 19:51
  • $\begingroup$ For a nontrivial application of such a pigeonhole technique see how not to reinvent the wheel (cycle) when studying the Fibonacci sequence $\bmod 7$ $\ \ $ $\endgroup$ – Bill Dubuque Apr 6 '19 at 20:38
1
$\begingroup$

$$y\bmod m \equiv b \bmod m\implies y=mx+b$$ where y,m,x,b are all integers. we typically can avoid caring about x in basic modular arithmetic( or at all for most people).

The order of pairs matters, so there are 25 possible pairs:$$\begin{array}{ccccc}(0,0)&(0,1)&(0,2)&(0,3)&(0,4)\\(1,0)&(1,1)&(1,2)&(1,3)&(1,4)\\(2,0)&(2,1)&(2,2)&(2,3)&(2,4)\\(3,0)&(3,1)&(3,2)&(3,3)&(3,4)\\(4,0)&(4,1)&(4,2)&(4,3)&(4,4)\end{array}$$ This means, if we have 26 ordered pairs of integers, we are forced into overlap.

You may be confused why the answer isn't 16. That's because we care about order, if not, only 15 pairings exist, and 16 would then be the answer.

$\endgroup$
  • $\begingroup$ Thank you so much, makes sense!! $\endgroup$ – Nev Apr 7 '19 at 3:14
  • $\begingroup$ ironically because you can order pairs, this only takes 6 distinct numbers ( which have ordered 30 pairs of distinct numbers) so 1,2,3,4,5,6 any number paired with both 1 and 6, leads to overlap if all orderings are considered. $\endgroup$ – Roddy MacPhee Apr 7 '19 at 12:38
1
$\begingroup$

The question is asking how many different ordered pairs of $mod 5$ exists.

Since one number $mod 5$ can only have 5 results, the number of total pairs should be $5^2=25$.

Now the answer is trivial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.