2
$\begingroup$

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$.

  • 0
    As efficient as it gets I guess?2012-12-31

2 Answers 2

3

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.

  • 0
    @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.2012-12-31
1

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.

  • 0
    @Paresh Since every $n\in\mathbb{N}$ and $a\in\mathbb{N}$ can be written as$a$product of prime powers you can choose those primes that do not appear in $a$ and are smaller than $a$. Then use every possible product of them that is smaller than $a$. To be honest though...overall it's not a very efficient method you're right.2012-12-31