Simple number theory

Question

I'm new in number theory and I was asked this question: For the number $N$ output the amount of numbers $M$, such that $1 \le M \le N$, $\gcd(M, N) \ne 1$ and $\gcd(M, N) \ne M$. How can i solve it?

Answer 1

Hints

• For a given integer $n$ the number of integers $m$ such that $\gcd(m,n)=1$ and $1\leq m\leq n$ is exactly $\varphi(n)$
• The number of integers $m$ such that $\gcd(m,n)=m\neq 1$ and $1\leq m\leq n$ is exactly $d(n)-1$ (don't count $m=1$).
• The number of all integers $m$ such that $1\leq m\leq n$ is $n$
• Conclude that the number of integers $1\leq m\leq n$,$\gcd(m,n)\neq1$ and $\gcd(m,n)\neq m$ is : $$n+1-d(n)-\varphi(n) $$