I am not quite sure how to approach this problem:
If a and n are such natural numbers that a divides n, then $n-ϕ(n)\ge a-ϕ(a)$
This is my thought process so far: Obviously the fact that $n=n*a$ should be used. If n is prime, then $n-ϕ(n)=a-ϕ(a)=1$ because only n and 1 could then possibly be a. If n is not prime, but a is, then $n-ϕ(n)>1$ and $a-ϕ(a)=1$ so $n-ϕ(n)>a-ϕ(a)=1$. Yet I am not sure what happens if both a and n are not prime.
Any help is appreciated. Thank you.
Answer
The number $\varphi(m)$ counts the numbers from $1$ to $m$ that are relatively prime to $m$. It follows that $m-\varphi(m)$ counts the numbers from $1$ to $m$ that are not relatively prime to $m$.
Let $n=ka$. If $1\le x\le a$, and $x$ is not relatively prime to $a$, then $x$ is a number between $1$ and $n$ that is not relatively prime to $n$. The result follows.
No comments:
Post a Comment