Exercise 4.5.3* (There are two integers in $\mathscr{S}$ whose sum or whose difference is divisible by $m$)

Question

For any positive integers $k$ and $m > 1$, let $\mathscr{S}$ be a set of $k$ integers none of which is a multiple of $m$. If $k>m/2$, prove that there are two integers in $\mathscr{S}$ whose sum or whose difference is divisible by $m$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

(See the note in the solution of Problem 1.)
\begin{proof} 
Let $\overline{a}$ denote the class of $a \in \Z$ in $\Z/m\Z$.

Let$\mathscr{P}$ be the set of unordered pairs $\{x, -x\}$, where $x \in \Z/m\Z \setminus \{0\}$:
$$\mathscr{P} = \{\{x, -x\} \mid x \in \Z/m\Z \setminus \{0\}\}.$$
Note that if $m$ is even and $x = \overline{m/2}$, then $\{x , -x\}$ is the singleton $\{\overline{m/2}\}$. For instance, for $m = 6$, $\mathscr{P} = \{\{\overline{1}, - \overline{1}\},\{\overline{2}, - \overline{2}\},\{\overline{3}\}\}$.

Consider now the map 
$$\varphi
\left\{
\begin{array}{ccl}
\mathscr{S} & 	o & \mathscr{P}\
a & \mapsto &\{\overline{a}, -\overline{a}\}.
\end{array}
ight.
$$
Since $\mathscr{S}$ is a set of $k$ integers none of which is a multiple of $m$, then for all $a \in \mathscr{S}$, $\overline{a} \in \Z/m\Z \setminus\{0\}$, so $\{\overline{a}, -\overline{a}\} \in \mathscr{P}$.
\begin{itemize}
\item If $m$ is odd, then
$$\mathscr{P} =\left \{\{\overline{1}, - \overline{1}\},\{\overline{2}, - \overline{2}\},\ldots, \left\{\overline{\frac{m-1}{2}}, - \overline{\frac{m-1}{2}}ight\}ight\},$$
thus 
$\mathrm{Card}(\mathscr{P}) = (m-1)/2$.
\item If $m$ is even, then 
$$\mathscr{P} =\left \{\{\overline{1}, - \overline{1}\},\{\overline{2}, - \overline{2}\},\ldots, \left\{\overline{\frac{m}{2} - 1} , - \left(\overline{\frac{m}{2}+1}ight)ight\},\left\{ \overline{\frac{m}{2}} ight\}ight\},$$
thus $\mathrm{Card}(\mathscr{P}) = m/2$.
\end{itemize}
In both cases,
$$\mathrm{Card}(\mathscr{P})  \leq \frac{m}{2} < k = \mathrm{Card}(\mathscr{S}).$$
Therefore $\varphi$ cannot be injective, so there are two elements $a, b$ in $\mathscr{S}$ such that
$$a 
e b 	ext{ and } \{\overline{a}, -\overline{a}\} = \{\overline{b}, -\overline{b}\}.$$
Since $\overline{a}  \in  \{\overline{b}, -\overline{b}\}$, we obtain 
$$\overline{a} = \overline{b} 	ext{ or } \overline{a} = -\overline{b},$$
thus $m \mid a-b$ or $m \mid a + b$.

If $\mathscr{S}$ is a set of $k > m/2$ integers none of which is a multiple of $m$, then there are two integers in $\mathscr{S}$ whose sum or whose difference is divisible by $m$.

\end{proof}

Exercise 4.5.3* (There are two integers in $\mathscr{S}$ whose sum or whose difference is divisible by $m$)

Answers

Comments

Exercise 4.5.3* (There are two integers in $\mathscr{S}$ whose sum or whose difference is divisible by $m$)

Answers

Comments

Add answer