Prove that if $k\mid q_1...q_n$ then we can find $k_i$ such that $k=k_1...k_n$ and for every $i$, $k_i\mid q_i$

Question

Let $k=8$ and $q_1=12$, $q_2=2, q_3=5$. We note that $k\mid q_1q_2q_3$, but $k\nmid q_1$ and $k\nmid q_2$ and $k\nmid q_3$.
Also

$$ 8=k_1k_2k_3=4*2*1, $$

where $k_1\mid q_1$, $k_2\mid q_2$, and $k_3\mid q_3$.

I want to prove that if $k\mid q_1...q_n$, then we can find $k_i$ such that $k=k_1...k_n$ and for every $i$ holds $k_i\mid q_i$, like in the example of the beginning.

---

My idea is to descompose every $q_i$ in prime numbers by the Fundamental theorem of aritmethic. Then

$$ q_1...q_n=p_1^{a_1}...p_s^{a_s}. $$

So if $k\mid q_1...q_n$, then

$$ k=p_1^{b_1}..p_s^{b_s} $$

and

$$ 0\leq b_i\leq a_i. $$

Now I know every $q_i$ is a combination of powers of $p_i$ so if want to make a $k_i$ such that $k_i\mid q_i$, the $k_i$ should be a combination of this $p_i$ and its exponent should be less than $b_i$, let's call it $c_{i,j}$. Then $\sum_{j=1} c_{i,j}=b_i$.
(Do I make myself clear?)

In the example $$q_1\cdot q_2\cdot q_3=(2^2\cdot 3)\cdot(2)\cdot(5)=2^3\cdot3\cdot5$$ then $$8=2^{b_1}\cdot3^{b_2}\cdot5^{b_3}$$ Obviously by the FTA $b_1=3$, $b_2=0$, $b_3=0$

Note $q_1$ and $q_2$ has powers of $2$ then we need $c_{1,1}$ and $c_{1,2}$

$c_{1,1}=2$ and $c_{1,2}=1$ and it verify $c_{1,1}+c_{1,2}=2+1=3=b_1$

Then

$k_1=2^{c_{1,1}}\cdot 3^{b_2}=2^2\cdot3^0=4$

$k_2=2^{c_{1,2}}=2^1=2$

$k_3=5^{b_3}=5^0=1$

---

I don't know how to make more clear my proof or if it is incorrect or just I don't proof anything. Can you help me please?

Answer 1

It is easier to prove for $n=2$ and then by induction on $n.$

If $k\mid q_1q_2,$ then let $k_1=\gcd(k,q_1).$ Then $$\frac k{k_1}\mid\frac{q_1}{k_1}q_2,\\\gcd\left(\frac k{k_1},\frac {q_1}{k_1}\right)=1,$$ so $$\frac k{k_1}\mid q_2.$$

So letting $k_2=k/k_1,$ we get our result.

The induction step is easy.

---

The above argument uses the results:

Result 1: If $a,b$ are non-zero integers then $$\gcd\left(\frac{a}{\gcd(a,b)},\frac b{\gcd(a,b)}\right)=1.$$

And:

Result 2: If $u,v,w$ are integers such that $u\mid vw$ with $\gcd(u,v)=1$ then $u\mid w.$

Both of these can be proven by Bèzout’s identity.

Answer 2

We can generalize this as follows: if

$$x_1 \cdot \cdots x_m = y_1 \cdot \cdots y_n$$

then there exists $a_{ij}$ such that $$x_i = \prod_j a_{ij} \\ y_j = \prod_i a_{ij}$$

In other words, there exists a matrix $(a_{ij})$ such that the $x_i$'s are the row products and $y_j$'s are the column products.

Now, if we were working in a commutative group, that would be trivial. But it also works in $(\mathbb{N}, +)$, $(\mathbb{N}_{+}, \cdot)$ or products of them. An illuminating proof for $(\mathbb{N}_{+}, \cdot)$ can be had using Schreier refinement theorem for the group $\mathbb{Z}/N$, with $N = x_1 \cdots x_m = y_1 \cdots y_n$, that also provides directly a formula for the $a_{ij}$