Question

Prove by induction that 5 to the power n, plus 3 is divisible by 4

Answer 1

To prove that \( 5^n + 3 \) is divisible by 4 for all integers \( n \geq 0 \), we will use mathematical induction.

**Base case:** We start with \( n = 0 \).

\[
5^0 + 3 = 1 + 3 = 4
\]

Since \( 4 \) is divisible by \( 4 \), the base case holds.

**Inductive step:** Now, we will assume that the statement is true for some integer \( k \); that is, we assume:

\[
5^k + 3 \equiv 0 \pmod{4}
\]

This means that \( 5^k + 3 \) is divisible by \( 4 \). This is our inductive hypothesis.

We need to show that the statement also holds for \( k+1 \), i.e., we need to show that:

\[
5^{k+1} + 3 \equiv 0 \pmod{4}
\]

We can write \( 5^{k+1} \) as follows:

\[
5^{k+1} = 5^k \cdot 5
\]

Now we break this down under modulo \( 4 \). First, we compute \( 5 \mod 4 \):

\[
5 \equiv 1 \pmod{4}
\]

Thus, we have:

\[
5^{k+1} \equiv 5^k \cdot 5 \equiv 5^k \cdot 1 \equiv 5^k \pmod{4}
\]

Now we can use our inductive hypothesis:

\[
5^k + 3 \equiv 0 \pmod{4} \implies 5^k \equiv -3 \equiv 1 \pmod{4}
\]

So we substitute back:

\[
5^{k+1} \equiv 5^k \equiv 1 \pmod{4}
\]

Now we can combine it with our original claim for \( k + 1 \):

\[
5^{k+1} + 3 \equiv 1 + 3 \equiv 4 \equiv 0 \pmod{4}
\]

Thus, \( 5^{k+1} + 3 \) is also divisible by \( 4 \).

**Conclusion:** By mathematical induction, we have shown that \( 5^n + 3 \) is divisible by \( 4 \) for all integers \( n \geq 0 \).