初等数论第一章整除1–4.ppt

《初等数论》 教师：何艳 数论的基本内容 按照研究方法的不同，数论可分为 初等数论 解析数论 代数数论 几何数论 参考书目 1、南基洙主编《初等数论》； 2、柯召、孙琦编著《数论讲义》，高等教育 出版社； 3、闵嗣鹤、严士健编《初等数论》，高等教 育出版社； 4、郑克明主编《初等数论》，西南师范大学 出版社。 初等数论 第一章 整除 §1 自然数与整数 归纳原理 设S是N的一个子集，满足条件： (ⅰ)1∈S; (ⅱ)如果n ∈S，则n+1 ∈S, 那么，S=N. 定理1 数学归纳法 设P(n)是关于自然数n的一种性质或命题.如果 (ⅰ)当n=1时，P(1)成立； (ⅱ)由P(n)成立必可推出P(n+1)成立， 那么， P(n)对所有自然数n成立. 定理2 最小自然数原理 设T是N的一个非空子集. 那么，必有t0 ∈T, 使对任意的t ∈T有t0≤t，即t0是T中的最小 自然数. 定理3 最大自然数原理 设M是N的非空子集.若M有上界，即存在 a∈N, 使对任意的m ∈M有m ≤ a, 那么必 有m0 ∈M，使对任意的m ∈M有m ≤ m0， 即m0是M中的最大自然数。 定理4 第二数学归纳法 设 P(n) 是关于自然数 n 的一种性质或命题. 如果(ⅰ) 当 n=1 时， P(1) 成立； (ⅱ)设 n1. 若对所有的自然数 mn, P(m)成立， 则必可推出P(n)成立，那么, P(n) 对所有 自然数 n 成立. 定理5 鸽巢原理 设n是一个自然数.现有n个盒子和n+1个物体. 无论怎样把这n+1个物体放入这n个盒子中， 一定有一个盒子中被放了两个或两个以上的 物体。 §2 整除 定义1 设a，b是整数，a ? 0，如果存在整数q， 使得b = aq，则称b可被a整除，记作a?b ， 且称b是a的倍数，a是b的约数(因数、除数)； 如果不存在整数q使得b = aq成立，则称b不被 a整除，记为a b。 被2整除的数称为偶数，不被2整除的称为奇数 定理1 下面的结论成立： (ⅰ) a|b (-a)|b a|(-b) (-a)|(-b) |a|||b|； (ⅱ) a?b，b?c ? a?c； (ⅲ) a?b, a?c 对任意 x、y , 有a?bx+cy ,一般地， a?bi，i = 1, 2, ?, k a?b1x1 ? b2x2 ? ?? bkxk， 此处xi（i = 1, 2, ?, k）是任意的整数； (ⅳ) a?b ac?bc，c是任意的非零整数； (ⅴ) a?b且b?a ? a= ? b； (ⅵ) a?b，b ? 0 ? |a| ≤|b|；a?b且|b| |a| ? b = 0. 例1 证明：若3|n且7|n，则21|n. 例2 设a=2t-1. 若a|2n, 则a|n. 例3 设a 、b是两个给定的非零整数，且有整数 x、 y，使得 ax+by=1. 证明：若a|n且b|n, 则ab|n. 例4 设f(x)=anxn+an-1xn-1+?+a1x+a0 ∈Z[x], 其中Z[x]表示全体一元整系数多项式组成的 集合. 若d|b-c, 则 d|f(b)-f(c). 定义2 显然每个非零整数a都有约数 ?1，?a，称 这四个数为a的显然因数，a的另外的因数 称为非显然因数。 若整数a ? 0，?1，并且只有约数 ?1和 ?a， 则称a是素数（或质数）；否则称a为合数。 以后在本书中若无特别说明，素数总是指 正素数。 定理2 设A = { d1, d2, ?, dk }是n的所有约数的集合，则 B = 也是n的所有约数的集合。 解 由以下三点理由可以证得结论： (ⅰ) A和B的元素个数相同； (ⅱ) 若di?A，即di?n，则 n，反之亦然； (ⅲ) 若di ? dj，则 . 定理3 (ⅰ) a1是合数的充要条件是 a=de,1da,1ea; (ⅱ)若d1, q是不可约数且d|q, 则d=q. 定理4 若a是合数，则必有不可约数p|a. 定理5 设整数a≥2, 那么a一定可表为素数的乘积 (包括a本身是素数)，即 a=p1p2 ?ps其中pj（1≤j ≤s) 是素数. 证明 当a = 2时，结论显然成立。 假设对于2 ≤ a ≤ k，式(1)成立，我们来证明式(1) 对于a = k ? 1也成立，若k ? 1是素数，式(1)显成立. 如果k ? 1是合数，则存在素数p与整数d，使得k ? 1 = pd.由于2 ≤ d ≤ k，由归纳假定