Thread: Induction Proof: is congruent to....

1. Induction Proof: is congruent to....

Hi Math Forum,

Any one have any solutions for this:

Prove by induction: that for every positive integer n, 4^n +14 is congruent to 0 (mod 6).

I been at it for days, any help would be greatly appreciated

2. Originally Posted by brainspasm
Prove by induction: that for every positive integer n, 4^n +14 is congruent to 0 (mod 6).
You do realize that means $\displaystyle 4^n+14$ is divisible by six for each n?
Clearly it is true for $\displaystyle n=1$. No?
Suppose that it is true for $\displaystyle n=N$ now prove it is true for $\displaystyle n=N+1$.
Look at this $\displaystyle 4^{N+1}+14=\left(4^{N+1}+4\cdot 14\right)- 4\cdot 14 +14=4\left(4^{N}+ 14\right)- 6\cdot 7$.
Is that a multiple of six?

3. hey brainspasm,
it's no so much an induction problem but a problem related to equivalence classes, note:
$\displaystyle (4^n + 14) \text{mod} 6$
$\displaystyle 4 \text{mod} 6 = 4 \wedge 14 \text{mod} 6 = 2 \wedge (4 + 2) \text{mod} 6 = 0$

Why does: $\displaystyle 4^n \text{mod} 6 = 4.4^n \text{mod} 6$ ?

And I think you're done.