Modular arithmetic 5群 +n群 n群 (2n+)是有限Abe群 m其中Zn={aln:gcd(an)=1} 12478134 清手大学城想 Euler's phi function 由一个元素生成[张成]的子群 d(n)=nILp(1-1/p) is the size of z欧拉ψ函数 Lagranges theorem:有限群的子群的元素个 Order of a:使a=e的最小k 数是原群元素个数的约数 手大学想 Solving modular linear equation 孙子点兵【中国余数定理】 ax≡b(modm <a>表示由a生成的Zn的子群 ma→(a1,a2……a), →<a>=cd>inzn sa>l=n/d n=n1n2…nk所有n两两互素 利用扩充欧拉算法求解上述问题,可以得到有无解,有解 Zn与Zn1×Zn2×…×Zmk等价 时给出所有解 m求逆与系数。 如果d则有b个解,x=x(b/d)modn,x是扩展欧几理 a=e am(m-l mod n) 德算法的系数 x+nd)modn;i=0,d-1通解 -ny 其中m( m:-1 mod n)是基本解3 清华大学 宋斌恒 13 Modular arithmetic „ ＋n群， „ ×n群 „ (Zn,+n)是有限Abel群 „ (Z* n,×n)是有限Abel群 „ 其中Z* n ＝{[a]n : gcd(a,n)=1} 清华大学 宋斌恒 14 . 15群 14 13 11 8 7 4 4 1 2 4 1 .15 1 2 4 7 8 11 13 14 清华大学 宋斌恒 15 Euler’s phi function φ(n)=nΠp|n(1-1/p) is the size of Z* n. 欧拉φ函数 „ 子群，真子群， „ Lagrange’s theorem: 有限群的子群的元素个 数是原群元素个数的约数。 清华大学 宋斌恒 16 由一个元素生成[张成]的子群 „ 幂： „ a(k)= a ⊕ a ⊕ a ⊕ a ⊕ …⊕ a „ <a>={a(k), k>=1} „ Order of a: 使a(k)＝e的最小k 清华大学 宋斌恒 17 Solving modular linear equation „ ax ≡ b (mod n) „ <a> 表示 由 a 生成的Zn的子群 „ d=gcd(a,n) „ Î<a>=<d> in Zn. „ |<a>|=n/d „ 利用扩充欧拉算法求解上述问题，可以得到有无解，有解 时给出所有解。 „ 如果d|b则有b/d个解，x0=x’(b/d) mod n, x’是扩展欧几理 德算法的系数 „ x0+i(n/d) mod n; i=0,…,d-1通解 清华大学 宋斌恒 18 孙子点兵【中国余数定理】 „ a ÅÆ(a1,a2,…,ak)， „ a in Zn, „ ai in Zni , „ n= n1n2…nk 所有ni 两两互素 „ Zn 与Zn1× Zn2×… × Znk.等价 „ 求逆与系数。 „ a=Σ ai mi (mi -1 mod ni ), „ mi =n1n2…ni-1ni+1…nk „ 其中mi (mi -1 mod ni )是基本解