Congruency with Mod (Induction Question)

Hi,

I wanted to clarify my answer for this question. Please note if I did anything wrong.

The question uses induction.

Prove that for every positive integer n, 4^n+14 congruent 0(mod 6)

My work:

P(n): 4^n +14 congruent 0(mod6)

P(1): 4^1 +14 congruent 0(mod6)

18 congruent 0(mod6)

because 6 divides 18-0 since 6*3=18 check!

P(k): 4^k +14 congruent 0(mod6)

4^k +14 divides 6

P(k+1): 4^k +14 + 4^k+1 +14 congruent 0(mod6)


And this is a valid proof.

Am I right? Help is greatly appreciated.

Quote:

---

Originally Posted by coder752

P(k): 4^k +14 congruent 0(mod6)

4^k +14 divides 6

P(k+1): 4^k +14 + 4^k+1 +14 congruent 0(mod6)

---

The 1st line above is the induction assumption - you assume that for some arbitrary number k,

Code:

---

P(k) = 4^k + 14 is congruent to 0 (mod6).

---

Now you need to prove that:

Code:

---

P(k+1) = 4^(k+1) + 14  is congruent to 0 (mod 6).

---

However, your induction step seems incorrect.
The formula is:
P(n) = 4^n + 14

You just need to replace n with k+1 and try to manipulate the formula to a one which is divisible by 6:

Code:

---

P(k+1) = 4^(k+1) + 14 =
            = 4 * 4^k + 14 =
            = (4^k + 14) + 3 * 4^k

---

Now, (4^k+14) is divisible by 6 - this is because of the induction assumption.
3 * 4^k is also divisible by 6 because you can represent is like this:

Code:

---

3 * 4^k =  3 * 4 * 4^(k-1) = 12 * 4^(k-1) = 6 * (2 * 4^(k-1))

---

Since both (4^k + 14) and 3 * 4^k are divisible by 6, their sum must also be divisible by 6. Their sum is also equal to P(k+1) --->
P(k+1) is congruent to 0 (mod 6).
q.e.d.

Regards,
Zachm

i got a question

Code:

---

P(k+1) = 4^(k+1) + 14 =
            = 4 * 4^k + 14 =
            = (4^k + 14) + 3 * 4^k

---

in this line

Code:

---

= (4^k + 14) + 3 * 4^k

---

where you got the 3*4^k from??

and please explain this part

Code:

---

3 * 4^k =  3 * 4 * 4^(k-1) = 12 * 4^(k-1) = 6 * (2 * 4^(k-1))

---

i don't understand why do you need a 4^(k-1) and where is the 2nd 4 came from?

Quote:

---

Originally Posted by DarksMagician

in this line

Code:

---

= (4^k + 14) + 3 * 4^k

---

where you got the 3*4^k from??

---

I uses the distribution rule:

Code:

---

(a+b)*c = a*c + b*c

---

More specifically:

Code:

---

4 * 4^k = (3+1) * 4^k = 3 * 4^k + 1 * 4^k =  3 * 4^k + 4^k

---

I think that this is 6th grade math (or some lower grade).

Quote:

---

Originally Posted by DarksMagician

Code:

---

3 * 4^k =  3 * 4 * 4^(k-1) = 12 * 4^(k-1) = 6 * (2 * 4^(k-1))

---

i don't understand why do you need a 4^(k-1)

---

Well, I don't really need the 4^(k-1), I just need to show the the entire expression is divisible by 6.
Work the math from right to left and you'll see that it works.

Quote:

---

Originally Posted by DarksMagician

and where is the 2nd 4 came from?

---

It came from the power distribution rule:

Code:

---

a^(b+c) = (a^b) * (a^c)

---

Or more specific:

Code:

---

4^k = 4^(k - 1 + 1) = 4^(1 + (k-1)) = (4^1) * (4^(k-1)) = 4 * 4^(k-1)

---

Regards,
Zachm

Code:

---

4 * 4^k = (3+1) * 4^k = 3 * 4^k + 1 * 4^k =  3 * 4^k + 4^k

---

i still don't understand where you got that 3+1 from

and then
you got 3*4^k+4^k

but in your step you got (4^+14)+3*4^k then we got 3*4^k but we missing 4^k




p.s. THANK ZACHM
i really learning alot from this

Quote:

---

Originally Posted by DarksMagician

Code:

---

4 * 4^k = (3+1) * 4^k = 3 * 4^k + 1 * 4^k =  3 * 4^k + 4^k

---

i still don't understand where you got that 3+1 from

---

Well, 4 = 3 + 1, or isn't it ?

Quote:

---

Originally Posted by DarksMagician

and then
you got 3*4^k+4^k

but in your step you got (4^+14)+3*4^k then we got 3*4^k but we missing 4^k

---

This was just an example how this rule would be applied with familiar numbers. I didn't claim it to be identical to this proof step:

Code:

---

P(k+1) = 4^(k+1) + 14 =
            = 4 * 4^k + 14 =
            = (4^k + 14) + 3 * 4^k

---

Maybe I will separate it into smaller steps and elaborate each step ?

this following line just states the function for which we need to prove is congruent to 0 (mod 6):

Code:

---

P(k+1) = 4^(k+1) + 14  =

---

the nest step would be to develop the formula in a way that we will be able to claim it is divisible by 6 ( and thus congruent to 0 (mod 6) ), so we'll apply the power distribution rule on 4^(k+1):

Code:

---

          = (4 ^1) * (4^k) + 14 = 4 *(4^k) + 14 =

---

Now, we know that (4^k + 14) is congruent to 0 (mod 6) - this is due to the induction assumption, we can try to separate it so it would be multiplied individually and try to prove that the rest of the sum is also divisible by 6.
Fortunately, (4^k + 14) can be extracted easily by applying the multiplication distribution rule on 4*(4^k):

Code:

---


          =  4^k + 4^k + 4^k + 4^k + 14 =

---

The next step is just to unite 3 of the summed 4^k 's and add brackets around 4^k + 14:

Code:

---

          =  3 * (4^k) + (4^k + 14) =
              --- A ---  ---- B ---

---

The B part is divisible by 6 due to the induction assumption. All we are left to do is to show that the A part is also divisible by 6, and thus if both A and B are divisible by 6, then (A+B) is also divisible by 6 and is congruent to 0 (mod 6).

I already specified in detail in former posts how this can be done.

Regards,
Zachm

THANKS ZACHM
this really helps