算法导论第三十一(31)章数论算法

方法 3 的时间复杂度分析
方法 3 的核心思想
第三种方法基于矩阵乘法和快速幂的思想。我们将斐波那契数通过矩阵表示：
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F{n+1} & Fn \\ Fn & F{n-1} \end{bmatrix}
通过提升这个矩阵到高次幂（即 n 次），我们就可以直接得到 F_n 的值。
快速幂算法的关键步骤
为了高效地计算大指数的矩阼幂次而不进行 O(n^2) 的逐元素相乘操作（对于 2\times 2 矩阵而言），我们采用类似快速求平方的方法：
分解指数：将 n 表示成二进制形式。
平方并合并：对于每一个二进制位置设为 1 的位置，分别平方当前结果并将其与自身相乘。
这样，在每一步中我们只需进行一次或几次矩阵相乘的操作（ O(4\times4\times4)= O(64) 次基本算术运算）。
时间复杂度分析
由于每次提升指数时都需要进行约 \log_2 n 次平方操作，并且每次平方需要进行固定的算术运算次数（与 n 无关），因此总时间复杂度为：
T(n) = O(\log n)
其中常数因子来自每一步中的固定算术运算次数（如矩阵相乘、加法等）。
总结
第三种方法通过利用快速幂的思想将斐波那契数的计算从线性时间降到了对数时间：
\boxed{O(\log n)}

1 基础数论概念

先简要回顾一下书中内容：

整除性与约数 ：d|a 表示为d整除a，存在整数k,使得a=kd

若d≥0，则称d是a的约数。

素数与合数 ：素数 ：如果能被平凡约数1和自身整除即为素数 。

合数 ：如果整数a>1且不是素数，则称之为合数 。

除法定理，余数和等模

对于任意给定的整数a和正整数n,根据除法定理,必然存在唯一的两个整数组合(q,r)，使得等式关系成立: a = q·n + r，并且满足条件：余数r满足不等式0 ≤ r < n。其中商q由下取整运算（floor）作用于比值(a/n)得到,而余数值r等于模运算结果(a mod n)。

同余：将整数按照模n进行分类。其中包含整数a的模n等价类被定义为[a]_n={a+kn:k∈Z}。

公约数与最大公约数 ：

公约数 ：d|a,a|b,则d是a与b的公约数。

最大公因数：两个非零整数a和b的所有公约數中最巨大者即為其最大公因數。記作gcd(a, b)。

相关定理：1.当任意整数a和b非全为零时，则gcd(a,b即为a与b所形成的线性组合集合{ax+by|x,y∈Z}中的最小正元素。

2.对任意整数a与b，如果d|a且d|b,，则d|gcd(a,b).

3.对所有整数a与b以及任意非负整数n.有gcd(an,bn)=ngcd(a,b)

4.对于任意正整数n,a,b .如果n|ab且gcd(a,n)=1,则n|b。

互质数 ：如果两个数的只有公约数1，则a与b称为互质数 。

相关定理：5.对于任意整数a,b和p,如果gcd(a,p)=1且gcd(b,p)=1则 gcd(ab,p)=1.

唯一因子分解定理

相关定理：1.对所有素数p和所有整数a,b，如果p|ab,则p|a或p|b(或者两者都成立)。

第二种技能中合数a采用了因式分解的方式表示为：a = p(e_1, 1)p(e_2, 2)\dotsm p(e_r, r) ，其中每个p_i均为素因数，并且按照从小到大的顺序排列满足p_1 < p_2 < \dotsb < p_r 。此外，在这种分解中指数部分e_r均为正整数值。

31.1-1 证明：若a >b>0,且c=a+b,则c mod a=b.

令c除以a余x，则存在整数k使得c = a×k + x = a + b。当k等于1时，则x等于b；如果k不等于1，则因为a大于b且b大于0，所以c = a + b也大于0；同时，向下取整(c除以a)的结果也大于0。因此可得：k至少为2。这样就有：ak + x = a + b ≥ 2×a + x；从而得出：b ≥ a + x ≥ a。这与题目假设矛盾。

所以k=1,x=b,c mod a=b.

31.1-2证明有无穷多个素数。(提示：证明素数p1,p2....,pk都不能整除(p1p2....pk)+1)

首先证明提示部分：假设 pi（i=1,2,…,k）能整除 (p₁p₂…p_k)+1，则有 (p₁p₂…p_k)+1 = k·pi。那么 pi 乘以（k - p₁…pk 中其他项的积）等于 1。因此 pi = 1 / (k - 其他项) > 1。这表明（k - 其他项）< 0 或者 （k - 其他项）> 0？如果（k - 其他项）< 0，则会导致矛盾；如果（k - 其他项）> 0，则同样会导致矛盾。因此与假设矛盾

现在说明原题：假设只有有限多个素数p₁,p₂,...,p_k，则(p₁p₂…p_k)+1是一个比这有限多个素数都大的合数。但是根据提示可知：无论选取哪一个素数p_i（i=1,2,…,k），p_i都不整除这个新构造的合数

依据定理3007（注：可能是笔误）。考虑到自然界的每一个合成体都可分解为若干质因数组成的形式，则可推断出对于任意k个质因数值之积加一的结果都无法被这些合成体整除的事实成立；进一步推论可知该结果既不含有除了自身及一之外的因素影响；因此可得出结论该合成体加一的结果必然是一个质数值；上述结论得证！

31.1-3 证明：如果a|b且b|c，则a|c.

a|b =>存在整数k1,b=k1a. 同理 存在整数k2,c=k2b所以c=k2b=k2(k1a)=(k1k2)*a 所以a|c

31.1-4 证明：如果p是素数并且0 <k<p,则gcd(k,p)=1.

假设k是一个素數。其中0 < k < p ，并且p也是一个素umber。其因數仅有 \boxed{ \text{仅} } \boxed{ \text{有} } \boxed{ \text{仅} } 。因此k与p的最大公約數仅为 \boxed{ \text{仅} } ，故有\gcd(k,p)= 3.

假设k是一个合数，并且满足0 < k < p（其中p是一个素数值）。其因数值包括1以及若干个均小于自身大小的数量；另一方面，在另一个数值q = p中（即该素值），其因数值仅为1及自身。所有这些因数值都小于q = p；因此可知两者的最大公约数值仅为一。

31.1-5 证明：对于任意正整数n,a,b .如果n|ab且gcd(a,n)=1,则n|b。

由于n整除ab，则存在整数k满足关系式 ab = kn；当已知条件 gcd(a,n) = 1时，则可推导出 gcd(a, ab/k) = 1；进一步地，在这种情况下有 k·gcd(a, ab/k) = k；接着得出结论 gcd(ak, ab) = k；最后得到等式 a·gcd(k,b) = k 成立。

所以ab=kn => ab= a*gcd(k,b)n => b=gcd(k,b)n => n|b

**31.1-6 证明：如果p是素数且0 <k<p,则

.证明对所有整数a,b和素数p,有(a+b)^p≡ap+b^p(mod p).**

属于组合数学的范畴之一的是一个整数值变量k，在这种情况下，
由于涉及到了素因子分解，
我们有K! \cdot (P-K)!能够整除p!，
其中p是一个素数，
并且对于任意i\in(1,p-1)，
都有\gcd(p,i)=1。
因此必然满足\gcd(p,K! \cdot (P-K)!)=1。
虽然教材中未提及这一性质，
但根据已知定理：
如果\gcd(m,a)=1且m|ab，
则必然满足m|b。
由此可知，
对于所有k\in[1,p-1]，
都有k! \cdot (P-K)!能够整除(P-1)!
同样依据另一条定理：
如果m|ab且\gcd(m,a)=1，
那么必定存在某个整数z使得a^{-1}b=z \mod m
在本题中，
我们可以推断出：
对于给定的p和k值，
一定存在某个整数z使得等式成立：
(P-1)!=z \cdot K! \cdot (P-K)!
接着，在方程两边同时乘以素数p得到：
p! = z \cdot K! \cdot (P-K)! \cdot p
进一步化简可得：
\frac{P!}{K! \cdot (P-K)!} = z p
这表明该分数必定能被p所整除

下面证明第二个问题

因为

所以

所以存在整数k,使(a+b)^p=ap+b^p+kp. 因为b^p+kp≡ b^p(mod p)，所以可证结论。

命题31.1-7 证明：任意给定两个正整数a和b, 若a整除b, 则对于所有整数x, 都有(x modulo b) modulo a等于x modulo a. 在此基础上, 证明如下: 如果存在两个整数x和y满足x与y同余于模b（即x ≡ y (mod b)), 则必有这两个数在模a意义下也必定相等（即x ≡ y (mod a)).

