# 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 $4^n+14$ is divisible by six for each n?
Clearly it is true for $n=1$. No?
Suppose that it is true for $n=N$ now prove it is true for $n=N+1$.
Look at this $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:
$
(4^n + 14) \text{mod} 6
$

$
4 \text{mod} 6 = 4 \wedge 14 \text{mod} 6 = 2 \wedge (4 + 2) \text{mod} 6 = 0
$

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

And I think you're done.