編程找逆元

⑴ 威爾遜定理 —— 數論四大定理之一

歡迎來到數論的奇妙世界，今天我們將深入探討威爾遜定理，這不僅是四大定理之一，而且在實際問題中擁有不可忽視的應用價值。盡管它在常規考試和編程挑戰中鮮有出現，但對理論的探索從不因看似冷門而停止。讓我們一起揭開這個神秘定理的面紗吧。

威爾遜定理：素數的鑰匙

定義：一個素數 的一個鮮為人知但至關重要的特性是，若 ，則 是素數的充分必要條件。

對於非素數，我們通過分類來揭示其背後的數學邏輯：

• 當 是完全平方數時，直接代入公式，我們有 。接著，比較 和 ，可得 ，因此，威爾遜定理不成立。


• 當 不是完全平方數，可以分解為兩個不等的平方數乘積，設 ，則 。這時，我們有 ，即威爾遜定理在非素數情況下不成立。

當 是素數時，考慮其二次剩餘式，我們得到 。通過因式分解，這個等式揭示了素數的特性：或者 ，這意味著存在不等於 的逆元 ，使得 。因此， 的乘積為1，即威爾遜定理成立。

威爾遜定理在實戰中的應用

盡管威爾遜定理在演算法競賽中不常見，但其背後的思想卻有著廣泛的適用性。

通過威爾遜定理，廣義問題可以轉化為對 的分析，無論是素數還是非素數，都有明確的解法，這展示了定理的強大普適性。

在求解關於 的表達式時，利用威爾遜定理能快速判斷是否為素數，這對於素數篩選和預處理問題至關重要。

在尋找比 素數小的素數時，威爾遜定理為我們提供了關鍵的線索，通過逆元的運用，可以有效地枚舉並找到所需的答案。

威爾遜定理，看似冷門，實則蘊含著數學的精妙。它就像一把打開素數世界大門的鑰匙，雖然在日常應用中可能不顯眼，但在理論探索和問題解決中，它發揮著不可或缺的作用。不妨深入研究，你可能會發現更多隱藏的寶藏。

⑵ 用C語言編制的求模逆元的擴展歐幾里德演算法，只要能基本上實現這個功能就行

1. 擴展歐幾里德演算法是用來在已知a, b求解一組x，y，使它們滿足貝祖等式： ax+by = gcd(a, b) =d（解一定存在，根據數論中的相關定理）。擴展歐幾里德常用在求解模線性方程及方程組中。

2. 下面是一個使用C語言的實現：
   

   intexGcd(inta,intb,int&x,int&y)
   {
   if(b==0)//當b==0時，得到解
   {
   x=1;y=0;
   returna;
   }
   intr=exGcd(b,a%b,x,y);//遞歸調用自身，求解
   intt=x;x=y;y=t-a/b*y;
   returnr;
   }