设x mod b=y则存在整数k1,使得x=bk1+y.设y mod a=z,则存在整数k2使得y=ak2+z 所以x=bk1+ak2+z 又因为a|b,则存在整数k. b=ak 所以x=(ak)k1+ak2+z=a(kk1+k2)+z所以x mod a=z=y mod a=(x mod b) mod a.

在满足同一前提条件下，在相同假设下：

• x ≡ y (mod b)，即存在整数k₁使得 y = b k₁ + x。
• 由于a | b，则存在整数k使得b = a k。
• 因此有 y = a (k k₁) + x。
• 所以可得x ≡ y (mod a)。

对于任意正整數k>0，若存在某個整數a使得a的k次方等於n，則稱這类整數n為k次幂数。特别地，在k>1且n>1的情況下，我們将這樣的數n稱為非平凡幂数（nontrivial power）。请阐述如何能够在\beta多項式的時間内判斷一個具有\beta位的數n是否為非平凡幂数？

以下是代码：

 //最朴素的多项式时间内判断一个数是否为某个数的幂的形式：就是用枚举法，挨个找,但是这个是关于n的多项式，关于β的多项式暂时没有想出。

    
 #include <iostream>
    
 #include <math.h>
    
 using namespace std;
    
 void main()
    
 {
    
     int n=64,flag=1;
    
 	//O(√nlgn)
    
     for (int i=2;i<=sqrt(n);i++)//O(a=√n)
    
 	{
    
 		int m=n,k=0;
    
 		while (m%i==0)//O(k=lgn)
    
 		{
    
 			m=m/i;
    
 			k++;
    
 		}
    
 		if (m==1&&k>1)
    
 		{
    
 			cout<<n<<"是非平凡幂,存在一个整数"<<i<<"它的"<<k<<"次幂="<<n<<endl;
    
 			flag=0;
    
 			break;
    
 		}
    
 	}
    
 	if (flag)
    
 	{
    
 		cout<<"n="<<n<<"不存在非平凡幂"<<endl;
    
 	}
    
 }

31.1-9证明等式(31.6)-31.10

需要证明的等式已用加粗

31.6 gcd(a,b)=gcd(b,a) 根据整数的交换率便知

令******** d为整數a和b的一個公約數，则根據定義可知d \mid a和d \mid b。 存在某個整數k使得等式成立：$

$a = d \cdot k$

由此可得 $$

\left|\, a \,\right|\, = d \cdot (\pm k)

從而推出 $$

\left., d ,\right|, (\pm a)

進一步地可知因為$d \mid b$并且 $- a$與$b$的所有公約數都一樣 因此最大公約數值也保持不變。 故此

\textbf{gcd}(-! a,, b) = \textbf{gcd}(a,, b)

