大家好，我是一名計算機科學專業的學生，??我正在獨立學習演算法課程。
在課程中我看到了這個問題：我認為這是一個簡單的問題，但我無法理解
證明或反駁：5^{3001} = 12^{301} (mod 31)$
我解決它的計劃是從（5 和 12）開始并反復以 31 為模進行平方。
我的解決方案：
5^{3001} = 12^{301} (mod 31) =
5*5^{3000} = 12*12^{300} (mod 31) =
5*125^{2998} = 12*6^{300}*2^{300} (mod 31) =
5*1^{2998} = 12*36^{299}*32^{296} (mod 31) =
5 = 12*36^{299}*32^{296} (mod 31) =
5 = 12*5^{299}*1^{296} (mod 31) =
5 = 12*125^{297}*1 (mod 31) =
5 = 12*1^{297}*1 (mod 31) =
5 = 12
這就是我所做的，我認為這樣做是不對的，還有其他方法可以證明或反駁該主張嗎？
uj5u.com熱心網友回復：
通過平方取冪當然可以，但看起來作業量很大，您可以使用捷徑：a 30 ≡ 1 mod 31 if gcd(a, 31) = 1（歐拉定理）。
5 3001 ≡ 5 * (5 30 ) 100 ≡ 5 * 1 100 ≡ 5 mod 31
12 301 ≡ 12 * (12 30 ) 10 ≡ 12 * 1 10 ≡ 12 mod 31
指數 3001 和 301（結合模數 31）看起來像是專門為啟用基于歐拉定理的方法而選擇的。對于可以選擇的大多數任意數字，這種方法不會那么好。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/443790.html
上一篇：如何按順序添加鏈表串列的元素？