Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**daisy****Guest**

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

(use mathematical induction)

**ganesh****Moderator**- Registered: 2005-06-28
- Posts: 22,093

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....

It is no good to try to stop knowledge from going forward. Ignorance is never better than knowledge - Enrico Fermi.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

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**

Offline

**ganesh****Moderator**- Registered: 2005-06-28
- Posts: 22,093

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

It is no good to try to stop knowledge from going forward. Ignorance is never better than knowledge - Enrico Fermi.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.

Offline

Pages: **1**