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$.
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$.
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.
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:
If $m\in \mathbb{N}$ such that $gcd(a,m)=1$ and $m\leq a$ then $m$ is correct.
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.