根据31.7的结果可知：令$d$为$a$和$b$的一个公约数，则有$d \mid a \Rightarrow d \mid |a|$；同理可得$d \mid b \Rightarrow d \mid |b|$；因此可知$d$也是它们的一个公约数。由此可见，在公约数方面两者并无差别；从而得出它们的最大公约数值必然相同；于是我们有$\begin{cases} d \mid a &\Rightarrow d \mid |a|\text{；}\\ d \mid b &\Rightarrow d \mid |b|\text{；}\\ 所以$d$是$|\,a\,|$与$|\,b\,|$的一个公约数。\end{cases}$ 因此$\gcd(a,b) = \gcd(|\,a\,|, |\,b\,|)$ 得证。 设d是整数a的一个因数，则显然地d也是零的一个因数（因为任何整数值乘以零必定得到零））。由此可见，d也是a与零之间的公约因数之一。为了找到这些公约因数中的最大者，则可知当考虑绝对值时,a的最大因数值为其自身即| a |（当然仅当| a |大于零时成立）。由此可知,a等于gcd(a, 0)（即 a = gcd(a, 0) 当 a > 0）。同样地若 a < 0 ，则 - a = gcd(- a, 0 ) = gcd(a, 0 )（参考定理31.7）。综上所述，则可得对于所有整数值 a ，有| a | = gcd(| a | , ⁰ ) = gcd( a , ⁰ ) （参考定理31.8）。 当正整数值设定为$a$时，则满足关系式$\gcd(a,\ ka)= a \times \gcd(1,\ k)$；由于任何整数值与其相邻值的最大公约数必然是一个单位量**（即$\gcd(n,\ n+1)=\mathbf{1}$）**；因此，在上述条件下计算得到的结果表明：当正整数值设定为$k$时，则满足关系式$\gcd(k\times a,\ a)= a$）。 若$a<0$（即$a$为负数），则$\gcd(a, ka) = \gcd(-a, -ka) = (-a) \cdot \gcd(1, k)$（根据推论31.4）。另一方面，在计算$\gcd(1, k)$时可知：由于任意整数与1的最大公约数必定为1，则$\gcd(a, ka) = -a$。 若a=0,则gcd(0,0)=0，所以gcd(a,ka)=a 总结：**gcd(a,ka)=|a|** 下面将证明：最大公约数运算具有结合性。即对于任意整数a, b和c，则有$gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)$。 在证明之前，先证明：gcd(a,b,c)=gcd(a,gcd(b,c)) 令$d$等于$a$与$b$、$c$的最大公约数，则$d$整除$a$且$d$整除$b$、$c$的最大公约数。因此$d$整除$a$、$b$以及$c$。由此可知，$d$是$a$、$b$$c的一个公约数。因此可以推导出：最大公约数$\text{gcd}(a, b, c)$至少与$\text{gcd}(a, \text{gcd}(b, c))相等。（1） 令$d'= \gcd(a,b,c)$。由此可知$d'$整除$a$、$b$以及$c$。根据推论31.3可知$d'$也能够整除$b$和$c$的最大公约数$\gcd(b,c)$。由于$d'$已经能够整除$a$这一前提条件，在此基础上进一步考虑$\gcd(a,\,\gcd(b,c))$的存在性问题。注意到最大公约数必为正整数，则存在某个正整数$k$满足关系式：$\gcd(a,\,\gcd(b,c)) = k\cdot d'$。 对于任意整数a、b、c来说，d'的最大值不超过a与b、c的最大公约数之积；由此可得a、b、c的最大公约数同样不超过a与b、c的最大公约数之积。根据以上两式可知，三个整数a、b、c的最大公约数等于其中一个 数值与其余两个数值最大公约 度之积。类似地， 我们 可以证明三 个 整 数值 的最 大公因 数值也等 于它 们中两个数值最 大公因数值与其余一数值之间的最大公因数值 所以gcd(a,b,c)=gcd(a,gcd(b,c))=gcd(gcd(a,b),c) 。 **31.2-11 证明定理31.8** 注释如下：此定理的证明过程可源自北师大《初等数论》第6讲中的相关内容，并且其中提供了较为详细的解答过程。由于篇幅或其他原因，在此不做进一步展开讨论。 请阐述一种适用于β位整除与短整数相除的高效运算方法，并同时请详细说明如何用高效方法计算β位整数与其短整数相除后的余数值。要求该方法的时间复杂度必须达到θ(β²)级别。鉴于此，请考虑采用快速傅里叶变换（FFT）来解决这两个问题。 既然用高效的算法，那就用位运算。 ``` //位运算的乘法与除法 #include using namespace std; //位运算的乘法 int bit_Multiplication(int a,int b) { int ans=0; for (int i=1;i;i<<=1,a<<=1) { if (b&i) { ans+=a; } } return ans; } //位运算的除法 int bit_Division1(int x,int y) { int ans=0; for (int i=31;i>=0;i--) { if ((x>>i)>=y) { ans+=(1<>=1; i++; } return i; } //位运算的除法 计算商 int bit_Division2_quotient(int x,int y) { int c2=bit_num(x),c1=bit_num(y),quotient=0; for (int i=c2-c1;i>=0;i--)//i=c2-c1防止除数y移位后超过无符号整数最大值 时间复杂度O(c2-c1) { unsigned int a=(y<=0;i--)//i=c2-c1防止除数y移位后超过无符号整数最大值 时间复杂度O(c2-c1) { unsigned int a=(y<10),写得不好，凑合看吧 /*#include #include using namespace std; #define BIT 6//二进制整数的位数，可根据所要输入的二进制位数设置BIT。 int t=-1; int Bit_merge(int a[],int p,int r) { static ans=0; p=(p>t)?p:(t+1); for (int i=p;i<=r;i++) { t++; ans+=a[i]<>x; int j=0; while (j!=BIT) { a[j]=x[BIT-1-j]-'0'; j++; } cout<b≥0,并且EUCLID(a,b)执行了k≥1次递归调用，则a≥F(k+2),b≥F(k+1) 定理31.11（Lame定理）对于所有整数k ≥ 1，在条件a大于b且b至少为一的情况下，并且当满足b小于斐波那契数F_{k+2}时，则Euclid算法在处理参数a和b时的递归调用次数将不超过k次。 代码如下： ``` //欧几里得算法递归形式 #include using namespace std; int Euclid(int a,int b) { cout<<"gcd("< using namespace std; struct a { int d,x,y; }s; struct a extended_eucild(int a,int b) { if(b==0) { s.d=a,s.x=1,s.y=0; return s; } else { struct a ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } int Fibonacci(int n) { if (n==1) { return 1; } else if (n==0) { return 0; } else { return Fibonacci(n-2)+Fibonacci(n-1); } } void main() { struct a s=extended_eucild(99,78); cout<31.2-1 证明：由式(31.11)和式(31.12)可推得式(31.13） ``` **  ** **31.2-2计算调用过程EXTENDED-EUCLID(899,493)的返回值为(d,x,y).** |a|b|向下取整a/b|d|x|y| |---|---|---|---|---|---| |899|493|1|29|-6|11| |493|406|1|29|5|-6| |406|87|4|29|-1|5| |87|58|1|29|1|-1| |58|29|2|29|0|1| |29|0|一|29|1|0| ||||||| ||||||| ||||||| **31.2-3 证明：对所有整数a,k和n，gcd(a,n)=gcd(a+kn,n)** 计算a和n的最大公约数时，等价于计算n和a除以n的余数的最大公约数。对于任意整数a、k'、n和x，假设a除以n的余数为x，则有a = nk' + x；即余数x等于a减去nk。因此，gcd(a, n)等于gcd(a - nk', n)。由于k'可取任意整数值，则令k = -k’即可完成证明。 则gcd(a,n)=gcd(a+nk,n). **31.2-4 仅借助固定数量的存储单元将过程 EUCLID 转换为迭代形式。** 代码如下： ``` //欧几里得算法迭代形式 #include using namespace std; int Euclid(int a,int b) { while (b) { int c=b; b=a%b; a=c; } return a; } void main() { cout< b且b ≥ 0的非负整数。为了证明该结论成立，请考虑欧几里得算法在输入a和b时最多进行1 + log b次递归调用。进一步地，我们能将这个上界优化至1 + log(b / gcd(a, b))。  改进的界我暂时不会。 **31.2-6 过程EXTENDED-EUCLID(F(k+1),Fk)返回什么值？证明答案的正确性。** ``` #include using namespace std; struct a { int d,x,y; }s; struct a extended_eucild(int a,int b) { if(b==0) { s.d=a,s.x=1,s.y=0; return s; } else { struct a ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } int Fibonacci(int n) { if (n==1) { return 1; } else if (n==0) { return 0; } else { return Fibonacci(n-2)+Fibonacci(n-1); } } int power(int k) { int i=1; int t=1; while (i!=k+1) { t*=-1; i++; } return t; } void main() { const int k=10; struct a s=extended_eucild(Fibonacci(k+1),Fibonacci(k)); cout<\gcd(a_i,\gcd(a_1,\dots,a_{i-1},a_{i+1},\dots,a_n)) = d = \gcd(a_0,a_1,\dots,a_n)

