How to prove that there exists such integer number?

Question

Let $m, n, k> 0$ and $m$ is a divisor of $n$, $\gcd(k, m) = 1$ How can I prove that there exists such integer number $\alpha$, that $\gcd(k + \alpha m, n) = 1$?

Any ideas or hints?

Thanks.

Answer 1

Let $n=mt,t\in\mathbb{N}^*$.Then $\text{gcd}(k+\alpha m,n)=\text{gcd}(k+\alpha m,mt)$.Since $\text{gcd}(m,k)=1$ it follows that $\text{gcd}(k+\alpha m,m)=1$,so $\text{gcd}(k+\alpha m,mt)=\text{gcd}(k+\alpha m,t)$.Thus we want to prove that there exists $\alpha\in\mathbb{N}$ such that $\text{gcd}(k+\alpha m,t)=1$.Here is one method to prove that(it's an overkill):

Since $\text{gcd}(k,m)=1$,by Dirichlet's Theorem it follows that the set $A=\{k+xm|x\in\mathbb{N}\}$ contains infinitely many prime numbers.Since $t$ has a finite number of prime divisors,it follows that there is some prime number $p,p\in A$ such that $\text{gcd}(p,t)=1$.Thus we can choose $\alpha=\frac{p-k}{m}$(note that $p\in A$ so the chosen $\alpha$ is a positive integer).