初等数论第一章第3节 带余数除法

第一章整数的可除性整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的§1整除的概念及带余数除法一、整除的概念定义1 设a，b是整数，b≠ 0，如果存在整数q，使得成立，则称a能被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b∣a；如果不存在整数q使得a = bq成立，则称a不被b整除，记为显然每个非零整数a称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

定理1 下面的结论成立：∣a⇔±b∣±a；(ⅱ) c ∣b，b∣a⇒c∣a；(ⅲ) b∣a i，i = 1, 2, …, n⇒b∣a1q1+a2q2+…+a n q n，此处q i（i = 1, 2, , n）是任意的整数；(ⅳ) b∣a ⇒bc∣ac，此处c是任意的非零整数；(ⅴ) b∣a，a≠ 0 ⇒|b|≤|a|；b∣a且|a|<|b|⇒a = 0。

2) 设a 与b 是两个整数，b > 0，则存在q 和r ，使得a = bq + r ，0 ≤ r <b (2) 成立且q。

中的q 叫做a 被b 除所得的不完全商，r 叫做a 被例1 若1n >，且111nn -+ 求n222x y z +=的整数解能否全是奇数？为什300”位于哪个字母的下面A B C D E F G1 2 3 4 5 6 78 9 10 11 12 13 1415 16 17 …….解：观察可以发现两行7个数组成一组故300=7×42+6与6同在字母D 的下面例4 a 除以b 商为c ，余数为r ，则am 除以bm 商为 ， 余数为 。

m N +∈3某整数除以3余2，除以4余1，该整数除以12，余 ？三、整除的特征从正整数121n n N a a a a a a -=的末位a 起向左每k 个数码分为一节，最后剩下若有不足k 个数码的也为一节，记为()1()(),,,k k t k A A A并记()1()()()k k k t k S N A A A =+++----数节和1()1()2()()()(1)t k k k k t k S N A A A A -'=-++-----数节代数和1、设d 是10k 的约数，则()k d N d A ⇔推论：能被2或5整除的数的特征是：这个数的末一位数能被2或5整除。

带余除法定理的内容及证明带余除法定理（也称为欧几里得除法）是指对于任意整数a和正整数b，存在唯一的整数q和r，使得a = bq + r，并且满足0 ≤r < b。

下面是带余除法的证明：证明步骤：假设a和b为任意的整数，其中b为正整数。

定义集合S = {a - nb | n为整数}，即S为所有a - nb的整数倍所构成的集合。

由于S包含整数，根据整数的性质，S中必然存在最小的非负整数r，即r = min{a -nb | n为整数}。

考虑r的取值范围，由于r属于集合S，可知存在某个整数n_0，使得a - n_0b = r。

可以将等式a = n_0b + r表示为a = qb + r，其中q = n_0。

接下来需要证明r的取值满足0 ≤r < b。

假设r ≥b，则可以将r表示为r = b + m，其中m ≥0。

将等式a = qb + r代入得到a = qb + b + m，整理得到a = (q + 1)b + m。

根据等式a = qb + r，我们可以得到另一个表示a的等式：a = qb' + r'，其中q' = q + 1，r' = m。

由于m = r - b，可知r - b属于集合S，这与r是集合S中最小的非负整数矛盾。

因此，假设r ≥b是错误的，即可以得出结论0 ≤r < b。

综上所述，对于任意整数a和正整数b，存在唯一的整数q和r，使得a = qb + r，并且满足0 ≤r < b。

证毕。

带余除法定理的证明基于整数的性质以及集合的最小元素的定义。

它说明了在整数除法中，商和余数总是存在且唯一的。

这个定理在数论和代数中具有重要的应用，例如在多项式除法、模运算等领域中被广泛使用。

1。

