Let $a,b,c,d$ be positive integers such that $ab=cd$. Prove that $\gcd(a,c)\gcd(a,d) = a\gcd(a,b,c,d).$

Question

Let $a,b,c,d$ be positive integers such that $ab=cd$. Prove that

$\gcd(a,c)\gcd(a,d) = a\gcd(a,b,c,d).$

I wasn't sure how to approach this so I arbitrarily substituted variables for $\gcd(a,c), \gcd(a,d),$ and $\gcd(a,b,c,d)$ and rewrote the first equality in search for some sort of solvable Diophantine equation or GCD property with little luck. Could someone explain how they attacked this type of problem? Thanks.

Answer 1

Following a corrected version of lab bhattacharjee's hint . . .

Let $p$ be an arbitrary prime, and let $A,B,C,D$ be the highest powers of $p$ which divide $a,b,c,d$, respectively.

The highest power of $p$ which divides $ab$ is $A+B$, and the highest power of $p$ which divides $cd$ is $C+D$, hence, since $ab=cd$, we have $$A + B = C + D$$ The highest power of $p$ which divides the gcd of a set of one or more positive integers is the least of the highest powers of $p$ dividing the members of the set, hence the highest powers of $p$ for $$\gcd(a,c)\gcd(a,d)$$ $$\text{and}$$ $$a\gcd(a,b,c,d)$$ will be equal if and only if $$\min(A,C)+\min(A,D) = A+\min(A,B,C,D)$$ Consider $4$ cases . . .

Case $(1)$: $\min(A,B,C,D) = A$. \begin{align*} \text{Then}\;\;&\min(A,C)=A\\[4pt] &\min(A,D)=A\\[4pt] &\min(A,B,C,D)=A\\[4pt] \end{align*} hence $$\min(A,C)+\min(A,D) = A + A = A+\min(A,B,C,D)$$ as required.

Case $(2)$: $\min(A,B,C,D) = B$.

Then $A+B=C+D \implies \max(A,B,C,D) = A$, \begin{align*} \text{so}\;\;&\min(A,C)=C\\[4pt] &\min(A,D)=D\\[4pt] &\min(A,B,C,D)=B\\[4pt] \end{align*} hence $$\min(A,C)+\min(A,D) = C+D = A + B = A+\min(A,B,C,D)$$ as required.

Case $(3)$: $\min(A,B,C,D) = C$.

Then $A+B=C+D \implies \max(A,B,C,D) = D$, \begin{align*} \text{so}\;\;&\min(A,C)=C\\[4pt] &\min(A,D)=A\\[4pt] &\min(A,B,C,D)=C\\[4pt] \end{align*} hence $$\min(A,C)+\min(A,D) = C+A = A + C= A+\min(A,B,C,D)$$ as required.

Case $(4)$: $\min(A,B,C,D) = D$.

Then $A+B=C+D \implies \max(A,B,C,D) = C$, \begin{align*} \text{so}\;\;&\min(A,C)=A\\[4pt] &\min(A,D)=D\\[4pt] &\min(A,B,C,D)=D\\[4pt] \end{align*} hence $$\min(A,C)+\min(A,D) = A + D = A+\min(A,B,C,D)$$ as required.

Thus, in all $4$ cases, we have $$\min(A,C)+\min(A,D) = A+\min(A,B,C,D)$$

Since for all primes $p$, the highest power of $p$ which divides $$\gcd(a,c)\gcd(a,d)$$ is the same as the highest power of $p$ which divides $$a\gcd(a,b,c,d)$$ it follows that $$\gcd(a,c)\gcd(a,d) = a\gcd(a,b,c,d)$$ as was to be shown.

Answer 2

Simplifying the gcd notation to $(a,b)$, etc., note first that for any four numbers,

$$(a,b,c,d)=((a,b,c),d)=((a,b),c),d)=((a,b),(c,d))$$

with any permutations of the variables. This is because for each prime the gcd picks out the least power that divides the numbers under consideration.

Note next that $m(a,b)=(ma,mb)$ in general. Together, these equalities imply

$$\begin{align} (a,c)(a,d)&=(a(a,c),d(a,c))\quad\text{letting }m=(a,c)\\ &=(a(a,c),(ad,cd))\quad\text{letting }m=d\\ &=(a(a,c),(ad,ab))\quad\text{using }ab=cd\\ &=(a(a,c),a(d,b))\\ &=a((a,c),(d,b))\\ &=a(a,c,d,b)\\ &=a(a,b,c,d) \end{align}$$

Answer 3

Hint $\ \ \rm \color{#c00}{ab = cd}\ \Rightarrow\ (a,c)\,(a,d)\, =\ (aa,\color{#c00}{cd},ac,ad)\, =\, \color{#c00}a\,(a,\color{#c00}b,c,d)$

using basic GCD laws (distributive, commutative, associative). More clearly, in infix notation

$\qquad\ \ \ \rm \color{#c00}{ab = cd}\ \Rightarrow\, (a\dot+c)\,(a\dot+d) = aa\dot+\color{#c00}{cd}\dot+ac\dot+ad = \color{#c00}a(a\dot+\color{#c00}b\dot+c\dot+d)$

just like polynomial arithmetic, writing the gcd $(x,y) = x\dot+ y$ in infix notation to highlight its analogy with addition (both are associative, commutative, and multiplication distributes over them, which are the only special laws used above). See the note here for another example.

Remark $ $ If you study ideal theory you will encounter such additive notation for gcds. Namely, in a PID we have $\ (\gcd(a,b)) = (a)+(b)\,$ is an ideal sum, and the above laws hold true. One can unify the gcd and ideal proofs by using divisor theory.