# Common denominators

Is there a function to get all common denominators (except for 1) for two numbers? I think it could use summation, the lower limit would be 1 and upper limit would be the greatest common denominator, but I'm not sure.

-
Do you have two numbers $p/q$ and $r/s$ and you want to find the common factors of $q$ and $s$? – Américo Tavares Jun 22 '11 at 19:57
When you say greatest common denominator, do you mean greatest common divisor (or as I was taught, highest common factor)? – Henry Jun 22 '11 at 22:43

To get the common factors (divisors if you must) of two numbers, one approach is to take their prime factorisations and then see which exponents they have in common. For example take 48 and 180:

• $48 = 2^4 \times 3^1$
• $180 = 2^2 \times 3^2 \times 5^1$

So the highest common factor is $2^2 \times 3^1 \times 5^0 = 12$. To find all the common factors of 48 and 180 (i.e. the factors of 12), you can use lower exponents of the primes, so you can choose $2^0$, $2^1$ or $2^2$, and multiply this by $3^0$ or $3^1$, making six possibilities, namely $1$, $2$, $3$, $4$, $6$, or $12$.

-

There is an algorithm (not a formula) for finding all common divisors of two integers $a$ and $b$. It breaks into two parts:

• Finding the greatest common divisor of $a$ and $b$; this part is "easy" (in the computational sense, it is a 'fast' algorithm).
• Finding all divisors of the greatest common divisor; this part is computationally hard in general (takes a long time for arbitrary numbers).

They key is that the greatest common divisor of $a$ and $b$ satisfies a universal property relative to all common divisors: namely, $d\gt 0$ is the greatest common divisor of $a$ and $b$ if and only if:

1. $d$ divides $a$ and $d$ divides $b$; and
2. If $c$ is any integer that divides $a$ and also divides $b$, then it divides $d$ as well.

To find $d$, the greatest common divisor, you can use the Euclidean Algorithm. This does not require you to factor either $a$ or $b$, just do subtractions.

Once you find $d$, the common divisors of $a$ and $b$ are precisely the divisors of $d$; to find all divisors of $d$, one usually does need to factor $d$ into primes; this is computationally hard, but it can be done by many known methods.

-
+1 Exactly what I was just going to post (Euclidean Algorithm at least), before I "refreshed" the page! You're just too quick for me, Arturo ;-) – amWhy Jun 22 '11 at 20:50
FGITW${}{}{}{}$ – Gerry Myerson Jun 23 '11 at 0:22

First of all there is no greatest common denominator (there is the greatest common divisor). Maybe you meant the lowest common denominator or greatest common divisor.

I think you meant the second one, since you mention $1$. So, you want to find all common divisors of $a,b$. Then denote by $c=\gcd(a,b)$. Pick $d |a, d|b$ a common divisor. Then $d| ka+lb$ for all $k,l \in \Bbb{Z}$. There is a theorem which states that there exist $k_0,l_0$ such that $ak_0+bl_0=c$. Therefore $d|c$. All common divisors are divisors of the greatest common divisor. To find them all, there is no general formula, but if you have concrete examples, the computations are not very hard.

-