# For what $1\leq r\leq a$ does $\gcd(a,r)\mid b$?

For what $1\leq r\leq a$ does $\gcd(a,r)\mid b$?

I am looking for an easy way to calculate these $r$ for any given $a$ and $b$.

-
What is $b$ here? – Álvaro Lozano-Robledo Mar 23 '13 at 19:56
Any given integer – Ethan Mar 23 '13 at 19:58
Does $b|\gcd(a,r)$ or $\gcd(a,r)|b$? – Álvaro Lozano-Robledo Mar 23 '13 at 19:58
@ÁlvaroLozano-Robledo $\gcd(a,r)\mid b$ , sorry I fixed it – Ethan Mar 23 '13 at 20:00

If $(a,r)\mid b$ then, since $(a,r)\mid a$ automatically, the stronger claim $(a,r)\mid(a,b)$ is also satisfied, and the converse holds as well since $(a,b)\mid b$. That is, $(a,r)\mid b\iff (a,r)\mid(a,b)$.

The $1\le r\le a$ for which $(a,r)\mid(a,b)$ are $\{dc:~d\mid(a,b),~1\le c\le a/d,~(c,a)=1\}$.

-

Hint $\rm\ \ (a,r)\mid b \iff (a,r)\mid a,b \iff (a,r)\mid (a,b)$

-

Hint:

Case 1:

$a=a_1a_2..a_n$

$b=b_1b_2..b_n$

$\gcd(a,b)=1$

If you have $\gcd(a,r) | b \implies \gcd(a,r)=1$

For the other case, take $\gcd (a,b)=k$ and see how it works.

Then $a=nk$, and $b=mk$ (Where again $\gcd (m,n)=1$)

If $\gcd (a,r) |b \implies \gcd(a,r)=k$

The conditions for $r$ is $\gcd (a,r) =\gcd(a,b)$

-