第14章 简单的数论问题-2022全国重点大学招生【强基计划】数学解难

全国重点大学招生强基计划数学解难 第十四章 简单的数论问题 知识要点回顽 1.整数的p进位制 给定一个m位的正整数A,其各位上的数字分别记为am-1,am-2,…,o,则此数可以简记 为A=am-1am-2…ao,（其中am1≠0) 正整数A的p进位制表示： A=am-1×p”-1+am-2×p-2+…+a1×p+a0,其中a∈{0,1,2，…，p-1},i=1,2,…,m-1且 am-1≠0.而m仍为十进制数字， 简记为：A=（am-1am-2…ao)· 2.整除的概念及其性质 定义：设a,b是给定的数，b≠0，若存在整数c,使得a=bc,则称b整除a,记作ba,并称b是a的一个 约数（因子），称a是b的一个倍数，如果不存在上述c,则称b不能整除a记作ba(如果不加特殊说 明，我们所涉及的数都是整数，所采用的字母也表示整数) 由整除的定义，容易推出以下性质： (1)若bc且ca,则ba(传递性质)； (2)若ba且bc,则b(a±c) (3)若ba,则或者a=0,或者|a≥b1,因此若ba且ab,则a=士b: (4)a,b互质，若ac,bc,则abc; (5)p是质数，若pa1a2…an,则p能整除其中a1,a2,…,an的某一个；特别地，若p是质数，若pa”,则pa; 带余除法：设a,b为整数，b>0,则存在整数q和r,使得a=bg十r,其中0≤r<b,并且q和r由上述条 件唯一确定；整数q被称为a被b除得的（不完全）商，数r称为a被b除得的余数.注意：r共有b种可 能的取值：0,1，…，b一1.若r=0,即为a被b整除的情形； 若n是正整数，则x”一y=(x一y)(x1十x2y十…十xy2十y1); 若n是正奇数，则x”十y=(x十y)(x1一x”2y十…一xy-2十y-1). 整数整除性的一些数码特征（即常见结论） (1)若一个整数的末位数字能被2（或5）整除，则这个数能被2（或5）整除，否则不能； (2)一个整数的数码之和能被3（或9）整除，则这个数能被3（或9）整除，否则不能； (3)若一个整数的末两位数字能被4（或25）整除，则这个数能被4（或25）整除，否则不能； (4)若一个整数的末三位数字能被8（或125）整除，则这个数能被8（或125）整除，否则不能； (5)若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除， 否则不能 算术基本定理： 设整数a>1,那么必有a=p1p2…pn,(※)其中p,(1≤j≤n)是素数，且不在记次序的意义下，（※）式 是唯一的. 若把（※）式中相同的素数合并，即得a=p2…ppma1十a2十…十a,=n,p<2<…<p (这里p:互不相同i=1,2,…,s),称为a的标准素因数分解式. 裴蜀(Bezout)定理：设a1,a2,…,a是不完全为零的整数，则对于整数n,存在整数y1y2,…,y, 使得n=a1y1十a2y2十…十ay(*)成立的的充要条件是(a1,a2,…,a)n. -182 第十四章简单的数论问题 特别地，(*)式对n=1成立的充要条件是(a1,a2,…,a)=1,即a1,a2,…,a互素.这里符号 (a1,a2,…,a)指a1,a2,…,ak的最大公约数. 两个整数a,b互素的充要条件是存在整数x,y,使得ax十by=1. 3.同余的定义及性质 定义：设m>0,若m(a一b),则称a和b对模m同余，记作a三b(modm);若不然，则称a和b对模m 不同余，记作a丰b(modm).当0≤b<m时，a三b(modm),则称b是a对模m的最小非负剩余 由带余除法可知，a和b对模m同余的充要条件是a与b被m除得的余数相同.对于固定的模m,模 m的同余式与通常的等式有许多类似的性质： 性质1.a三b(modm)的充要条件是a=b+mt,t∈Z也即m(a一b) 性质2.同余关系满足以下规律： (1)(反身性)a三a(modm); (2)(对称性)若a=b(modm),则b=a(modm); (3)(传递性)若a三b(modm),b三c(modm),则a三c(modm); (4)(同余式相加)若a=b(modm),c=d(modm),则a土c=b士d(modm); (5)(同余式相乘)若a=b(modm),c三d(modm),则ac=bd(modm); 4.不定方程 定义：变数个数多于方程个数，且取整数值的方程（方程组）称为不定方程（组） (1)不定方程问题的常见类型： ①求不定方程的解； ②判定不定方程是否有解； ③判定不定方程的解的个数（有限个还是无限个）. 一次不定方程 设整数k≥2，c,a1a2,…,a是整数且a1,a2,…,ak都不等于零，以及x1,x2,…,x6是整数变量.方程 a1x1十a2x2十…akx=c,称为k元一次不定