Exercise 2.3.25 ($\mathrm{Card} \{a \in ]\!]0, mk]\!] \mid \mathrm{gcd}(a,m) = 1\}$)

Question

If $m$ and $k$ are positive integers, prove that the number of positive integers $\leq mk$ that are prime to $m$ is $k\phi(m)$.

Richard Ganaye · Accepted Answer

\begin{proof} Write $I = ]\!]0, k m]\!]$, and $I_j = ]\!] jm, (j+1)m]\!]$, and also $A = \{a \in I \mid a \wedge m =1\}$, $A_j = \{a \in I_j \mid a\wedge m = 1\}$.
Then 
$$I = \bigcup_{j=0}^{k-1} I_j, \qquad A = \bigcup_{j=0}^{k-1} A_j\qquad 	ext{(disjoint unions).}$$
Therefore $N = |A| = \sum\limits_{j=0}^{k-1} |A_k| $ is the number of positive integers $a \leq mk$ that are prime to $m$.

By definition, 
$$\phi(m) = \mathrm{Card}\, \{a \in I_0 \mid a \wedge m = 1\} =  |A_0|.$$
We show first that $|A_j| = |A_0|$ for all $j$.

Let
$$
\chi
\left\{
\begin{array}{ccl}
A_0 & 	o & A_j\
a & \mapsto &a + jm.
\end{array}
ight.
\qquad
\xi
\left\{
\begin{array}{ccl}
A_j & 	o & A_0\
b& \mapsto &b - jm.
\end{array}
ight.
$$
If $a \in A_0$, then $0<a \leq m$, thus $jm<a + jm \leq (j+1)m$, so $\chi(a) = a+jm \in I_j$. Moreover, if $a \wedge m = 1$, thus $(a+jm) \wedge m = 1$. This shows that $\chi(a) = a + jm \in A_j$, so $\chi$ is well defined. Similarly, $\xi$ is well defined.

Moreover, for all $a$ in $A_0$, $(\xi \circ \chi)(a) = (a+jm) - jm = a$, so $\xi \circ \chi = 1_{A_0}$, and similarly $\chi \circ \xi = 1_{A_j}$. This proves that $\xi$ is bijective, thus
$$|A_0| = |A_j| \qquad j = 1,\ldots k-1.$$
Then
$$|A| = \sum\limits_{j=0}^{k-1} |A_k|  = k |A_0| = k \phi(m).$$
\end{proof}

Exercise 2.3.25 ($\mathrm{Card} \{a \in ]\!]0, mk]\!] \mid \mathrm{gcd}(a,m) = 1\}$)

Answers

Comments

Exercise 2.3.25 ($\mathrm{Card} \{a \in ]\!]0, mk]\!] \mid \mathrm{gcd}(a,m) = 1\}$)

Answers

Comments

Add answer