离散数学-教案 -第8章8.1-8.3 整除

课堂教学设计1章节（专题）第8章数论计划学时2计划学时8.1整除教育教学目的1.理解整除的概念与性质，掌握带余除法。2.掌握最大公约数、最小公倍数的概念与求法（素因子分解法、辗转相除法）。3.理解互素的概念。4.掌握取整函数的定义与性质。5.课程思政目标：通过介绍辗转相除法的历史（出自《九章算术》），增强民族自豪感，培养学生严谨的数学思维。教学重点及难点重点：整除的性质、最大公约数与最小公倍数的求法。难点：带余除法的理解、辗转相除法的原理及证明。教学方法及手段1.讲授法2.引导探究3.多媒体辅助教学4.小组讨论教学互动环节设计1.导入新课：从整数除法的结果（整除与带余）引入整除概念。2.课堂讨论：如何求两个数的最大公约数？有哪些方法？3.小组合作：使用辗转相除法求两个数的最大公约数，并尝试回代求整数系数。4.练习与展示：求最小公倍数，并验证与最大公约数的关系。课后总结与反思一、整除的概念定义8.1：对于整数a和非零整数b，若存在整数c，使得a=bc，则称b能整除a（或a能被b整除），记作b|a。此时b是a的约数（或因数），a是b的倍数。若不存在这样的整数c，则称b不能整除a，记作b∤a。示例：8能被±1、±2、±4、±8整除，其中1和8是8的平凡因数，±2、±4是8的真因数。核心问题：不超过a的正整数中有多少个能被b整除？分析：能被b整除的正整数可表示为bk（k为正整数），满足0<bk≤a，即0<k≤a/b。结论：满足条件的正整数个数为⌊a/b⌋（下取整函数）。示例：不超过12且能被3整除的正整数有3、6、9、12，共⌊12/3⌋=4个。二、整除的性质定理8.1（对称性）：b|a⇔-b|a⇔b|-a⇔|b|||a|。定理8.2（传递性）：若b|a，a|c，且a≠0，b≠0，则b|c。定理8.3：若b|a，则a=0或|b|≤|a|；若a|b且b|a，则a=±b；若a|b，则对任意整数c，有a|bc。定理8.4（线性组合性）：若a|b且a|c，则对任意整数m、n，有a|(mb+nc)。定理8.5（带余除法）：对任意两个整数a、b（b≠0），存在唯一一对整数s（商）和r（余数），使得a=bs+r，其中0≤r<|b|。推论：b|a的充分必要条件是a被b除时的余数r=0。示例：360被33除，360=33×10+30，商为10，余数为30；-11被3除，-11=3×(-4)+1，商为-4，余数为1。三、最大公约数定义8.2：设d是一个非零整数，若d|a且d|b，则称d是a和b的公约数；若d是a和b所有公约数中的最大者，则称d是a和b的最大公约数，记作d=gcd(a,b)。约定：gcd(0,0)=0；若gcd(a,b)=1，则称a与b互素。示例：12和36的正公约数为1、2、3、4、6、12，故gcd(12,36)=12。求最大公约数的方法：枚举法：列出两个数的所有正公约数，取最大值（适用于较小整数）。素因子分解法：设a=p₁^a₁p₂^a₂…p_k^a_k，b=p₁^b₁p₂^b₂…p_k^b_k（p₁,p₂,…,p_k为互异素数，a_i,b_i为非负整数），则gcd(a,b)=p₁^min(a₁,b₁)p₂^min(a₂,b₂)…p_k^min(a_k,b_k)。示例：500=2²×5³，120=2³×3×5，故gcd(500,120)=2²×5¹=20。辗转相除法（欧几里得算法）：设a≥b>0，令r₀=a，r₁=b，反复应用带余除法：r₀=r₁s₁+r₂（0≤r₂<r₁），r₁=r₂s₂+r₃（0≤r₃<r₂），…，直到rₙ₊₁=0，则rₙ即为a和b的最大公约数。示例：用辗转相除法求452和610的最大公约数（分步演示计算过程）。定理8.6：设a=bq+c（q∈Z），则a、b与b、c有相同的公约数，故gcd(a,b)=gcd(b,c)（辗转相除法的理论依据）。四、最小公倍数定义8.3：设a、b是两个非零整数，若a|m且b|m，则称m是a和b的公倍数；在所有公倍数中最小的正整数称为a和b的最小公倍数，记作lcm(a,b)。示例：14和21的最小公倍数为42。定理8.7：若a|m且b|m，则lcm(a,b)|m。素因子分解法求最小公倍数：设a、b的素因子分解式如前所述，则lcm(a,b)=p₁^max(a₁,b₁)p₂^max(a₂,b₂)…p_k^max(a_k,b_k)。示例：432=2⁴×3³，95256=2³×3⁵×7²，故lcm(432,95256)=2⁴×3⁵×7²=142884。最大公约数与最小公倍数的关系：对两个正整数a、b，有a×b=gcd(a,b)×lcm(a,b)。五、取整函数定义8.4（下取整函数）：⌊a⌋表示不大于a的最大整数，满足a-1≤⌊a⌋≤a。定义8.5（上取整函数）：⌈a⌉表示不小于a的最小整数，满足a≤⌈a⌉≤a+1。应用：主要用于计算不超过某整数且能被另一整数整除的正整数个数（如⌊a/b⌋）。课堂教学设计2章节（专题）第8章数论计划学时2课题（内容）8.2素数教育教学目的1.掌握素数与合数的概念，理解素数的性质。2.掌握判断素数的方法（试除法、爱氏筛法）。3.理解并掌握算术基本定理（整数的唯一分解定理）。4.课程思政目标：通过介绍素数在密码学中的应用，引导学生认识数学在信息安全中的重要作用，培养科学精神与责任感。教学重点及难点重点：素数的概念与性质、算术基本定理。难点：算术基本定理的证明、素数无穷多的证明。教学方法及手段1.讲授法2.启发式教学3.多媒体辅助教学4.探究学习教学互动环节设计1.导入新课：从大于1的整数的因数个数引入素数定义。2.课堂讨论：如何判断一个数是否为素数？有哪些高效方法？3.小组合作：使用爱氏筛法制作100以内的素数表。4.探究学习：算术基本定理的唯一性证明思路。课后总结与反思一、素数与合数的概念1.定义8.6：一个大于1的正整数，如果它的正因数只有1和它本身，那么就称这个正整数为素数（也称为质数）；如果它除了1和它本身之外还有其他正因数，那么就称这个正整数为合数。2.关键说明：1既不是素数也不是合数；2是唯一的偶素数，其余素数均为奇数；素数有无穷多个（后续证明）。3.示例：2、3、5、7、11等是素数；4、6、8、9、10等是合数。4.素数的分布：素数在正整数中的分布不规律，但随着正整数的增大，素数的密度逐渐减小。5.示例：1-100中有25个素数，101-200中有21个素数，201-300中有16个素数。二、素数的相关定理1.定理8.8（素数的最小正因数性质）：任何大于1的正整数n，其最小正因数一定是素数。2.证明思路：假设n的最小正因数d是合数，则存在正整数k，使得1<k<d且k|d。由整除的传递性可知k|n，这与d是n的最小正因数矛盾，故d是素数。3.推论：若n是大于1的正整数，且所有不大于√n的素数都不能整除n，则n是素数（根号判别法的理论依据）。4.定理8.9（素数有无穷多个）：正整数中存在无穷多个素数。5.经典证明（反证法）：假设素数只有有限个，记为p₁,p₂,...,pₙ。构造整数N=p₁p₂...pₙ+1。由于N>1，根据定理8.8，N有素因数p，且p必为p₁,p₂,...,pₙ中的一个。但p|p₁p₂...pₙ，故p|(N-p₁p₂...pₙ)=1，这与p是素数（p≥2）矛盾，因此假设不成立，素数有无穷多个。6.定理8.10（欧几里得引理）：若p是素数，且p|ab，则p|a或p|b。7.推广：若p是素数，且p|a₁a₂...aₙ，则p至少整除a₁,a₂,...,aₙ中的一个。8.示例：若5|2×15，则5|2（不成立）或5|15（成立），故5|15。三、素数的判断方法1.根号判别法：对于大于1的正整数n，依次用不大于√n的素数去除n，若都不能整除，则n是素数；否则n是合数。2.示例：判断157是否为素数。√157≈12.53，不大于12.53的素数有2、3、5、7、11。157是奇数，不能被2整除；1+5+7=13，不能被3整除；末位不是0或5，不能被5整除；157÷7≈22.43，7×22=154，157-154=3，不能被7整除；157÷11≈14.27，11×14=154，157-154=3，不能被11整除。因此157是素数。3.爱氏筛法（埃拉托斯特尼筛法）：制作不大于N的素数表的方法，步骤如下：4.第一步：列出从2到N的所有正整数，构成一个数列：2,3,4,...,N。5.第二步：取数列中的第一个数2，将它的倍数（4,6,8,...）从数列中划去（2本身保留）。6.第三步：取数列中剩下的第一个数3，将它的倍数（6,9,12,...）从数列中划去（3本身保留）。7.第四步：重复第二步和第三步，直到所取的数大于√N为止。8.第五步：数列中剩下的数即为不大于N的所有素数。9.示例：用爱氏筛法制作60以内的素数表，最终得到素数：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59。四、算术基本定理1.定理8.11（算术基本定理）：任何大于1的正整数n，都可以唯一地分解成有限个素数的乘积，即n=p₁p₂...pₖ，其中p₁≤p₂≤...≤pₖ是素数。若不考虑素因数的顺序，则这种分解是唯一的。2.标准分解式：将n的素因子分解式中相同的素数合并成幂的形式，即n=p₁^α₁p₂^α₂...pₙ^αₙ，其中p₁<p₂<...<pₙ是素数，α₁,α₂,...,αₙ是正整数，称为素因子pᵢ的指数。3.示例：12=2×2×3=2²×3；99099=3×3×7×11×13×11=3²×7×11²×13。4.算术基本定理的应用：5.求最大公约数：设a=p₁^α₁p₂^α₂...pₙ^αₙ，b=p₁^β₁p₂^β₂...pₙ^βₙ（αᵢ,βᵢ为非负整数），则gcd(a,b)=p₁^min(α₁,β₁)p₂^min(α₂,β₂)...pₙ^min(αₙ,βₙ)。6.求最小公倍数：lcm(a,b)=p₁^max(α₁,β₁)p₂^max(α₂,β₂)...pₙ^max(αₙ,βₙ)。7.示例：求144和180的最大公约数与最小公倍数。144=2⁴×3²，180=2²×3²×5，故gcd(144,180)=2²×3²=36，lcm(144,180)=2⁴×3²×5=720。课堂教学设计3章节（专题）第8章数论计划学时2课题（内容）8.3同余教育教学目的1.理解同余的概念及其与整除的关系。2.掌握同余的基本性质及同余类的概念。3.掌握一次同余式的求解方法，理解孙子定理（中国剩余定理）并会求解一次同余方程组。4.课程思政目标：通过介绍中国剩余定理（孙子定理）的历史，增强文化自信，培养学生运用数学知识解决实际问题的能力。教学重点及难点重点：同余的性质、一次同余式的求解、孙子定理。难点：同余式的化简、孙子定理的构造性证明与求解过程。教学方法及手段1.讲授法2.合作探究3.互动式教学4.多媒体辅助教学教学互动环节设计1.导入新课：从星期几的计算引入同余概念。2.课堂讨论：同余与整除的关系，同余的性质有哪些？3.小组合作：求解一次同余式，并总结解的存在条件。4.案例分析：使用孙子定理解"物不知数"问题，并推广到一般同余方程组。课后总结与反思一、同余的概念1.定义8.12：设m是大于1的正整数，a、b是整数，若m|(a-b)，则称a与b模m同余，记作a≡b(modm)；若m不能整除(a-b)，则称a与b模m不同余，记作a≢b(modm)。其中m称为模。2.核心关联：a≡b(modm)⇔a-b=km（k为整数）⇔a=b+km⇔a与b被m除所得的余数相同。3.示例解析：￮判断28与13是否模3同余：28-13=15，3|15，故28≡13(mod3)；也可通过余数判断，28÷3余1，13÷3余1，余数相同，因此同余。￮生活实例：“5月8日是星期三，5月15日是星期三”，因15-8=7，7|7，故15≡8(mod7)，体现了同余的循环性。二、同余的基本性质1.等价关系性质（奠定同余分类的基础）：￮自反性：对任意整数a，有a≡a(modm)（因m|(a-a)=0）；￮对称性：若a≡b(modm)，则b≡a(modm)（因m|(a-b)⇒m|(b-a)）；￮传递性：若a≡b(modm)，b≡c(modm)，则a≡c(modm)（因m|(a-b)且m|(b-c)，由整除性质得m|(a-c)）。2.算术运算性质（同余的核心应用工具）：￮若a≡b(modm)，c≡d(modm)，则a+c≡b+d(modm)；￮若a≡b(modm)，c≡d(modm)，则a-c≡b-d(modm)；￮若a≡b(modm)，c≡d(modm)，则ac≡bd(modm)；￮推论1：若a≡b(modm)，则ka≡kb(modm)（k为整数，令c=k、d=k即可推导）；￮推论2：若a≡b(modm)，则aⁿ≡bⁿ(modm)（n为正整数，多次运用乘法性质推导）；￮推论3：若a≡b(modm)，且d|m、d|a、d|b，则a/d≡b/d(modm/d)（d为正整数，需注意整除条件）。3.性质应用示例：已知a≡3(mod5)，b≡4(mod5)，求a+b、ab模5的结果。￮a+b≡3+4=7≡2(mod5)；￮ab≡3×4=12≡2(mod5)。三、同余类与剩余类环1.定义8.13（同余类）：设m是大于1的正整数，将整数集Z中所有与整数a模m同余的整数构成的集合，称为a模m的同余类（也称为剩余类），记作[a]ₘ（或简记为[a]），即[a]ₘ={x∈Z|x≡a(modm)}。2.同余类的核心性质：￮模m的同余类共有m个，分别为[0]ₘ,[1]ₘ,[2]ₘ,...,[m-1]ₘ（对应被m除所得的m种余数）；￮任意两个不同的同余类互不相交，且所有同余类的并集为整数集Z（即整数集可按模m划分为m个互不相交的同余类）；￮x∈[a]ₘ⇔[x]ₘ=[a]ₘ。3.示例：模3的同余类有3个，分别为[0]₃={...,-6,-3,0,3,6,...}，[1]₃={...,-5,-2,1,4,7,...}，[2]₃={...,-4,-1,2,5,8,...}。4.剩余类环Zₘ：将模m的m个同余类作为元素，定义同余类的加法和乘法如下：此时这m个同余类构成的集合关于上述加法和乘法构成一个环，称为模m的剩余类环，记作Zₘ。￮加法：[a]ₘ+[b]ₘ=[a+b]ₘ；￮乘法：[a]ₘ×[b]ₘ=[ab]ₘ。5.Zₘ的运算示例（以Z₅为例）：￮加法：[2]₅+[3]₅=[5]₅=[0]₅；￮乘法：[2]₅×[3]₅=[6]₅=[1]₅。四、一次同余式1.定义8.14：形如ax≡b(modm)（其中m>1，a、b为整数，x为未知整数）的同余式，称为一元一次同余式，简称为一次同余式。2.一次同余式有解的条件（定理8.12）：一次同余式ax≡b(modm)有解的充分必要条件是gcd(a,m)|b。记d=gcd(a,m)，若同余式有解，则共有d个解（模m互不相同）。3.一次同余式的求解步骤（以ax≡b(modm)为例）：￮步骤1：计算d=gcd(a,m)，判断d是否整除b。若d∤b，同余式无解；若d|b，进入下一步；￮步骤2：将同余式两边同时除以d，得到简化同余式(a/d)x≡(b/d)(modm/d)。此时gcd(a/d,m/d)=1，即a/d与m/d互素；￮步骤3：求a/d模m/d的逆元x₀，即满足(a/d)x₀≡1(modm/d)的整数x₀（因a/d与m/d互素，逆元存在）；￮步骤4：简化同余式的解为x≡x₀×(b/d)(modm/d)；￮步骤5：原同余式的所有解（模m）为x≡x₀×(b/d)+k×(m/d)(modm)，其中k=0,1,...,d-1。4.求解示例：解一次同余式2x≡1(mod5)。￮步骤1：d=gcd(2,5)=1，1|1，同余式有解；￮步骤2：简化同余式为2x≡1(mod5)（因d=1，无需化简）；￮步骤3：求2模5的逆元，因2×3=6≡1(mod5)，故逆元x₀=3；￮步骤4：简化同余式的解为x≡3×1=3(mod5)；￮步骤5：原同余式的解为x≡3(mod5)（因d=1，仅有1个解）。五、孙子定理（中国剩余定理）1.定理8.13（孙子定理）：设m₁,m₂,...,mₙ是n个两两互素的大于1的正整数，令M=m₁m₂...mₙ，Mᵢ=M/mᵢ（i=1,2,...,n），则对任意整数b₁,b₂,...,bₙ，一次同余方程组$\begin{cases