Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
(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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.