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!

  • $\begingroup$ If $k$ divides $m$ then it must be odd. So if it also divides $2n$, then it must divide $n$. $\endgroup$ – almagest Feb 9 '19 at 18:13
  • $\begingroup$ Every factor of $n$ is a factor of $2n$, odd or otherwise. If $n=a\times b$ then $2n=2\times a \times b$. $\endgroup$ – lulu Feb 9 '19 at 18:13
  • $\begingroup$ 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$ $\endgroup$ – Bill Dubuque Feb 9 '19 at 18:20
  • $\begingroup$ 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! $\endgroup$ – 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.....

| cite | improve this answer | |
  • $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Feb 10 '19 at 0:15
  • $\begingroup$ 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... $\endgroup$ – fleablood Feb 10 '19 at 2:06
  • $\begingroup$ 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. $\endgroup$ – fleablood Feb 10 '19 at 2:11
  • $\begingroup$ 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! $\endgroup$ – 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)<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)$

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ I'm okay with down-votes, but I wish I knew why! $\endgroup$ – Carser Feb 9 '19 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.