# How to prove $\gcd(a,b) \cdot \gcd(c,d)=\gcd(ac,ad,bc,bd)$?

I want to prove the identity $\gcd(a,b) \cdot \gcd(c,d)=\gcd(ac,ad,bc,bd)$. I tried this: if $x=\gcd(a,b)$ and $y=\gcd(c,d)$ then I must show $xy=\gcd(ac,ad,bc,bd)$ so I think I have to use the property $\gcd(ar,br)=r\cdot \gcd(a,b)$ but I don't know how to apply it. Can someone help me?

• The same way you prove $\,(a+b)(c+d) = ac+ad+bc+bd,\,$ since gcd obeys the same laws used for the addition form (associative, distributive), so you can replace '+' by 'gcd'. – Bill Dubuque Apr 8 '17 at 21:10

Indeed you use the formula $\gcd(ar,br)=r\cdot gcd(a,b)$ twice like this: \begin{align} \gcd(a,b)\cdot\gcd(c,d) &= \gcd(a\cdot\gcd(c,d), b\cdot \gcd(c,d)) \\ &= \gcd(\gcd(ac,ad),\gcd(bc,bd)) \\ &= \gcd(ac,ad,bc,bd) \end{align}

• i.e. replace + by gcd in $\,(a\!+\!b)(c\!+\!d) = a(c\!+\!d) \!+\! b (c\!+\!d) = (ac\!+\!ad) \!+\! (bc\!+\!bd) = ac\!+\!ad\!+\!bc\!+\!bd\,$ which is valid since both operations are associative and multiplication distributes over them, i.e. the same laws hold in both cases. – Bill Dubuque Apr 8 '17 at 22:12

\begin{align*} gcd(a,b) \cdot gcd(c,d) &= gcd(c\cdot gcd(a,b),d\cdot gcd(a,b)) \\ & = gcd( gcd(ca,cb), gcd(ad,bd)) \\ & = gcd(ca,cb,ad,bd)\end{align*}

If you have access to the ideal-theoretic characterization of $\gcd$ in a principal ideal domain: $$\langle \gcd(S) \rangle = \langle S \rangle$$ for any set $S$ of elements.

We can compute the product of ideals $$\langle a,b\rangle\langle c,d\rangle = \langle ac,ad,bc,bd \rangle$$

And the product of principal ideals is $$\langle x \rangle \langle y \rangle = \langle x y \rangle$$ so we compute $$\langle \gcd(a,b) \gcd(c,d) \rangle = \langle \gcd(a,b) \rangle \langle \gcd(c,d) \rangle \\= \langle a,b \rangle\langle c,d \rangle \\= \langle ac,ad,bc,bd \rangle \\= \langle \gcd(ac,ad,bc,bd) \rangle$$

• This does not work in any gcd domain (only PIDs). – Bill Dubuque Apr 8 '17 at 21:12
• @BillDubuque nitpick: I think it works over Bezout domains, not only PIDs. – MatheinBoulomenos Apr 13 '17 at 10:39

Another way to think about this problem is the following fact: two integers $a$ and $b$ are equal when $r \mid a \implies r \mid b$ and $r \mid b \implies r \mid a$.

(This is similar to how equality works for sets, where $S=T$ when $x \in S \implies x \in T$ and $x \in T \implies x \in S$.)

Here's how you can prove one direction. Suppose $r \mid \gcd(a,b) \cdot \gcd(c,d)$. This means that either $r \mid \gcd(a,b)$ or else $r \mid \gcd(c,d)$.

• If $r \mid \gcd(a,b)$, then $r \mid a$ and $r \mid b$. Therefore $r \mid ac, r \mid ad, r \mid bc, r \mid bd$. From this, we can conclude that $r$ is a common divisor of $\{ac, ad, bc, bd\}$, so $r \mid \gcd(ac, ad, bc, bd)$.
• If $r \mid \gcd(c,d)$, then $r \mid c$ and $r \mid d$. So in this case, too, $r \mid ac, r \mid ad, r \mid bc, r \mid bd$. Once again, we can conclude that $r$ is a common divisor of $\{ac, ad, bc, bd\}$, so $r \mid \gcd(ac, ad, bc, bd)$.

Can you prove the other direction: that if $r \mid \gcd(ac, ad, bc, bd)$, then $r \mid \gcd(a,b) \cdot \gcd(c,d)$?

For any prime $p$ and $n\in\mathbb{N}$, let $e_p(n)$ be the exponent of $p$ in $n$. Then $e_p(gcd(a,b)) = min(e_p(a),e_p(b))$ and similarly for $c,d$. Also $e_p(m\cdot n) = e_p(m)+e_p(n)$. Your result follows from distributivity of $+$ over $min$.