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