1. Not finding help here? Sign up for a free 30min 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!

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

    morphism

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number theory: gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k
  1. Prove gcd(nn!, n!+1)=1 (Replies: 1)

Loading...