8^101+1是9的倍數 算法請教

設 f(x) = x^101 + 1

f(x) 除以 (x + 1)，餘數
= f(-1)
= (-1)^101 + 1
= -1 + 1
= 0
根據因式定律，(x^101 + 1) 可被 (x + 1) 整除。

令 x =- 8，則
(8^101 + 1) 可被 (8 + 1) 整除。
即 (8^101 + 1) 可被 9 整除。
即 (8^101 + 1) 是 9 的倍數。

8=-1(mod9)
8^101+1(mod9)
=(-1)^101+1(mod9)
=0

8^101=(9-1)^101

二項展開你將會發現8^101≡-1(mod 9)

8^2 = 1(mod 9)

8^101 + 1 (mod 9)
= (8^2)^50 乘 8^1 + 1
= 1^50乘8 + 1
=1*8 + 1
=0 (mod 9)

2013-07-07 16:51:45 補充：
這很基本喔! 務必要學會!

2013-07-07 16:56:11 補充：
fooks 方法也不錯 讓我開眼界了.