信息安全数学基础-欧拉定理 快速模幂 2021-09-28
6. 欧拉定理 快速模幂1. 欧拉定理和Fermat定理欧拉定理（很重要！！！！！）定理（Euler定理）若(k,m)=1, 则 kφ(m)≡1(mod m)若(k,m)=1,\ 则\ k^{\varphi(m)}≡1(mod\ m)若(k,m)=1, 则 kφ(m)≡1(mod m)证明设置a1,a2,...,aφ(m)是模m的一个既约
6. 欧拉定理 快速模幂
1. 欧拉定理和Fermat定理
欧拉定理（很重要！！！！！）
定理（Euler定理）
若(k,m)=1, 则 kφ(m)≡1(mod m) 若(k,m)=1,\ 则\ k^{\varphi(m)}≡1(mod\ m) 若(k,m)=1, 则 kφ(m)≡1(mod m)
证明
设置a1,a2,...,aφ(m)是模m的一个既约剩余系由于(k,m)=1,则ka1,ka2,...,kaφ(m)也是模m的一个既约剩余系从而有：∏i=1φ(m)(kai)≡∏i=1φ(m)(ai)(mod m)(左右两边都是一个既约剩余系相乘)进而有：kφ(m)∏i=1φ(m)(ai)≡∏i=1φ(m)(ai)(mod m)从而kφ(m)≡1(mod m)(由于每一个ai都与m互素，因此∏i=1φ(m)(ai)与m互素，由同余的性质知可以约去) 设置a_1,a_2,...,a_{\varphi(m)}是模m的一个既约剩余系 \\由于(k,m)=1,则ka_1,ka_2,...,ka_{\varphi(m)}也是模m的一个既约剩余系 \\从而有：\prod_{i = 1}^{\varphi(m)}(ka_i)≡\prod_{i = 1}^{\varphi(m)}(a_i)(mod\ m) \\(左右两边都是一个既约剩余系相乘) \\进而有：k^{\varphi(m)}\prod_{i = 1}^{\varphi(m)}(a_i)≡\prod_{i = 1}^{\varphi(m)}(a_i)(mod\ m) \\从而k^{\varphi(m)}≡1(mod\ m) \\(由于每一个a_i都与m互素，因此\prod_{i = 1}^{\varphi(m)}(a_i)与m互素，由同余的性质知可以约去) 设置a1,a2,...,aφ(m)是模m的一个既约剩余系由于(k,m)=1,则ka1,ka2,...,kaφ(m)也是模m的一个既约剩余系从而有：i=1∏φ(m)(kai)≡i=1∏φ(m)(ai)(mod m)(左右两边都是一个既约剩余系相乘)进而有：kφ(m)i=1∏φ(m)(ai)≡i=1∏φ(m)(ai)(mod m)从而kφ(m)≡1(mod m)(由于每一个ai都与m互素，因此i=1∏φ(m)(ai)与m互素，由同余的性质知可以约去)
Fermat小定理
Corollary（Fermat小定理）
若p为素数，则对所有的整数a有ap≡a(mod p) 若p为素数，则对所有的整数a有a^p≡a(mod\ p) 若p为素数，则对所有的整数a有ap≡a(mod p)
证明
因p是素数，则对任何整数a，有p∣a，或(a,p)=1若p∣a，显然有ap≡a(mod p)（令pq=a,一看便知）若(a,p)=1，则由欧拉定理, aφ(p)≡1(mod p)又φ(p)=p−1，于是ap−1≡1(mod p)⇨ap≡a(mod p) 因p是素数，则对任何整数a，有p|a，或(a,p)=1 \\若p|a，显然有a^p≡a(mod\ p)（令pq=a,一看便知） \\若(a,p)=1，则由欧拉定理,\ a^{\varphi(p)}≡1(mod\ p) \\又\varphi(p)=p-1，于是 \\a^{p-1}≡1(mod\ p)⇨a^p≡a(mod\ p) 因p是素数，则对任何整数a，有p∣a，或(a,p)=1若p∣a，显然有ap≡a(mod p)（令pq=a,一看便知）若(a,p)=1，则由欧拉定理, aφ(p)≡1(mod p)又φ(p)=p−1，于是ap−1≡1(mod p)⇨ap≡a(mod p)
- 费马小定理虽然可以看作是欧拉定理的推论，但从费马小定理也可以推出欧拉定理
Fermat小定理的逆定理是否成立？答案：不成立
证明思路：2Fn≡2(modFn)2^{F_n}≡2(mod F_n)2Fn≡2(modFn)，但是F5F_5F5是合数
证明过程如下：
设n是正整数，记Fn=22n+1，则有2Fn≡2(mod Fn)证明：当n≤4时，Fn是素数，由Fermat小定理可知结论成立当n≥5时，有n+1<2n,从而2n+1∣2n记22n=k2n+1,则2Fn−2=(222n+1−2)=(2k2n+1+1−2)=(2⋅2k2n+1−2)=2(2k2n+1−1)=2((2n+1)k−1)=2Q1(22n+1−1)=2Q1(22n⋅2−1)=2Q1((22n)2−1)=Q2(22n+1)由于Q1,Q2是整数，上式即为：2Fn≡2(modFn)由于F5是合数，说明Fermat小定理的逆定理不成立 设n是正整数，记F_n=2^{2^n}+1，则有2^{F_n}≡2(mod\ F_n) \\证明：当n\leq 4时，F_n是素数，由Fermat小定理可知结论成立 \\当n\geq 5时，有n+1<2^n,从而2^{n+1}|2^n \\记2^{2^n}=k2^{n+1},则 \\2^{F_n}-2=(2^{2^{2^n}+1}-2) \\=(2^{k2^{n+1}+1}-2) \\=(2·2^{k2^{n+1}}-2) \\=2(2^{k2^{n+1}}-1) \\=2({(2^{n+1})}^k-1) \\=2Q_1(2^{2^{n+1}}-1) \\=2Q_1(2^{2^n·2}-1) \\=2Q_1({(2^{2^n})}^2-1) \\=Q_2(2^{2^n}+1) \\由于Q_1,Q_2是整数，上式即为：2^{F_n}≡2(mod F_n) \\由于F_5是合数，说明Fermat小定理的逆定理不成立 设n是正整数，记Fn=22n+1，则有2Fn≡2(mod Fn)证明：当n≤4时，Fn是素数，由Fermat小定理可知结论成立当n≥5时，有n+1<2n,从而2n+1∣2n记22n=k2n+1,则2Fn−2=(222n+1−2)=(2k2n+1+1−2)=(2⋅2k2n+1−2)=2(2k2n+1−1)=2((2n+1)k−1)=2Q1(22n+1−1)=2Q1(22n⋅2−1)=2Q1((22n)2−1)=Q2(22n+1)由于Q1,Q2是整数，上式即为：2Fn≡2(modFn)由于F5是合数，说明Fermat小定理的逆定理不成立
2. Wilson定理
定理（Wilson定理）
设p是一个素数，则 (p−1)!≡−1(mod p) 设p是一个素数，则\ (p-1)!≡-1(mod\ p) 设p是一个素数，则 (p−1)!≡−1(mod p)
证明
p=2时，(2−1)!≡−1(mod 2)设p≤3,则对于每个a, 1≤a<p,存在唯一的整数a′, 1≤a′<p,使得:aa′≡1(mod p)(这是因为p是素数，对于小于p的整数a，一定有(a,p)=1)于是，a′=a⇿a2≡1(mod p),这时a=1或a=p−1（为什么呢???）因此当a与a′取2,...p−2中的数时，a≠a′。把2,3,...,p−2中的a与a′配对，有(aa′)(aa′)...(aa′)=2⋅3...(p−2)因aa′≡1(mod p)，所以2⋅3...(p−2)≡1(mod p)故(p−1)!≡1⋅(p−1)≡−1(mod p) p = 2时，(2-1)!≡-1(mod\ 2) \\设p\leq 3,则对于每个a,\ 1\leq a <p,存在唯一的整数a',\ 1\leq a'<p ,使得: \\aa'≡1(mod\ p) \\(这是因为p是素数，对于小于p的整数a，一定有(a,p)=1) \\于是，a'=a⇿a^2≡1(mod \ p),这时a=1或a=p-1（为什么呢???） \\因此当a与a'取2,...p-2中的数时，a≠a'。 \\把2,3,...,p-2中的a与a'配对，有 \\(aa')(aa')...(aa')=2·3...(p-2) \\因aa'≡1(mod\ p)，所以2·3...(p-2)≡1(mod\ p) \\故(p-1)!≡1·(p-1)≡-1(mod\ p) p=2时，(2−1)!≡−1(mod 2)设p≤3,则对于每个a, 1≤a<p,存在唯一的整数a′, 1≤a′<p,使得:aa′≡1(mod p)(这是因为p是素数，对于小于p的整数a，一定有(a,p)=1)于是，a′=a⇿a2≡1(mod p),这时a=1或a=p−1（为什么呢???）因此当a与a′取2,...p−2中的数时，a=a′。把2,3,...,p−2中的a与a′配对，有(aa′)(aa′)...(aa′)=2⋅3...(p−2)因aa′≡1(mod p)，所以2⋅3...(p−2)≡1(mod p)故(p−1)!≡1⋅(p−1)≡−1(mod p)
对（为什么呢???）的解答：
aa′≡1(mod p)且a=a′⇒a2−1≡0(mod p)⇒p∣a2−1⇒p∣(a−1)(a+1)由于p是素数，因此p∣(a−1)和p∣(a+1)至少一个成立若p∣(a−1)，由于1≤a<p，知只能取a−1=0⇒a=1若p∣(a+1)，由于1≤a<p，知只能取a+1=p⇒a=p−1 aa'≡1(mod\ p)且a=a' \\ \Rightarrow a^2-1≡0(mod\ p) \\ \Rightarrow p|a^2-1 \\ \Rightarrow p|(a-1)(a+1) \\由于p是素数，因此p|(a-1)和p|(a+1)至少一个成立 \\若p|(a-1)，由于1\leq a<p，知只能取a-1 = 0\Rightarrow a=1 \\若p|(a+1)，由于1\leq a<p，知只能取a+1 = p\Rightarrow a=p-1 aa′≡1(mod p)且a=a′⇒a2−1≡0(mod p)⇒p∣a2−1⇒p∣(a−1)(a+1)由于p是素数，因此p∣(a−1)和p∣(a+1)至少一个成立若p∣(a−1)，由于1≤a<p，知只能取a−1=0⇒a=1若p∣(a+1)，由于1≤a<p，知只能取a+1=p⇒a=p−1
Wilson定理的逆定理成立
逆定理
设n是使得(n−1)!≡−1(mod n)成立的正整数且n≥2,则n是一个素数。 设n是使得(n-1)!≡-1(mod\ n)成立的正整数且n\geq 2,则n是一个素数。 设n是使得(n−1)!≡−1(mod n)成立的正整数且n≥2,则n是一个素数。
证明
反证法：假设n是一个合数，则存在整数1<a<n，1<b<n，使得n=ab因此a∣(n−1)!，而由题设(n−1)!≡−1(mod n),得n∣(n−1)!+1而a∣n，得a∣(n−1)!+1又a∣(n−1)!，得a∣1，但a>1，矛盾 反证法：假设n是一个合数，则存在整数1<a<n，1<b<n，使得n = ab \\因此a|(n-1)!，而由题 \\设(n-1)!≡-1(mod\ n),得n|(n-1)!+1而a|n，得a|(n-1)!+1 \\又a|(n-1)!，得a|1，但a>1，矛盾 反证法：假设n是一个合数，则存在整数1<a<n，1<b<n，使得n=ab因此a∣(n−1)!，而由题设(n−1)!≡−1(mod n),得n∣(n−1)!+1而a∣n，得a∣(n−1)!+1又a∣(n−1)!，得a∣1，但a>1，矛盾
- Wilson定理可用来判断一个合数不是素数
欧拉定理得应用
1. 计算7100017^{10001}710001的十进制表示中的个位数
7φ(10)≡1(mod 10)710001=74∗2500+1≡7(mod 10) 7^{\varphi(10)}≡1(mod\ 10) \\7^{10001}=7^{4*2500+1}≡7(mod\ 10) 7φ(10)≡1(mod 10)710001=74∗2500+1≡7(mod 10)
2. 求逆元
利用欧拉定理，可以得到一个求元素逆元的方法，即给定正整数a和n，其中(a , n)=1，求a−1mod na^{-1}mod\ na−1mod n
利用欧拉定理aφ(n)≡1(mod n)从而有a⋅aφ(n)−1≡1(mod n)，因此a−1≡aφ(n)−1(mod n) 利用欧拉定理a^{\varphi(n)}≡1(mod\ n) \\从而有a·a^{\varphi(n)-1}≡1(mod\ n)，因此 \\a^{-1}≡a^{\varphi(n)-1}(mod\ n) 利用欧拉定理aφ(n)≡1(mod n)从而有a⋅aφ(n)−1≡1(mod n)，因此a−1≡aφ(n)−1(mod n)
3. 快速模幂算法
模幂算法：直观算法
在模运算中，常常要对大模数m和大整数n，计算bn(mod m)b^n(mod\ m)bn(mod m)
最直观的想法，可以递归地计算
b1≡b(mod m),b2≡b⋅b1(mod m),b3≡b⋅b2(mod m),...,bn≡b⋅bn−1(mod m)b_1≡b(mod\ m),b_2≡b·b_1(mod\ m),b_3≡b·b_2(mod\ m),...,b_n≡b·b_{n-1}(mod\ m)b1≡b(mod m),b2≡b⋅b1(mod m),b3≡b⋅b2(mod m),...,bn≡b⋅bn−1(mod m)
当n很大时，直观算法不实用，乘法取模次数为n-1
当n=21000时，这个次数是个天文数字
快速模幂算法
求bn mod mb^n\ mod\ mbn mod m快速模幂算法
Step1. 计算n的二进制表示
n=n0⋅20+n1⋅21+n2⋅22+...+nr⋅2r,n0,...,nr∈{0，1}n = n_0·2^{0}+n_1·2^{1}+n_2·2^{2}+...+n_r·2^{r},n_0,...,n_r∈\{0，1\}n=n0⋅20+n1⋅21+n2⋅22+...+nr⋅2r,n0,...,nr∈{0，1}
这里nr=1n_r=1nr=1
Step2. 计算b2i(mod m)，0≤i≤rb^{2^i}(mod\ m)，0\leq i\leq rb2i(mod m)，0≤i≤r
a0≡b(mod m)a_0≡b(mod\ m)a0≡b(mod m)
a1≡a02≡b21(mod m)a_1≡{a_0}^2≡b^{2^1}(mod\ m)a1≡a02≡b21(mod m)
a2≡a12≡b22(mod m)a_2≡{a_1}^2≡b^{2^2}(mod\ m)a2≡a12≡b22(mod m)
a3≡a22≡b23(mod m)a_3≡{a_2}^2≡b^{2^3}(mod\ m)a3≡a22≡b23(mod m)
…
ar≡ar−12≡b2r(mod m)a_r≡{a_{r-1}}^2≡b^{2^r}(mod\ m)ar≡ar−12≡b2r(mod m)
每一项是前一项的平方，因此总共需要r次乘法
Step3. 最后计算bn(mpd m)b^n(mpd\ m)bn(mpd m)如下
bn=bn0+n1⋅21+n2⋅22+...+nr⋅2r=bn0⋅(b2)n1⋅(b22)n2⋅(b23)n3...⋅(b2r)nr≡a0n0⋅a1n1⋅a2n2⋅a3n3⋅...arnr(mod m) b^n=b^{n_0+n^1·2^{1}+n^2·2^{2}+...+n^r·2^{r}} \\=b^{n_0}·{(b^2)}^{n_1}·{({b^2}^2)}^{n_2}·{({b^2}^3)}^{n_3}...·{({b^2}^r)}^{n_r} \\≡{a_0}^{n_0}·{a_1}^{n_1}·{a_2}^{n_2}·{a_3}^{n_3}·...{a_r}^{n_r}(mod \ m) bn=bn0+n1⋅21+n2⋅22+...+nr⋅2r=bn0⋅(b2)n1⋅(b22)n2⋅(b23)n3...⋅(b2r)nr≡a0n0⋅a1n1⋅a2n2⋅a3n3⋅...arnr(mod m)
由于在第二部已经计算了a0,a1,...,ara_0,a_1,...,a_ra0,a1,...,ar，最后只需要查看哪些nin_ini不为0，共需要不超过r的乘法
快速模幂算法的运行时间：
- 至多2r次模乘运算，由于n>2r2^r2r，从而至多2log2n2{log}_2n2log2n次模乘运算
- 当n约等于210002^{1000}21000时，计算2n mod m2^n\ mod\ m2n mod m需要大约2000次模乘即可完成
- 但是，快速模幂算法需要储存中间结果，为进一步优化，需考虑减少存储需求，进而有平方乘算法。
平方乘算法（从低位到高位）
n的二进制展开后，循环从低位到高位
Square-and-Multiply(b , n , m){
#平方乘算法，计算c=b^n(mod m)
#输入：整数b,幂次n，模数m
#输出：模幂的结果c
n = n0+n1*2^1+n2*2^2+...+nr*2^r, n0,...,n(r-1)取值0或1，n_r = 1
c = 1,若n = 0，返回c
A = b
若n0 = 1，则令c = b
for i = 1 to r{
A = A*A mod m
if ni = 1 c ← A*c mod m
}
return c
}
平方乘算法（从高位到低位）
n的二进制展开后，循环从高位到低位
Square-and-Multiply(b , n , m){
#平方乘算法，计算c=b^n(mod m)
#输入：整数b,幂次n，模数m
#输出：模幂的结果c
n = n0+n1*2^1+n2*2^2+...+nr*2^r, n0,...,n(r-1)取值0或1，n_r = 1
c = 1
for i = r to 0{
c = c*c mod m
if ni = 1 c ← c*b mod m
}
return c
}
平方乘算法注记：
- 从低位到高位计算的次序、计算的复杂度相同，但存储略有不同（从高位到地位略好），一般采用高位到低位
- 两种次序的平方乘算法的正确性证明：作业
- 其他进制表示法：预计算 + 从低位到高位
- 平方乘算法应用在RSA密码算法的实现中
几个例子
快速模幂算法
计算3218(mod 100)3^{218}(mod \ 100)3218(mod 100)：
3218=2+23+24+26+273^{218}=2+2^3+2^4+2^6+2^73218=2+23+24+26+27
3218=32+23+24+26+27=321⋅323⋅324⋅326⋅3273^{218}=3^{2+2^3+2^4+2^6+2^7}=3^{2^1}·3^{2^3}·3^{2^4}·3^{2^6}·3^{2^7}3218=32+23+24+26+27=321⋅323⋅324⋅326⋅327
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 32i(mod 1000)3^{2^i}(mod\ 1000)32i(mod 1000) | 3 | 9 | 81 | 561 | 721 | 841 | 281 | 961 |
3218=321⋅323⋅324⋅326⋅3273^{218}=3^{2^1}·3^{2^3}·3^{2^4}·3^{2^6}·3^{2^7}3218=321⋅323⋅324⋅326⋅327
≡9⋅561⋅721⋅281⋅961(mod 1000)≡9·561·721·281·961(mod\ 1000)≡9⋅561⋅721⋅281⋅961(mod 1000)
≡489(mod 1000)≡489(mod\ 1000)≡489(mod 1000)
平方乘算法（从低位到高位）
5596 mod 12345^{596}\ mod\ 12345596 mod 1234
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| nin_ini | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| A | 5 | 25 | 625 | 681 | 1011 | 369 | 421 | 779 | 947 | 925 |
| c | 1 | 1 | 625 | 625 | 67 | 67 | 1059 | 1059 | 1059 | 1013 |
平方乘算法（从高位到低位）
5596 mod 12345^{596}\ mod\ 12345596 mod 1234
| i | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|
| nin_ini | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| c | 5 | 25 | 625 | 937 | 595 | 596 | 453 | 591 | 59 | 1013 |
4. 欧拉定理的应用：循环小数秘密
问题的提出
任何一个有理数都可以写成分数的形式，即ab,b>0\frac{a}{b},b>0ba,b>0。由带余除法知，a=qb+r，0≤r<ba = qb + r，0\leq r<ba=qb+r，0≤r<b，即：
ab=q+br, 0≤rb<1 \frac{a}{b}=q+\frac{b}{r},\ \ 0\leq \frac{r}{b}<1 ba=q+rb, 0≤br<1
那么只需要讨论0与1之间的分数与小数互化
循环小数的定义
循环小数的定义
若对一个无限小数0.a1a2...an...0.a_1a_2...a_n...0.a1a2...an...（ana_nan是0 , 1 , … , 9中的一个数，并且从任何一位以后不全是0），能找到两个整数s≥0,t>0s\geq0,t>0s≥0,t>0使得
as+i=as+i+kt , i=1,2,...,t;k=0,1,2,... a_{s+i}=a_{s+i+kt} \ , \ \ i=1,2,...,t;k=0,1,2,... as+i=as+i+kt , i=1,2,...,t;k=0,1,2,...
则称之为循环小数，并简单记作0.a1a2...asa˙s+1...a˙s+t0.a_1a_2...a_s\dot{a}_{s+1}...\dot{a}_{s+t}0.a1a2...asa˙s+1...a˙s+t
对于循环小数而言，具有上述性质的s及t是不止一个的，若找到的t是最小的，则称as+1...as+t{a}_{s+1}...a_{s+t}as+1...as+t为循环节；t称为循环节的长度；若最小的s = 0，则称这个小数为纯循环小数，否则叫混循环小数。
问题的提出
对有理数ab，0≤a<b，(a,b)=1\frac{a}{b}，0\leq a<b，(a,b)=1ba，0≤a<b，(a,b)=1，满足什么条件下可以表示成纯循环小数？
纯循环小数的判定
定理
有理数ab，0≤a<b，(a,b)=1\frac{a}{b}，0\leq a<b，(a,b)=1ba，0≤a<b，(a,b)=1，能表成纯循环小数的充分必要条件是(b,10)=1(b,10)=1(b,10)=1
证明
必要性：
先证明必要性：若ab能表成纯循环小数，则由0<ab<1可知ab=0.a1a2...ata1a2...at...因而10tab=10t−1a1+10t−2a2+...+10at−1+at+0.a1a2...ata1a2...at...=q+ab(q>0)故有ab=q10t−1,即a(10t−1)=bq.由(a,b)=1即得b∣(10t−1)，因而(b,10)=1（b=10t−1=99...9=11...1×9,因此b与10互素） 先证明必要性：若\frac{a}{b}能表成纯循环小数，则由0<\frac{a}{b}<1可知 \\\frac{a}{b}=0.a_1a_2...a_ta_1a_2...a_t... \\因而10^t\frac{a}{b} \\=10^{t-1}a_1+10^{t-2}a_2+...+10a_{t-1}+a_t+0.a_1a_2...a_ta_1a_2...a_t... \\=q+\frac{a}{b}(q>0) \\故有\frac{a}{b}=\frac{q}{10^t-1},即a(10^t-1)=bq. \\由(a,b)=1即得b|(10^t-1)，因而(b,10)=1 \\（b=10^t-1=99...9=11...1×9,因此b与10互素） 先证明必要性：若ba能表成纯循环小数，则由0<ba<1可知ba=0.a1a2...ata1a2...at...因而10tba=10t−1a1+10t−2a2+...+10at−1+at+0.a1a2...ata1a2...at...=q+ba(q>0)故有ba=10t−1q,即a(10t−1)=bq.由(a,b)=1即得b∣(10t−1)，因而(b,10)=1（b=10t−1=99...9=11...1×9,因此b与10互素）
没看懂充分性的证明……一定回来复盘重新看一下！！！！！！！
再证明充分性：若(b,10)=1,则由欧拉定理知，存在一个整数t，使得10t≡1(mod b),0≤t≤φ(b)因此10ta=qb+a，且0<q<10tab≤10t(1−1b)<10t−1，（第一个≤号：用到a+1≤b；最后一个<号：用到b<10t）(这又是为什么呢？？？)故10tab=q+ab令q=10q1+at, q1=10q2+at−1,..., qt−1=10qt+a1, 0≤ai则q=10tqt+10t−1a1+...+10at−1+at,由0<q<10t−1得qt=0且a1,a2,...,at不全是9，也不全是0，因此q10t=0.a1a2...atab=0.a1a2...at+110t⋅ab反复应用上式即得ab=0.a1a2...ata1a2...at=0.a˙1...a˙t 再证明充分性：若(b,10)=1,则由欧拉定理知，存在一个整数t，使得 \\10^t≡1(mod\ b),0\leq t\leq\varphi(b) \\因此10^ta=qb+a， \\且0<q<10^t\frac{a}{b}\leq10^t(1-\frac{1}{b})<10^t-1， \\（第一个\leq号：用到a+1\leq b；最后一个<号：用到b<10^t） \\(这又是为什么呢？？？) \\故10^t\frac{a}{b}=q+\frac{a}{b} \\令q=10q_1+a_t,\ q_1=10q_2+a_{t-1},...,\ q_{t-1}=10q_t+a_1,\ 0\leq a_i \\则q=10^tq^t+10^{t-1}a_1+...+10a_{t-1}+a_t,由0<q<10^t-1 \\得q_t=0且a_1,a_2,...,a_t不全是9，也不全是0，因此 \\ \frac{q}{10^t}=0.a_1a_2...a_t \\ \frac{a}{b}=0.a_1a_2...a_t+\frac{1}{10^t}·\frac{a}{b} \\反复应用上式即得\frac{a} {b}=0.a_1a_2...a_ta_1a_2...a_t=0.\dot{a}_{1}...\dot{a}_{t} 再证明充分性：若(b,10)=1,则由欧拉定理知，存在一个整数t，使得10t≡1(mod b),0≤t≤φ(b)因此10ta=qb+a，且0<q<10tba≤10t(1−b1)<10t−1，（第一个≤号：用到a+1≤b；最后一个<号：用到b<10t）(这又是为什么呢？？？)故10tba=q+ba令q=10q1+at, q1=10q2+at−1,..., qt−1=10qt+a1, 0≤ai则q=10tqt+10t−1a1+...+10at−1+at,由0<q<10t−1得qt=0且a1,a2,...,at不全是9，也不全是0，因此10tq=0.a1a2...atba=0.a1a2...at+10t1⋅ba反复应用上式即得ba=0.a1a2...ata1a2...at=0.a˙1...a˙t
这一章知识点感觉还蛮多的。单个看似懂非懂，综合起来脑子里面就一片空白了……还是要多复习多练习多熟悉
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)