# Prove $\gcd(m, n)=\gcd(m, 2n)$

For all integers $$m$$ and $$n$$, if $$m$$ is odd, prove $$\gcd(m, n) = \gcd(m, 2n)$$. There is an external fact that can be used if both numbers are odd, their product is odd as well. I think I need to prove that every odd factor of $$n$$ is also a factor of $$2n$$, as I cannot assume this, but I am stuck with it and cannot get any ideas. Any help is appreciated!

• If $k$ divides $m$ then it must be odd. So if it also divides $2n$, then it must divide $n$. – almagest Feb 9 '19 at 18:13
• Every factor of $n$ is a factor of $2n$, odd or otherwise. If $n=a\times b$ then $2n=2\times a \times b$. – lulu Feb 9 '19 at 18:13
• Similar proof as in your prior (deleted) question: if $\,d\mid m\,$ then $\,d\,$ is odd, so $\,d\mid 2n\iff d\mid n\$ $\qquad$ – Bill Dubuque Feb 9 '19 at 18:20
• I realize it is simular, and I deleted the old one as it was duplicate. I see the proof (intuitively), I am stuck with how to prove it formally, but thanks for the hint! – r3dm1ke Feb 9 '19 at 18:27

Actually this will be true if only $$m$$ is odd.

$$m$$ is odd so it has no even divisors. So $$\gcd(m,2n)$$, which divides $$m$$ is odd.

Now here's the thing. If $$d$$ is an odd integer and if $$d|2n$$ then $$d|n$$.

Now as every divisor of $$m$$ is odd, then every common divisor of $$m$$ and $$2n$$ will be odd, so every common divisor of $$m$$ and $$2n$$ will be a common divisor of $$m$$ and $$n$$.

(And vice versa is obvious: every common divisor or $$m$$ and $$n$$ will be a common divisor of $$m$$ and $2n.) So as $$m$$ and $$2n$$ have the exact same common divisors, the greatest of these common divisors will be the same. "Now here's the thing. If $$d$$ is an odd integer and if $$d|2n$$ then $$d|n$$." But why could I say that? well.... $$d|2n$$ means there is an integer $$k$$ so that $$2n = k*d$$ so $$2|kd$$ and by Euclid's lemma as $$2$$ is prime $$2|k$$ or $$2|d$$. As $$d$$ is odd the $$2\not \mid d$$ so $$2|k$$ so $$k = 2k'$$ for so integer $$k'$$ and $$2n = 2k'*d$$ and $$n = k'*d$$ and $$d|n$$. IMPORTANT COROLLARY: If $$\gcd(m,k) = 1$$ then $$\gcd(m, kn) = \gcd(m,n)$$. $$m$$ and $$k$$ have no common divisors so any common divisor of $$m$$ and $$kn$$ will be a common divisor of $$m$$ and $$n$$ and so..... • Or (equivalently) we can use parity (vs. "$2$is prime ..."), i.e.$\,d\,$odd,$\,dk\,$even$\Rightarrow k$even, therefore cancelling$2$in$\,2n = dk\,$yields$\,n = d(k/2),\,$so$\,d\mid n\ \ $– Bill Dubuque Feb 10 '19 at 0:15 • Is that easier to say or to follow? I don't know. But Euclid's Lemma should be learned eventually. Well, I guess maybe to be consistent with even/odd arguments... Still, I feel a bit uneasy saying$d$odd and$dk$even implies$k$is even. We can't take it for granted but on the other hand it's a tedious distraction to spell out... I don't know... – fleablood Feb 10 '19 at 2:06 • I suppose an easy question deserves an easy answer. If$m$and$k$have no factors in common then the only factors$m$and$kn$will have in common will be factors of$n$and that's it.... except... why can't$kn$have a factor in common with$m$that neither$k$nor$n\$ has? .... Well, we'll need to introduce Euclid's Lemma/Unique prime factorization some time. Not sure which is the easiest for the student to grasp. – fleablood Feb 10 '19 at 2:11
• It's just in case the OP hasn't learned the more advanced methods yet. Also the parity arguments provide motivation for the generalizations. That's where we all started with modular reasoning - even if we've long forgotten! – Bill Dubuque Feb 10 '19 at 2:12

Consider the primes $$p_1=2,\ p_2=3,\ p_3=5\dots p_k\le \max(m,n).

$$m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k};\ \alpha_i \ge 0$$. Note that many of the exponents $$\alpha$$ will be $$0$$ in this formulation, since it is not possible that $$n$$ has every prime $$\le \max(m,n)$$ as a factor. Since $$m$$ is stated to be odd, we know that $$\alpha_1=0$$.

Similarly, $$n=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$$, and $$2n=p_1^{\beta_1+1}p_2^{\beta_2}\cdots p_k^{\beta_k}$$. Here also, many of the exponents $$\beta$$ will be $$0$$.

$$\gcd(m,n)=p_1^{\min(\alpha_1,\beta_1)}p_2^{\min(\alpha_2,\beta_2)}\cdots p_k^{\min(\alpha_k,\beta_k)}$$ and $$\gcd(m,2n)=p_1^{\min(\alpha_1,\beta_1+1)}p_2^{\min(\alpha_2,\beta_2)}\cdots p_k^{\min(\alpha_k,\beta_k)}$$

Note that these two products have identical factors except for $$p_1^{\min(\alpha_1,\beta_1)}$$ and $$p_1^{\min(\alpha_1,\beta_1+1)}$$. But since $$\alpha_1=0$$, $$\min(\alpha_1,\beta_1)=\min(\alpha_1,\beta_1+1)=0$$ and $$p_1^{\min(\alpha_1,\beta_1)}=p_1^{\min(\alpha_1,\beta_1+1)}=1$$.

Since the non-identical factors are equal, and all other factors are identical, it follows that $$\gcd(m,n)=\gcd(m,2n)$$

We wish to show that $$\gcd(m,n)=\gcd(m,2n)$$ where $$m$$ is odd. Let $$k=\gcd(m,n)$$, then the prime factorization of $$k$$ is the intersection of the set of prime factors of $$m$$ and $$n$$. For example, if $$m=21=\color{red}{3}\cdot7$$ and $$n=36=2\cdot2\cdot \color{red}{3} \cdot3$$ then $$\gcd(21,36)=3$$ Notice here that $$\gcd(21,72)$$ is still $$3$$.

Generally, given that $$m$$ is odd, $$2$$ is not in its prime factorization, so if $$P_{m}$$ is the set of prime factors of $$m$$ and $$P_{n}$$ is the set of prime factors of $$n$$, we note that $$2 \notin P_{m}$$ and therefore $$P_{m} \cap P_{n} = P_{m} \cap \{2 \cup P_{n}\}$$ i.e., $$\gcd(m,n)=\gcd(m,2n)$$ given that $$m$$ is odd.

• I'm okay with down-votes, but I wish I knew why! – Carser Feb 9 '19 at 21:27