congruences

Any natural number n is one of the forms 8k , k∈N, 8k+1, 8k+2, 8k+3, 8k+4, 8k+5, 8k+6, 8k+7, k∈ N ∪{0}.

Let S(n)=9ⁿ⁺¹ -8n-9. Let' s prove it 64|S(n), where n is any of the mentioned forms, which means that 64|S(n) for any natural number n.

Let' s first notice that it is

9¹ ≡ 9 (mod 64); 9²=81 , 81 ≡ 17 (mod 64), 9² ≡ 17 (mod 64),

9³â‰¡ 9×17 (mod 64); 9×17 =153 , 153 ≡ 25 (mod 64), 9³ ≡ 25 (mod 64),

9⁴ ≡ 9×25 (mod 64); 9×25 =225 , 225 ≡33 (mod 64), 9⁴ ≡ 33 (mod 64),

9⁵ ≡ 9×33 (mod 64); 9×33 =297 , 297 ≡41 (mod 64), 9⁵ ≡ 41 (mod 64),

9⁶ ≡ 9×41 (mod 64); 9×41 =369 , 369 ≡49 (mod 64), 9⁶ ≡ 49 (mod 64),

9⁷ ≡ 9×49 (mod 64); 9×49 =441 , 441 ≡57 (mod 64), 57≡ -7 (mod 64), 9⁷ ≡ -7 (mod 64),

9⁸ ≡ -7×9 (mod 64); -7×9 =-63 , -63 ≡1 (mod 64), 9⁸ ≡ 1 (mod 64).

We have

1° n=8k, k∈N∪{0}. Then S(8k)=9×9^8k-64k-9,

S(8k)≡9×9^8k-9 (mod 64), 9×9^8k-9≡9×1-9 (mod 64),

S(8k)≡0 (mod 64) (from 9⁸≡1 (mod 64) follows 9^8k≡ 1 (mod 64)),

2° n=8k+1, k∈N∪{0}. S(8k+1)=9×9^8k+1-64k-8-9,

S(8k+1)=9²Ã—9^8k-64k-17, S(8k+1)≡9²Ã—9^8k-17 (mod 64),

9²Ã—9^8k-17≡17×1-17 (mod 64), S(8k+1)≡0 (mod 64),

3° n=8k+2, k∈N∪{0}. S(8k+2)=9×9^8k+2-64k-16-9,

S(8k+2)=9³Ã—9^8k-64k-25, S(8k+2)≡9³Ã—9^8k-25 (mod 64),

9³Ã—9^8k-25≡25×1-25 (mod 64), S(8k+2)≡0 (mod 64),

4° n=8k+3, k∈N∪{0}. S(8k+3)=9×9^8k+3-64k-24-9,

S(8k+3)=9⁴×9^8k-64k-33, S(8k+3)≡9⁴×9^8k-33 (mod 64),

9⁴×9^8k-33≡33×1-33 (mod 64), S(8k+3)≡0 (mod 64),

5° n=8k+4, k∈N∪{0}. S(8k+4)=9×9^8k+4-64k-32-9,

S(8k+4)=9⁵×9^8k-64k-41, S(8k+4)≡9⁵×9^8k-41 (mod 64),

9⁵×9^8k-41≡41×1-41 (mod 64), S(8k+4)≡0 (mod 64),

6° n=8k+5, k∈N∪{0}. S(8k+5)=9×9^8k+5-64k-40-9,

S(8k+5)=9⁶×9^8k-64k-49, S(8k+5)≡9⁶×9^8k-49 (mod 64),

9⁶×9^8k-49≡49×1-49 (mod 64), S(8k+5)≡0 (mod 64),

7° n=8k+6, k∈N∪{0}. S(8k+6)=9×9^8k+6-64k-48-9,

S(8k+6)=9⁷×9^8k-64k-57, S(8k+6)≡9⁷×9^8k-57(mod 64),

9⁷×9^8k-57≡-7×1-57 (mod 64), S(8k+6)≡0 (mod 64),

8° n=8k+7, k∈N∪{0}. S(8k+7)=9×9^8k+7-64k-56-9,

S(8k+7)=98×9^8k-64k-65, S(8k+7)≡9⁸×9^8k-65(mod 64),

9⁸×9^8k-65≡1×1-65 (mod 64), S(8k+7)≡0 (mod 64).

Therfor S(8k+j)≡0 (mod 64), j∈{0,1,2,3,4,5,6,7} whence it follows S(n)≡0 (mod 64), for any natural number n.

The task was done by Dr. Dženis Pučić at State University of Novi Pazar, Serbia.