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$

arithmeticprime factorizationprime numbers

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?

Best Answer

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.