# Product of pairwise coprime integers divides $b$ if each integer divides $b$

Let $a_1....a_n$ be pairwise coprime. That is $gcd(a_i, a_k) = 1$ for distinct $i,k$, I would like to show that if each $a_i$ divides $b$ then so does the product.

I can understand intuitively why it's true - just not sure how to formulate the proof exactly. I want to say if we consider the prime factorizations of each $a_i$, then no two prime factorizations share any prime numbers. So the product of $a_1...a_n$ must appear in the prime factorization of $b$. Is this correct? Or at least if if the idea is correct, any way to formulate it more clearly?

-

One way of arguing that avoids looking at prime factorizations is to note that $gcd(a,b)=1$ iff $a\alpha+b\beta=1$ for some integers $\alpha,\beta$.

But then, if $a,b$ both divide $c$, say $at=c$ and $br=c$ where $t,r$ are integers, we have $$ab(\alpha r+\beta t)=br(\alpha a)+at(\beta b)= c(\alpha a+\beta b)=c.$$

This explicitly shows that $ab$ also divides $c$. Now use induction.

-
(Just in case, one could ask then how to verify that if $a,b$ are each relatively prime with $c$, then also $ab$ is relatively prime with $c$, since this is what the induction relies on. But if $a\alpha+c\beta=1$ and $b\gamma+c\delta=1$, multiplying these two equations we get $ab(\alpha\beta)+c(a\alpha\delta+b\beta\gamma+c\beta\delta)=1$, and the result follows.) –  Andres Caicedo Jan 28 '13 at 23:31
Thanks, just a quick question about the inductive step. Given $a_1, .... a_{k+1}$ positive integers that satisfies the given conditions, since $gcd(a_1...a_k, a_{k+1}) = 1$, you just apply the base step again, right? –  user60018 Jan 28 '13 at 23:38
I was thinking, for example, for $a_1,a_2,a_3,a_4$, pairwise relatively prime, and all dividing $b$, you would first see that $a_1a_2$ divides $b$, then that $a_1a_2a_3$ also divides $b$, and finally that $a_1a_2a_3a_4$ does as well. –  Andres Caicedo Jan 28 '13 at 23:43
Oh okay. That makes sense. I thought my induction was a little suspicious. –  user60018 Jan 28 '13 at 23:48

If $(a_1,a_2) = 1$, then there exists integers $x,y \in \mathbb{Z}$, such that $$a_1 x + a_2 y =1 \,\,\,\,\,\, (\star)$$ We also have that $b = a_1 k_1 = a_2 k_2$.

Multiplying $(\star)$ by $k_1$, we get that $a_1k_1x + a_2k_1y = k_1 \implies a_2 k_2 x + a_2k_1 y = k_1$. Hence, $a_2 \vert k_1$. This gives us $k_1 = a_2 m$. Hence, $b = a_1 a_2 m$. Hence, $a_1 a_2$ divides $b$.

Use this inductively, to conclude what you want.

-

Use unique prime factorization for each $a_i$ to write it as $$a_i = \prod_{i=1}^k p_i^{\alpha_i}.$$ $k$ is chosen such that it will number all prime factors across the $a_i$, with $\alpha_i = 0$ when $p_i$ is not a factor of $a_i$. In other words, $k$ will be the same number for each $a_i$. By the assumption, $b$ will then be of form $$b = \prod_{i=1}^k p_i^{\beta_i} \cdot d = \prod_{i=1}^n a_i \cdot d,$$

for some integer $d$, and where $\beta_i$ is the unique (as the $\alpha_i$ are coprime, and each divide $b$) $\alpha_i \neq 0$ for all $i$. This was to be shown.

-