1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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