Exercise 2.3.43* ($n - \phi(n) > d - \phi(d)$ if $d \mid n, 0 < d < n$)

Proof. Here $n\ge 2$, since $0<d<n$. Consider the sets $I=]]0,n[[$,

so that $A^{\prime }$ is the complementary of $A$ in $I$, thus

Now consider $J=]]1,d[[$, and

Then

We prove that $B^{\prime }\subseteq A^{\prime }$. If $a\in B^{\prime }$, then $0<a<d$, and $a\wedge d>1$. There is some prime number $p$ such that $p\mid a$ and $p\mid d$. Since $d\mid n$, $p\mid n$ (and $p\mid a$), thus $a\wedge n>1$. Moreover $0<a<d<n$. This shows that $a\in A^{\prime }$. Since this is true for every $a\in A^{\prime }$, we obtain $B^{\prime }\subseteq A^{\prime }$ (and $n-\varphi (n)\ge d-\varphi (d)$).

Now we prove that $B^{\prime }\ne A^{\prime }$.We must find an element $a$ in $A^{\prime }$ which is not in $B^{\prime }$.

Note that $d\mid n$, thus $n=\mathit{kd}$ for some integer $k$, and $k\ge 2$ since $n>d$. If $d=1$, then, since $n\ge 2$, $n-\varphi (n)>0=d-\varphi (d)$. We suppose now that $d>1$. Then $n=\mathit{kd}\ge 2d>2$.

• If $n$ is odd, we know that $n=\mathit{kd}$, where $k\ge 2$. But $n=2d$ is impossible, since $n$ is odd, so $n\ge 3d$. Take $a=2d$. Then $a>d$, thus $a\notin B^{\prime }$. Since $0<a<n$ and $a\wedge n=(2d)\wedge (\mathit{kd})\ge d>1$, we obtain $a\in A^{\prime }$.
• If $n$ is even, take $a=n-2$. Then $n\ge 2d$, thus $a=n-2\ge 2d-2\ge d$, because $d\ge 2$. Therefore $a\notin B^{\prime }$. But $n-2$ and $n$ are even, thus $a\wedge n=(n-2)\wedge n>1$, and $0<n-2<n$, so $a=n-2\in A^{\prime }$.

In both cases, $B^{\prime }⊊A^{\prime }$. Therefore

If $d\mid n$ and $0<d<n$, then $n-\varphi (n)>d-\varphi (d).$ □