# Thread: show that if (a,b)=1,c>0, then (a+bx,c)=1 for some x

1. ## show that if (a,b)=1,c>0, then (a+bx,c)=1 for some x

Salutations! I am stuck with this interesting problem:
Let (a,b)=1 and c>0. Prove that there is an integer x such that (a+bx,c)=1.

Thanks for any help.

2. ## Dirichlet

This follows almost immediately from Dirichlet's Theorem on Arithmetic Progressions, which states that given any two coprime numbers a and b, there exists an infinite number of primes of the form a+bx. Since c has only a finite number of prime factors, there must be some x such that a+bx is prime and does not divide c.

Sorry for simply referring you to another theorem. I leave it to someone else to find an elementary proof.