2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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'. $\endgroup$ – Bill Dubuque Apr 8 '17 at 21:10
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Apr 8 '17 at 22:12
3
$\begingroup$

$$\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*}$$

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.