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

## Homework Statement

$a$ and $b$ are coprime. Show that for any $n$, there exists a nonzero integer $k$ that makes $a+bk$ and $n$ coprime.

## Homework 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}$

## 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: