If $\gcd(u,m)=1$ then there exists an integer $k_1\in\Bbb Z$ such that $\gcd(mk_1+u,mk)=1$

Question

I believe that the following statement is true, but I couldn't prove it.

Let $u,m,k\in \Bbb Z$. If $\gcd(u,m)=1$ then there exists an integer $k_1\in\Bbb Z$ such that $\gcd(mk_1+u,mk)=1$ Thanks.

Answer 1

You assertion holds for $k\neq 0$, for by Dirichlet's theorem the arithmetic progression $u+hm$ for $h\in\Bbb Z$ contains infinitely many prime numbers hence at least one of them doesn't divide (and, thus, it is prime with) $mk$.

Alternatively, take $k_1$ to be the product of prime divisors of $k $ which doesn't divide $u $.

See also here.