Proving $\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)=\gcd(\text{all products $a_ib_j$})$

Question

Prove that $$\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)=\gcd(a_1b_1,a_2b_2,\ldots,a_mb_n)$$ where the parentheses on the right include all $mn$ products $a_ib_j$, $i=1,\dots,m$, $j=1,\ldots,n$

My attempt was as following:

Let $d=\gcd(a_1,\ldots,a_m)$ and $b=\gcd(b_1,\ldots,b_n)$. Then $db|a_ib_j$ for all $i=1,\ldots,m$, $j=1,\ldots,n$.

Thus $$\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)\le\gcd(a_1b_1,a_2b_2,\ldots,a_mb_n)$$

So what's left is to prove that

$$\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)\geq\gcd(a_1b_1,a_2b_2,\ldots,a_mb_n)$$

Any hint will be appreciated

Answer 1

Suppose $A=\gcd(a_1,a_2,...,a_m), B=\gcd(b_1,b_2,...,b_m), C=\gcd($all mn products of $a_ib_j)$. Define a new function $\gamma_p(x)$ to be the maximum exponent on a prime $p$. Observe that $\gamma_p(xy)=\gamma_p(x)+\gamma_p(y)$. This will be important later.

We can also define $A,B,$ and $C$ in terms of our new function.

$$A=\prod_{p|a_i} p^{\min(\gamma_p(a_1),\gamma_p(a_2),...,\gamma_p(a_m))}$$ $$B=\prod_{p|b_j} p^{\min(\gamma_p(b_1),\gamma_p(b_2),...,\gamma_p(b_n))}$$ $$\begin{align*}C&=\prod_{p|a_ib_j}p^{\min(\gamma_p(a_1b_1),\gamma_p(a_1b_2),...,\gamma_p(a_mb_n))}\\&=\prod_{p|a_ib_j}p^{\min((\gamma_p(a_1),\gamma_p(a_2),...,\gamma_p(a_m))+\min(\gamma_p(b_1),\gamma_p(b_2),...,\gamma_p(b_n))}\end{align*}$$

We can do this because of the rules of exponents and the way our new function behaves. Upon multiplying $A$ with $B$, we can see that $AB=C$. This is called the multiplicative property of the gcd. Just showing that $\gcd(a,xy)=\gcd(a,x)\gcd(a,y)$ would be enough to show this property as well.

Answer 2

Hint Suppose that a prime power $p^k$ divides the LHS (resp. RHS), show that it divides the RHS (resp. LHS).

Answer 3

Thanks to JCAA, I got an idea how to prove it. Let's call gcd$(a_1b_1,a_2b_2,.....,a_mb_n)$ as $m$ and let $p$ be one of the prime factors of $m$. Then $m$ divides $a_ib_1,..., a_ib_n$ since m is prime then it either divide $a_i$ or $b_x$ for all $x$ such that $1\le x\le n$, $x\in \mathbb{N}$

case 1: if $m|b_x$ for all $x$, then $m$ is in $\gcd(b_1,\ldots,b_n)$.

case 2: if $m|a_i$ then reapeating it for other elements we get m is in $gcd(a_1,\ldots,a_m)$

therefore $\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)\geq\gcd(a_1b_1,a_2b_2,\ldots,a_mb_n)$

so

$\gcd(a_1,\ldots,a_m)\gcd(b_1,\ldots,b_n)=\gcd(a_1b_1,a_2b_2,\ldots,a_mb_n)$