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

[Just a nobody]

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.

 

[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?