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$

Solution 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.