Proving that there is some $x$ such that $\gcd(a + bx, c) = 1$ Let $\gcd(a,b) = 1$ and $c&gt;0$. Pove that there is an integer x such that $\gcd(a + bx, c) = 1$.
This question is from Section 2.3 (Covers the Chinese Remainder Theorem) Problem 15 of An Introduction to the Theory of Numbers by Niven and Zuckerman.
I didn't use the Chinese Remainder Theorem in my attempt, but I suspect that it should, since $\gcd(a,b) = 1$. In fact I didn't even use that $\gcd(a,b)=1$, either.
Attempt: Instead of finding $x$, we find what $x$ cannot be. That is, $y$ such that $\gcd(a+by,c) \neq 1$.
Reduce $c$ into its prime factors, so that $c = c_{1}^{i_{1}}c_{2}^{i_{2}}c_{3}^{i_{3}}...c_{n}^{i_{n}}$. Then we can solve, for each $1 \leq m \leq n$,
$a + by \equiv _{c_{m}}0 \Leftrightarrow by \equiv _{c_{m}} -a$
The point is that if $a + by$ and $c$ have a GCD other than $1$, then one prime factor must be in common.
$by \equiv _{c_{m}} -a$ has solutions when $gcd(b,c_{m})$ divides $-a$ and has no solution otherwise. Suppose there are no solutions for all $m$. Then we are done, for there are no restrictions on $x$. Suppose for some or all $m$, there are solutions. Then $by \equiv _{c_{m}} -a$, has solutions $y \equiv _{c_{m}} -(\frac{a}{g})y_{0}+t(\frac{c_{m}}{g})$. Where $g = \gcd(b,c_{m})$, $t = 0,1,..,g - 1$, and $y_{0}$ is a solution to $(\frac{b}{g})y \equiv _{c_{m}}1$. But the set of all these solutions cannot equal $\mathbb{Z}$, because there are infinite primes and finite $c_{m}$. So there must be some integer $x$ such that $gcd(a + bx, c) = 1$.
$\blacksquare$
I don't like this proof, because it's nonconstructive. Is there a way to use the CRT or some other basic number theorem?
Let $c=c_1c_2$ where every prime divisor of $c_1$ is a prime divisor of $a$ and $c_2$ is coprime with $a$.
Then $a+bc_2$ and $c$ are coprime.
This is almost certainly not what the problem in Niven and Zuckerman is looking for, but if you have Dirichlet's Theorem at your disposal, then from the assumption $\gcd(a,b)=1$ you can conclude there are infinitely many prime numbers of the form $a+bx$, at which point you can just take one that's greater than $c$.