Exercise 2.2.2 (First examples, part 2.)

Question

Denoting the number of solutions of $f(x) \equiv k \pmod m$ by $N(k)$, prove that $\sum_{k=1}^m N(k) = m$.

Richard Ganaye · Accepted Answer

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

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

\begin{proof}
Consider, for every $k$, $1\leq k \leq m$,
$$A_k = \{u \in \Z/m\Z \mid f(u) = [k]_m\}.$$
Then by definition, $N(k) = |A_k|$.

Since $\Z/m\Z = \{[1]_k,\ldots,[m]_k\}$,  $(A_k)_{k \in [\![1, m]\!]}$ is a partition of $\Z/m\Z$
(if $f : E 	o F$, $(f^{-1}(\{k\}))_{k \in F}$ is always a partition of $E$). Therefore
$$ m  = |\Z/m\Z| = \sum_{k=1}^m |A_k| = \sum_{k=1}^m N(k).$$
\end{proof}

Exercise 2.2.2 (First examples, part 2.)

Answers

Comments

Exercise 2.2.2 (First examples, part 2.)

Answers

Comments

Add answer