If d divides N, and gcd(k,d)=1, show that there exists an integer m such that gcd( k+md, N)=1.

Question

From a bit of experimentation, I believe it's true that:

If d divides N, and gcd(k,d)=1, then there exists an integer m such that gcd(k+md, N)=1.

But I am struggling to find a proof. Any ideas?

Answer 1

Since $d$ divides $N$, and $\gcd(k,d)=1$, we can write $N$ in the form $N=dmn$ such that $n=\gcd(N,k)$. Notice that $\gcd(k,m)=1$.

We will show that $\gcd(k+md,N)=\gcd(k+md,dmn)=1$. Suppose otherwise, then there is a prime number $p$ such that $p$ divides both $N=dmn$ and $k+md$ simultaneously. Since $p$ is prime, we have that $p$ divides either $d,m$ or $n$. We consider the three cases:

1. If $p$ divides $d$: then since $p$ also divides $k+md$ we conclude that $p$ divides $k$, contradicting that $\gcd(k,d)=1$.
2. If $p$ divides $m$: then $p$ divides both $k+md$ and $md$, so $p$ divides $k$, contradicting $\gcd(k,m)=1$.
3. If $p$ divides $n$: then $p$ also divides $k$ and since $p$ divides $k+md$, we conclude that $p$ divides $md$. This is absurd because $\gcd(k,m)=\gcd(d,k)=1$.

This contradiction shows that $gcd(k+md,N)=1$. $\Box$