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
    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.2012-12-31
  • 0
    thats not what i mean2012-12-31
  • 0
    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.2012-12-31
  • 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
    Sense gcd(a,r) divides a, and we also have gcd(a,r) divides b, we must have gcd(a,r)2012-12-31
  • 0
    Yes of course. So we may choose those $r$ that divide both $a$ and $b$.2012-12-31
  • 0
    wait so is r simply all the divisors of gcd(a,b)2012-12-31
  • 0
    @Ethan Even in this case, there are more $r$. For instance if $a=18, b=30$, then $r=7$ works.2012-12-31
  • 0
    I don't understand any of these answers.2012-12-31
  • 0
    Sorry, I've corrected a mistake and improved a bit what I was writing taking into account @peoplepower comment.2012-12-31
  • 0
    Simply, $r$ is all the divisors of $gcd(a,b)$. Moreover all the multiples of $r$ of the form $r\cdot m $ where $gcd(a,m)=1$ and $rm\leq a$ are also correct.2012-12-31
  • 0
    @epsilon How do you efficiently find all $m$ such that $gcd(a, m) = 1$?2012-12-31
  • 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