搜狗做题网数论引理证明,欧拉函数
来源：学生作业帮 编辑：搜狗做题网作业帮 分类：数学作业 时间：2024/07/24 05:09:27
数论引理证明,欧拉函数
求证下面引理：若n=n1×n2,且n1,n2互素,则φ（n）=φ(n1)×φ(n2)
其中φ(m)=m(1-1/p1)(1-1/p2)……(1-1/pr).p1,p2,……pr为m的全部因子
ps：这是推导欧拉定理的一步.不要直接用欧拉定理证明.最好设φ（n）中点的集合为C,φ(n1)和φ(n2)中点的集合分别为A和B,设法建立C与A×B之间的双射关系
求证下面引理：若n=n1×n2,且n1,n2互素,则φ（n）=φ(n1)×φ(n2)
其中φ(m)=m(1-1/p1)(1-1/p2)……(1-1/pr).p1,p2,……pr为m的全部因子
ps：这是推导欧拉定理的一步.不要直接用欧拉定理证明.最好设φ（n）中点的集合为C,φ(n1)和φ(n2)中点的集合分别为A和B,设法建立C与A×B之间的双射关系
套用结论的话,就是用中国剩余定理:
同余方程组x ≡ a (mod n1),x ≡ b (mod n2)在mod n意义下存在唯一解x ≡ c (mod n).
这样建立了{0,1,...,n1-1}×{0,1,...,n2-1} → {0,1,...,n-1}的单射,
比较元素个数可知这也是双射.
由c ≡ a (mod n1),c ≡ b (mod n2),n = n1·n2.
可验证(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
因此上述映射刚好给出A×B → C的双射.
用Bezout定理可以给出构造的细节.
由(n1,n2) = 1,存在整数u,v,满足n1·u+n2·v = 1.
可验证c = n1·ub+n2·va即满足c ≡ a (mod n1),c ≡ b (mod n2),
且c mod n的余数不依赖u,v的选取.
此外(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
构造映射将(a,b)映为c mod n的余数,可验证其为A×B → C的双射.
同余方程组x ≡ a (mod n1),x ≡ b (mod n2)在mod n意义下存在唯一解x ≡ c (mod n).
这样建立了{0,1,...,n1-1}×{0,1,...,n2-1} → {0,1,...,n-1}的单射,
比较元素个数可知这也是双射.
由c ≡ a (mod n1),c ≡ b (mod n2),n = n1·n2.
可验证(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
因此上述映射刚好给出A×B → C的双射.
用Bezout定理可以给出构造的细节.
由(n1,n2) = 1,存在整数u,v,满足n1·u+n2·v = 1.
可验证c = n1·ub+n2·va即满足c ≡ a (mod n1),c ≡ b (mod n2),
且c mod n的余数不依赖u,v的选取.
此外(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
构造映射将(a,b)映为c mod n的余数,可验证其为A×B → C的双射.