数论1课件.ppt

初等数论(一) Number Theory (1) 本章主要介绍整数的整除性和因数分解等内容． 在本章或下一章中，如无特别说明，常以小写英文字母，或有时标以足码或肩码表示整数．当几个字母写在一起时，表示它们相乘，如: abc=a×b×c; 但注意数目字写在一起不表示相乘，如 168不是1×6×8而是一百六十八．当数目字和字母写在一起时，则表示该数目字和字母相乘, 如168abc＝168×a×b×C. 1.1 因数和倍数 定义7.1.1 设 a,b为整数，a≠0. 若有一整数q, 使得 b = aq, 则称 a是b的因数为是a的倍数; 并称a整除b, 记为a|b, 可形式地表示为: a|b:=(?q)(b=aq) 若a不能整除b，记为a\b. 若b=aq,而a既非b又非1,则称a是b的真因数. 7.1 因数和倍数 关于整除，显然有下列定理： 定理7.1.2 ①对所有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. 7.1 因数和倍数 ⑦若 a | b且a|c,则对任意的 m,n,有 a|(bm+cn). ⑧若a|b, 则b=0或|a|≤|b|,其中|a|是a的绝对值,当a≥0时|a|= a; 当a＜0时|a|=-a. ⑨若a|b, 则(-a)|b, a|(-b),(-a)|(-b), |a|||b|. 证明 只证明⑦, 余下不难证明. ⑦因为a|b且a|c, 故b=aq1和c=aq2. 于是, bm+cn=a(q1m+q2n), 所以, a|(bm+cn). 7.1 因数和倍数 定理 7.1.2 若 a是b的真因数, 则 1＜|a|＜|b|. 定理 7.1.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|和q≥1有|a||b|, 这与|a||b|矛盾, 故q=0; 若q=0和|a|=|b|q有a=0. 7.1 因数和倍数 定理7.1.4(带余除法)若a为是二个整数,b≠0, 则唯一存在二个整数q和r, 使得下式成立: a=bq+r, 0≤r|b|. 证明 考虑两种可能： 只证明①. 存在一整数q, 使得a=bq, 故r=0, 定理成立. 7.2 素数和合数 在正整数中, 1只能被它本身整除. 任何大于1的整数都至少能被1和它本身整除． 定义7.2.1 一个大于1且只能被1和它本身整除的整数, 称为素数; 否则, 称为合数. 由该定义可知，正整数集合可分三类: 素数、合数和1. 素数常用户或p或p1, p2…,来表示. 7.2 素数和合数 定义7.2.2 若正整数a有一因数b,而b又是素数,则称b为a的素因数． 例:12=3×4, 其中3是12的素因数, 而4则不是. 定理7.2.1 若a是大于1的整数, 则a的大于1的最小因数一定是素数. 证明 若a是素数, 显然a的大于二的最小因素就是素数a; 若a是合数, 则除1和a外还有其它的因数，令b是这些正因数中最小者, 可以证明b不是合数而是素数, 若其不然, b必有大于1且不等于b的因数c, 于是由c|b和b|c可知c|a, 即c是a的因数,又有1cb, 这与假设b是a的大于1的最小因数相矛盾．故b不是合数而是素数．因此，a的大于1的最小因数b是素数． 7.2 素数和合数 本定理说明了: 任何大于1的整数均可被一素数整除, 或者说都至少有一素因数. 观察一正整数a是否素数, 要用小于a大于1的整数一一来试除吗？不要. 7.2 素数和合数 定理7.2.2 若a是大于1的整数而所有小于或等于人的素数都不能整除a, 则a是素数. 证明 首先证明, 若a不能被大于1且小于或等于人的整数整除, 则a是素数. 假设是合数且a＝be, 其中b和c都是大于1的整数, 由于a不能被大于1且小于或等于 的整数整除, 所以 b＞ ,c＞ , 于是, 可得bc＞ . =a, 这与bc=a矛盾. 因此, 若a不能被大于三且小于或等于 的整数整除，则是素数． 7.2 素数和合数 由上可知, 若a是合数, 则a一定有大于1且小于或等于人的因数. 由定理7.2.1知, a的大于1的最小因数一定是素数, 故本定理得证. 素数有多少？公元前三世纪, 古希腊数学家欧几里德Euclid就证