当前位置：网站首页>取模运算(MOD)

取模运算(MOD)

2022-08-04 00:15:00 【super阿真】

定理（消去律）：如果gcd(c,p) = 1 ，则 ac ≡ bc mod p 可以推出 a ≡ (b mod p)

欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n)，其中φ(1)被定义为1，但是并没有任何实质的意义。

定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。

显然，对于素数p，φ(p)= p -1.对于两个素数p、q，他们的乘积n = pq 满足φ(n) =(p-1)(q-1)

证明：对于质数p,q，满足φ(n) =(p-1)(q-1)

考虑n的完全余数集Zn = { 1,2,....,pq -1}，而不和n互质的集合由下面三个集合的并构成：

1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个

2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个

3)很显然，1、2集合中没有共同的元素，因此Zn中元素个数 = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

版权声明
本文为[super阿真]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_54223524/article/details/126145378