Prove that if $a, b$ are both even then $\gcd(a,b) = 2\cdot\gcd(a/2,b/2)$.

Little confused here. I have tried the following but it's basically just repeating the proof unfortunately:

  • $a = 2 \cdot a_1 $ and $ b = 2 \cdot b_1$ (Take factor of 2 out)
  • $d = \gcd(a,b)$
  • $d = 2\gcd(a_1, b_1)$
  • $a/2 = a_1$ and $b/2 = b_1$

I've even confused myself! Could someone help!


Following the first bullet, we let

  • $a = 2a_1,\;b = 2b_1$, since we are given that $a, b$ are even.

Then why don't write $\gcd(a, b)$ in terms of the above equalities: $$\begin{align} \gcd(a, b) & = \gcd(2a_1, 2b_1) \tag{1}\\ \\ & = 2\gcd(a_1, a_2) \tag{2} \end{align} $$

Now, by our bullet, solving for $a_1, a_2$, we get $a_1 = \dfrac{a}{2},\;\;b_1 = \dfrac b2$ (which is your last bullet!)

Now, the only step left is to just substitute these values of $a_1, b_1$ into $(2)$, and you're done!

| cite | improve this answer | |
  • $\begingroup$ Like this? a = 2a1 and b = 2b1 (Take factor of 2 out) then... gcd(a,b) = gcd(2a1, 2b1) = 2*gcd(a1, b1) $\endgroup$ – mino Apr 28 '13 at 19:51
  • $\begingroup$ Yes, exactly: now see what I added: what do $a_1, b_1$ equal? $\endgroup$ – amWhy Apr 28 '13 at 19:54
  • 2
    $\begingroup$ @mino and AmWhy: Unfortunately this is not a correct proof unless you have already proved the gcd distributive law $\rm\:gcd(ab,ac) = a\,gcd(b,c)\ $ [or a sufficent special case]. Have you? $\endgroup$ – Math Gems Apr 28 '13 at 20:24

With the notation $\rm\ (x,y) := gcd(x,y),\ $ we have $\rm\:2(m,n)\mid 2m,2n\:\Rightarrow\:\color{#c00}{2(m,n)\mid (2m,2n)},\:$

$\rm\ (2m,2n)\mid 2m,2n\:\Rightarrow\: (2m,2n)/2\mid m,n\:\Rightarrow\:(2n,2m)/2\mid (m,n)\:\Rightarrow\:\color{#c00}{(2n,2m)\mid 2\,(m,n)}.$

Remark $\ $ Note that $\rm\:(2m,2n)/2\in\Bbb Z\:$ since $\rm\: 2\mid 2n,2m\:\Rightarrow\:2\mid (2n,2m)$

The proof exploits to the hilt the fundamental universal property of the gcd, i.e.

$$\rm a\mid b,c\iff a\mid(b,c)$$

Note that the same proof works if we replace $2$ by any integer $\ne 0,\,$ yielding the

GCD Distributive Law $\rm\ \ \ (ac,bc)\, =\, (a,b)c$

See here for a few proofs (by linearity (Bezout); universality; prime factorization), e.g. the following more efficient version of the original proof above.

Theorem $\rm\ \ (a,b)\,c\, =\, (ac,bc)$

Proof $\rm\quad\: d\mid(a,b)\iff d\ |\ a,b \iff dc\ |\ ac,bc \iff dc\ |\ (ac,bc) \iff d\ |\ (ac,bc)/c$

| cite | improve this answer | |

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