For prime $p$, show that $p\mid a^n\Rightarrow p\mid a$

Question

I already try to solve this with divisibility rule $p = ka, a^n$ = $ka*ka$ as much as $n$ times $a^n≡a (mod n)$, then $p^n=ka*ka$ therefore $p^n= a^n$ be $^n√p^n|^n√a^n$ which $p|a$ but im not sure how right am i or wrong

Answer 1

There are several ways. You could use the contraposition for example. But I think the best way to understand the relation is the direct way.

Let $p$ be a prime with $p\mid a^n$ for some natural $a$ and $n$. If $a = p$, we are done. Now look at the unique prime decomposition of a: $$ a = p_1\cdot p_2 \cdot \dots \cdot p_k $$ where every $p_i$ is a prime number. These do not have to be distinct. Then $$ a^n = (p_1\cdot p_2 \cdot \dots \cdot p_k)^n = p_1^n \cdot p_2^n \cdot \dots \cdot p_k^n. $$ Since $p$ is a divisor of $a^n$, there is a prime number $p_i$ in this decomposition, such that $$ p\mid p_i^n. $$ But since $p$ and $p_i$ are prime, it follows that $p = p_i$ (because multiplying two numbers does not lead to new divisors). So $$ p\mid p_i\mid a \Rightarrow p\mid a. $$