Prove: $n - \varphi(n) > d - \varphi(d)$ if d divides n

Question

I am trying to prove that if $d|n$ and $0 < d < n$, then $n - \varphi(n) > d - \varphi(d)$

I know that $\varphi(n) \geq \varphi(d)$, which is making this a difficult inequality for me to prove.

Answer 1

HINT: For each integer $N$, let $A_N$ be defined as follows: $A_n =$ $\{$positive integers $m < N$ such that $\gcd(m,N) \ge 2\}$. Then note the equation $|A_N| = N-\varphi(N)$.

So to show that the inequality $d - \varphi(d) < n - \varphi(n)$ holds for such $d,n$ as in the OP with $d<n$, it suffices to show that $A_d$ is a proper subset of $A_n$.

1. But on the one hand if $m$ is an integer in $A_d$, then $m$ is in $A_n$. [Indeed, if $m$ is in $A_d$, then both $\gcd(m,d)$ is at least $2$, and $m \le d$. But then as $d|n$, it follows that $\gcd(m,n) \ge gcd(m,d)$ so $\gcd(m,n)$ is at least $2$, and as $d|n$, that $m<n$.]

2. On the other hand, $n$ is in $A_n$ but not in $A_d$.

But 1. and 2. together imply that $A_d$ is indeed a proper subset of $A_n$, and thus as noted earlier, the inequality $d - \varphi(d) < n - \varphi(n)$ indeed holds.

Answer 2

This proof uses $\varphi(n)=n\prod_{p \mid n}\frac{p-1}{p}$ and a bit of algebra. Since $(p-1)/p<1$, for $d \mid n$ we have $$\prod_{p \mid n}\frac{p-1}{p}\leq\prod_{p \mid d}\frac{p-1}{p}$$ ($d$ can only have same or fewer prime factors than $n$ does). Hence $$1-\prod_{p \mid n}\frac{p-1}{p}\geq 1-\prod_{p \mid d}\frac{p-1}{p}$$ with both sides positive (the products are strictly between $0$ and $1$). Combining this with a strict inequality $n>d$ we get $$n-n\prod_{p \mid n}\frac{p-1}{p}> d-d\prod_{p \mid d}\frac{p-1}{p}$$ which is just $$ n - \varphi(n) > d - \varphi(d). $$