Exercise 2.23

Proof. My interpretation of this statement is that $\psi (n)$ is the number of $j,j=1,2,\dots ,n$, such that $(f(j),n)=1$ (if $f$ is not one to one, we may obtain a different value).

Let $A_n=\{j\in \mathbb{Z},1\le j\le n|f(j)\wedge n=1\}$. Then $\psi (n)=|A_n|$. If $f(x)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=0}^d{a}_k{x}^k$, note $f_n(x)\in (\mathbb{Z}∕\mathit{n\mathbb{Z}})[x]$ the polynomial $f_n(x)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=0}^n{[a_k]}_n{x}^k$ (here, we represent the class of $j\in \mathbb{Z}$ in $\mathbb{Z}∕\mathit{n\mathbb{Z}}$ by ${[j]}_n$ ). We can write without inconvenient $f=f_n$.

Let $B_n=\{a\in \mathbb{Z}∕\mathit{n\mathbb{Z}}|f(a)\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{∗}}\}$, where ${(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{∗}}$ is the group of invertible elements of $\mathbb{Z}∕\mathit{n\mathbb{Z}}$.

Then $u:A_n\to B_n,j\mapsto {[j]}_n$ is a bijection.

Indeed $u$ is well defined : if $j\in A_n,f(j)\wedge n=1$ , so $f({[j]}_n)={[f(j)]}_n\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{∗}}$.

$u$ is injective : ${[j]}_n={[k]}_n$ with $1\le j\le n,1\le k\le n$ implies $j=k$.

$u$ is surjective : if $a\in \mathbb{Z}∕n∕Z$ verifies $f(a)\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{∗}}$, let $j$ the unique representative of $a$ such that $1\le j\le n$. Then $f(j)\wedge n=1$, so $u(j)=a$.

Thus

Suppose $n\wedge m=1$. Let

$\text{∙}$ $\phi$ is well defined : ${[j]}_{\mathit{nm}}={[k]}_{\mathit{nm}}\Rightarrow j\equiv k(\mathit{mod}\mathit{nm})\Rightarrow (j\equiv k(modn),j\equiv k(modm))\Rightarrow ({[j]}_n,{[j]}_m)=({[k]}_n,{[k]}_m)$.

$\text{∙}$ $\phi$ is injective : if $\phi ({[j]}_{\mathit{nm}})=\phi ({[k]}_{\mathit{nm}})$, then ${[j]}_n={[k]}_n,{[j]}_m={[k]}_m$, so $n\mid j-k,m\mid j-k$. As $n\wedge m=1,\mathit{nm}\mid j-k$ so ${[j]}_{\mathit{nm}}={[k]}_{\mathit{nm}}$.

$\text{∙}$ $\phi$ is surjective : if $(a,b)\in B_n\times B_m$, there exist $j,k\in \mathbb{Z},1\le j\le n,1\le j\le m$, such that $a={[j]}_n,b={[k]}_m$. From the Chinese Remainder Theorem, there exists $i\in \mathbb{Z},1\le i\le n$, such that $i\equiv j(\mathit{mod}n),i\equiv k(modm)$. Then $\phi ({[i]}_{\mathit{nm}})=({[i]}_n,{[i]}_m)=({[j]}_n,{[k]}_m)=(a,b)$.

Finally, $\psi (\mathit{nm})=|B_{\mathit{nm}}|=|B_n||B_m|=\psi (n)\psi (m)$, if $n\wedge m=1$ : $\psi$ is a multiplicative function.

The interval $I=[1,p^t]$ is the disjoint reunion of the $p^{t-1}$ intervals $I_k=[\mathit{kp}+1,(k+1)p]$ for $k=0,1,\cdots ,p^{t-1}-1$, so $\psi (p^t)=\underset{k=0}{\overset{p^{t-1}-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\mathrm{Card}{C}_k$, where $C_k=\{j\in I_k|f(j)\wedge p^t=1\}=\{j\in I_k|f(j)\wedge p=1\}$.

As $f(j)\wedge p=1⟺f(j-\mathit{kp})\wedge p=1$, the application $v:C_k\to C_0,j\mapsto j-\mathit{kp}$ is well defined and is bijective, so $|C_k|=|C_0|=\psi (p)$. Thus $\psi (p^t)=p^{t-1}\mathrm{Card}{I}_0=p^{t-1}\psi (p)$ :

If $n={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{p\mid n}{p}^{t(p)}$, then