Prime Divides Power

Theorem

Let $p$ be a prime number.

Let $a, b$ be integers.

Then $p$ divides $a^n$ iff $p^n$ divides $a^n$.

Proof

• Let $p^n \backslash a^n$.

We have $p \backslash p^n$ as $p \left({p^{n-1}}\right)$.

From the fact that divides is transitive, we have that $p \backslash a^n$.

• Let $p \backslash a^n$.

Using Euclid's Lemma for Prime Divisors with $a_1 = a_2 = \cdots = a_n = a$ we have that $p \backslash a^n \implies p \backslash a$.

Hence $a = p r$ for some $r \in \Z$.

Raising both sides of the equation to the power $n$ we get that $p^n = a^n r^n$.

So $p^n \backslash a^n$.

$\blacksquare$