Use strong induction to show for every positive integer n that if $p|a^n$ then $p|a$

Question

Use strong induction to show for every positive integer $n$ that if $p|a^n$ then $p|a$, where p is prime.

I'm not too good at proof by induction, so please correct me if my assumptions are incorrect. I think if $p|a^n$, then I need to prove $p|a^{n+1}$, but then how does that help me prove $p|a$?

Also, I'm a bit uncertain how many base cases I need to complete.

Answer 1

Edit: I am of course assuming that $p$ is prime. If this is not the case, then see Gerry Myerson's comment.

The thing with any type of induction is you need to start with a base case, which is presumably $n=1$ in this instance. It is easy to see that the base case holds (I leave it to you to write this out in your proof). Note: the base case is simply $p\mid a^1\implies p\mid a$, which is trivial.

Now the strong induction hypothesis is "suppose that $n>1$ and the result holds for all values less than $n$" and we want to show that "the result holds for $n$". More formally, we suppose that, for all $k<n$ (with $n>1$ now), we have $p\mid a^k\implies p\mid a$. Now we want to show that $p\mid a^n\implies p\mid a$.

Spoiler:

So suppose that $p\mid a^n$. Then $p\mid a^n=a^{n-1}a$ so because $p$ is prime we have $p\mid a$ or $p\mid a^{n-1}$. By the induction hypothesis, the latter case implies $p\mid a$. Note that strong induction is unnecessary here.

Answer 2

If $p$ is prime $p|ab \implies p|a$ or $p|b$

Base case $n=1$

$p|a \implies p|a$

Suppose $p|a^n \implies p|a$

We must show that $p|a^{n+1} \implies p|a$ base on the hypothesis.

$p|a^{n+1}\\ p|aa^n$

$p|a$ or $p|a^n$

If $p|a$ we are done.
If $p|a^n$ then $p|a$ by the inductive hypothesis.