I came across this question in the book An Excursion in Mathematics:
Let $a,b,c \in \Bbb{Z}$ such that $\gcd(a,b) =1, c>0$. Prove that $\exists\ x \in \Bbb{Z}$ such that $ \gcd (a+bx,c) = 1$.
There is one proof that is easy enough: By Dirichlet's Theorem, there are infinitely many primes of the form $a+bx$ where $a,b$ are relatively prime, so we merely take the first prime of the form $a+bx>c$.
On the other hand, however, the book is a fairly elementary textbook on high-school math contests and Dirichlet's theorem is not mentioned. I am having difficulty coming up with another proof for this. I have tried to construct an $x$ such that $a+bx$ is relatively prime to $c$, but to no avail.
How would I proceed towards the proof?
Consider a prime factor $p$ of $c$. Then if $p\mid b$, $p\nmid a$ and all $x$ satisfy $a+bx\not\equiv0\pmod p$. If $p\nmid b$ the solutions to $a+bx\equiv1\pmod p$ form a conguruence class modulo $p$.
All one needs is to choose $x$ so that $a+bx\equiv1\pmod p$ for all primes $p\mid c$, $p\nmid b$. Now use Chinese Remainder Theorem.