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.