Lesson Why 3^n + 7^n - 2 is divisible by 8 for all positive integer n ?

Why is divisible by 8 for all positive integer n ?

Problem 1

Make a table for degrees  ,    and the expression  , as shown below.


    n           

   -------------------------------------------------------------------

    1		3		7		8
    2		1		1		0
    3		3		7		8
    4		1		1		0
    5		3		7		8
    6		1		1		0
    7		3		7		8
    8		1		1		0
    9		3		7		8
   10		1		1		0


From this table, you see that the sequence  is cyclic with the cycle length of 2.

It is easy to understand, because 3^2 = 9 is 1 modulo 8;  so, multiplication by 3^2 keeps the value modulo 8 THE SAME.

Therefore, the remainder  modulo 8 is cyclic with the period 2.



Similarly, from the table, you see that the sequence  is cyclic with the cycle length of 2.

It is easy to understand, too, because 7^2 = 49 is 1 modulo 8;  so, multiplication by 7^2 keeps the value modulo 8 THE SAME.

Therefore, if the remainder  modulo 8 is is cyclic with the period 2.



After that, it is clear why the expression  is zero,
and the problem is solved.

Problem 2

First, notice that 7^n and 3^n give THE SAME REMAINDER when divided by 4.


    It is because the difference

        7^n - 3^n = (7-3) * (7^(n-1) + 7^(n-2)*3 + 7^(n-3)*3^2 + . . . 7^1*3^(n-2)  + 3^(n-1))

    is divizible by 7-3 = 4.  // Recall the general formula  

        a^n - b^n = (a-b) * (a^(n-1) + a^(n-2)*b + a^(n-3)*b^2 + . . . a^1*b^(n-2)  + b^(n-1)).



Therefore, 6*7^n — 2*3^n gives the same remainder, when divided by 4, as 6*3^n — 2*3^n, 

which simply equals to  (collect like terms)  4*3^n, 

which is, obviously, divisible by 4, since it is a multiple of 4.


At this point, the statement is proved and the problem is solved, in full.