好久沒更新了。
前一陣子在網路上看到一個頗有趣的題目：
求n。
乍看之下可能會不知道怎麼下手，
想了幾天後，
大概想到了個解法。
首先，
當然還是類似暴力解。
不過不是真的笨到從 1 開始帶回去解答，
而是要找出「答案可能的形式」再來從中挑出正解。
以下為了表達整齊，
這裡統一把 n 的 5 次方表示為 m。
看到指數問題，
第一步還是想到求餘數。
道理很簡單，
如果 x 對 y 求餘數得到 z，
那我們就能把 x 表示成 my+z。
那麼不論把 x 做幾次方，
只有z的次方向不是 y 的倍數對吧？
所以說，
我們要做的就是把各項去求餘數。
首先對2求餘數：
mod (133,2)=1
mod (110,2)=0
mod (84,2)=0
mod (27,2)=1
所以
mod (133^5,2)=1
mod (110^5,2)=0
mod (84^5,2)=0
mod (27^5,2)=1
左邊四項對2求餘數分別是1、0、0、1，
因此只要再把餘數合計再對2取一次餘數，
就等於合計值對2取餘數了，
這個道理應該可以理解吧？
所以我們馬上得到，
mod (m,2)=0
也就是說 m 是 2 的倍數，
而 2 是質數，
因此必然的 n 是 2 的倍數。
結論1：mod (n,2)=0
第二步重複第一步的動作，
mod (133,3)=1
mod (110,3)=2
mod (84,3)=0
mod (27,3)=0
所以
mod (133^5,3)=1
mod (110^5,3)=2
mod (84^5,3)=0
mod (27^5,3)=0
這邊說明一下為什麼好了？
133=132+1對吧，
那麼 5 次方就是 132 的 5 次方 + 132 的 4 次方乘以一個係數 ... + 1 的 5 次方對吧？
那前面那些項通通都是 3 的倍數對吧（因為 132 是 3 的倍數）？
所以對 3 取餘數通通都是 0 對吧？
所以最後結果就是 1。
而 110=108+2，
同樣的道理，
最後項是 2 的 5 次方=32，
對 3 取餘數的結果為 2，
這樣說明應該就沒有問題的吧。
所以合計起來，
mod (m,3)=0，
同樣的道理，
mod (n,3)=0。
結論2：mod (n,3)=0
第三步重複第一步的動作：
mod (133,5)=3
mod (110,5)=0
mod (84,5)=4
mod (27,5)=2
所以
mod (133^5,5)=3
mod (110^5,5)=0
mod (84^5,5)=4
mod (27^5,5)=2
這邊也說明一下，
3 的 5 次方是 243 ，因此對 5 取餘數為 3。
後面同理 4 的 5 次方是 1024，
2 的 5 次方是 32。
至於為什麼跳過 4 不對 4 取餘數呢？
因為 n 是 2 的倍數，
那麼 n 的平方就已經是 4 的倍數了，
你取到 5 次方就必然是 4 的倍數，
因此沒有意義。
所以 3 + 4 + 2 = 9，
對 5 取餘數為 4，
我們得到 mod (m,5) =4。
餘 4 而不是餘 0，
這個就略顯尷尬了。
不過還不算太複雜，
因為對 5 取餘數只會有 0、1、2、3、4 共 5 種可能，
而餘 0 的場合將永遠餘 0 所以只需要討論 1、2、3、4 共 4 種狀況即可。
1 的 5 次方為 1，對 5 餘 1。
2 的 5 次方為 32，對 5 餘 2。
3 的 5 次方為 243，對 5 餘 3。
4 的 5 次方為 1024，對 5 餘 4。
因此，
只有當 n 對 5 餘 4 的情況成立，
因此 mod (n,5) =4結論3：mod (n,5)=4
第四步來點不一樣的，
那就是對 n 找通式。
由於 2、3、5 的最小公倍數是 30，
於是我們令 n=30a+b。
為什麼要這樣令呢？
因為30a的部分可以被 2、3、5 整除，
所以我們只需要討論 b 對 2、3、5 的餘數即可，
算是最大程度簡化問題。
那麼結合結論 1~3，
n 同時能被 2、3 整除，
代表 n 是 6 的倍數，
因此 b 是 6 的倍數，
所以 b 只能是 6、12、18、24。
當中，
b 又必須對 5 餘 4，
因此 b=24，
也因此我們得到 n 的表達式為 n=30a+24，
當中 a 是正整數。
第五步，
尋找 n 的上下限。
首先下限很好找，
133 的 5 次方加上後面一堆東西，
就必然比 133 的 5 次方更大吧？
上限也很好找，
左邊 4 項最大的是 133 的 5 次方，
其餘都比 133 的 5 次方要小，
所以必然比 4 倍的 133 的 5 次方要小，
沒問題吧？
具體來說是這樣：
接下來是重頭戲了。
4×133^5 這一項，
我們令它就是 z^5，
那麼 z 就會等於 五次根號4 乘以 133對吧？那麼「五次根號4」怎麼求呢？
有一個取巧方法：
2^5=32
3^5=243
4^5=1024
5^5=3125
這裡如果對數字敏感一點的應該立刻可以想到：
分子變小分母變大，
所以值變小，
因此三分之四的五次方大於4，
所以 z 小於133的三分之四倍，
大約是 177.3，
因此我們找到 n 的範圍：
帶回 n=30a+24 的通式，
第六步重複第一步的動作：
很容易找到 n 只能是 144 跟 174 其中之一。
那麼是哪一個呢？
就要驗證了。
說要驗證，
真的乘開 5 次方做兩次那真的太笨了，
我們繼續回去玩「求餘數」。
mod (133,7)=0
mod (110,7)=5
mod (84,7)=0
mod (27,7)=6
所以
mod (133^5,7)=0
mod (110^5,7)=3
mod (84^5,7)=0
mod (27^5,7)=6
這裡有個小技巧，
對 7 餘 5 我們可以想像成對 7 餘 -2，
因此 5 次方就是餘 -32，
此時補上 35 就是餘 3，
因此 mod (110^5,7)=3 就算出來了。
同樣的道理，
對 7 餘 6 我們可以想像成對 7 餘 -1，
因此 5 次方還是餘 -1，
因此 mod (27^5,7)=6 就算出來了。
OK，
mod (m,7)=2（3+6=9，所以餘 2），
那 mod (n,7) 是餘多少呢？
一樣的方法：展開討論。
如果 mod (n,7)=以下數字的話，
若為 1，1 的 5 次方為 1，對 7 餘 1，不合。
若為 2，2 的 5 次方為 32，對 7 餘 4，不合。
若為 3，3 的 5 次方為 243，對 7 餘 5，不合。
若為 4，4 的 5 次方為 1024，對 7 餘 2，合。
若為 5，5 的 5 次方為 3125，對 7 餘 3，不合。
若為 6，6 的 5 次方為 7776，對 7 餘 6，不合。
那麼我們就找到了，
mod (n,7)=4。
帶回原本的解，
mod (144,7)=4；mod (174,7)=6，
很明顯 144 才是正確答案。
因此我們得到解為 n=144。
驗算：
5次方欸開玩笑，
有興趣的自己按按看，
反正答案一定是對的，
因為敝人按過了www。
計算機表示：咩油啜啦～
為什麼前面求餘的準備只做到 5 呢？
因為肯定不可能毫無限制地一直做下去吧？
只做到 3 的話，
通式會是 6x+b，
這樣候選數是每 6 個數就有 1 個，
密度還是太大；
但如果做到 7 的話，
通式會是 210x+b，
這會變成要確定 b 的數值非常困難。
這種題目就是「數論」題目而不是常態性的題目，
因此必然就是使用「暴力解」，
只是這個「暴力」的程度不能是毫無止境的一值運算下去而必須控制在一個可接受的範圍內。
咩！油！啜！啦！
封面圖片：角巻わため pixiv id = 94972945
本篇使用的方程式編輯素材來自：LaTeX公式編輯器
達人
