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

Question

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!

Answer 1

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.....

Answer 2

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.

Answer 3

Consider the primes $p_1=2,\ p_2=3,\ p_3=5\dots p_k\le \max(m,n)<p_{k+1}$.

$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)$