其中$i = 0, 1, \dots, n$。 即$a_0,a_1,\dots,a_n$这一系列整数的最大公约数， 等于其中任意选取的一个$a_i$与其对应其余各项的最大公约数。 下面给出满足gcd(a0,a1,...,an)=a0x0+a1x1+...+anxn的算法代码如下： ``` #include #include using namespace std; #define n 5//根据输入确定元素个数。 struct t { int d; int x; int y; int z[n];//存放题目中的x0,x1...xn }s; struct t extended_eucild(int a,int b) { if (b==0) { s.d=a; s.x=1; s.y=0; return s; } else { struct t ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } struct t extended_eucild1(int a[]) { struct t s3,s1,s2; for (int i=0;i #include using namespace std; #define n 4//根据输入确定元素个数。 struct t { int d; int x; int y; int z[n];//存放题目中的x0,x1...xn }s; struct t extended_eucild(int a,int b) { if (b==0) { s.d=a; s.x=1; s.y=0; return s; } else { struct t ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } struct t extended_eucild1(int a[]) { struct t s3,s1,s2; for (int i=0;igcd(n1n2,n3n4)=gcd(n1n3,n2n4)=1 由于$n_¹$, $ⁿ_²$, $ⁿ_³$, $ⁿ_⁴$任意两个数互质，在此条件下我们有$\text{GCD}(ⁿ_¹,\;ⁿ_³)\;=\;\text{GCD}(ⁿ_²,\;ⁿ_³)\;=\;①$。由定理③一①六可知$\text{GCD}(ⁿ_¹\n⁴,\;ⁿ_³)\;=\;①$。同样地，在上述基础上再进一步应用定理③一①六得到$\text{GCD}(ⁿ_¹\n⁴,\;ⁿ_³\n⁴)\;=\;①$。对于其他组合如$\text{GCD}(ⁿ_¹\n³,\;ⁿ_²\n⁴)$等也可通过类似的方法证明其等于① 因为$ \text{gcd}(n_1 n_2, n_3 n_4)$和$\text{gcd}(n_1 n_3, n_2 n_4)$都等于一， 所以我们可以推断$n_1$、$n_2$、$n_3$、$n_4$之间任意两个都是互质的。 进一步地， 存在这样的线性组合：$n_1 (a x) + n_2 (b y) = 1$ 这表明该组合涉及变量$n_1$和$n_2$， 而其最小正值即为一。 因此， 我们可以得出结论$\text{gcd}(n_1, n_2) = 1$ 类似地， 根据定理3.7， 我们可以推导出$\text{gcd}(n_i, j) = 0 \quad (i \neq j)$ 从而证实$n_i$与$j$之间也是互质的关系。 综上所述， 命题得以证明 第二个证明不太会 **31.3模运算** **群的定义** ：群(S,(+))是一个集合S和定义在S上的二进制运算(+) **群的性质** ：封闭性，单位元，结合律，逆元 **子群** ：如果(S,(+))是一个群，S'‘⊆S,并且(S',(+))称为(S,(+))的子群。 绘制两个群（Z₄, +₄）与（Z₅*, ×₅）的运算表格。寻找这两个群元素之间的一一对应的映射关系α。使得对于任意a, b属于Z₄，在模4下有a + b ≡ c (mod 4)，同时在模5下有α(a) × α(b) ≡ α(c)(mod 5)，从而证明这两个群之间存在同构关系。 |+4|0|1|2|3| |---|---|---|---|---| |0|0|1|2|3| |1|1|2|3|0| |2|2|3|0|1| | 3| 3| 0| 1| 2 || |x5|1|2|3|4| |---|---|---|---|---| |1|1|2|3|4| |2|2|4|1|3| |3|3|1|4|2| |4|4|3|2|1| 可以证明满足a+b ≡c(mod 4)当仅当α(a)Xα(b)≡α(c)(mod 5).考察两个群中的每一个元素以及对应的二元运算结果。a(行)与b(列)代表群(Z4,+4)中的元素，c代表a与b的二元运算结果。并且经过关系α ，有α(a)(行)与α(b)(列)是相同位置下的群(Z5*,X5)的元素，α(c)是α(a)与α(b)经过群(Z5*,X5)二元运算结果。举3个例子来说明：当a=0,b=0时.c=0 则α(a)=1,α(b)=1, α(c)=1 => 0+0≡0mod4 当仅当1*1≡1mod5 当a=3,b=2时,c=1.则α(a)=4,α(b)=3, α(c)=2.=>3+2≡1mod4, 当仅当4*3≡2mod5 当a=2,b=1,c=3时 。则α(a)=3,α(b)=2, α(c)=1.=>2+1≡3mod4, 当仅当3*2≡1mod5. 同样地，在运算表中的所有数据都能得出相应的结论。然而关系α具有一一对应性。这一点我还未能完全理解。显然，一旦我们证实了关系α具有一一对应性，则它们之间的同构性也随之成立。 **31.3-2列举出Z9和Z13*的所有子群。** Z9各元素={0,1,2,3,4,5,6,7,8} 各元素生成的子群<0>={0}. <1>={0,1,2,3,4,5,6,7,8}. <1>=<2>=<4>=<5>=<7>=<8>. <3>=<6>={0,3,6} Z13*各元素={1,2,3,4,5,6,7,8,9,10,11,12} 各元素生成的子群 <1>={1}. <2>=<6>=<7>=<11>={1,2,3,4,5,6,7,8,9,10,11,12}.<3>=<9>={1,3,9}.<4>={1,3,4,9,10,12},<5>=<8>={1,5,8,12},<10>={1,3,4,9,10,12} <12>={1,12} **31.3-3证明定理31.14** 定理31.14（每个有限群里满足条件的非空闭包都是其自身的子群） 设$(S,+)$是一有限群，则对于任取的$S'\subseteq S$且满足$\forall a,b\in S'$有$a+b \in S'$时，则$(S',+)$构成$(S,+)$的一个子群。 由于$ S' $是非空真子集且满足封闭性条件，则必有$ S' \subseteq S $。对于任意元素$a,b \in S'$而言，在该运算下运算结果$a(+)b$也在$ S'$中，并且根据群的定义可知$( S', (+) )$自身构成一个群结构。因此$( S', (+) )$作为原群$( S, (+) )$的一个非空闭合子集，并满足单位元与逆元的存在性条件（隐含于群定义中），故而$( S', (+) )$确实是$( S, (+) )$的一个子群。 **31.3-4证明：如果p是素数且e是正整数，则φ(p^e)=(p^(e-1))(p-1)** 对于整数p^e的素因数只有一个p,所以φ(p^e)=(p^e)π(1-1/p)=(p^e)(1-1/p)=(p^(e-1))(p-1) 命题：对于任何整数$n>1$以及任意$a$属于集合$\mathbb{Z}_n^*$,映射关系$f(x)=ax \bmod n$所确定的函数$f:\mathbb{Z}_n^*\rightarrow\mathbb{Z}_n^*$是一个置换。 对于任意一个a和n，在Zn*中存在唯一的x映射到唯一的y上；即f(x)是一个双射函数。因此，在Zn*上定义的函数f: Zn*->Zn*构成该群的一个置换。 **31.4 求解模线性方程** 定理31.20 对任意正整数a和n，如果d=gcd(a,n),则在Zn中，=={0,d,2d,....((n/d)-1)d},因此，||=n/d; 推论31.21 当且仅当d|b,方程ax≡b(mod n)对于未知量x有解，这里d=gcd(a,n). 推论31.22 方程ax≡b(mod n)或者对模n有d个不同的解，或者无解，这里d=gcd(a,n). 定理31.23 设$d = \gcd(a, n)$．假设存在整数$x'$和$y'$满足$d = ax' + ny'$．当且仅当$d$整除$b$时，在模$n$意义下方程$ax \equiv b \pmod{n}$存在一个解$x_0$（记作$x_0$），其中$x_0$等于$(x'\cdot (b/d)) \mod n$的结果． 定理31.24 若线性同余式ax ≡ b (mod n)存在解（其中d为a与n的最大公约数，并且d整除b），则设x₀为此同余式的任一解。由此可知，在模n的意义下, 该同余式共有n个不同的解, 分别为xi = x₀ + i(n/d)，其中i为整数 代码如下： ``` #include using namespace std; struct t { int d,x,y,z; }s; struct t extended_eucild(int a,int b) { if (b==0) { s.d=a; s.x=1; s.y=0; return s; } else { struct t ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } void MODULAR_LINEAR_EQUATION_SOLVER(int a,int b,int n) { struct t ss=extended_eucild(a,n); if (b%ss.d==0) { int x=(ss.x*(b/ss.d))%(n);//100k-105 if (x<0) { x+=n; } for (int i=0;i ``` **31.4-1 找出方程35x≡10(mod50)** 带入上面代码后得：  31.4-2 证明：如果gcd(a,n)=1, 那么方程ax≡ay(mod n) 将导致x≡y(mod n). 通过提供一个当gcd(a,n)>1时的反例, 可以说明条件gcd(a,n)=1是必要存在的. 由$ax ≡ ay \pmod{n}$可得$ax = ay + nk$ ，即$a(x - y) = nk$ 。由于$\gcd(a, n) = 1$并且根据推论31.5可知$n$整除$(x - y)$ ，因此$x - y = nk$ ，即$x ≡ y \pmod{n}$ 。若$\gcd(a, n) > 1$（例如），设$a = 12$,$n = 3$,$\gcd(a, n) = 3$ 。根据$a(x - y) = nk$ ，假设$k = 4$, 则$x - y = 1$, 即$x = 6$, $y = 5$ 。然而$x - y ≠ nk$ ，所以$x ≡ y \pmod{n}$ 不成立。 分析对MODULAR-LINEAR-EQUATION-SOLVER过程第3行的更正措施：方程3 x0 = x'(b/d) mod (n/d)能否正常运行？请阐述其成功与否的原因。 能，因为x'(b/d)mod (n/d) 与x'(b/d)mod n 同余。 具体阐述为什么两者间存在同余关系。由于已知条件中给出$x_0 \equiv x'\left(\frac{b}{d}\right) \mod \left(\frac{n}{d}\right)$成立，并设定$x_0' \equiv x'\left(\frac{b}{d}\right) \mod n$满足条件，则可推导出$n$整除$(x_0' - x'\left(\frac{b}{d}\right))$这一结果。进一步展开可得$x_0' - x'\left(\frac{b}{d}\right) = nk$（其中$k$为整数），从而得出$d$能够整除$n$（即$n = dk'$）。将此关系代入原式可得$x_0' - x'\left(\frac{b}{d}\right) = dk'k$（其中$k'$和$k$均为整数），由此可知$k'$必须能够整除$(x_0' - x'\left(\frac{b}{d}\right))$这一差值结果。基于上述分析可知$x_0'$满足模$\frac{n}{d}$意义下的同余关系式$x_0' \equiv x'\left(\frac{b}{d}\right) \mod \left(\frac{n}{d}\right)$成立的条件要求。因此，在这种情况下若$x_0'$是满足模$n$意义下的解，则必然也是模$\frac{n}{d}$意义下的解；反之亦然。综上所述，在满足上述条件的情况下$x_0 = x'_1 = x'_2 = \dots = x'_k = x\left(\frac{b}{d}\right)\mod\left(\frac{n}{d}\right)$即为该方程组的唯一解 由此引出一条普遍又常用的定理：如果a≡b(mod m)， 若m1|m，则 a≡b(mod m1) 31.4-4 略。 **31.5中国余数定理** 定理31.27（中国剩余定理）令$n = n₁·n₂·…·n_k$（其中各$n_i$两两互质）。考虑如下的对应关系：$a ↔ (a₁, a₂, …, a_k)$。（1）这里$a ∈ \mathbb{Z}_n$且$a_i ∈ \mathbb{Z}_{n_i}$（对$i = 1, 2,…,k$），满足$a ≡ a_i \pmod{n_i}$。因此映射（1）是在$\mathbb{Z}_n$与笛卡尔积$\mathbb{Z}_{n₁} × \mathbb{Z}_{n₂} × … × \mathbb{Z}_{n_k}$之间的一一对应即双射。（2）在适当的系统框架下，在各个坐标位置上独立进行操作，则$\mathbb{Z}_n$中元素所对应的运算可被等价地作用于其对应的$k$元组。具体而言若$a ↔ (a₁, a₂,…,a_k)$且$b ↔ (b₁,b₂,…,b_k)$则： - $(a + b) \mod n ↔ ((a₁ + b₁) \mod n₁,…,(a_k + b_k) \mod n_k)$ - 类似地可推导出$(a - b) \mod n$与$(ab) \mod n$各自的对应关系 此推论若各ni互质且互不相同，则对于任意整数a₁,a₂,…,a_k，在未知量x上满足联立方程组x ≡ a_i (mod n_i)，i = 1, 2,…, k时，在模n下存在唯一的解。 推论31.29 若$n_1, n_2, \dots, n_k$两两互质，则$n = n_1 n_2 \dots n_k$；对于任意整数$x$和$a$而言，在模$n_i$下$x ≡ a\ (i=1, 2, \dots, k)$成立当且仅当在模$n$下$x ≡ a\ (mod\ n)$成立。 代码如下： ``` //孙子定理(中国剩余定理) #include using namespace std; #define num 3//方程个数 #define LEN 10 struct t { int d,x,y,z; }s; struct t extended_eucild(int a,int b) { if (b==0) { s.d=a; s.x=1; s.y=0; return s; } else { struct t ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } int MODULAR_LINEAR_EQUATION_SOLVER(int a,int b,int n) { struct t ss=extended_eucild(a,n); int *c=new int[LEN]; if (b%ss.d==0) { int x=(ss.x*(b/ss.d))%(n);//100k-105 if (x<0) { x+=n; } return x; } else { cout<<"no solutions"< ``` **31.5-1 找出所有解，使方程x≡4(mod 5) x≡5(mod 11)同时成立。** 根据以上面代码，num调整为2，这样可得结果为x≡49(mod 55) **31.5-2 找出被9,8,7除时，余数分别为1,2,3的所有整数x.** 根据以上面代码，num调整为3，这样可得结果为x≡10(mod 504) 31.5-3 略。不太懂a<->(a1,a2,....,ak) 这种式子的含义。 基于定理31.27的条件，在多项式环Z_n中考虑以下问题：证明，在该条件下，对于任意多项式f(x)，其在模n意义下的同余式（1）f(x) ≡ 0 (mod n) 的解的数量等于其在各子模n_i意义下的同余式（2）f(x) ≡ 0 (mod n₁), f(x) ≡ 0 (mod n₂), ..., f(x) ≡ 0 (mod n_k))等式成立；每个子模n_i对应的同余式的解的数量之积即为原方程（1）的所有解的数量 证明：(1)的解一定是(2)的解：由于f(x)≡0(mod n) 所以n|f(x),又ni|n=>ni|f(x)=>f(x)≡0(mod ni) (2)的解一定是(1)的解： f(x)≡0(mod ni) => ni|f(x) => 又因为ni两两互质，n1n2..nk|f(x) n|f(x)=>f(x)≡0(mod n) 所以(1)与(2)等价。 现在设 ： f(x)≡0(mod ni)的解为 x=biti (ti=1,2...Ti) 一共有Ti个解 在给定的k个线性同余式中,任取其中每个同余式的一个解,即可构成如下的联立方程组:x ≡ b₁t₁ (mod m₁), x ≡ b₂t₂ (mod m₂), …… , x ≡ bₖtₖ (mod mₖ).应用孙子定理可知该联立方程组存在唯一解. x ≡ ∑_{i=1}^{n} M_i M_i' b_i \pmod{m} \quad (3)] 方程组中的每个方程各自具有 T₁, T₂, ..., T_k 个解, 因此共有 T₁ × T₂ × … × T_k 个排列组合方法, 即共有此数量的根. 由于（1）与（2）互为充要条件, 所以（1）中的根的数量等于（2）中各因子解的数量乘积. **31.6元素的幂** 欧拉定理：对于任意整数n>1,a^φ(n)≡1(mod n)对所有a∈Zn*都成立。 费马定理：如果p是素数，则a^(p-1))≡1(mod p)对所有a∈Zp*都成立. 定理31.32 对所有的素数p>2和所有正整数e,使得Zn*是循环群的n>1的值为2,4，p^e 2p^e. 如果$\text{ord}_n(g) = \left| \mathbb{Z}_n^* \right|$ ，那么对于模$n$下的每一个元素，在$\mathbb{Z}_n^*$中都可表示为$g$的某个幂次；并且$g$既是$\mathbb{Z}_n^*$中的一个原根也是其生成元。 当$g$为原根且$a$属于$\mathbb{Z}_n^*$时，则必然存在某个整数$z$满足$g^z \equiv a \pmod{n}$。此时，这个整数$z$被称为在模$n$下的离散对数或者基数为$g$的指数，并用$\operatorname{ind}(a)$表示。 定理31.34 如果p是一个奇素数且指数e≥1，则同余方程x²≡1(mod p^e)仅有两个平凡解即x=±1；当x不等于这两个平凡根±1时，则称其为模n（此处指模p^e）下的**非平凡平方根** 推论31.35 如果对模n存在1的非平凡平方根，则n是合数。 根据题意： 请先画一个表格来列出$Z_{11}^*$中各个元素及其阶数。 随后确定最小的那个生成元g 并完成另一个表格来计算每个$x \in Z_{11}^*$对应的指数ind(x) | 元素= | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |||||||||||| |---|---|---|---|---|---|---|---|---|---|---| | i次=1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 || | 2 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 || | 3 | 1 | 8 | 5 | 9 | 4 | 7 | 2 | 6 | 3 | 10 || | 4 | 1 | 5 | 4 | 3 | 9 | 9 | 3 | 4 | 5 | 1 || | 5 | 1 | 10 | 1 | 1 | 1 | 10 | 10 | 10 | 1 | 10 || | 6 | 1 | 9 | 3 | 4 | 5 | 5 | 4 | 3 | 9 | 1 || | 7 | 1 | 7 | 9 | 5 | 3 | 8 | 6 | 2 | 4 | 10 || | 8 | 1 | 3 | 5 | 9 | 4 | 4 | 9 | 5 | 3 | 1 || | 9 | 1 | 6 | 4 | 3 | 9 | 2 | 8 | 7 | 5 | 10 || | 10 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 || | 阶ord | 1 | 10 | 5 | 5 | 5 | 10 | 10 | 10 | 5 | 2 || 最小原根g=2 | x= | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |||||||||||| |---|---|---|---|---|---|---|---|---|---|---| | ind | 10 | 1 | 8 | 2 | 4 | 9 | 7 | 3 | 6 |5| 请编写一个模取幂算法，请描述该算法需依次处理b各位数字时遵循自低位至高位的顺序而无需遵循自高位至低位的标准流程。 ``` #include using namespace std; #define len 10 //int c[len]={0}; int* BIT(int bb,int b[]) {    int i=0;      while (i!=len&&b!=0)    {     b[i]=bb%2;     bb=bb/2;     i++;    }    return b; } //从右向左检查b的各位顺序 int MODULAR_EXPONENTIATION(int a,int b[],int n) {  int c=0;  int d=a;  int t=1;  for (int i=0;i #include using namespace std; #define len 10 #define nn 120 struct t {  int d,x,y,z; }s; struct t extended_eucild(int a,int b) {  if (b==0)  {   s.d=a;   s.x=1;   s.y=0;   return s;  }  else  {      struct t ss=extended_eucild(b,a%b);   s.d=ss.d;   s.x=ss.y;   s.y=ss.x-(a/b)*ss.y;   return s;  } } int* BIT(int bb,int b[]) {  int i=0;    while (i!=len&&b!=0)  {   b[i]=bb%2;   bb=bb/2;   i++;  }  return b; } //从左向右检查b的各位顺序 int MODULAR_EXPONENTIATION(int a,int b[],int n) {  int c=0;  int d=1;  for (int i=len-1;i>=0;i--)  {   c=2*c;   d=(d*d)%n;   if (b[i]==1)   {    c++;    d=(d*a)%n;   }  }  return d; } //计算F(n) 欧拉常数 int f(int n) {  double temp=n;   for (int i=2;i<=n;i++)  {   int flag=0;   if (n%i==0)   {    for (int j=2;j<=sqrt(i);j++)    {     if (i%j==0)     {      flag=1;     }    }        if (flag==0)    {     double k=i;     temp*=((k-1.0)/k);    }   }  }  return temp; } //求Zn*中所有元素a的集合 也是对于模n的乘法群 int ZnX(int a[],int n) {  int t=0;  for (int i=1;id=187 M=100时，密文C=P(M)=M^e mod n=100^3 mod 319=254 31.7-2和31.7-3以我现有知识无法解决，略去. **31.8素数的测试** 素数的密度：**定理31.37（素数定理） lim(π(n)/(n/lnn))=1** 我可以用**埃拉托斯特尼筛法**对素数进行验证。然而，在效率上来看，经过实际测试发现该方法在速度和计算资源消耗上不及MILLER-RABIN算法。 如果n是一个合数，且a^(n-1)≡1(mod n) 则称n是一个基为a的**伪素数** 。 **Carmichael number** is referred to as a composite number that can falsely pass the Fermat primality test, which is a property derived from Fermat's little theorem. Such numbers, though rare (only 255 in the range up to 1 billion), do exist and pose challenges in primality testing using the Fermat method. Below, we will explore the detection of Carmichael numbers and provide a practical implementation for identifying primes using Fermat's theorem. ``` //查找carmichael数:这个代码利用朴素的试除法与简单的费马定理作对比，两者结果相反，则是carmichael数 #include #include using namespace std; #define len 15 #define COMPOSITE 0 #define PRIME 1 int* BIT(int bb,int b[]) { int i=0; while (i!=len&&b!=0) { b[i]=bb%2; bb=bb/2; i++; } return b; } //从左向右检查b的各位顺序 int MODULAR_EXPONENTIATION(int a,int b[],int n) { int c=0; int d=1; for (int i=len-1;i>=0;i--) { c=2*c; d=(d*d)%n; if (b[i]==1) { c++; d=(d*a)%n; } } return d; } bool PSEUDOPRIME(int n,int b[]) { if (MODULAR_EXPONENTIATION(2,BIT(n-1,b),n)!=1) { return COMPOSITE; } else return PRIME; } int Primer(int n) { int Flag=0; for (int i=2;i<=sqrt(n);i++) { if (n%i==0) { Flag=1; cout< using namespace std; #define len 80 #define COMPOSITE 0 #define PRIME 1 unsigned __int64 bit_Multiplication(__int64 a, __int64 b,unsigned __int64 m)//防止溢出__int64 {//思想是将a与b尽量转化成较小的数再求余数.转化过程中遇＞m的情况，则对m求余 // 比如求(56*121)mod 200=(56*(4*30+1))mod 200=((56*4-200)*30+56*1)mod 200=(24*(9*3+3)+56*1)mod 200=((24*9-200)*3+3*24+56)mod 200=(48+73+56) mod200 __int64 rem=0;//初始化余数 while (b) { __int64 t=a;//将乘数a用临时变量t保存起来 if ((a<<=1)>=m)//如果在移位时＞m了， { a-=(a/m)*m;//那么只保留余数 } if (b&1)//如果乘数b的二进制位上是1，则执行if语句 { rem+=t;//对分解a与b过程中产生的剩余部分求和 if (rem>=m)//如果这个和＞m { rem-=(rem/m)*m;//那么对剩余部分求余 } } b>>=1; } return rem; } int* BIT(unsigned __int64 bb, int b[]) { int i = 0; while (i != len&&bb != 0) { b[i] = bb % 2; bb>>=1; i++; } return b; } //从左向右检查b的各位顺序 unsigned __int64 MODULAR_EXPONENTIATION(unsigned __int64 a, int b[], unsigned __int64 n) { int c = 0; unsigned __int64 d = 1; for (int i = len - 1; i >= 0; i--) { d=bit_Multiplication(d,d,n); if (d>n/2) { d = n-d;//利用同余原理，取较小的余数 } if (b[i] == 1) { d=bit_Multiplication(d,a,n); if (d>n/2) { d = n-d;//利用同余原理，取较小的余数 } } } return d; } bool WITNESS(unsigned __int64 a, int b[], unsigned __int64 n)//由于n为偶数时比为合数，所以我们忽略偶数情况，只对奇数进行判断！ { unsigned __int64 temp = n - 1, s = 0; int t=0; while (!bit_Multiplication(temp,1,2)) { temp /= 2; t++; } unsigned __int64 u = temp; __int64 x = MODULAR_EXPONENTIATION(a, BIT(u, b), n); __int64 y=1; for (int i = 0; in / 2) { y -= n;//利用同余原理，取较小的余数 } if (y == 1 && x != 1 &&x!=-1&& x != n - 1) { return true; } x=y; } if (y != 1) { return true; } return false; } int MILLER_RABIN(unsigned __int64 n, unsigned __int64 s, int b[]) { unsigned __int64 t = bit_Multiplication(n,1,2); if (n==2||n==3) { return PRIME; } if ((!t)) { return COMPOSITE; } if( n < 1373653 ) //下面这一组if-else是网上找到选取基值a方法 { if( WITNESS(2, b, n) || WITNESS(3, b, n) ) return COMPOSITE; } else if( n < 9080191 ) { if( WITNESS(31, b, n) || WITNESS(73, b, n) ) return COMPOSITE; } else if( n < 4759123141 ) { if( WITNESS(2, b, n) ||WITNESS(3, b, n) ||WITNESS(5, b, n) ||WITNESS(11, b, n) ) return COMPOSITE; } else if( n < 2152302898747 ) { if( WITNESS(7, b, n) ||WITNESS(3, b, n) || WITNESS(5, b, n) || WITNESS(2, b, n) || WITNESS(11, b, n) ) return COMPOSITE; } else { if( WITNESS(7, b, n) || WITNESS(3, b, n) || WITNESS(5, b, n) || WITNESS(2, b, n) || WITNESS(11, b, n) || WITNESS(31, b, n) || WITNESS(61, b, n) || WITNESS(73, b, n) ) return COMPOSITE; } return PRIME; } int main() { int j = 0; for (double i = 11111111900; i<11111112000; i++) //for (double i=2;i<100;i++) { int *b = new int[len]; if (MILLER_RABIN(i, 1, b)) { j++; cout << i << " "; } } cout << "共" << j << endl; return 0; } ``` **31.8-1 证明**：如果一个奇整数$n>1$不是素数或者其幂，则必定存在一对以$n$为模的一对非平凡平方根。 设n为不同素因数组成（每个素因数均不小于3）的乘积形式。根据定义可知，在这种情况下自然满足以下条件：一是整数值必须大于等于3；二是各个指数均为正整数值且互不相同。 因为p₁、p₂……pₙ均为不小于3的不同素数。所以它们各自的幂次形式分别为互质关系。基于孙子定理可知：求解同余式x² ≡ 1 (mod n)的问题等价于求解同余式组x² ≡ 1 (mod p_i^{e_i})（i = 1, 2, …, k）。对于每一个奇素数p_i和指数e_i ≥ ¹而言，在模p_i^{e_i}下同余式x² ≡ ¹仅存在两个解。根据前述讨论可知：当n至少有两个不同的素因子时（即n = p₁^{¹} × p₂^{¹} × … × p_k^{¹}），则在模n下同余式x² ≡ ¹将至少有两个不同的平凡解（即±₁）。然而，在模每个不同素因子幂次下的方程均只有两个平凡解的情况下（如前述），其乘积结果将产生更多的非平凡平方根 **3.8-2 可以将欧拉定理稍作加强……** 其中$n=\prod_{i=1}^{r} p_i^{e_i}$ ，而$\lambda (n)$则被定义为$\lambda (n)=\text{lcm}\{\phi (p_₁^{e₁}),\ldots,\phi (p_r^{e_r})\}$ 。请证明$\lambda (n)$能够整除$\phi (n)$ 。如果进一步满足$\lambda (n)$能够整除$n−$ $ ¹$ ，那么合数$n$就被称为卡迈克尔（Carmichael）数字。最小的卡迈克尔数字是$56₁=3×¹¹×¹₇$；这里计算得$\lambda (56₁)=\text{lcm}\{2,~¹⁰,~¹⁶\}=8₀$ ，并且它能够整除$56₀$ 。进一步证明卡迈克尔数字必须同时满足两个条件：一是它们不含平方因子（即不能被任何素因式的平方所整除）；二是它们必须至少分解为三个不同素因式的乘积。（因此这类数字并不常见） 由此可得： $φ(p_r^{e_r}) = p_r^{e_r - 1}(p_r - 1)$， 因此， $φ(n) = n \prod_{i=1}^{r}\left( 1 - \frac{ }{p_i} \right )$， 即， $φ(n) = \left ( \prod_{i= }^{ } p_i^{e_i} \right ) \cdot \prod_{i= }^{ } \left ( 1 - \frac{ }{p_i} \right ) = \prod_{i= }^{ } φ(p_i^{e_i})$。 因为 λ(n) 是 $\{\varphi(p_ i^{ e_i })\}_{i= }^{ }$ 的最小公倍数， 所以 λ(n) 整除 φ(n)，即 λ(n)|φ(n)。 由此可得： $\varphi(p_r^{e_r}) = p_r^{e_r - ¹}(p_r -¹)$， 因此， $\varphi(n) = n\prod_{i=¹}^{r}\left( ¹ - \frac{ }{p_i}\right)$， 即， $\varphi(n) = \left(\prod_{i= } p_i^{e_i}\right)\cdot\prod_{i= } \left( ¹ - \frac{ }{p_i}\right) = \prod_{i= }\varphi(p_i^{e_i})$。 因为 $\lambda (n)$ 是 $\{\varphi(p_ i ^{ e_i })\}_{i= }$ 的最小公倍數， 所以 $\lambda (n)\mid\varphi (n)$ 即 $\lambda (n)|\varphi (n)$。 **(2)** 如果$\lambda (n)$能够整除$n−$** **** ** ** ** ** ** ** ** ** ** ** ** ** ** $**$**$**$**$**$**$**, 那么可以表示为$n−= \lambda (n)\cdot k$（其中$k\in Z$）。对于所有$a\in Z_n^*$（即模$n$可逆的整数组成的集合），都有$a^{\lambda (n)} ≡ 1 \pmod{n}$。根据同余性质可知其可乘性：$(a^{\lambda (n)})^k ≡ 1^k \pmod{n}$ 即 $a^{n−} ≡ 1 \pmod{n}$。（见式(Ⅰ)) 因此如果$n$是合数并且满足上述式(Ⅰ)，则称其为Carmichael数。 **（3）若对于所有整数a满足$2 \leq a \leq n-2$都有$a^{n-2} \equiv 2 \mod n$成立，则设$n$有一个素因子$p$且$p^{k}$为其最大指数幂次（其中$k > 0$）。取$a = p^{k} \in (2, n-2)$时，则有$p^{k(n - k)} \equiv p^{k} \mod n$即$n$整除$p^{k(n - k)} - p^{k}$。然而由于$p^{k + 1}$能够整除$n$可知：

p^{k + 1} \mid p^{k(n - k)} - p^{k}