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!
Consider the primes $p_1=2,\ p_2=3,\ p_3=5\dots p_k\le \max(m,n)&lt;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)$
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.