I was asked to prove the following: For any given $(a,b) = 1$ and $m > 0$ there are infinitely many integers $x$ such that $(a+bx,m) = 1$.
Now, I have a proof worked out that involves the following steps:
1) Prove that if one solution exists, then infinitely many do.
2) Then I show that there are solutions if $m$ is prime
3) Write $m= p_{1}^{e_{1}} \cdots p_{k}^{e_{k}}$. Then if a solution exists for $\overline{m} = p_{1}\cdots p_{k}$, then it holds for $m$ as well.
4) Let $m,n > 1$ and $(m,n) = 1$. Then if the claim holds for $m$ and $n$, it holds for $mn$ as well.
Finally, for a given $m$, apply (3) to reduce $m$ to a product of primes, repeatedly use (4) to reduce to individual primes, and then use (2) to prove the result.
While I think this proof works, I feel like there must be a better proof of this statement that isn't as complicated... Does anyone know of such a proof?
Hint: $\gcd(a + bx, m) = \gcd (a + b(x+m), m) $. Hence, if one solution exists, then infinitely many do.
Hint: Let $x=1$ to $m$. Show that at least one solution must exist. This essentially boils down to $m > \phi(m) $.
Elaboration. Suppose that $ \gcd ( a + bx^* , m ) = m^* \neq 1 $. We must have $m^* \mid m$.
For how many values of $x$ do we have $m^* \mid \gcd( a + bx,m)$? This means that $\frac{a+bx}{m^*}$ is an integer. Clearly $ x = x^* + km^*$ will work. If any other value works, then we must have $ \gcd(a,b) > 1 $. Hence, there are $\frac{m}{m^*}$ such values that don't work.
Now, apply the Principle of Inclusion and Exclusion, to count the number of values of $x$ which don't work. Show that there are $\phi(m)$ values that don't work.