1 下面会用到的数学公式：

①如果a%b=c，那么如果x%b=c/2，此时x=a/2；也就是说除数相等时，被除数和余数是成比例的。
②如果a%b=c，那么 (a + k*b)%b=c，其中k为整数

2 问题引入：

  在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。

具体解法分下面三步：
1、找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
2、用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
3、用233除以3、5、7的最小公倍数105，得到余数23，这个余数23就是符合条件的最小数。

3 解释：

   那么我们可能会问：为什么要这样算……
   如果我们设出三个数n1、n2、n3，满足：n1%3=2、n2%5=3、n3%7=2；
   那么，我们先从n1这个角度出发，能不能让n1+n2也满足%3=2呢？根据上面的公式②，如果n2是3的倍数就完全可以满足，  同样如果让n1+n2+n3满足%3=2，需要n2和n3都是3的倍数；

同样的，我们从n2和n3的角度出发可以得到：
1、n1需要是5、7的倍数；
2、n2需要是3、7的倍数；
3、n3需要是3、5的倍数；

   如果找到了满足上面的三个条件的n1、n2、n3，根据上面的推论，n1+n2+n3就是满足题目要求的那个数，（但不一定是最小的哈）

4 接下来的问题就是

我们要怎么在5和7的倍数中找出一个数满足%3=2（2、3条件类似）
我们最开始列出的第一个公式还没有用呢！是不是可以转化成在5和7的倍数中找到一个数满足%3=1就可以了呢？然后我们再*2就可以了，为什么会想要让余数为1呢？因为这个跟逆元的求法几乎一样~。

5 补充：求逆元的方法：

①费马小定理

费马小定理:
a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)
证明这个定理非常简单，由于p是质数，所以有φ(p) = p-1，代入欧拉定理即可证明。推论：对于任意正整数a，有a^p ≡ a (mod p)，因为a能被p整除时结论显然成立。

②扩展欧几里得

6 欧拉定理：

$$a^{\phi(n)}$$≡$$1 (mod \ n) $$ 其中a,n互素
这个定理可以用来简化幂的模运算。比如计算7^{222}的个位数，实际是求7^{222}被10除的余数。7和10[[互素]]，且φ(10)=4。由欧拉定理知7^4Ξ1(mod 10)。所以7^{222}=(7^4)^55(7^2)Ξ1^{55}7^2Ξ49Ξ9 (mod 10)。
证明见下：
https://blog.csdn.net/ymzqwq/article/details/96269772

6.1 欧拉定理扩展：

再也不用担心指数爆炸
欧拉定理扩展.PNG
证明见下：
https://www.cnblogs.com/1024th/p/11349355.html

6.2 欧拉定理的群论证明：

7 欧拉函数：

就是对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。
欧拉函数的通式：φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)……(1-1/pn)
欧拉函数的一些性质：
$$\phi$$(2)=1
$$\phi$$(p)=p-1,p为质数
① 当m,n互质时，有$$\phi$$（mn）= $$\phi$$（m）$$\phi$$（n）；
② 若i%p==0，有$$\phi$$（ip） = p $$\phi$$(i)；
③ 对于互质x与p，有$$x^{\phi}$$≡1（mod p),因此x的逆元为$$x^{\phi-1}$$，即欧拉定理。
（特别地，当p为质数时，$$\phi$$（p）=p-1,此时逆元为$$x^{p-2}$$，即费马小定理）
④ 当n为奇数时，$$\phi$$(2n)=$$\phi$$(n)
⑤ 若x与p互质，则p-x也与p互质，因此小于p且与p互质的数之和为$$\phi$$(x)*x/2;
⑥N>1，不大于N且和N互素的所有正整数的和是 1/2 N eular(N)。
⑦若(N%a == 0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
⑧若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

8 贝祖等式

一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。
线性组合 ax + by = gcd(a,b)
一个重要的定理：gcd(a,b)是a和b的最小的正线性组合。

9 模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
ab≡1(mod n)
这时，b就叫做a对模数n的“模反元素”。比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。
$$a^{\phi(n)= a \times a^{\phi(n-1)}}$$≡1(mod n)
可以看到，a的 φ(n)-1 次方，就是a对模数n的模反元素。

10 欧几里得算法（求gcd）

ax + by = gcd(a,b)

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

11 扩展欧几里得算法（不但求gcd还能求xy）

47x+30y=1
过程可以用矩阵表示（其中q表示商，r表示余数）。

手算 47x+30y=1 (或者求47，30gcd)

算法说明How to solve "aX + bY = gcd(a,b)" ?
1、if b=0,
     gcd(a,b) = a,
     X = 1 , Y is any number.
     For convenience,we make Y equals 0.
2、if b!=0,
    gcd(a,b)   = aX1 + bY1;
    gcd(b,a%b) = bX2 + (a%b)Y2;
                 ----> (a-a//b*b)Y2;
--> aX1 + bY1  = aY2 +  b(X2-a//b*Y2);
--> X1 = Y2 , Y1 = X2-a/b*Y2;
    So we can use recursion to sovle it.

def ext_euclid(a, b):
     if b == 0:
         return 1, 0, a
     else:
         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
         x, y = y, (x - (a // b) * y)
         return x, y, q

扩欧2.png
https://blog.csdn.net/hzj1054689699/article/details/80693756

发表新评论

孙子定理以及欧拉定理--互质版