Prime Decomposition Divisor

Theorem

Let $a, b \in \Z_+$.

Then $a \backslash b$ iff every prime in the decomposition of $a$ appears in the decomposition of $b$ and its exponent in $a$ is less than or equal to its exponent in $b$.

Proof

Let $a, b \in \Z_+$. Let their prime decompositions be:

• $a = p_1^{k_1} p_2^{k_2} \ldots p_n^{k_n}$
• $b = q_1^{l_1} q_2^{l_2} \ldots q_n^{l_n}$

• Suppose every prime in the decomposition of $a$ appears in the decomposition of $b$ and its exponent in $a$ is less than or equal to its exponent in $b$.

Then we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle b\)	\(=\)	\(\displaystyle p_1^{l_1} p_2^{l_2} \cdots p_r^{l_r} \ldots p_s^{l_s}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

where $k_1 \le l_1, k_2 \le l_2, \ldots, k_r \le l_r, r \le s$.

Thus $d = p_1^{l_1-k_1} p_2^{l_2-k_2} \ldots p_r^{l_r-k_r} \in \Z$ and $b = a d$.

So $a \backslash b$.

• Now suppose $a \backslash b$.

Let $a = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$ be the prime decomposition of $a$.

Then $\forall i \in \N_r: p_i^{k_i} \backslash a$. Hence by Divides is Ordering on Positive Integers it also divides $b$.

Thus $\exists c \in \Z: b = p_i^{k_i} c$.

The prime decomposition of $b$ is therefore:

$b = p_i^{k_i} ($ prime decomposition of $c)$

which may need to be rearranged.

So $p_i$ must occur in the prime decomposition of $b$ with an exponent at least as big as $k_i$.

The result follows.

$\blacksquare$