3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "...If GCD=2..." of whom ? $\endgroup$ – DonAntonio May 25 '13 at 15:27
  • $\begingroup$ @DonAntonio: The OP is asking for the function counting the numbers $k$ with $1\leq k\leq n$ for which $\gcd(k,n)=2$. $\endgroup$ – Zev Chonoles May 25 '13 at 15:32
  • $\begingroup$ I think he means how many numbers m<n are there so that GCD(n,m)=2 or 3 or... $\endgroup$ – CODE May 25 '13 at 15:32
  • $\begingroup$ Yes, that seems to be so, Zev...perhaps. $\endgroup$ – DonAntonio May 25 '13 at 15:32
  • $\begingroup$ You can use Inclusion-Exclusion principle.. $\endgroup$ – Inceptio May 25 '13 at 15:46
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kostek May 25 '13 at 15:48
  • $\begingroup$ @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$. $\endgroup$ – Andreas Caranti May 25 '13 at 15:50
  • $\begingroup$ 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. $\endgroup$ – Kostek May 25 '13 at 15:52
  • $\begingroup$ @Kostek, when in Rome, I mean, MSE, do like the mathematicians! ;-) $\endgroup$ – Andreas Caranti May 25 '13 at 15:54
  • $\begingroup$ I know :) but sometimes it's easier to find answer for math algorithm here. $\endgroup$ – Kostek May 25 '13 at 15:55

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.