# Is there a formula to find the number of integers $k$ such that $\gcd(k,n)=d$?

Here $0\le k\lt n$ and $d\mid n$.
All are positive.

I know that the number of integers satisfying $\gcd(k,n)=1$ is $\phi(n)$.
Initially, I thought that the formula would be simply $\phi(n/d)$ because $\gcd(k,n) = d \implies \gcd(k,n/d)=1$.
Soon I realized that this is a mistake : $\gcd(2, 12) = 2 \not \implies \gcd(2,6)=1$.

So I'm kinda stuck looking for a formula. Appreciate any help. Thanks!

• It is true that $\gcd(k,n)=d \implies \gcd(k/d, n/d)=1$, though.
– πr8
Apr 20 '17 at 9:21
• Yeah, relating $\phi$ function to that seems a bit tricky ! Apr 20 '17 at 9:23

I think your formula is correct, because $\gcd(k,n)=d\Longrightarrow \gcd(k/d,n/d)=1$ and $\gcd(j,n/d)=1 \Longrightarrow \gcd(jd,n)=d$.
• Hey is this a counter example to the second statement ? $$\gcd(3,20/2)=1 \not \Longrightarrow \gcd(3*2,20)=1$$ Apr 20 '17 at 9:34
• Sorry, there is a typo in the second statement, will fix. The point is there is a one-to-one correspondence between solutions to $\gcd(j,n/d)=1$ and $\gcd(k,n)=d$ (multiply by $d$). Apr 20 '17 at 9:36
• Ah I see, awesome! $jd = k$. Thank you (: Apr 20 '17 at 9:41