3

I have number written as factors for instance: n = 2 * 3 * 3 * 5. What I have to do is find how many numbers between <1, n) are co-prime to n, which means GCD = 1. It can simply be done using Euler's Totient. But what if GCD = 2 or more? Is there any totient-like function?

UPDATE:

I seeking how many numbers between ai = <1, n) will return GCD(ai,n) = 2. For GCD(ai, n) = 1. It's Euler Totient, what about higher GCD's?

Community
  • 1
Kostek
  • 255

1 Answers1

2

Let $n > 1$, and let $d < n$ be a positive divisor of $n$. You want to count the number of elements of the set $$ A = \{ a : 0 \le a < n, \gcd(a, n) = d \}. $$ Note that if $a \in A$, then $\gcd\left(\dfrac{a}{d}, \dfrac{n}{d}\right) = 1$, so $\dfrac{a}{d} \in B$, where $$ B = \left\{ b : 0 \le b < \frac{n}{d}, \gcd\left(b, \frac{n}{d}\right) = 1 \right\}, $$ and $B$ has $\varphi(n/d)$ elements. Conversely, if $b \in B$, then $b d \in A$, as $$ \gcd(b d, n) = \gcd \left(b d, \frac{n}{d} d \right) = \gcd \left( b, \frac{n}{d} \right) d = d. $$

So $A$ has $\varphi(n/d)$ elements.

Andreas Caranti
  • 68,873
  • Are you sure phi(7) = 6, because all previous number are co-prime to it (all numbers less than prime are co-prime). phi(7/2) = 3 or 4 (doesn't matter since both return 2-> phi(3) = phi(4) = 2)

    So what you are saying there are 2 numbers in range ai = <1-6> that gives GCD(ai, 7) = 2? Interesting since all previous give 1 as stated before. Am I right or I get something wrong, from what you have written?

     – Kostek May 25 '13 at 15:48
  • @Kostek, $\varphi(7/2)$ makes no sense, Euler's function is only defined for integers. And I am only considering the case when $d$ divides $n$, otherwise $\gcd(a, n) = d$ has no solution $a$. – Andreas Caranti May 25 '13 at 15:50
  • Oh sorry, I think more computer programming way :D that's '/' means either floor() or ceil() :) I will give it try.

    Well all seems to be correct from data I have, so :) thank you very much - nice explanation.

     – Kostek May 25 '13 at 15:52
  • @Kostek, when in Rome, I mean, MSE, do like the mathematicians! ;-) – Andreas Caranti May 25 '13 at 15:54
  • I know :) but sometimes it's easier to find answer for math algorithm here. – Kostek May 25 '13 at 15:55
  • @AndreasCaranti: Is $\varphi(n)=\phi(n)$? – Inceptio May 25 '13 at 16:06
  • @Inceptio, yes, I do have to admit I studied Greek at school, and ever since there's only been one $\varphi$ for me. – Andreas Caranti May 25 '13 at 16:14