Take two relatively prime numbers $m,n \in \mathbb{Z}$ (i.e. $gcd(m,n) = 1$) where $m \neq 1$.
Show that:
$$\forall a \in \mathbb{Z} \textrm{ s.t. } 0<a<n$$
$$\exists i \in \mathbb{Z^+} \textrm{ s.t. }\gcd( n-a + i*a , m)\neq 1$$
Attempt:
I can think of a way of simplifiying the problem.
Say we want to make $n-a + i*a$ a multiple of $m$ (lets say $k*m$)
Then $$n-a + i*a = k*m$$ $$i = \frac{k*m-n+a}{a}$$ $$i = \frac{k*m-n}{a}+1$$
So that now the problem is whether
$$\forall m \forall n \forall a \exists k$$
such that $$ k*m-n\equiv 0\pmod a $$
Is this simplification going to work? What is the proof? is there a counterexample for it?