第一章 整数的唯一分解定理第一节 整除性教学重点：应用带余数除法定义1 设a ，b 是整数，b ≠ 0，如果存在整数c ，使得a = bc成立，则称a 被b 整除，a 是b 的倍数，b 是a 的约数（因数或除数），并且使用记号b ∣a ；如果不存在整数c 使得a = bc 成立，则称a 不被b 整除，记为b |/a . 如果a = bc 里的c 不存在，我们就说b 不能整除a 或a 不被b 整除，记作b |/a . 定理1 （传递性）若a 是b 的倍数，b 是c 的倍数，则a 是c 的倍数， 也就是b |a,c|b ⇒c|a.证 b |a,c|b 就是说存在两个整数1a ，1b 使得111111,(),a ab b bc a a b c a b ===成立因此但是是一个整数，故c|a 定理2 若a ，b 都是m 的倍数，则a ±b 也是m 的倍数.证 a ，b 是m 的倍数的意义就是存在两个整数a 1 , b 1，使得111111,.(),a a m b b m a b a b m a b a b m ==±=±±±因此但是整数，故是的倍数 .定理3 若1212,,,,,,n n a a a m q q q 都是的倍数，是任意个整数，1122.n n q a q a q a m +++ 则是的倍数注：1、显然每个非零整数a 都有约数 ±1，±a ，称这四个数为a 的平凡约数，a 的另外的约数称为非平凡约数.2、若整数a ≠ 0，±1，并且只有约数 ±1和 ±a ，则称a 是素数（或质数）；否则称a 为合数.以后若无特别说明，素数总是指正素数.3、下面的结论成立：(ⅰ) a ∣b ⇔ ±a ∣±b ；·(ⅱ) a ∣b ，b ∣c ⇒ a ∣c ；(ⅲ) b ∣a i ，i = 1, 2, , k ⇒ b ∣a 1x 1 + a 2x 2 + + a k x k ，此处x i （i = 1, 2, , k ）是任意的整数；(ⅳ) b ∣a ⇒ bc ∣ac ，此处c 是任意的非零整数；(ⅴ) b ∣a ，a ≠ 0 ⇒ |b | ≤ |a |；b ∣a 且|a | < |b | ⇒ a = 0；(ⅴi) b ∣a ，a ≠ 0 ⇒ ba ∣a . 定理4(带余数除法) 设a 与b 是两个整数，b ≠ 0，则存在唯一的两个整数q 和r ，使得a = bq + r ，0 ≤ r < |b |. (1)证明 存在性 若b ∣a ，a = bq ，q ∈Z ，可取r = 0. 若b |/a ，考虑集合A = { a + kb ；k ∈Z },其中Z 表示所有整数的集合.在集合A 中有无限多个正整数，设最小的正整数是r = a + k 0b ，则必有0 < r < |b |， (2)否则就有r ≥ |b |. 因为b |/a ，所以r ≠ |b |. 于是r > |b |，即a + k 0b > |b |，a + k 0b - |b | > 0，这样，在集合A 中，又有正整数a + k 0b - |b | < r ，这与r 的最小性矛盾. 所以式(2)必定成立. 取q = - k 0知式(1)成立. 存在性得证.唯一性 假设有两对整数q '，r '与q ''，r ''都使得式(1)成立，即a = q ''b + r '' = q 'b + r '，0 ≤ r ', r '' < |b |，则(q '' - q ')b = r ' - r ''，|r ' - r ''| < |b |， (3)因此r ' - r '' = 0，r ' = r ''，再由式(3)得出q ' = q ''，唯一性得证. 证毕3、定义2 称式(1)中的q 是a 被b 除的不完全商，r 是a 被b 除的余数，也叫最小非负剩余，记作r a b =><.第二节 最大公因数与辗转相除法第三节 最小公倍数教学目的：1、掌握最大公因数与最小公倍数性质；2、掌握辗转相除法；3、会求最大公因数与最小公倍数.教学重点：最大公因数与最小公倍数性质教学难点：辗转相除法一、最大公因数定义 设12,,,2).n a a a n n d ≥ 是（个整数若整数是它们之中每一个的因数， 12,,,n d a a a 那么就叫作的一个公因数.整数a 1, a 2, , a k 的公共约数称为a 1, a 2, , a k 的公约数.不全为零的整数a 1, a 2, , a k 的公约数中最大的一个叫做a 1, a 2, , a k 的最大公约数（或最大公因数），记为(a 1, a 2, , a k ).如果(a 1, a 2, , a k ) = 1，则称a 1, a 2, , a k 是互素的（或互质的）；如果(a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j ，则称a 1, a 2, , a k 是两两互素的（或两两互质的）.显然，a 1, a 2, , a k 两两互素可以推出(a 1, a 2, , a k ) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2.定理1 12,,,n a a a n 若是任意个不全为零的整数，则1212i ,,,,,n n a a a a a a （）与的公因数相同； 1212ii ,,,,,.n n a a a a a a = （）(）（）证 12,,,.,1,2,,,n i d a a a d a i n = 设是的任一公因数由定义12,1,2,,,,,i n d a i n d a a a = 因而故是的一个公因数，121,2,,,.n n a a a a a 同法可证，的任一个公因数都是，a 的一个公因数 121,2,,,n n a a a a a 故与a 有相同的公因数.定理2 若b 是任一正整数，则（i ）0与b 的公因数就是b 的因数， 反之，b 的因数也就是0与b 的公因数 . (ii) (0,b)=b .证 显然0与b 的公因数是b 的公因数 .由于任何非零整数都是0的因数， 故b 的因数也就是0，b 的公因数，于是（i ）得证.其次，我们立刻知道b 的最大因数是b ；而0，b 的最大公因数是b 的最大公因数，故（0，b ）=b.推论2.1 若b 是任一非零整数，则（0，b ）= b .定理3 ,,,,,,)(,).a b c a bq c q a b b c a b b c =+=设是任意三个不全为零的整数，且其中是非零整数，则与有相同的公因数，因而（ 定理4 ,(,)a b a b 若是任意两个整数，则就是a = bq 1 + r 1， 0 < r 1 < |b |，b = r 1q 2 + r 2， 0 < r 2 < r 1 ，r k - 1 = r k q k + 1 + r k + 1，0 < r k + 1 < r k ， (1)r n - 2 = r n - 1q n + r n ， 0 < r n < r n-1 ，r n - 1 = r n q n + 1 .中的最后一个不等于零的余数，即得(,)n a b r =推论4.1 ,(,).a b a b 的公因数与的因数相同例（1）1859,1573185928621431859143.a b =-=-⨯⨯=⨯-=由定理得（，1573）=（1859,1573）.1859=11573+2861573=5286+143所以（，1573）=（1859,1573）例（2）169,121484812532512322311212211.a b ==⨯⨯=⨯+=⨯+=⨯+=⨯=由定理得169=1121+48121=2+25所以（169,121）定理5 ,i (,),a b a b a b δδδδ设是任意两个不全为零的整数，（）若m 是任一正整数，则(am,bm)=(a,b)m.(ii)若是a,b 的任一公因数，则（,）= 特别地, )(),(,),(b a b b a a = 1. 定理6 1212,,,,,,).n n n a a a n a a a d = 若是个整数，则(二、最小公倍数1、定义 整数a 1, a 2, , a k 的公共倍数称为a 1, a 2, , a k 的公倍数. a 1, a 2, , a k 的正公倍数中的最小的一个叫做a 1, a 2, , a k 的最小公倍数，记为[a 1, a 2, , a k ].2、定理1 下面的等式成立：(ⅰ) [a , 1] = |a |，[a , a ] = |a |；(ⅱ) [a , b ] = [b , a ]；(ⅲ) [a 1, a 2, , a k ] = [|a 1|, |a 2| , |a k |]；(ⅳ) 若a ∣b ，则[a , b ] = |b |.3、定理2 对任意的正整数a ，b ，有[a , b ] =),(b a ab . 证明：设m 是a 和b 的一个公倍数，那么存在整数k 1，k 2，使得m = ak 1，m = bk 2，因此ak 1 = bk 2 . (1)于是21),(),(k b a b k b a a =. 由于)(),(,),(b a b b a a = 1，所以 t b a b k k b a b ),(),(11|=即，， 其中t 是某个整数. 将上式代入式(1)得到m =),(b a ab t . (2) 另一方面，对于任意的整数t ，由式(2)所确定的m 显然是a 与b 的公倍数，因此a 与b 的公倍数必是式(2)中的形式，其中t 是整数.当t = 1时，得到最小公倍数[a , b ] =),(b a ab . 推论1 两个整数的任何公倍数可以被它们的最小公倍数整除.证明 由式(2)可得证.这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数.推论2 设m ，a ，b 是正整数，则[ma , mb ] = m [a , b ].证明 由定理2及前面的定理2的推论得到[ma , mb ] =),(),(),(22b a mab b a m ab m mb ma ab m === m [a , b ]. 证毕4、定理3 对于任意的n 个整数a 1, a 2, , a n ，记[a 1, a 2] = m 2，[m 2, a 3] = m 3， ，[m n -2, a n -1] = m n -1，[m n -1, a n ] = m n ，则[a 1, a 2, , a n ] = m n .证明：我们有m n = [m n -1, a n ] ⇒ m n -1∣m n ，a n ∣m n ，m n -1 = [m n -2, a n -1] ⇒ m n -2∣m n -1∣m n ，a n ∣m n ，a n -1∣m n -1∣m n ，m n -2 = [m n -3, a n -2] ⇒ m n -3∣m n -2∣m n ，a n ∣m n ，a n -1∣m n ，a n -2∣m n ，m 2 = [a 1, a 2] ⇒ a n ∣m n ， ，a 2∣m n ，a 1∣m n ，即m n 是a 1, a 2, , a n 的一个公倍数.另一方面，对于a 1, a 2, , a n 的任何公倍数m ，由定理2的推论及m 2, , m n 的定义，得m 2∣m ，m 3∣m ， ，m n ∣m .即m n 是a 1, a 2, , a n 最小的正的公倍数. 证毕推论 若m 是整数a 1, a 2, , a n 的公倍数，则[a 1, a 2, , a n ]∣m .定理4 整数a 1, a 2, , a n 两两互素，即(a i , a j ) = 1，1 ≤ i , j ≤ n ，i ≠ j的充要条件是[a 1, a 2, , a n ] = a 1a 2 a n . (3)证明：必要性 因为(a 1, a 2) = 1，由定理2得到[a 1, a 2] =),(2121a a a a = a 1a 2 . 由(a 1, a 3) = (a 2, a 3) = 1及前面的定理4推论得到(a 1a 2, a 3) = 1，由此及定理3得到[a 1, a 2, a 3] = [[a 1, a 2], a 3] = [a 1a 2, a 3] = a 1a 2a 3 .如此继续下去，就得到式(3).充分性 用归纳法证明. 当n = 2时，式(3)成为[a 1, a 2] = a 1a 2. 由定理2a 1a 2 = [a 1, a 2] =),(2121a a a a ⇒ (a 1, a 2) = 1， 即当n = 2时，充分性成立.假设充分性当n = k 时成立，即[a 1, a 2, , a k ] = a 1a 2 a k ⇒ (a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j .对于整数a 1, a 2, , a k , a k + 1，使用定理3中的记号，由定理3可知[a 1, a 2, , a k , a k + 1] = [m k , a k + 1]. (4)其中m k = [a 1, a 2, , a k ].因此，如果[a 1, a 2, , a k , a k + 1] = a 1a 2 a k a k + 1，那么，由此及式(4)得到[a 1, a 2, , a k , a k + 1] = [m k , a k + 1] =),(11++k k k k a m a m = a 1a 2 a k a k + 1， 即),(1+k k k a m m = a 1a 2 a k ， 显然m k ≤ a 1a 2 a k ，(m k , a k + 1) ≥ 1.所以若使上式成立，必是(m k , a k + 1) = 1， (5)并且m k = a 1a 2 a k . (6)由式(6)与式(5)推出(a i , a k + 1) = 1，1 ≤ i ≤ k ； (7)由式(6)及归纳假设推出(a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j . (8)综合式(7)与式(8)，可知当n = k + 1时，充分性成立. 由归纳法证明了充分性. 证毕三、辗转相除法本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid 算法.它是数论中的一个重要方法，在其他数学分支中也有广泛的应用.1、定义1 下面的一组带余数除法，称为辗转相除法.设a 和b 是整数，b ≠ 0，依次做带余数除法：a = bq 1 + r 1， 0 < r 1 < |b |，b = r 1q 2 + r 2， 0 < r 2 < r 1 ，r k - 1 = r k q k + 1 + r k + 1，0 < r k + 1 < r k ， (1)r n - 2 = r n - 1q n + r n ， 0 < r n < r n-1 ，r n - 1 = r n q n + 1 .由于b 是固定的，而且|b | > r 1 > r 2 > ，所以式(1)中只包含有限个等式.下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计.2、引理1 用下面的方式定义Fibonacci 数列{F n }：F 1 = F 2 = 1，F n = F n - 1 + F n - 2，n ≥ 3，那么对于任意的整数n ≥ 3，有F n > α n - 2， (2)其中α =251+.证明：容易验证α 2 = α + 1.当n = 3时，由F 3 = 2 >251+= α 可知式(2)成立.假设式(2)对于所有的整数k ≤ n （n ≥ 3）成立，即F k > α k - 2，k ≤ n ，则F n + 1 = F n + F n - 1 > α n - 2 + α n - 3 = α n - 3(α + 1) = α n - 3α 2 = α n - 1，即当k = n + 1时式(2)也成立.由归纳法知式(2)对一切n ≥ 3成立.证毕. 定理11(1),1,,;k k k k a P b r k n --=-= 若a,b 是任意两个正整数，则Q其中 0111201121,,,0,1,,k k k k k k k k P P q P q P P Q Q Q q Q Q ----===+===+ 其中k=2,,n.推论1.1若a,b 是任意两个不全为零的整数，则存在两个整数s,t 使得as+bt=(a,b).定理2 若a,b,c 是三个整数，且(a,c)=1.则i （）ab,c 与b,c 有相同的公因数，ii （） (ab,c)=(b,c),,.b c 上面假定了至少有一不为零推论2.1 ,.ab c b 若（a,c)=1,c 则推论2.2 1212,,,,,,.n m a a a b b 设及b 是任意两组整数1212,,,,,,.n m a a a b b 若前一组中任意整数与后一组中任意整数互质，则与b 互质例2 用辗转相除法求(125, 17)，以及x ，y ，使得125x + 17y = (125, 17).解：做辗转相除法：125 = 7⋅17 + 6，q 1 = 7，r 1 = 6，17 = 2⋅6 + 5， q 2 = 2，r 2 = 5，6 = 1⋅5 + 1， q 3 = 1，r 3 = 1，5 = 5⋅1， q 4 = 5.由定理4，(125, 17) = r 3 = 1.利用定理2计算（n = 3）P 0 = 1，P 1 = 7，P 2 = 2⋅7 + 1 = 15，P 3 = 1⋅15 + 7 = 22，Q 0 = 0，Q 1 = 1，Q 2 = 2⋅1 + 0 = 2，Q 3 = 1⋅2 + 1 = 3，取x = (-1)3 - 1Q 3 = 3，y = (-1)3P 3 = -22，则125⋅3 + 17⋅(-22) = (125, 17) = 1.例3 求(12345, 678).解：(12345, 678) = (12345, 339) = (12006, 339) = (6003, 339)= (5664, 339) = (177, 339) = (177, 162) = (177, 81)= (96, 81) = (3, 81) = 3.例4 在m 个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n （n < m ）个盒子中各放一个硬币.证明：若(m , n ) = 1，那么无论开始时每个盒子中有多少硬币，经过若干次放硬币后，总可使所有盒子含有同样数量的硬币.解：由于(m , n ) = 1，所以存在整数x ，y ，使得mx + ny = 1. 因此对于任意的自然数k ，有1 + m (-x + kn ) = n (km + y )，这样，当k 充分大时，总可找出正整数x 0，y 0，使得1 + mx 0 = ny 0 .上式说明，如果放y 0次（每次放n 个），那么在使m 个盒子中各放x 0个后，还多出一个硬币.把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1. 因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同.四、小结.第四节 素数、整数的唯一分解定理教学目的：1、掌握素数的一系列性质；2、理解并掌握唯一分解定理.教学重点：素数的性质及唯一分解定理的证明及应用教学难点：唯一分解定理的证明及应用教学课时：4课时教学过程一、素数1、定义 大于1的整数，如果只有平凡因子，就叫素数，否则叫合数.2、定理1 设a 是任意大于1的整数，则a 除1以外的最小正因子p 是素数，并且当a 是合数时，则a p ≤ .3、定理2 设p 是素数，a 是任意整数，则a p |或1),(=a p .4、定理3 设p 是素数，p|ab , 则p|a 或p|b.5、定理4 素数有无穷多个.6、定理2 形如4n-1型的素数有无穷多个.例1 写出不超过100的所有的素数。

