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.

Printable View

- October 11th 2009, 03:52 PMkeityoshow 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. - October 11th 2009, 07:21 PMMedia_ManDirichlet
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.