# Greatest common divisor problem

For fixed integers $a,b$, how can I find all integers $r$, $1\leq r\le a$, such that $\gcd(a,r)\text{ divides } b$?

That is, I need an efficient way of finding those integers $r$.

-
I presume by efficient you mean you want something faster than just factoring $a$ and $b$? If this is what you mean, you should say so. – Potato Dec 31 '12 at 1:22
thats not what i mean – Ethan Dec 31 '12 at 1:22
Well, efficient relative to what? You can do it as in Ross Millikan's answer, but for large $a$ and $b$ it's going to be very slow. – Potato Dec 31 '12 at 1:23
As efficient as it gets I guess? – Ethan Dec 31 '12 at 1:25

The only way you can fail is if $a$ has more powers of some prime in its factorization than $b$ does and so does $r$. So factor $a,b$ into primes, $a=p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}=\prod p_i^{e_i}, b=\prod q_i^{f_i}$. Look for any primes where $a$ has more factors than $b$ does. You need to avoid $r$'s that have too many of those factors.

For example, take $a=24=2^3\cdot 3^1, b=140=2^2\cdot 5^1 \cdot 7^1$. The only way you can fail is to either have $r$ have a factor of $8$ or a factor of $3$. So check all the numbers below $a$ for those properties.

-
@Ethan: for small values like this you won't do better. For large ones you can-if $a$ were $168=2^3\cdot 3 \cdot 7$ and $b$ were $1820=2^2\cdot 5 \cdot 7 \cdot 13$, you would again have that $r$ cannot be a multiple of $3$ or $8$. You could use the Chinese Remainder Theorem to determine the acceptable values $\pmod {24}$ and repeat the pattern up to $a$. This helps more when $a$ and $b$ have more factors in common. – Ross Millikan Dec 31 '12 at 1:30

Suppose $a=p_{1}^{e_1}p_{2}^{e_2}...p_n^{e_n}$ where $e_i=0$ or $e_i=1$ and $b=p_{1}^{\delta_1}p_{2}^{\delta_2}...p_n^{\delta_n}$ where $\delta_i=0$ or $\delta_i=1$.

$p_i$ may equal $p_j$ for some $i,j$ and of course $p_i,i=1,...,n$ are prime numbers.

Now pick all $p_i$ that exist in both $a$ and $b$.To be precise those $p_i$ that $e_i=\delta_i=1$. Let's say those are the following ${\{p_{i_1}},{p_{i_2}},...,{p_{i_m}}\}$.

You may choose $r$ to be the product of every possible combination of those ${\{p_{i_1}},{p_{i_2}},...,{p_{i_m}}\}$.

an example: $a=18=2\cdot 3\cdot 3\cdot 5^0$ and $b=30=2 \cdot 3^0\cdot 3\cdot 5$ then you can choose $r$ to be any of the following $r=2,r=3,r=2\cdot 3$

Furthermore:

1. If $m\in \mathbb{N}$ such that $gcd(a,m)=1$ and $m\leq a$ then $m$ is correct.

2. If $m\in \mathbb{N}$, $r$ as described above such that $gcd(a,m)=1$ and $m\cdot r\leq a$ then $r\cdot m$ is also correct.

-
Sense gcd(a,r) divides a, and we also have gcd(a,r) divides b, we must have gcd(a,r)<gcd(a,b) – Ethan Dec 31 '12 at 1:41
Yes of course. So we may choose those $r$ that divide both $a$ and $b$. – epsilon Dec 31 '12 at 1:45
wait so is r simply all the divisors of gcd(a,b) – Ethan Dec 31 '12 at 1:46
@Ethan Even in this case, there are more $r$. For instance if $a=18, b=30$, then $r=7$ works. – peoplepower Dec 31 '12 at 2:05
I don't understand any of these answers. – Ethan Dec 31 '12 at 2:12