Re: [解題] 高一數學 餘數

[crazymars (什麼時候才有日出)]

※ 引述《linsir0825 (我不想這樣)》之銘言：
: ※ 引述《boyzone66 (打籃球ㄟ)》之銘言：
: : 1.年級：高一(其實是高三總複習的題目)
: : 2.科目：數學
: : 3.章節：數與座標係
: : 4.題目：
: : 2004的95次方 除以13的餘數是多少?
: : 5.想法：
: : 解答上是這樣寫
: : 2004的95次方 = (13‧154+2）的95次方 =13Q + 2的95次方
: : 這邊當然沒問題 也知道怎麼來的...
: : 問題是它下一步就寫2的n次方除以13的餘數依序為 2 4 1 三數循環 故所求為4
: : ＝　＝
: : 但不管我怎麼除　哪有循環？？　沒有阿.....Excel算不出這麼大的餘數 不知對還錯
不可能不會循環 因為有費馬定理 不是那個很有名的費馬最後定理

雖然你可能不知道除以13最多13個一循環

但是我很納悶的是 你用2^n 也不過最大會遇到2^12=4096 為什麼會當機咧@@"

以下mod看不懂的話 你就把≡當做兩邊餘數相等就好了

有興趣可以自己去翻一下數論的書 他的定義很簡單

而我只是覺得寫中文字很多 所以偷懶一下

2^1 ≡ 2 (mod 13)

2^2 ≡ 4 (mod 13)

2^3 ≡ 8 (mod 13)

2^4 ≡ 3 (mod 13)

2^5 ≡ 6 (mod 13)

2^6 ≡12 (mod 13)

2^7 ≡11 (mod 13)

2^8 ≡ 9 (mod 13)

2^9 ≡ 5 (mod 13)

2^10≡10 (mod 13)

2^11≡ 7 (mod 13)

2^12≡ 1 (mod 13)

所以12個一循環如題要求的是 2^95除以13的餘數為7(因為95除以12餘11)

另外實際上我不是直接去算2^12再除以13

這樣題目變成7當底數可能會算到死掉

你可以利用 (2^n)除以13的餘數

          =(2^{n-1}除以13的餘數*2)此數除以13的餘數

至於為什麼 如果妳是老師我覺得你應該要知道

如果你是學生 我希望你自己思考一下

這跟我們會討論四則運算餘數性質裡面的其中一個的簡單應用

最後提醒 由費馬定理得 除以p的餘數最多 p-1 個循環一次

所以如果今天有人問你除以97的餘數可能會算到96次

故上面那個版友的方法也是好方法

基本上太多才循環就降次吧

這樣不一定會比較慢

只是一般學生對循環比較有感覺

我用再次算一次

先觀察2^6=64除以13餘-1

   2^95

≡ 2^90*2^5      (mod 13)

≡ (2^6)^15*2^5  (mod 13)

≡ (-1)^15*32    (mod 13)

≡ (-1)(6)       (mod 13)

≡ 7             (mod 13)
: : 我算 2的95次方=10k+8 (k是整數)
: : 因為 2的n次方 個位數 2,4,8,6 循環
: : 95/4=23...3 所以個位數是8
: : 接下來我就當機了....
: : 麻煩誰幫我一下>"<
: : 拜託了
: 答案是錯的..不是4..應該為7
: 利用同餘原理：
: 1. 若a/c的餘數為r
:    那(a^b)/c的餘數 = (r^b)/c的餘數
: 2. 若a/c的餘數為r1，b/c的餘數為r2
:    那(a*b)/c的餘數 = (r1*r2)/c的餘數
: 所以這一題
:   (2009^95)/13的餘數
: = (2^95)/13的餘數
: = (32^19)/13的餘數
: = (6^19)/13的餘數
: = 216*(6^16)/13的餘數
: = 8*(36^8)/13的餘數
: = 8*(10^8)/13的餘數
: = 8*(100^4)/13的餘數
: = 8*(9^4)/13的餘數
: = 8*(81^2)/13的餘數
: = 8*(3^2)/13的餘數
: = 72/13的餘數
: = 7

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.37.131.39
推 n19860423:倒數第四行，應該是 (2^6)^15 * 2^5
※ 編輯: crazymars       來自: 114.37.131.39        (08/17 13:07)
→ crazymars:thx 已修正
推 boyzone66:我的意思是沒有2 4 1循環...我自己也有把每個餘數都算了
→ boyzone66:我所謂的當機是 這是我想到其中一個方法 但這只有到個位
推 boyzone66:而且我後來也發現 我想的方向好像不太對..
→ boyzone66:我是新手老師 我單純覺得 出這種考題這樣算很麻煩
→ boyzone66:總之 謝謝
推 boyzone66:PS 我說麻煩是指 把餘1~12的循環每個都算出來 才求餘數
推 charater:樓上 如果您有餘數可加減乘的觀念就不會這樣覺得了~