6
$\begingroup$

I'm trying to solve this problem using the pigeon hole principle. When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" (remainders of those 5 integers after being divided by 6) as there are "pigeons" I'm not sure how to go about solving this.

$\endgroup$
  • 3
    $\begingroup$ In general, don't force yourself to find pigeons and holes unless they pop up and greet you. =) $\endgroup$ – user21820 Jun 2 '15 at 10:06
10
$\begingroup$

HINT: If two of the numbers have the same remainder on division by $6$, their difference is divisible by $6$, so you can focus on the case in which all five integers have different remainders on division by $6$. Try to show that no matter which of the $6$ possible remainders is missing, you must have two numbers whose sum is a multiple of $6$.

$\endgroup$
  • $\begingroup$ Hi Brian, since you are the high scorer for this post could you please verify my proof for feasibility in this thread? Thank you, regards BLAZE $\endgroup$ – BLAZE Aug 29 '15 at 15:43
3
$\begingroup$

Simple.

As noted above if you have two different integers which give same remainder when divided by 6, then their difference will be divisible by 6.

Consider case of integers which all have diffrent reminders when divided by 6. There can only be 6 remainders then - 0,1,2,3,4,5 It is easy to notice that 1+5 = 6 which means that sum integers which give remainder of 1 and 5 when divided by 6 will be divisible by 6, and 2+4 = 6, which means that sum integers which give remainder of 2 and 4 when divided by 6 will be divisible by 6,

Since you need to choose 5 integers from the six possible types of remainders, you cannot elude both pairs. Therefore at least one sum will be divisible by 6 QED

$\endgroup$
2
$\begingroup$

$a\equiv b\pmod{\! m}$ denotes '$a,b$ leave same remainders when divided by $m$', or $m\mid a-b$ (see Modular Arithmetic).

$x^2\equiv \{0,1,3,4\}\pmod{\! 6}$ for any $x\in\Bbb Z$ ($\color{#0af}4$ possible remainders).

To see why, square $6k,\, 6k\pm 1,\, 6k\pm 2,\, 6k+ 3$.

Let your integers be $a_1,a_2,a_3,a_4,a_5$ ($\color{#0af}{4}+1$ integers).

By pigeonhole principle exist $i\neq j$ with $a_i^2\equiv a_j^2\pmod{\! 6}$, or i.e. $6\mid (a_i+a_j)(a_i-a_j)$

Assume for contr. that $6\nmid a_i+a_j, a_i-a_j$. Then WLOG $3\mid a_i+ a_j,\, 2\mid a_i- a_j$

But $a_i+ a_j=a_i- a_j+ 2a_j$, so $a_i+ a_j$ is even too and $6\mid a_i+ a_j$, contr assumption.

This used elementary methods, but it generalizes. $\,x^2\not\equiv 2$, $\,x^2\not\equiv -1$$\pmod{\! 6}$ is a consequence of quadratic reciprocity, because $3$ (a prime divisor of $6$) is of the form $8k+3$. So you did not need to square $0,\pm 1,\pm 2, 3$, which is neat since the $6$ could've been larger.

$\endgroup$
1
$\begingroup$

Hint: Instead of using the smallest non-negative remainders mod $6$, use remainders of smallest absolute value (e.g., $-2,-1,0,1,2,3$). What can you say about two numbers with the same absolute value?

$\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.