Exercise 4.5.1 (Revisited example 1)

Question

Given any $m$ integers none of which is a multiple of $m$, prove that two can be selected whose difference is a multiple of $m$.

Richard Ganaye · Accepted Answer

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

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

Note: I use the "pigeonhole principle" under the following form:

\medskip
{\it If $\varphi: A 	o B\ $ is injective (one-to-one), then $ \mathrm{Card}(A) \leq  \mathrm{Card}(B)$.
}

\medskip
or equivalently,

\medskip
{\it Let $\varphi: A 	o B\ $ be a map. If $ \mathrm{Card}(A) >  \mathrm{Card}(B)$, then $\varphi\ $ is not injective.
}

\begin{proof} 
Let $\mathscr{S}$ a set of $m$ integers, none of which is a multiple of $m$.

Consider the map 
$$\varphi
\left\{
\begin{array}{ccl}
\mathscr{S} & 	o & (\Z/m\Z) \setminus \{0\}\
a & \mapsto & [a]_m.
\end{array}
ight.
$$
This makes sense, because every $a \in \mathscr{S}$ is such that $[a]_m 
e 0$.

Since $m= \mathrm{Card}(\mathscr{S}) > \mathrm{Card}((\Z/m\Z) \setminus \{0\}) = m-1$, $\varphi$ is not injective, thus there are two distinct elements $a,b$ in $\mathscr{S}$ such that
$$a 
e b 	ext{ and } \varphi(a) = \varphi(b).$$
Then $[a]_m = [b]_m$, thus $a \equiv b \pmod m$, so  the difference $a -b$ is a multiple of $m$.
\end{proof}

Exercise 4.5.1 (Revisited example 1)

Answers

Comments

Exercise 4.5.1 (Revisited example 1)

Answers

Comments

Add answer