Chapt19 整数讲义.pptVIP

* 离散数学 * 乘积的Euler函数 证明：bxi+ayj i=1, …, φ(a); j=1, …, φ(b) (19.8) (1)先证(19.8)中的数模ab互不同余。 bxi+ayj ≡ bxr+ays (mod ab) ? bxi+ayj ≡ bxr+ays (mod a) 由同余的定义可知： (bxi+ayj) – (bx r+ays)= ab ×m =a×bm ∴ bxi+ayj ≡ bxr+ays (mod a) ? bxi ≡ bxr (mod a) ∵a, b互质 ? xi ≡ xr (mod a) ? i = r 同理可证 j = s ∴ bxi+ayj = bxr+ays。 ？ * 离散数学 * 乘积的Euler函数 证明：bxi+ayj i=1, …, φ(a); j=1, …, φ(b) (19.8) (2)再证(19.8)中的数都与模ab互质。 因为xi与a互质，且b与a互质，所以b xi与a互质。从而b xi + a yj与a互质。同理可证b xi + a yj与b互质。于是b xi + a yj与ab互质。 所以(19.8)中的每个数都与ab互质。 * 离散数学 * 乘积的Euler函数 设w与ab互质。∵a与b互质，∴bx0+ay0 = 1。 ∴bx0w+ay0w = w。令x0w、y0w分别为x、y。 易知w与a互质，∴bx与a互质，因此x与a互质。 ∴ x≡xi (mod a), 1≤i≤φ(a)。bx≡bxi (mod ab)。 同理y≡yj (mod b), 1≤j≤φ(b). ay≡ayj (mod ab)。 ∴ w=bx+ay ≡ bxi + ayj (mod ab)。 证明：bxi+ayj i=1, …, φ(a); j=1, …, φ(b) (19.8) (3)最后证: 与ab互质的数与(19.8)中的某数同余。 * 离散数学 * 乘积的Euler函数 证明：我们已证明，对于以下φ(a) φ(b)个数： bxi+ayj i=1, …, φ(a); j=1, …, φ(b) (19.8) (1)(19.8)中的数模ab互不同余。 (2)(19.8)中的数都与模ab互质。 (3)任何与ab互质的数都与(19.8)中的某数同余。 所以(19.8)中的数为模ab的简化剩余系。即有 φ(ab) = φ(a)φ(b) 。 定理19.4.5：若a与b互质，则 φ(ab) = φ(a)φ(b) 。 (19.7) * 离散数学 * 质数p的幂的Euler函数φ(pr) 引理19.4.1：设p为质数，则 φ(pr) = pr ( 1 – 1/p)。 证明：在模pr的完全剩余系中，易知与pr不互质的数只有那些p的倍数，即 p，2p，… ，pr–1p。 它们一共有pr-1个，而其余的pr – pr–1都与pr 互质。因此φ(pr) = pr – pr–1 = pr (1– 1/ p)。 * 离散数学 * Euler函数φ(n)的计算 定理19.4.6：设n= p1r1 p2r2… pkrk是n的质因数分解式， p1, p2, …, pk是k个互异的质数。于是 φ(n) = n (1–1/p1) (1–1/p2) … (1–1/pk)。 证明：由引理19.4.1知φ(pr) = pr ( 1 – 1/p)。于是由定理19.2.2，并反复应用定理19.4.5，有 φ(n) = φ(p1r1) φ(p2r2) … φ(pkrk) = p1r1(1–1/p1) p2r2(1–1/p2)… pkrk(1–1/pk) = n(1–1/p1) (1–1/p2)… (1–1/pk)。 例如： φ(100) = φ(22×52 )=φ(22) φ(52) = 22 × 52 × (1 – 1/2) × (1 – 1/5) = 40 * * 离散数学 * 质数有无穷多个 定理19.2.7：质数有无穷多个。 证明：设p是任意质数。令a = p！+1。设存在q是a的质约数，q | a，即q |p！+1。易证q不能整除p！[=p(p-1)(p-2)…2·1]。 ？ 因为q | a，若q | p！，由整除性质2之⑹知，在等式a = p！+ 1中q也应整除第三项1，即q | 1，于是q = 1。矛盾。所以q不能整除p！。 从而q＞p，这说明对任给的质数，还有比它更大的质数。所以质数有无穷多个。 * 离散数学 * §19.3 同余 * 离散数学 * 同余的定义 定义19.3.1：设a，b，m∈Z，m≠0，若m |(a – b)，则说a与b模m