If $(N,M)=N$ and $(k,2N)=1$, does there exist $m\equiv k \pmod{2N}$ such that $(m,M)=1$?

Question

I found this claim while looking over some papers and can't seem to prove it. A possibility could be that $(m,M)=1$ should in fact be $(m,2M)=1$. Is there an elementary way to prove this that I am overlooking? Perhaps the CRT would be of some help (as it is referenced shortly after this claim) but, my intuition is not up to par to make any connection as to why. I would greatly appreciate help with this

Question: If $(N,M)=N$ and $(k,2N)=1$, does there exist $m\equiv k \pmod{2N}$ such that $(m,M)=1$?

Answer 1

The answer is yes. Let $p_1,\dots,p_n$ be the primes dividing $M$ but not $2N$. By the CRT, choose $m$ so that $m \equiv k \pmod{2N}$ and $m \equiv 1 \pmod{p_i}$ for all $i=1,\dots,n$. If $(m,M)\neq 1$, then let $q$ be a prime dividing $(m,M)$. We have both $q\mid m$ and $q\mid M$, and the latter implies that either $q\mid 2N$ or $q=p_i$ for some $i$. We cannot have $q=p_i$, because then we would have $p_i=q\mid m$ in contradiction to $m\equiv 1\pmod{p_i}$, so we must have $q\mid 2N$. Now, since $q\mid m$ and $m \equiv k \pmod{2N}$, it follows that $q\mid k$. But then we have $q\mid k$ and $q\mid 2N$, in contradiction to $(k,2N)=1$. Therefore we must have $(m,M)=1$. (Note that we did not need to use the hypothesis $(N,M)=N$.)

Answer 2

This can be solved intuitively by using a slight twist on Euclid's idea for generating new primes. Euclid employed $\,1 + p_1\cdots p_n$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too, which motivates the following

Key Idea $\, $ Coprimes to $\,c\,$ arise by partitioning into $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ all prime factors of $\,c,\,$ i.e.

Theorem $\,\ \ \color{#c00}a+\color{#0a0}b\ $ is coprime to $\ c\:$ if every prime factor of $\,c\,$ divides $\,a\,$ or $\,b,\,$ but not both.

Proof $\ $ If not then $\,a+b\,$ and $\,c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid a\,$ or $\,p\mid b.\,$ Wlog, say $\,p\mid b.\,$ Then $\,p\mid (a+b)-b = a,\,$ so $\,p\,$ divides both $\,a,b,\,$ contra hypothesis. $ $ QED

We seek $\,j\,$ so that $\ m = k + 2jN\,$ is coprime to $\,M = iN.\,$ By the above it suffices to choose $\,j\,$ so that the prime factors of $\,i\,$ are partitioned into $\,k\,$ and $\,j,\,$ e.g. let $\,j\,$ be the product of the prime factors of $\,i\,$ which do not divide $\,k.$

Remark $\ $ Note how the solution becomes quite obvious after employing Stieltjes idea, amounting to nothing but a trivial calculation of a difference of sets (of primes), i.e. the problem reduce from a problem in number theory to a trivial problem in set theory.