Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
@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
add comment

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.

share|improve this answer
    
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
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.