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

1. Mar 2, 2012

### Just a nobody

1. The problem statement, all variables and given/known data
$a$ and $b$ are coprime. Show that for any $n$, there exists a nonzero integer $k$ that makes $a+bk$ and $n$ coprime.

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

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

If $a$ and $n$ are coprime, then setting $k=0$ makes $a+bk$ and $n$ coprime.

I couldn't figure out the case where $a$ and $n$ have a gcd other than 1.

Last edited: Mar 2, 2012
2. Mar 8, 2012

### morphism

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?