elementary number theory - Prove That $3^n + 8^n$ is Not Divisible by $5$ (Using Induction)

Prove that $3^n+8^n$ is not divisible by 5.

I know that this can be proved by using congruence and I am providing the proof by congruence below. But is there any way to Prove It By Induction.

The proof by congruence goes like this:

$3\equiv 3\pmod 5 \\ 3^2 \equiv 4\pmod 5 \\ 3^3\equiv 7\pmod 5 \\ 3^4\equiv 1\pmod 5 \\ 3^5\equiv 3\pmod 5$

Also,

$8\equiv 3\pmod 5 \\ 8^2 \equiv 4\pmod 5 \\ 8^3\equiv 7\pmod 5 \\ 8^4\equiv 1\pmod 5 \\ 8^5\equiv 3\pmod 5$

Adding the congruence up (since the same cycle repeats after the 4th power) none of them are divisible by 5 or equal to 0.

But I need a proof by Induction.

Any help will be appreciated.

Answer

=====Answer 3:======

It's important that one realizes that whenever they use an argument that a pattern repeats or an observation will recur indefinitely, they are fundamentally relying upon and using the Principal of induction. To wit:

They are showing something is true for a few base cases; They are (hopefully-- sometimes this step is weak---) that if it is true for some cases is will follow through for the next cases; and they make it clear that this will repeat and be true for an infinite or indefinite number of iterations.

So your argument is an argument of induction.

You've shown for base cases: $n = 1,2,3,4,5$ That $3^n + 8^n $ are none divisible by $4$.

You state that the cycle repeats. (You actually need to give a reason why the cycle repeats. That is why if $3^n + 8^n\equiv K \pmod 5$ why $3^{n+4} + 8^{n+4} $ is also $\equiv K \pmod 5$. You just noticed that $3^{5} \equiv 3^{1}$ and $8^{5} \equiv 8^{1}$ and assumed that means it is true for all $n$ and $n + 4$. You have to justify this.)

And therefore you concluded it is true for all $n$.

It is a principal if induction that allows you to conclude this.

So if you can give a reason why $3^{n+4}\equiv 3^{n}$ and $8^{n+4}\equiv 8^n$ you would be done.

(Hint: $3^{n+4} = 3^{n-1}3^5\equiv 3^{n-1}3^1 \equiv 3^n\pmod 5$. That is, after all, the reason you assumed the cycle repeated, isn't it?)

===== Answer 2: =======

You DID a proof by induction!

Notice the key phrase in you proof and the phrase that assures that you are done is:

since the same cycle repeats after the 4th power

This means that if it is true for $3^n + 8^n$ it will be true for $3^{n+4} + 8^{n+4}$ and so by induction:

As you showed a Base case that it is true for $n = 1,2,3, 4$ (as well as $n=5$ and an induction case that if it is true for $n$, we can conclude it it true for all $n = 1+4k, 2+4k, 3+4k, 4+4k$. WHich means it is true for all $n$.

That IS a prove by induction.

....

But another proof by induction follows.

===== Answer 1: ======

Well, follow the rules of a proof by induction.

Base case: $n=1$

$3^1 + 8^1 =11 $ which is not divisible by $5$.

Base case done:

Inductive case:

Assume that $3^n + 8^n$ is not divisible $5$.

Now we need to prove that thereform $3^{n+1} + 8^{n+1}$ is not divisible by $5$.

Now my advice is that when you need to prove something about $P(n+1)$ is to put it into terms of $P(n)$ and use what you know about $P(n)$.

$3^{n+1} + 8^{n+1} = 3*3^n + 8*8^n = 3*3^n + 3*8^n + 5*8^n= 3*(3^n + 8^n) + 5*8^n$ and....

$5$ is prime. $5\not \mid 3$ and $5\not \mid (3^n + 8^n)$ and $5|5*8^n$ so $5 \not \mid 3*(3^n+8^n) + 5*8^n$.

Induction step done.

Principal of induction declares we are done. Base case: $3^n + 8^n$ is not divisible by $5$ for $n = 1$. Induction case: If $3^n+8^n$ is not divisible by $5$ for a value of $n$ then in will not be divisible by $5$ for the next value of $n$. Therefore: As we can get to all values of $n$ by starting at $1$ and then going the next, and the next after that, and so on.... it must be true that $3^n +8^n$ is not divisible by $5$ for any natural $n$.

By the way...