# Given that $p$ is a prime and $p\mid a^n$, prove that $p^n\mid a^n$.

Given that $p$ is a prime and $p\mid a^n$, prove that $p^n\mid a^n$.

I know that the fundamental theorem of arithmetic states that any positive integer can be represented as a product of primes but how do I apply this to the proof?

• Can you convince yourself that $p | a$? – user61527 Mar 13 '14 at 22:46
• With elementary number theory, before you embark on a proof you almost always want to ask yourself why the statement is true. Once you figure out that, the ideas of how to prove it should be the same ideas you used to convince yourself of the verity of the statement. – MCT Mar 13 '14 at 23:06

Prime factorization and the Fundamental Theorem of Arithmetic can be used, but seem too high powered for this.

We can inductively show that if $p\mid a^n$ then $p\mid a$:

Clearly, it is true for $n=1$.

Suppose it is true for $n-1$, and $p\mid a^n=a\,a^{n-1}$. Since $p$ is prime, $p\mid a$ or $p\mid a^{n-1}$ either of which means that $p\mid a$.

Since $p\mid a^n$, we have that $p\mid a$ and therefore, $p^n\mid a^n$ (i.e. $a=kp\implies a^n=k^np^n$).

• Uniqueness of prime factorizations is an immediate inductive consequence of the Prime Divisor Property, i.e. prime $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b.\,$ The converse is clear. So they are equivalent. Neither is more "high-powered". – Bill Dubuque Mar 22 '14 at 15:09

Use the fundamental theorem of arithmetic to uniquely express $a$ as a product of powers of primes $$a=p_1^{r_1}\dotsb p_\ell^{r_\ell}$$ where $p_1<\dotsb<p_\ell$ and $r_i\geq1$ for $1\leq i\leq \ell$. The assumption $p\mid a^n$ then implies $p\mid p_k^{n r_k}$ for some $1\leq k\leq \ell$. It follows that $p=p_k$ since otherwise $p$ would not be prime. Hence $p^n=p_k^n$ which clearly divides $a^n$.

Since $p$ is prime and $p\mid a^n$, we have $p\mid a$. (Do you see why?) Thus $a=pk$ for some $k\in\mathbb{N}$, so $a^n=p^nk^n$. Hence $p^n\mid a^n$.

You don't need unique factorization, you just need Euclid's Proposition 12 from Book IX, that if $p\mid a^n$, then $p\mid a$, from which you can say that $a=pb$ for some $b$, hence $a^n=(pb)^n=p^nb^n$, which implies $p^n\mid a^n$, all by definition of divisibility.

• Uniqueness of prime factorizations is an immediate inductive consequence of Euclid's Lemma. The converse is clear. So they are equivalent. – Bill Dubuque Mar 22 '14 at 15:06
• @BillDubuque, Euclid's Lemma is Proposition 30 in Book VII. The proof (in Euclid) of IX.12 does not use VII.30! – Barry Cipra Mar 22 '14 at 16:46