费马小定理（通俗易懂）

今天给各位分享费马小定理（通俗易懂）的知识，其中也会对费马小定理（通俗易懂）进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文导读目录：

1、费马小定理 —— 欧拉定理的特殊情况

2、费马小定理（通俗易懂）

3、费马小定理

　　    今天要讲的内容，是数论中一个非常著名的定理 —— 费马小定理。阅读之前请确保对 二分快速幂 和 欧拉函数 已经有了一定的了解。本文的内容较短，但是作为 大素数判定 有着重要的意义，所以打算单独拿出一个章节来讲，内容较为简单，适合打算放弃学习数论的小伙伴重新找回学习的动力和勇气。【定义1】对于任意素数 ，和正整数 ，且 不是 的倍数，则： 　　    我们在学习欧拉函数的时候，已经知道了欧拉定理，如下： 　　    当 为 素数 时，它的欧拉函数为 ，将它带入欧拉定理，得到：     费马小定理，得证。 　　    我们可以用费马小定理来做什么？    一个比较直观的想法就是：可以随机找几个和 互素的 ，然后对它计算： 　　    如果结果都为 1，我们就可以认为 是一个素数。    如果这个结论成立，那么素数判定的时间复杂度就变成了 ，其中 为常数，代表找 个 来做判定试验， 则为利用二分快速幂进行判定的时间复杂度。    以上假设成立吗？    答案是 否！ 　　    事实上，费马小定理给出的是关于素数判定的 必要非充分 条件。    如果 是素数，则 ；相反，如果 ，则不能推导出 是素数。    原因是存在一些数 ，对于所有和 互素的 ，都能满足 ，这样的数，我们称它为伪素数。    第一个伪素数是 341，由 萨鲁斯 在 1819 年提出。【例题1】 给出一个大整数 ，求：    任何一个正整数都就可以表示成 的形式，其中 为除数， 为商， 为余数，并且 ；其中除数 可以是任意非零整数。    为了公式看起来整洁，我们用 来代替素数 ，并且令 那么根据费马小定理，有： 　　    原式就可以表示成： 　　    这里的 ，可以利用大数取余求解。求得的 ，再利用二分快速幂求解上面的式子即可。【例题2】给定素数 和 正整数 ，求满足 的最小正整数 x，如果不存在返回 -1。 　　    这个问题实际上是求正整数 在 模 域上的逆元。    首先，当 为 的倍数时，，所以一定不存在，直接返回 -1；    否则，根据费马小定理，我们可以知道： 　　    则可以得到： 　　    对比原式，就可以得到： 　　    对于一个很大的数 （例如十进制表示有 位），如何判断它是素数还是合数？　　费马小定理：假如 是一个整数， 是一个质数，那么 是 的倍数，也可以表示为 。如果 不是 的倍数的话，这个定理可以改写成我们常看的形式： 。 　　对密码学的数学基础不太好的同学可能还不太懂上面的形式，我会逐个解释。 　　表示的是 对 求余数， 是一个求余的符号。比如 。 　　表示的是恒等号，而 表示的是 。 　　本文采用的证明方法主要参考费马小定理的Wiki百科，在Wiki百科基础上，用更加通俗的语言解释它。 　　参考链接：Wiki百科-费马小定理。 　　若 是整数， 是质数，且 ，其中 表示求 的最大公约数。 　　这时，我们知道 ，共有 个数，然后让它们都除以 ，就会得到它们除之后的余数，将余数们设为 ，这个余数集合其实就是 这个集合中元素的重新置换，即 在余数集合 中恰好都出现一次。Ok，我第一次看到这里，整个人就彻底的毫无余地的懵掉了... 　　我们举个栗子看看。 　　假如 ，那么按照上面的步骤计算一下： 　　看起来，余数集合刚好就是 里的元素打乱顺序后的集合。如果 的话，计算后的余数集合就是这个集合，顺序都没变。为什么会这样嘞？ 　　我们可以这样思考这个问题， 的结果的取值范围是不是只能在 这个范围内，比如取任意一个正整数对数字7取余，余数只能在 这个区间里，不然的话，假如余数是7，就表示这个正整数是7的倍数，那余数就得是0了，所以不存在余数等于除数的情况。所以，我们就能理解了余数的集合里的数不可能等于除数或是超过除数。 　　回到上面的例子，余数的集合里的元素只能是 里的元素。那为什么 在余数集合 中恰好都出现一次？ 　　这就有点像我之前有篇文章里说的循环群。只需看那篇文章里的循环群那部分即可，点击即可访问那篇文章。事实上，这就是从 里的每个数的正整数倍数再对 取余，余数的集合就是 这个集合里元素的重新排序。然后轮到 时， 的正整数倍再对 取余，其结果肯定是为0的，直到 的这个范围里的数 之后的结果与 里的每个数的正整数倍数再对 取余的余数的集合是一样的。也就是说，从 里的每个数的正整数倍数再对 取余，假如余数的集合表示为 。那么在 里的每个数的正整数倍数再对p取余，余数的集合还是，对，顺序没有变化，一模一样。这就是一轮又一轮的循环。也就是循环群的概念。到 ，又开启下一轮循环。我这里只是简略叙述一下，更通俗易懂的详细叙述可以看我上面说的那篇文章的循环群部分。 　　从这个例子中，我们可以很容易看出来， ， 时，在 即 这个范围内依次取值乘以5的结果再对 取余的结果集合是 ，然后在下一个的 即 的范围内依次取值乘以5的结果再对 取余的结果集合还是，这就是一种循环群。 　　所以，到这里我们应该就知道了 ，这 个数，都分别 ，其结果设为 ，这个结果集合其实就是 这个集合中元素的重新排序，即 在结果集合 中恰好都出现一次。 　　OK！我们继续往下走。 　　我们将，这 个数进行相乘。然后乘积对 求余，那么结果就等于 。蛤？Why？ 　　我们上面知道了 ，我们不考虑集合的顺序的话，这个式子是成立的，因为乘法是有交换律的，所以，我们不需要管乘的顺序，反正哪种顺序乘积后的结果都是一样的，。 　　乘法也可以写成：。毕竟乘法也有结合律。 　　我们令 ，所以上面的式子就变成了 。当然也可以写成 。很显然， 不为0，整个式子除以 ，就得到了费马小定理的公式： 。当然，也可以写成 。 　　若 能整除 ，则显然 也能整除 ，那么 。 　　到此证毕！　　费马小定律(Fermat's Little Theorem) 　　费马小定理是数论中的一个定理。其内容为假如a是一个整数，p是一个质数的话，那么: 　　假如a不是p的倍数的话，那么这个定理也可以写成: 　　这个书写方式更加常用些。 　　费马小定理是欧拉定理 (数论)的一个特殊情况：假如n和a的最大公约数是1的话，那么: 　　在这里φ(n)是欧拉商数。欧拉商数的值是所有小于n的自然数中与n没有公约数的数的量。假如n是一个质数，则φ(n) = n-1，即费马小定理。 　　在费马小定理的基础上费马提出了一种测试质数的算法。 　　于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求。这个要求实际上不存在。 　　与费马无关的有一个中国猜想。这个猜想是中国数学家提出来的。其内容为如果，而且只有当成立时p才是一个质数。 　　假如p是一个质数的话，则成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。 　　一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了。但也有人认为实际上中国猜测是1872年提出的，认为它早就为人所知是出于一个误解。 　　若n不整除a-b，x>0，(x,n)=1，則n也不整除x(a-b)。取整數A为所有小於p的集（p不整除A），B为A中所有元素乘以a的集合。因任何两个A中的元素差都不能被p整除，所以任何两个B中的元素差也无法被p整除。因此: 　　即: 　　在这里W=1·2·3·...·(p-1)。将整个公式除以W即得到: 　　如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为伪质数。 　　假如所有符合1费马小定理（通俗易懂）的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于费马小定理（通俗易懂）、费马小定理（通俗易懂）的信息别忘了在本站进行查找喔。