3的100次方除以7的餘數?

Question

3的100次方除以7的餘數?

(如果知道log算法的也附送一下)

Answer 1

我用的是二項式定理

3^100=(3^2)^50=9^50

9^50=(7+2)^50=(50,0)(7^50)(2^0)+(50,1)(7^49)(2^1)+
..........+(50,49)(7^1)(2^49)+(50,50)(7^0)(2^50)

上式只要7的次方大於0就可以被7整除
所以接下來只需觀察)(50,50)(7^0)(2^50)

(50,50)(7^0)(2^50)=2^50=[(2^3)^16](2^2)=4(8^16)
=4(7+1)^16 再用上面的方法 4先擱置一旁

(7+1)^16=(16,0)(7^16)+(16,1)(7^15)(1^1)+...........
+(16,15)(7^1)(1^15)+(16,16)(7^0)(1^16)

同樣的只要7的次方大於0就可以被7整除
只剩下(16,16)(7^0)(1^16)不能被7整除

(16,16)(7^0)(1^16)=1 這時候就把剛剛擱置一旁的4乘回來

4*1=4

4/7=0.......4

所以3^100除以7的餘數是4


(50,50):C50取50

Answer 2

3^1/7......餘3 第一項
3^2/7......餘2 第二項
3^3/7......餘6 第三項
3^4/7......餘4 第四項
3^5/7......餘5 第五項
3^6/7......餘1 第六項
3^7/7......餘3 第七項
每6個循環一次，100/6＝16....4
所以是第四項
3^100/7 餘數是4
（算下一項的餘數只要把前一項的餘數乘3除7就可以了不用全部乘開再除7）

Answer 3

3/7餘3 3^2/7餘2 3^3/7餘6 3^4/7餘4 3^5/7餘5 3^6/7餘1 3^7/7餘3
所以 3^96/7餘1 3^97/7餘3 3^98/7餘2 3^100/7餘4

2007-08-18 14:56:58 補充：
給海豹頭:3的7次方=2187,除以7會餘3而非0

Answer 4

3^100 的個位數字 是 1 不是 0

2007-08-18 11:51:59 補充：
3^100 = 515377520732011331036461129765621272702107522001

Answer 5

3^100 mod 7
=((3^6)^16)*(3^4) mod 7
=(729^16)*(81) mod 7
=(1^16)*4 mod 7
=1*4 mod 7
=4 mod 7