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!

  • 2
    $\begingroup$ It is true that $\gcd(k,n)=d \implies \gcd(k/d, n/d)=1$, though. $\endgroup$
    – πr8
    Apr 20 '17 at 9:21
  • $\begingroup$ Yeah, relating $\phi$ function to that seems a bit tricky ! $\endgroup$
    – Hiiii
    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$.

  • 1
    $\begingroup$ Hey is this a counter example to the second statement ? $$\gcd(3,20/2)=1 \not \Longrightarrow \gcd(3*2,20)=1$$ $\endgroup$
    – Hiiii
    Apr 20 '17 at 9:34
  • 1
    $\begingroup$ 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$). $\endgroup$ Apr 20 '17 at 9:36
  • $\begingroup$ Ah I see, awesome! $jd = k$. Thank you (: $\endgroup$
    – Hiiii
    Apr 20 '17 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.