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

| cite | improve this answer | |
$\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$ – Gone 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*}$$

| cite | improve this answer | |
$\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 $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This does not work in any gcd domain (only PIDs). $\endgroup$ – Gone Apr 8 '17 at 21:12
  • $\begingroup$ @BillDubuque nitpick: I think it works over Bezout domains, not only PIDs. $\endgroup$ – Lukas Heger 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)$?

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\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.