Exercise 2.3.47* (Number of integers $a,\ 1 \leq a \leq m,$ such that $(f(a),m) = 1$)

Proof.

a)

Let $f\in \mathbb{Z}[x]$. Consider, for any integer $m>1$, the set $$A_m=\{u\in \mathbb{Z}∕\mathit{m\mathbb{Z}}\mid f(u)\in {(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}\}$$

Then, for all $a\in \mathbb{Z}$,

$${[a]}_m\in A_m⟺f(a)\wedge m=1.$$

By definition of ${\varphi }_f(m)$, ${\varphi }_f(m)=|A_m|$.

Assume that $m\wedge n=1$. Consider the map

$$\chi \{\begin{array}{ccc}\hfill A_{\mathit{mn}}\hfill & \hfill \to \hfill & A_m\times A_n\hfill \\ \hfill [a{\text{]}}_{\mathit{mn}}\hfill & \hfill \mapsto \hfill & ([a{\text{]}}_m,[a{\text{]}}_n)\hfill \end{array}$$

We show first that $\chi$ is well defined.

• If $a\equiv b(\mathit{mod}\mathit{mn})$, then $a\equiv b(\mathit{mod}n)$ and $a\equiv b(\mathit{mod}n)$, so that $({[a]}_m,{[a]}_n)$ does not depend of the choice of the representative $a$ in the class $[a{\text{]}}_{\mathit{mn}}$.
• If ${[a]}_m\in A_{\mathit{mn}}$, then $a\wedge \mathit{mn}=1$. Therefore $a\wedge m=1$ and $a\wedge n=1$, so $({[a]}_m,{[a]}_n)\in A_m\times A_n$.

Now we show that $\chi$ is bijective.

• If $\chi (u)=\chi (v)$, where $u={[a]}_{\mathit{mn}},v={[b]}_{\mathit{mn}}$, then $({[a]}_m,{[a]}_n)=({[b]}_m,{[b]}_n)$. Therefore

  $$a\equiv b(\mathit{mod}m),a\equiv b(modn).$$

  Since $m\wedge n=1$, $a\equiv b(\mathit{mod}\mathit{mn})$, so ${[a]}_{\mathit{mn}}={[b]}_{\mathit{mn}}$, and $u=v$. This shows that $f$ is injective (one-to-one).

• Let $(u,v)$ be any element of $A_m\times A_n$. There are integers $a,b\in \mathbb{Z}$ such that $u={[a]}_m,v={[b]}_n$, where $a\wedge m=1$ and $b\wedge n=1$.

  Since $m\wedge n=1$, the Chinese Remainder Theorem shows that there exists some integer x such that

  $$\{\begin{array}{c}x\equiv a(\mathit{mod}m),\hfill \\ x\equiv b(\mathit{mod}n).\hfill \end{array}$$

  So $x=a+\mathit{km}$ for some integer $k$, thus $x\wedge m=(a+\mathit{km})\wedge m=a\wedge m=1$. Similarly $x\wedge n=1$. Since $x\wedge m=1$ and $x\wedge n=1$, then $x\wedge \mathit{mn}=1$, so ${[x]}_{\mathit{mn}}\in A_{\mathit{mn}}$. Moreover ${[x]}_m={[a]}_m=u$, and ${[x]}_n={[b]}_n=v$, thus $\chi ({[x]}_{\mathit{mn}})=({[a]}_m,{[b]}_n)=(u,v)$. This shows that $\chi$ is surjective (onto).

  We conclude that $\chi$ is a bijection. Therefore

  $$|A_{\mathit{mn}}|=|A_m|\cdot |A_n|.$$

  This proves

  $${\varphi }_f(\mathit{mn})={\varphi }_f(m){\varphi }_f(n),\text{ if }m\wedge n=1.$$

b)

Suppose that $\alpha \ge 1$. Consider the map $$\xi \{\begin{array}{ccc}\hfill A_{p^{\alpha }}\hfill & \hfill \to \hfill & A_p\hfill \\ \hfill [a{\text{]}}_{p^{\alpha }}\hfill & \hfill \mapsto \hfill & [a{\text{]}}_p.\hfill \end{array}$$

• The map $\xi$ is well defined, because $a\equiv b(\mathit{mod}{p}^{\alpha })\Rightarrow a\equiv b(modp)$.
• If $u={[a]}_{p^{\alpha }}\in A_{p^{\alpha }}$, then $a\wedge p^{\alpha }=1$. Therefore $a\wedge p=1$, so $\xi (v)={[a]}_p\in A_p$.

If $v={[b]}_p\in A_p$, we count the number of antecedents of $v$ for $\chi$, i.e. we estimate

$$|{\xi }^{-1}(v)|=\mathrm{Card}\{u={[a]}_{p^{\alpha }}\in A_{p^{\alpha }}:\xi (u)={[a]}_p=v={[b]}_p\}.$$

We can take the representative $b$ of $v$ in the set $[[0,p-1]]$, and $a\in [[0,p^{\alpha }-1]]$, which is a complete system of residues modulo $p^{\alpha }$. Then $a=b+\mathit{kp}$, where $0\le k<p^{\alpha -1}$ are the solutions $a\in [[0,p^{\alpha }-1]]$ of $\xi ({[a]}_p)={[b]}_p$. Therefore

$$|{\xi }^{-1}(v)|=p^{\alpha -1},$$

for all $v={[b]}_p\in A_p$. This shows (principle of the shepherd, as said in France “principe du berger") that

$$|A_{p^{\alpha }}|=p^{\alpha -1}|A_p|,$$

that is

$${\varphi }_f(p^{\alpha })=p^{\alpha -1}{\varphi }_f(p).$$

c)

If $p$ is a prime number, the complementary of $A_p$ in $\mathbb{Z}∕\mathit{p\mathbb{Z}}$ is $$\begin{array}{llll}\hfill \mathbb{Z}∕\mathit{p\mathbb{Z}}\setminus A_p& =\{{[a]}_p\in \mathbb{Z}∕\mathit{p\mathbb{Z}}\mid f(a)\wedge p\ne 1\}& \hfill & \\ \hfill & =\{{[a]}_p\in \mathbb{Z}∕\mathit{p\mathbb{Z}}\mid p\mid f(a)\}& \hfill & \\ \hfill & =\{{[a]}_p\in \mathbb{Z}∕\mathit{p\mathbb{Z}}\mid f(a)\equiv 0(\mathit{mod}p)\}& \hfill & \\ \hfill & =\{u\in \mathbb{Z}∕\mathit{p\mathbb{Z}}\mid f(u)=0\}.& \hfill & \end{array}$$

Therefore $|\mathbb{Z}∕\mathit{p\mathbb{Z}}\setminus A_p|=N(p)$, by definition of $N(p)$. Thus $|A_p|=|\mathbb{Z}∕\mathit{p\mathbb{Z}}|-N(p)=p-N(p)$, so

$${\varphi }_f(p)=p-N(p).$$

d)

Write $n=p_1^{a_1}\cdots p_k^{a_k}$ the decomposition in prime factors of some integer $n>1$, where $a_i>0$.

By part (a),

$${\varphi }_f(n)=\underset{i=0}{\overset{k}{\prod }}{\varphi }_f(p_i^{a_i}).$$

By parts (b) and (c),

$$\begin{array}{llll}\hfill {\varphi }_f(p_i^{a_i})& =p_i^{a_i-1}{\varphi }_f(p_i)& \hfill & \\ \hfill & =p_i^{a_i-1}(p_i-N(p_i))& \hfill & \\ \hfill & =p_i^{a_i}\left(1-\frac{N(p_i}{p_i}\right).& \hfill & \end{array}$$

This gives

$$\begin{array}{llll}\hfill {\varphi }_f(n)& =\underset{i=0}{\overset{k}{\prod }}{p}_i^{a_i}\left(1-\frac{N(p_i}{p_i}\right)& \hfill & \\ \hfill & =n\underset{i=0}{\overset{k}{\prod }}\left(1-\frac{N(p_i)}{p_i}\right)& \hfill & \\ \hfill & =n\underset{p\mid n}{\prod }\left(1-\frac{N(p)}{p}\right).& \hfill & \end{array}$$

e)

If $f(x)=x$, we obtain Theorem 2.17 (the number of solutions of $x\equiv 0(\mathit{mod}p)$ is $1$).

If $f(x)=x(x+1)$, we obtain the solution of Problem 46 (the number of solutions of $x(x+1)\equiv 0(\mathit{mod}p)$ is $2$).

Conclusion: if ${\Phi }_f(m)$ denotes the number of integers $a,1\le a\le m$, such that $f(a)\wedge m=1$, then

where $N(p)$ denotes the number of solutions of the congruence $f(x)\equiv 0(\mathit{mod}m)$ □