Search
［趣味數學］大家知不知道3^1000除7的餘數是多少？
這是以前中學數學比賽非常常見的題目，秘訣在於一條非常簡單卻不在中學課程之內的數學定理—費馬小定理。
根據這定理，如果p是質數，且與a互質，那麼a^(p-1) ≡ 1 (mod p)，簡單來說a^(p-1)除p的餘數是1。
所以3^6除7的餘數是1，(3^6)^166除7的餘數是1^166 = 1，另外3^4除7的餘數是4。3^1000 除7的餘數等如(3^6)^166 x 3^4的餘數，等如1x4 = 4 ✌🏻😁
（下圖是費馬小定理的證明）
這算式好有才啊RRRRRRRRRRRRRRRRRRRRRRRR
希臘神強化符石計算公式如以下所示：
x = x0 + x1 + x2
x1 = int [ ( y + z1 ) / a ]
x2 = int [ ( y + z2 ) / b ]
z1 = ( y + z1 ) mod a
z2 = ( y + z2 ) mod b
※備註：
x = 本回合消除所產生的強化符石
x0 = 每一組 5 連消除所產生的強化符石
x1 = 自身希臘神隊長技能可產生的強化符石
x2 = 隊友希臘神隊長技能可產生的強化符石
y = 消除符石 (總消除數)
a = 自身希臘神每產生 1 顆強化符石所需累計消除的符石數
b = 隊友希臘神每產生 1 顆強化符石所需累計消除的符石數
z1 = 自身希臘神每回合消除符石的剩餘數
z2 = 隊友希臘神每回合消除符石的剩餘數
int = 將數字向下捨入至整數
mod = 前者除以後者的餘數
【摘要】
今天這集一口氣講了不少東西，從韓信點兵到同餘符號的介紹，再到中國餘式定理，然後再到 RSA 密碼系統的介紹，最後再以中國餘式定理在 RSA 上的應用。這集一開始很輕鬆，但後面很陡，這也是我做這個系列的主要精神之一，短時間內把基本到進階甚至值得研究的課題串起來。
【本系列其他影片】
上集 👉 從高中機率抽球問題，講到大學機率論的二項分布與卜松分布，最後教你如何開除員工 (https://youtu.be/gN8TWD1hvfw)
下集 👉 從高中數學排列組合的加法原理和乘法原理，講到大學離散數學的圖論的五色定理證明 (https://youtu.be/bhB5hubDgss)
【版權宣告】
本影片版權為張旭 (張舜為) 老師所有
嚴禁用於任何商業用途⛔
如果有學校老師在課堂使用我的影片的話
請透過以下聯絡方式通知我讓我知道，謝謝
FB：https://www.facebook.com/changhsumath
IG：https://www.instagram.com/changhsumath
本篇ShengYu 介紹Python mod 取餘數用法與範例，Python 取餘數使用的符號是%，它可用來計算除法的餘數， Python mod 取餘數用法與範例這邊示範Python ... ... <看更多>
以下為浮點數型態做算術運算的例子，請留意，浮點數型態不能做取餘數的計算 #include <stdio.h> int main(void) { float a, b, c; a = 8.3; b = 2.2; c = a + b; ... ... <看更多>
mod餘數 在 Re: [解題] 高一數學餘數- 看板tutor - 批踢踢實業坊 的推薦與評價
※ 引述《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
... <看更多>