史灵生《离散数学》清华大学-D05Integers.pdfVIP

Discrete Mathematics Lecture 5 Integers 1 Contents • Divisibility of Integers • Factorization into Primes • On the Set of Primes • Fermat’s Theorems • The Euclidean Algorithm • Congruences • Strange Numbers • Numbers and Combinatorics 2 Number Theory • 在本章中，如无特别说明，常以小写英文 字母，或有时标以足码或肩码表示整数． • 当几个字母写在一起时，表示它们相乘， 如: abc=a ×b ×c; • 但注意数目字写在一起不表示相乘，如168 不是1 ×6 ×8而是一百六十八． • 当数目字和字母写在一起时，则表示该数 目字和字母相乘, 如168abc ＝168 ×a ×b ×c. 3 6.1 因数(divisor)和倍数(multiple) 定义设a,b为整数，a≠0. 若有一整数q, 使得 b = aq, 则称a是b 的因数或b是a 的倍数; 并 称a整除b, 记为a |b, 可形式地表示为: a |b:=(q)(b=aq) • 若a不能整除b ，记为a∤b. • 若b=aq，而|a |既非b又非1，则称a是b 的 真因数. 4 性质1 ①对所有a, 1|a. ②对所有a, a |0. ③对所有a, a |a. ④若a |b且b |c, 则a |c. ⑤若a |b, 则对任意的c, 有ac |bc. ⑥若ac |bc且c≠0, 则a |b. 5 ⑦若a |b且a |c,则对任意的m,n,有a |(bm+cn). ⑧若a |b, 则b=0或|a |≤|b |,其中|a |是a 的绝对 值, 当a≥0时|a |=a; 当a0时|a |=-a. ⑨若a |b, 则(-a)|b, a |(-b),(-a)|(-b), |a |||b |. 证明: 只证明⑦, 余下不难证明. ⑦因为a |b且a |c, 故b=aq 和c=aq . 于是, 1 2 bm+cn = aq m+aq n = a(q m+q n), 1 2 1 2 所以, a |(bm+cn). 6 性质2 若a是b≠0 的真因数, 则1 |a ||b |. 性质3 若a为是整数,且|a ||b |, |b |||a |, 则a=0. 证明: 因为|b | | |a |, 故有整数q, 使得|a |=|b |q. 若|a |=0,则a=0. 若|a |0, 则由于0|a ||b |和|a |=|b |q, 有q≥0. 若q0, 则由q是整数而有q≥1 ⇒|a |≥|b |,这与 |a ||b |矛盾, 故q=0且|a |=|b |q=