(adsbygoogle = window.adsbygoogle || []).push({}); 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:

- [itex]\text{gcd}(a,b)=1[/itex]
- 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**