1
$\begingroup$

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.

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

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.

Hope this helps. Cheerio,

and as always,

Fiat Lux!!!

$\endgroup$
1
  • $\begingroup$ Like user115654 said in his comment, which I didn't see until after I posted! ;-) $\endgroup$ – Robert Lewis Jan 20 '14 at 5:51
0
$\begingroup$

Hint: Can you show that $$\gcd(bk + 1, b) = 1$$ for all integers $k$? Do you see how to use this?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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