Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2005-09-15 12:59:37

daisy
Guest

Help in Math Induction Question

prove that for every non-negative integer n , n^3 mod 6 = n mod 6.

(use mathematical induction)

#2 2005-09-15 14:16:20

ganesh
Moderator

Online

Re: Help in Math Induction Question

Put n=7.
7mod6=1
7^3mod6=343mod6=1
Put n=8
8mod6=2
8^3mod6=512mod6=2.
Assume this is true for k.
Therefore, kmod6=k^3mod6.
Try for k+1.
Lets say (k+1)mod6=m
(k+1)^3mod6 = (k^3 + 3k^2+3k+1)mod6.
= (k^3+3k^2+2k+k+1)mod6= (k^3+2k^2+k^2+2k+k+1)mod6
= [k(k^2+2)+k(k+2)+k+1]mod6...
Running out of time...gotta leave....


Character is who you are when no one is looking.

#3 2005-09-15 14:43:41

John E. Franklin
Star Member

Offline

Re: Help in Math Induction Question

P(n+1) is (n^3 + 3n^2 + 3n + 1)%6 = (n+1)%6 
and assume we start with n^3%6 = n%6, where % means mod (like in C language).
(n^3 + 3n^2 + 2n)%6 + (n+1)%6 = (n+1)%6
(n^3 + 3n^2 + 2n)%6 = 0
Substitute n%6 in place of n^3%6 and get:
(3n(n+1))%6=0
For even numbers, 3n is a multiple of 6, so that works.
For odd numbers, the (n+1) part is even, so that works.


igloo myrtilles fourmis

#4 2005-09-16 00:04:44

ganesh
Moderator

Online

Re: Help in Math Induction Question

ganesh wrote:

Put n=7.
7mod6=1
7^3mod6=343mod6=1
Put n=8
8mod6=2
8^3mod6=512mod6=2.
Assume this is true for k.
Therefore, kmod6=k^3mod6.
Try for k+1.
Lets say (k+1)mod6=m
(k+1)^3mod6 = (k^3 + 3k^2+3k+1)mod6.
= (k^3+3k^2+2k+k+1)mod6= (k^3+2k^2+k^2+2k+k+1)mod6

= {[k(k+2)+k(k+2)]+k+1}mod6
= {[(k+k)(k+2)] +k+1}mod6
={[(k(k+1)(k+2) + k+1}mod6

We know that k(k+1)(k+2) is divisble by 6 for any k>1, k∈N,
Hence the above is reduced to
(k+1)mod6

It is seen that it is true for k+1, hence, it is true for any value of k.

q.e.d smile


Character is who you are when no one is looking.

Board footer

Powered by FluxBB