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 \).
1 answer