Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory: gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k

  1. Mar 2, 2012 #1
    1. The problem statement, all variables and given/known data
    [itex]a[/itex] and [itex]b[/itex] are coprime. Show that for any [itex]n[/itex], there exists a nonzero integer [itex]k[/itex] that makes [itex]a+bk[/itex] and [itex]n[/itex] coprime.

    2. Relevant equations
    [itex]a[/itex] and [itex]b[/itex] are coprime if any of the following conditions are met:
    1. [itex]\text{gcd}(a,b)=1[/itex]
    2. the ideal [itex](a,b)=\{ax+by : x,y\in\mathbb{Z}\}[/itex] is equal to the set of all integers [itex]\mathbb{Z}[/itex]

    3. The attempt at a solution
    I tried expanding the desired result in terms of ideals:
    [itex](a+bk,n) = \{(a+bk)x+ny : x,y\in\mathbb{Z}\} = \{ax+bkx+ny : x,y\in\mathbb{Z}\}[/itex]

    If [itex]a[/itex] and [itex]n[/itex] are coprime, then setting [itex]k=0[/itex] makes [itex]a+bk[/itex] and [itex]n[/itex] coprime.

    I couldn't figure out the case where [itex]a[/itex] and [itex]n[/itex] have a gcd other than 1.
    Last edited: Mar 2, 2012
  2. jcsd
  3. Mar 8, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    If a and n have gcd other than 1 then there will be a prime p dividing both of them. Now suppose that p divides a+bk. What can you say now?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook