急~20點~數學-2604的81次方被17除之餘數

Question

各位大大

急~期中考題目

1.2604的81次方被17除之餘數是多少?
2.2604的87次方被17除之餘數是多少?
3.2604的88次方被17除之餘數是多少?

20點~謝謝

跪求

Answer 1

" ≡ "
a ≡ b ( mod n ) 表 a 跟 b 被 n 除了以後 有相同的餘數
ex. 7 ≡ 9 ( mod 2 ) . 11 ≡ 8 ( mod 3 )
Thm:
If p is a prime , & gcd ( a , p ) = 1
=> a^ ( p - 1 ) ≡ 1 ( mod p )
舉個例子 3 是個 質數
7 跟 3 互質
所以 7^( 3 - 1 ) = 49 ≡ 1 ( mod 3 )
1. 17是個質數 且 gcd ( 2604 , 17 ) = 1
=> 2604^ ( 16 ) ≡ 1 ( mod 17 )
=> ( 2604^ ( 16 ) )^5 = 2604^80 ≡ 1 ( mod 17 )
=> 2604^81 = 2604^80 * 2604 ≡ 1 * 2604 ≡ 3 ( mod 17 )
所以 第一題答案 3
2. 2604^87 = 2604^80 * 2604^7 ≡ 1 * 2604^7
≡ 1 * 3^7 = 2187 ≡ 11 ( mod 17 ) #
3. 2604^88 = 2604^87 * 2604 ≡ 11 * 2604 ≡ 11 * 3 = 33
≡ 15 ( mod 17 ) #

2007-11-28 11:50:42 補充：
呵呵...謝謝指正XD

33 = 1 * 17 + 16

Answer 2

1.因為 2604 = 3 (mod 17)，所以 2604^81 = 3^81 (mod 17)
又3^16 = 1 (mod=17) 這裡要辛苦一下
所以2604^81=3^81=(3^16*5)*3=1*3=3 (mod=17)
答案是:3

2.因為 2604 = 3 (mod 17)，所以 2604^87 = 3^87 (mod 17)
又3^16 = 1 (mod=17)
所以2604^87=3^87=(3^16*5)*3^7=1*2187=11 (mod=17)
答案是:11

3.因為 2604 = 3 (mod 17)，所以 2604^88 = 3^88 (mod 17)
又3^16 = 1 (mod=17)
所以2604^88=3^88=(3^16*5)*3^8=1*6561=16 (mod=17)
答案是:16

希望對你有幫助

Answer 3

2604/17=?.....3
2604^2/17=?.....9=3^2
2604^3/17=?.....10=3^3/17的餘數
2604^4/17=?.....13=3^4/17的餘數
2604^5/17=?.....5=3^5/17的餘數
2604^6/17=?.....15=3^6/17的餘數
2604^7/17=?.....11=3^7/17的餘數
2604^8/17=?.....16=3^8/17的餘數
...........
2604^16/17=?.....1=3^16/17的餘數
2604^17/17=?.....3=3^17/17的餘數
2604^18/17=?.....9=3^18/17的餘數
.........
所以
1. 2604的81次方被17除之餘數=2604的(16*5+1)次方被17除之餘數
=2604的1次方被17除之餘數= 3
2. 2604的87次方被17除之餘數=2604的(16*5+7)次方被17除之餘數
=2604的7次方被17除之餘數= 11
3. 2604的88次方被17除之餘數=2604的(16*5+8)次方被17除之餘數
=2604的8次方被17除之餘數= 16

2007-11-28 11:42:49 補充：
樓上的第三題不小心算錯了,因該是16 (33/17=1....16)