第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++ 是m 得倍数．证明： 12,,n a a a 都是m 的倍数。

∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n n q a q a q a ∴+++ 1122n n q p m q p m q p m =+++ 1122()n n p q q p q p m =+++即1122n n q a q a q a +++ 是m 的整数 2．证明 3|(1)(21)n n n ++ 证明 (1)(21)(1)(2n n n n n n n ++=+++-(1)(2)(1)(n n n n n n =+++-+又(1)(2)n n n ++ ，(1)(2)n n n -+是连续的三个整数 故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证： ,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？证：作序列33,,,,0,,,,2222b b b bb b --- 则a 必在此序列的某两项之间 即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t < ()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b ---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b rq r -=，┄, d '|21(,)n n n n r r q r a b --=+=, 即d '是(,)a b 的因数。

第一章整除理论整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节数的整除性定义1 设a, b是整数，b 0,如果存在整数c，使得a = bc成立，则称a被b整除，a是b的倍数，b是a 的约数(因数或除数)，并且使用记号b a ;如果不存在整数c使得a = bc成立，则称a不被b整除，记为b | a。

显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1 下面的结论成立：(i ) a b a b;(ii) a b，b c a c;(iii) b a i, i = 1,2, , k b a i x i a2X2a k X k，此处x(i = 1,2, , k)是任意的整数；(iv) b a be ac,此处c是任意的非零整数；(v ) b a, a 0 | b| | a| ; b a 且| a| < | b| a = 0。

证明留作习题。

定义2若整数a 0，1,并且只有约数1和a，则称a是素数(或质数)；否则称a 为合数。

以后在本书中若无特别说明，素数总是指正素数。

定理2 任何大于1的整数a都至少有一个素约数。

证明若a是素数，则定理是显然的。

若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d i, d2, , d k。

不妨设d i是其中最小的。

若d i不是素数，则存在e i > 1, e2 > 1，使得d1 = &e2，因此，e1和e2也是a的正的非平凡约数。

这与d1的最小性矛盾。

所以d1是素数。

证毕。

推论任何大于1的合数a必有一个不超过” a的素约数。

证明使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12 a。

证毕。

例1 设r是正奇数，证明：对任意的正整数n有n 21 1r 2r n r。

第一章 整除理论整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节 整除定义1 设a ，b 是整数，b ≠ 0，如果存在整数c ，使得a = bc成立，则称a 被b 整除，a 是b 的倍数，b 是a 的约数（因数或除数），并且使用记号b ∣a ；如果不存在整数c 使得a = bc 成立，则称a 不被b 整除，记为b |/a 。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1 下面的结论成立：(ⅰ) a ∣b ⇔ ±a ∣±b ； (ⅱ) a ∣b ，b ∣c ⇒ a ∣c ；(ⅲ) b ∣a i ，i = 1, 2, , k ⇒ b ∣a 1x 1 + a 2x 2 + + a k x k ，此处x i （i = 1, 2, , k ）是任意的整数；(ⅳ) b ∣a ⇒ bc ∣ac ，此处c 是任意的非零整数；(ⅴ) b ∣a ，a ≠ 0 ⇒ |b | ≤ |a |；b ∣a 且|a | < |b | ⇒ a = 0。

例1 设r 是正奇数，证明：对任意的正整数n ，有n + 2|/1r+ 2 r+ + n r。

例2 设A = { d 1, d 2, , d k }是n 的所有约数的集合，则B =}{,,,21kd n d n d n也是n 的所有约数的集合。

例3 以d (n )表示n 的正约数的个数，例如：d (1) = 1，d (2) = 2，d (3) = 2，d (4) = 3， 。

问：d (1) + d (2) + + d (1997)是否为偶数？例4 证明：存在无穷多个正整数a ，使得n 4 + a （n = 1, 2, 3, ）都是合数。

例5 设a 1, a 2, , a n 是整数，且a 1 + a 2 + + a n = 0，a 1a 2 a n = n ，则4∣n 。

1.2 带余除法-北师大版选修4-6 初等数论初步教案知识点简介带余除法也称为辗转相除法，是初等数论中一个重要而基本的算法。

本节课用模型的方法初步介绍带余除法，通过示例的讲解和题目的练习，帮助学生理解带余除法的基本思想和用法。

基本思想带余除法的基本思想是利用两个整数a与b（a > b），用b去逐步地余数取代a,直到余数小于b，此时的余数就是最大公约数。

带余除法步骤设a, b是两个互质的整数，用a去除以b得到商q1与余数r1,即a=bq1+r1用b去除以r1得到商q2与余数r2，即b=r1q2+r2……以此类推，直到余数为0，此时的除数（也即上面算出来的r n）即为a, b的最大公约数。

教学重点•用带余除法求两个数的最大公约数。

•带余除法的原理与步骤。

教学难点•基于带余除法理论解决问题的能力。

•对于模型方法的认知和理解。

教学方法•讲解法•实例分析法•数学模型法教学过程导入•通过提问，复习除法分离定理的概念和应用。

新课一、讲解1.强调带余除法的基本思想。

2.教师用具体数据演示做题思路，介绍带余除法的步骤。

3.教师引导学生思考以下问题：•为什么带余除法是正确的？•带余除法的几个步骤为什么是一定要的？二、实例分析1.针对实际问题，教师可以设置一到两个问题，让学生借助带余除法解决。

2.让部分同学上黑板，让自己的演示路径得到锻炼和检验。

三、数学模型1.针对实际问题穷举多个数值实现带余除法，呈现出不同结果2.强调数论中，模型的使用十分普遍。

3.让学生明白模型的威力和优越性。

作业•完成课后习题。

参考文献•严蕴毅. (2013). C 程序设计 (第二版). 机械工业出版社.•翁恺. (2013). 清华大学计算机系列教材–数据结构(第2版). 清华大学出版社.小结本节课，教师通过模型的方法，介绍了带余除法的基本思想及应用，利用实例分析法进行了案例演示。

培养学生应用带余除法解决问题的能力。

在平常的数学学习过程中，带余除法常被用来求最大公约数，尤其是当数据较大时，带余除法的优势便愈加显著。