# A question about relatively prime

Let $a,b$ be positive integers. Prove there is a positive integer n such that $gcd(a+n,b)=1$.

I have tried many ways but still get so solutions, could somebody give me some hints. Many thanks.

• Set $n=r\cdot b\pm 1-a$, choose $r$ such that $n>0$ – lab bhattacharjee Jan 20 '14 at 5:38
• Another choice: pick a prime $p > a, b$ and set $n = p - a$ – zcn Jan 20 '14 at 5:47
• How is this abstract algebra? – Mayank Pandey Jan 20 '14 at 5:58

My take on this is that the key here is to realize that we have exceptional latitude in choosing $n$, as long as $q \not\mid (a + n)$ for any prime $q$ such that $q \mid b$. So if $p_1 < p_2 < . . . p_N$ are the primes dividing $b$, simply choose a prime $p > \max \{a, p_N\}$ and set $n = p - a$. Then $p = a + n$ and $\gcd (a + n, b) = \gcd (p, b) = 1$, since $b$ and $p = a + n$ have no prime factors in common.
Hint: Can you show that $$\gcd(bk + 1, b) = 1$$ for all integers $k$? Do you see how to use this?