→ coolbetter33:推 04/03 02:55
看到你的信了, 不過我覺得要回答你的問題要寫一大篇東西
所以就直接回到版上來了
---
基本上問題的根源在於在同餘運算之下
除法跟開根號不一定有解, 有解時也不一定恰有一解
這裡的「除法」跟「開根號」就是回到原本的定義
a 除以 b 就是想找一個數乘以 b 後會是 a
n 開根號就是想找一個數平方後是 n
當然找到的結果也要做同餘化簡就是了
就以你的模 10 為例
除以 3 基本上沒什麼問題, 都找得到唯一的這樣的數:
6 除以 3 結果是 2 (這個不用說明了吧 XD
7 除以 3 結果是 9 (3x9 = 27 模 10 為 7)
但是除以 2 就很有問題了:
6 除以 2 結果有兩個, 3 跟 8 (可以發現兩個乘回去模 10 都是 6)
7 除以 2 無解 (你找不到一個整數乘以 2 模 10 會得 7)
開根號也是一樣
5 開根號可以得到唯一解 5 (5x5 = 25 模 10 為 5)
4 開根號可以得到兩解 2 跟 8 (2x2 = 4, 8x8 = 64 模 10 皆為 4)
3 開根號卻是無解 (沒有整數平方後模 10 為 3)
所以平常數學裡的結論有一些不能直接拿來同餘運算裡用
特別是推導裡面有除跟開根號時就要小心
這些通常需要在同餘運算下重新推演過才行
好在加減乘可以安心使用, 所以只要針對有問題的運算小心處理就好
---
那麼回到費氏數列的問題
首先那條在通常數學裡的通式不能拿來直接用
主要的問題是外面的 1/√5
剛剛提到 5 開根號依然得到 5 所以這裡對於模 10 事實上就是除以 5
問題是除以 5 要看東西不一定有答案
所以只好回到原先推導這條式子的方式
由費氏數列的遞迴式開始, 我們想要解 x^2-x-1 ≡ 0 (mod 10)
原先的配方是兩邊加上 1/4 之後配方, 但是模 10 底下 1 除以 4 無解
所以只好反過來兩邊乘上 4
配方成 4x^2-4x+1≡5 (mod 10)
開平方根, 右邊依然是 5, 左邊則可能是 ±(2x-1)
不過也由於右邊是 5 的關係, 正負號正好沒差
於是我們得到 2x-1≡5 (mod 10) 即 2x≡6 (mod 10)
再來是除以 2, 上面提到 6 除以 2 會得到 3 或 8
於是我們似乎找到了兩個答案
但是代回原式去驗算時卻發現兩個都不合
也就是這兩個都是增根, 原式無解
(這裡增根的出現地點是乘以 4 的時候, 原因可以自己想想)
所以在模 10 底下我們已經寫不出費式數列的通式了
更不用說用它去列式
---
話說回來, 同餘運算其實還有一個好玩的地方
當模數不一樣時世界就會完全不一樣
例如當把 10 小改一點變成 11 的話 (我看到有觀眾在偷笑了XD)
因為模 11 下面除以 2 是沒問題的 (事實上除以不是 0 的都沒問題)
5 也可以開根號, 有兩解是 4 跟 7
所以解 x^2-x-1≡0 (mod 11) 會得到 4 跟 8
解係數可以得到 4^n 的係數是 8, 8^n 的係數是 3
所以在模 11 下面就能寫出費氏數列的通式 8*4^n + 3*8^n (mod 11)
---
話再說回模 10
你原先的寫法似乎是想找出費氏數列模 10 的週期
這種週期被叫做 Pisano period
可以參照維基百科的說明:
http://en.wikipedia.org/wiki/Pisano_period
簡單說就是
10 正好是兩個特殊狀況 2 跟 5 的合併
所以很多事情正好在 2, 5, 10 上有例外
對其他質數就有比較好的性質了
這也是為什麼上面改成質數 11 之後計算會這麼順利
---
最後提一些相關的進階材料好了
在數論裡同餘運算是個還滿大的題目
關於當中的除法有所謂的「同餘乘法反元素」的討論
還會跟抽象代數的環論、體論有連結
特別是只要不是 0 的都能除的情形就是所謂的「有限體」
事實上當模數是質數時就會是一種有限體
(還有其他的有限體, 那個的運算又不一樣了)
所以才會說換成 11 知道的人會偷笑, 因為那就是質數, 具有這種漂亮的性質
而關於模某個數時平方根能不能開這回事稱做二次剩餘問題
高斯對此整理了一整套的理論 「二次剩餘」這個名字也是他起的
後來還有數學家把高斯的理論加以簡化
就產生了勒讓德符號跟雅可比符號
這裡狀況就又不一樣了, 對於每個模數都有些數有解, 有些數無解
或者換成比較數學的講法叫做「二次剩餘」跟「二次非剩餘」
高斯所整理的理論就是探討什麼狀況下是二次剩餘 什麼狀況下是二次非剩餘
這些東西除了數論理論之外, 近代密碼學跟它非常相關
還有其他很多的應用
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1396456835.A.630.html