编程找逆元

⑴ 威尔逊定理 —— 数论四大定理之一

欢迎来到数论的奇妙世界，今天我们将深入探讨威尔逊定理，这不仅是四大定理之一，而且在实际问题中拥有不可忽视的应用价值。尽管它在常规考试和编程挑战中鲜有出现，但对理论的探索从不因看似冷门而停止。让我们一起揭开这个神秘定理的面纱吧。

威尔逊定理：素数的钥匙

定义：一个素数 的一个鲜为人知但至关重要的特性是，若 ，则 是素数的充分必要条件。

对于非素数，我们通过分类来揭示其背后的数学逻辑：

• 当 是完全平方数时，直接代入公式，我们有 。接着，比较 和 ，可得 ，因此，威尔逊定理不成立。


• 当 不是完全平方数，可以分解为两个不等的平方数乘积，设 ，则 。这时，我们有 ，即威尔逊定理在非素数情况下不成立。

当 是素数时，考虑其二次剩余式，我们得到 。通过因式分解，这个等式揭示了素数的特性：或者 ，这意味着存在不等于 的逆元 ，使得 。因此， 的乘积为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;
   }