Power of Prime Divides

Theorem

Let $p$ be a prime and let $k, l \in \Z_+$.

Then $p^k \backslash p^l \iff k \le l$.

Proof

• Let $k \le l$.

Then $l - k \ge 0$.

Thus $p^k, p^{l-k} \in \Z$ such that $p^l = p^k p^{l-k}$.

Thus $p^k \backslash p^l$.

• Let $p^k \backslash p^l$.

Then $\exists b \in \Z_+: p^l = p^k b$

By the Fundamental Theorem of Arithmetic, $b$ has a unique decomposition.

Either $b = 1$ (in which case $k - l$) or have a prime decomposition consisting entirely of $p$'s.

In this case, $\exists m \in \Z: b = p^m$.

Hence, $p^{l-k} = p^m$.

Thus from the Fundamental Theorem of Arithmetic, $l - k = m > 0$.

Thus $l > k$.

The result follows from combining the two cases.

$\blacksquare$