数论基础知识 小学数论问题，起因于除法算式：被除数÷除数＝商……余数 1.能整除：整除，因数与倍数，奇数与偶数，质数与合数，公因数与公倍数，分解质因数等； 2.不能整除：余数，余数的性质与计算（余数），同余问题（除数），物不知数问题（被除数）。 一、因数与倍数 1、因数与倍数 （1）定义： 定义1：若整数a能够被b整除，a叫做b的倍数，b就叫做a的因数。 定义2：如果非零自然数a、b、c之间存在a×b＝c，或者c÷a＝b，那么称a、b是c的因数，c是a、b 的倍数。 注意：倍数与因数是相互依存关系，缺一不可。（a、b是因数，c是倍数） 一个数的因数个数是有限的，最小的因数是1，最大的因数是它本身。 一个数的倍数个数是无限的，最小的倍数是它本身，没有最大的倍数。 （2）一个数的因数的特点： ①最小的因数是1，第二小的因数一定是质数； ②最大的因数是它本身，第二大的因数是：原数÷第二小的因数 （3）完全平方数的因数特征： ①完全平方数的因数个数是奇数个，有奇数个因数的数是完全平方数。 ②完全平方数的质因数出现次数都是偶数次； ③1000以内的完全平方数的个数是31个，2000以内的完全平方数的个数是44个，3000以内的完 全平方数的个数是54个。（312=961，442=1936，542=2916） 2、数的整除（数的倍数） （1）定义： 定义1：一般地，三个整数a、b、c，且b≠0，如有a÷b＝c，则我们就说，a能被b整除，或b能整除a，或a能整除以b。 定义2：如果一个整数a，除以一个整数b（b≠0），得到一个整数商c，而且没有余数，那么叫做a能被b整除或b能整除a，记作b|a。（a≥b） （2）整除的性质： 如果a、b能被c整除，那么（a+b）与（a-b）也能被c整除。 如果a能被b整除，c是整数，那么a×c也能被b整除。 如果a能被b整除，b又能被c整除，那么a也能被c整除。 如果a能被b、c整除，那么a也能被b和c的最小公倍数整除。 （3）一些常见数的整除特征（倍数特征）： ①末位判别法 2、5的倍数特征：末位上的数字是2、5的倍数。 4、25的倍数特征：末两位上的数字是4、25的倍数。 8、125的倍数特征：末三位上的数字是8、125的倍数。 ②截断求和法（从右开始截） 9（及其因数3）的倍数特征：一位截断求和 99（及其因数3、9、11、33）的倍数特征：两位截断求和 999（及其因数3、9、27、37、111、333）的倍数特征：三位截断求和 ③截断求差法（从右开始截） 11的倍数特征：一位截断求差 101的倍数特征：两位截断求差 1001（及其因数7、11、13、77、91、143）的倍数特征：三位截断求差
小学数论基础知识
数论基础知识 一质数和合数 （1）一个数除了1和它本身，不再有别的约数，这个数叫做质数（也叫做素数）。 一个数除了1和它本身，还有别的约数，这个数叫做合数。 （2）自然数除0和1外，按约数的个数分为质数和合数两类。 任何一个合数都可以写成几个质数相乘的形式。 要特别记住：0和1不是质数，也不是合数。 （3）最小的质数是2 ，2是唯一的偶质数，其他质数都为奇数； 最小的合数是4。 （4）质数是一个数，是含有两个约数的自然数。 互质数是指两个数，是公约数只有一的两个数，组成互质数的两个数可能是两个质数（３和５），可能是一个质数和一个合数（３和４），可能是两个合数（４和９）或1与另一个自然数。 （５）如果一个质数是某个数的约数，那么就说这个质数是这个数的质因数。 把一个合数用质因数相乘的形式表示出来，叫做分解质因数。 （６）１００以内的质数有２５个： ２、３、５、７、 １１、１３、１７、１９、 ２３、２９、３１、３７、 ４１、４３、４７、
５３、５９、 ６１、６７、 ７１、７３、７９、 ８３、８９、 ９７ 二整除性 （１）概念 一般地，如a、b、c为整数，b≠0，且a÷b=c，即整数a除以整除b（b不等于0），除得的商c正好是整数而没有余数（或者说余数是0），我们就说，a能被b整除（或者说b能整除a）。记作b｜a.否则，称为a不能被b整除，（或b不能整除a），记作b a。 如果整数a能被整数b整除，a就叫做b的倍数，b就叫做a的约数。 （２）性质 性质1：（整除的加减性）如果a、b都能被c整除，那么它们的和与差也能被c整除。 即：如果c｜a，c｜b，那么c｜（a±b）。 例如：如果2｜10，2｜6，那么2｜（10＋6），并且2｜（10—6）。 也就是说，被除数加上或减去一些除数的倍数不影响除数对它的整除性。 性质2：如果b与c的积能整除a，那么b与c都能整除a. 即：如果bc｜a，那么b｜a，c｜a。 性质3：（整除的互质可积性）如果b、c都能整除a，且b和c互质，那么b 与c的积能整除a。
整除 一、常见数字的整除判定方法 1. 一个数的末位能被2或5整除，这个数就能被2或5整除； 一个数的末两位能被4或25整除，这个数就能被4或25整除； 一个数的末三位能被8或125整除，这个数就能被8或125整除； 2. 一个位数数字和能被3整除，这个数就能被3整除； 一个数各位数数字和能被9整除，这个数就能被9整除； 3. 如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个 数能被11整除. 4. 如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那么这 个数能被7、11或13整除. 5.如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数（如果有偶数位则 拆出的数都有两个数字，如果是奇数位则拆出的数中若干个有两个数字还有一个是一位数）的和是99的倍数，这个数一定是99的倍数。 【备注】（以上规律仅在十进制数中成立.） 二、整除性质 性质1 如果数a和数b都能被数c整除，那么它们的和或差也能被c整除．即如果c︱a，c︱b，那么c︱(a±b)． 性质2 如果数a能被数b整除，b又能被数c整除，那么a也能被c整除．即如果b∣a，c∣b，那么c∣a． 用同样的方法，我们还可以得出： 性质3如果数a能被数b与数c的积整除，那么a也能被b或c整除．即如果bc∣a，那么b∣a，c∣a． 性质4如果数a能被数b整除，也能被数c整除，且数b和数c互质，那么a一定能被b 与c的乘积整除．即如果b∣a，c∣a，且(b，c)=1，那么bc∣a． 例如：如果3∣12，4∣12，且(3，4)=1，那么(3×4) ∣12． 性质5 如果数a能被数b整除，那么am也能被bm整除．如果b｜a，那么bm｜am（m为非0整数）； 性质6如果数a能被数b整除，且数c能被数d整除，那么ac也能被bd整除．如果b｜a，且d｜c，那么bd｜ac； 余数 一、三大余数定理： 1.余数的加法定理 a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。 例如：23，16除以5的余数分别是3和1，所以23+16＝39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的 余数。 例如：23，19除以5的余数分别是3和4，所以23+19＝42除以5的余数等于3+4=7除以5的余数为2 2.余数的减法定理
数论基础知识 一质数和合数 （1）一个数除了1和它本身，不再有别的约数，这个数叫做质数（也叫做素数）。 一个数除了1和它本身，还有别的约数，这个数叫做合数。 （2）自然数除0和1外，按约数的个数分为质数和合数两类。 任何一个合数都可以写成几个质数相乘的形式。 要特别记住：0和1不是质数，也不是合数。 （3）最小的质数是2 ，2是唯一的偶质数，其他质数都为奇数； 最小的合数是4。 （4）质数是一个数，是含有两个约数的自然数。 互质数是指两个数，是公约数只有一的两个数，组成互质数的两个数可能是两个质数（３和５），可能是一个质数和一个合数（３和４），可能是两个合数（４和９）或1与另一个自然数。 （５）如果一个质数是某个数的约数，那么就说这个质数是这个数的质因数。 把一个合数用质因数相乘的形式表示出来，叫做分解质因数。 （６）１００以内的质数有２５个： ２、３、５、７、 １１、１３、１７、１９、 ２３、２９、３１、３７、 ４１、４３、４７、 ５３、５９、
６１、６７、 ７１、７３、７９、 ８３、８９、 ９７ 二整除性 （１）概念 一般地，如a、b、c为整数，b≠0，且a÷b=c，即整数a除以整除b（b不等于0），除得的商c正好是整数而没有余数（或者说余数是0），我们就说，a 能被b整除（或者说b能整除a）。记作b｜a.否则，称为a不能被b整除，（或b 不能整除a），记作b a。 如果整数a能被整数b整除，a就叫做b的倍数，b就叫做a的约数。 （２）性质 性质1：（整除的加减性）如果a、b都能被c整除，那么它们的和与差也能被c 整除。 即：如果c｜a，c｜b，那么c｜（a±b）。 例如：如果2｜10，2｜6，那么2｜（10＋6），并且2｜（10—6）。 也就是说，被除数加上或减去一些除数的倍数不影响除数对它的整除性。 性质2：如果b与c的积能整除a，那么b与c都能整除a. 即：如果bc｜a，那么b｜a，c｜a。 性质3：（整除的互质可积性）如果b、c都能整除a，且b和c互质，那么b与c 的积能整除a。 即：如果b｜a，c｜a，且（b，c）=1，那么bc｜a。
奥数数论基础知识 一质数和合数 （1）一个数除了1和它本身，不再有别的约数，这个数叫做质数（也叫做素数）。 一个数除了1和它本身，还有别的约数，这个数叫做合数。 （2）自然数除0和1外，按约数的个数分为质数和合数两类。 任何一个合数都可以写成几个质数相乘的形式。 要特别记住：0和1不是质数，也不是合数。（3）最小的质数是2 ，2是唯一的偶质数，其他质数都为奇数； 最小的合数是4。 （4）质数是一个数，是含有两个约数的自然数。 互质数是指两个数，是公约数只有一的两个数，组成互质数的两个数可能是两个质数（３和５），可能是一个质数和一个合数（３和４），可能是两个合数（４和９）或1与
另一个自然数。
（５）如果一个质数是某个数的约数，那么就说这个质数是这个数的质因数。 把一个合数用质因数相乘的形式表示出来，叫做分解质因数。 （６）１００以内的质数有２５个：２、３、５、７、１１、１３、１７、１９、２３、２９、３１、３７、４１、４３、４７、５３、５９、６１、６７、７１、７３、７９、８３、８９、９７． 二整除性 （１）概念 一般地，如a、b、c为整数，b≠0，且a÷b=c，即整数a除以整除b（b不等于0），除得的商c正好是整数而没有余数（或者说余数是0），我们就说，a能被b整除（或者说b能整除a）。记作b｜a.否则，称为a不能被b整除，（或b不能整除a），记作b a。
如果整数a能被整数b整除，a就叫做b的倍数，b就叫做a的约数。 （２）性质 性质1：（整除的加减性）如果a、b都能被c整除，那么它们的和与差也能被c整除。 即：如果c｜a，c｜b，那么c｜（a±b）。 例如：如果2｜10，2｜6，那么2｜（10＋6），并且2｜（10—6）。 也就是说，被除数加上或减去一些除数的倍数不影响除数对它的整除性。 性质2：如果b与c的积能整除a，那么b 与c都能整除a. 即：如果bc｜a，那么b｜a，c｜a。性质3：（整除的互质可积性）如果b、c都能整除a，且b和c互质，那么b与c的积能整除a。
1群、环、域概念 A1：加法的封闭性：如果a 和b 属于G ，则a+ｂ也属于G A2：加法结合律：对G 中的任意元素a,b,ｃ,ａ＋(b+c)=（a ＋ｂ)+c A3:加法单位元:G 中存在一个元素0，使得对于G 中的任意元素ａ，有a+０=０+a A4:加法逆元:对于Ｇ中的任意元素a ，G 中一定存在一个元素a,使得 ? a+（-a)＝（－a)＋a ＝０ Ａ5：加法交换律:对于Ｇ中的任意元素a 和b ，有a+b=ｂ+a M1:乘法的封闭性:如果a 和b 属于Ｇ,则ａｂ也属于G M2:乘法结合律：对于G 中的任意元素a,b,ｃ有ａ(bc)＝(ab ）c M3：乘法分配了:对于Ｇ中的任意元素a,b,ｃ,有a(b ＋c)＝ab+ac 和(a ＋ｂ)ｃ=ac+ｂc M4：乘法交换律：对于G 中的任意元素a ，b 有a ｂ＝ba M5:乘法单位元:对于G 中的任意元素a,在Ｇ中存在一个元素１，使得a1=１a ＝ａ M6:无零因子:对于G 中的元素ａ,b,若ab=0，则必有a=0或ｂ=0 M7：乘法逆元：如果a 属于G ，且a 不为０,则G 中存在一个元素1-a ，使得 111==--a a aa 满足A1--－A ４称为群 满足A1--－Ａ5称为可交换群 满足Ａ1-－-M ３称为环 满足A1---M ４称为可交换换 满足A １---Ｍ６称为整环 满足A1－－-M ７称为域 2循环群：如果群中的每一个元素都是一个固定元素)(G a a ∈的幂k a （k 为整数), 则称群G 是循环群。我们认为元素a 生成了群G ，或者说ａ是群G 的 生成元。 循环群总是交换群 3模运算 )mod ()mod (n b n a =则称整数ａ和b 是模n 同余的，可以表示为：)(mod n b a ≡ 若b 整除ａ。则用符号：a |b 表示。其性质可表示如下： ①如果a|1,那么a=-1或1。 ②如果ａ｜ｂ,且b|a ，那么a=b 或ａ=-b
《数论》第一章补充例题 整除性理论是初等数论的基础.本章要介绍带余数除法,辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们的一些应用. 1整数的整除性 例1设A={d1,d2,···,dk}是n的所有约数的集合,则 }{nnn,,···,B=d1d2dk 也是n的所有约数的集合. 解由以下三点理由可以证得结论: (i)A和B的元素个数相同; (ii)若di∈A,即di|n,则(iii)若di=dj,则问: d(1)+d(2)+···+d(1997) 是否为偶数? n解对于n的每个约数d,有n=d·n,因此,n的正约数d与是成对地出现的.只有 n2当d=n,即d=n时,d和才是同一个数.故当且仅当n是完全平方数时,d(n)是奇数.nini|n,反之亦然;=nj.例2以d(n)表示n的正约数的个数,例 如:d(1)=1,d(2)=2,d(3)=2,d(4)=3,···. 因为442<1997<452,所以在d(1),d(2),···,d(1997)中恰有44个奇数,故 d(1)+d(2)+···+d(1997)是偶数. 问题d2(1)+d2(2)+···+d2(1997)被4除的余数是多少? 例3证明:存在无穷多个正整数a,使得 n4+a(n=1,2,3,···) 都是合数. ? ?例题中引用的定理或推论可以在教材相应处找到. 1 解取a=4k4,对任意的n∈N,有 n4+4k4=(n2+2k2)2?4n2k2=(n2+2k2+2nk)(n2+2k2?2nk). 由 n2+2k2?2nk=(n?k)2+k2??k2, 所以,对于任意的k=2,3,···以及任意的n∈N,n4+a是合数.
第34讲数论基础知识应用 【培训提示】 1. 运用整数本身的基本特性分析解答简单的整数问题。 2.运用枚举方法和归纳方法的技巧。 数论是研究整数性质的一个数学分支。虽然数论问题看似简明，但是要解释清楚，并且证明它却是困难的；又因为整数以及相关的一些数学知识正是小学数学学习的重点，所以在各级各类的数学竞赛中，数论问题占有相当大的比重。 小学数学竞赛中的数论问题，常常涉及整数的整数性、带余除法、奇偶性、质数与合数、约束与倍数、整数的分解与分析等。分析解答数论问题，常常需要采取一些特殊的方法和技巧，本讲着重学习研讨用枚举法和归纳法分析解答数论问题的方法和技巧。 【培训示例】 例1 用三位数abc中的三个数字还可以组成五个三位数，如果这五个三位数加起 来的和是3194，那么三位数abc是是多少？（a、b、c都是不等于0的整数） 例2 从自然数1,2,3...2005中，最多可以取出多少个数，使得所取出的数中任意三个数之和能被18整除？ 例3 将自然数N接写在任意一个自然数的右面得到一个新数。如果所得到的新数正好能被N 整除，那么N就称为“魔术数”。问小于2005的自然数中有多少个魔术数？ 例4 有三张扑克牌，牌面数字都在10以内。把这三张牌洗好后，分别法给甲、乙、丙三人，每人都把自己的牌的数字记下后再重新洗牌、发牌、记数，这样反复几次后，三人各自记录的数字的和顺次为13,15,23。问：这三张牌的数字分别是多少？ 例5 有一摞卡片共100张，如果将上面的第一张去掉，把下一张卡片放在这摞卡片的最下面；在把上面的第一张（即原来这摞卡片的第三张）去掉，把下一张卡片（即原来这摞卡片的第四张）放在这摞卡片的最下面。反复这样做，知道手中只剩下一张卡片，那么最后剩下的这张卡片是原来这摞卡片的第几张？ 例6 若要用天平秤出1克、2克、3克...40克这些不同的整数克重量，至少要用多少个砝码？这些砝码的重量分别是多少克？
第一章整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。 第一节数的整除性 定义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下面的结论成立： (ⅰ) a∣b?±a∣±b； (ⅱ) a∣b，b∣c?a∣c； (ⅲ) b∣a i，i = 1, 2, , k?b∣a1x1+ a2x2+ +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。 证明留作习题。 定义2若整数a≠0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。 以后在本书中若无特别说明，素数总是指正素数。 定理2任何大于1的整数a都至少有一个素约数。 证明若a是素数，则定理是显然的。 若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , d k 。不妨设d1是其中最小的。若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。 推论任何大于1的合数a必有一个不超过 证明使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12≤a。证毕。 例1设r是正奇数，证明：对任意的正整数n，有 n+ 2|/1r+ 2r+ +n r。
九 进 制 乔治·兰伯特是美国加利福尼亚州一所中学的数学教师，他对数学特别敏感而且有极大的研究兴趣。他常年与数字、公式打交道，深感数学的神秘与魅力。他开始注意一些巧合的事件，力图用数学的方式来破解巧合。 他发现：法国皇帝拿破仑与纳粹元首希特勒相隔一个多世纪，但是他们之间有很多数字巧合。拿破仑1804年执政，希特勒1933年上台，相隔129年。拿破仑1816年战败，希 特勒1945年战败，相隔129年。拿破仑1809年占领维也纳，希特勒在1938 年攻人维也纳，也是相隔129年。拿破仑1812年进攻俄国，希特勒在相隔 129年后进攻苏联。美国第16届总统林肯于1861年任总统，美国第35届 总统肯尼迪于1961年任总统，时隔100年。两人同在星期五并在女人的参 与下被刺遇害。接任肯尼迪和林肯的总统的名字都叫约翰逊。更巧的是， 杀害林肯的凶手出生于1829年，杀害肯尼迪的凶手出生于1929年，相隔 又是100年。 兰伯特被这些数字迷住了，他经常将这些数字翻来覆去地分解组合。 他惊奇地发现，拿破仑和希特勒的巧合数129与林肯和肯尼迪的巧合数100，把它们颠倒过去分别是921和001，用921减去129，用100减去001，得数都能被9除尽：921-129=792，100-001=99；792+9=88，99÷9=11，结果都有一个十位和个位都相同的两位数的商。 兰伯特非常吃惊，他对9着了迷。他发现将l 、2、3、4、5、6、7、8、9加在一起是45，而4+5=9。他还发现，用9乘以任何一个数，将所得到的积的各位数字相加，所得到的和总是9。取任何一个数，比如说2004，将每位数加起来是2+0+0+4=6，用2004减去6结果得到1998，而1998÷9=222，能被9除尽。 他还总结出这样一个规律：把一个大数的各位数字相加得到一个和，再把这个和的各位数字相加又得到一个和。这样继续下去，直到最后的数字之和是一个一位数为止。最后这个数称为最初那个数的“数字根”，这个数字等于原数除；29的余数，这个计算过程被称作是“弃9法”。懂得了弃9法，蓝伯特醒悟了不少，他进而想到，人类不应该10个10个地数数，也不应该12个12个数数，而应该9个9个地数数，实行9进制。 课前预习 数论之整除性
数论基础知识 小学数论问题,起因于除法算式：被除数÷除数＝商……余数 1.能整除：整除,因数与倍数,奇数与偶数,质数与合数,公因数与公倍数,分解质因数等； 2.不能整除：余数,余数的性质与计算（余数）,同余问题（除数）,物不知数问题（被除数）。 一、因数与倍数 1、因数与倍数 （1）定义： 定义1：若整数a能够被b整除,a叫做b的倍数,b就叫做a的因数。 定义2：如果非零自然数a、b、c之间存在a×b＝c,或者c÷a＝b,那么称a、b是c的因数,c是a、b 的倍数。 注意：倍数与因数是相互依存关系,缺一不可。（a、b是因数,c是倍数） 一个数的因数个数是有限的,最小的因数是1,最大的因数是它本身。 一个数的倍数个数是无限的,最小的倍数是它本身,没有最大的倍数。 （2）一个数的因数的特点： ①最小的因数是1,第二小的因数一定是质数； ②最大的因数是它本身,第二大的因数是：原数÷第二小的因数 （3）完全平方数的因数特征： ①完全平方数的因数个数是奇数个,有奇数个因数的数是完全平方数。 ②完全平方数的质因数出现次数都是偶数次； ③1000以内的完全平方数的个数是31个,2000以内的完全平方数的个数是44个,3000以内的完 全平方数的个数是54个。（312=961,442=1936,542=2916） 2、数的整除（数的倍数） （1）定义： 定义1：一般地,三个整数a、b、c,且b≠0,如有a÷b＝c,则我们就说,a能被b整除,或b能整除a,或a能整除以b。 定义2：如果一个整数a,除以一个整数b（b≠0）,得到一个整数商c,而且没有余数,那么叫做a能被b 整除或b能整除a,记作b|a。（a≥b） （2）整除的性质： 如果a、b能被c整除,那么（a+b）与（a-b）也能被c整除。 如果a能被b整除,c是整数,那么a×c也能被b整除。 如果a能被b整除,b又能被c整除,那么a也能被c整除。 如果a能被b、c整除,那么a也能被b和c的最小公倍数整除。 （3）一些常见数的整除特征（倍数特征）： ①末位判别法 2、5的倍数特征：末位上的数字是2、5的倍数。 4、25的倍数特征：末两位上的数字是4、25的倍数。 8、125的倍数特征：末三位上的数字是8、125的倍数。 ②截断求和法（从右开始截） 9（及其因数3）的倍数特征：一位截断求和 99（及其因数3、9、11、33）的倍数特征：两位截断求和 999（及其因数3、9、27、37、111、333）的倍数特征：三位截断求和 ③截断求差法（从右开始截） 11的倍数特征：一位截断求差 101的倍数特征：两位截断求差
欧几里得算法 欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a,d|b，而r = a - kb，因此d|r 因此d也是（b,a mod b）的公约数 因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证欧几里得算法模板 int gcd(int n,int m) { int t,r; if(n
1. 数论——数的整除和余数 2.1基本概念和基本性质 整数a 除以整数b （b≠0），除得的商是整数而没有余数，我们就说a 能被b 整除，或者说b 能整除a 。 b ∣a ，读着b 能整除a;或a 能被b 整除； ba ，不能整除； ① 传递性：如果a|b,b|c,那么a|c;即b 是a 的倍数，c 是b 的倍数，则c 肯定是a 的倍 数； ② 加减性：如果a|b 、a|c ，那么a|(b c); ③ 因数性：如果ab|c ，那么a|c ，b|c;即如果ab 的积能整除c,则a 或b 皆能整除c; ④ 互质性，如果a|c ，b|c ，且（a,b ）=1,那么ab|c,即如果a 能整除c,b 能整除c ，且 ab 互质，则ab 的积能整除c; ⑤ a 个连续自然数中必恰有一个数能被a 整除。 2.2数的整除的判别法
各数位上数字的和是3或9的倍数，则能被3或9整除。 173652÷9:1+7+3+6+5+2的和除以3或9； 简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x 再除以3或9；如果x﹥9,则余数为x-9;如果x﹤9,则余数为x。 从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位上的数字的和的两者之差是否能被11整除； 奇数位和为6，偶数位和为27；如果奇数位和比偶数位和小，则奇数位和加1个或多个11，直到够减。余数的判断法与整数位的判断法一致。 2.2.4三位一截判别法（用以判别能否被7/11/13整除） 从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除； 两者差看能否被7整除，同样，不够减前面加1个或多个7，直到够减，余数位的判断法与整数位的判断法一致。 ①一般求空格数 如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，到最后看7的哪个倍数与缩减后的末位数相同，并看7的哪个倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减7后的这个数也为正确答案。
1. 倍数规律 末位系：2的倍数规律是末位数是偶数（即末位数是2的倍数），5的倍数规律是末位数是0或5（也即末位数是5的倍数）；4的倍数规律是末两位数是4的倍数（例如：28是4的倍数，则128、1128、23574335435328都是4的倍数），同样，25的倍数规律也是末两位是25的倍数；8的倍数规律是末三位是8的倍数，125的倍数规律是末三位是125的倍数。 练习：23400是上面提到的哪些数的倍数？（提示：0是任何数的倍数。） 数位和系：3或9的倍数规律是各个数位相加之和是3或9的倍数（例如：1+2+3=6是3的倍数但不是9的倍数，则123、321、213等等都是3的倍数而不是9的倍数；3+6=9既是3的倍数也是9的倍数，所以36、63也既是3的倍数也是9的倍数。） 练习：[ ]里能填哪些数可以使12[ ]34是3的倍数？9的倍数呢？ 数位差系：11的倍数规律是从后往前数奇数位上的数之和减去偶数位上的数之和是11的倍数。（若不够减则可通过加上11的倍数使其够减。）例：231，从后往前数，第1位是1，第2位3，第3位是2，所以奇数位的和是1+2=3，偶数位的和是3，所以奇数位和减偶数位和等于3-3=0是11的倍数，因此231就是11的倍数。6160，奇数位和等于1+0=1，偶数位和等于6+6=12，奇数位和减偶数位和不够减，但加上一个11以后就够减了，变成了1+11-12=0是11的倍数，所以6160是11的倍数。 7、11、13的倍数有个公共的规律，即将末3位与之前断开，形成两个新的数之差是7、11、13的倍数。例如：1012，把末三位断开后刚好变成了1与014（也就是12），于是这两数的差是11，因此是13的倍数，因此1014就是13的倍数。 练习：判断下列各数是不是7、11或13的倍数。 1131、25795、34177、12345 2. 分解质因数 把一个整数拆成成若干个质数（质数即只有1和本身作为因数的大于一的整数，如2、3、5、7……）相乘的形式。例：“1002255=???”就叫做把100分解质因数，而不能是1002105=??，因为10还可以进一步分解为25?。 练习：把下列各数分解质因数。 36= 24= 81= 96= 3. 质因数与整除的关系 例：12223=??，则12的倍数分解质因数后都得包含至少两个2和一个3（看上道题36和24的分解结果。）；12的因数分解质因数以后则必须包含了两个2和一个3之内，比如623=?、422=?、2、3都包含在12分解质因数的“组成”里。 练习：例如上面告诉的方法，以及36分解质因数的结果（上道题），写出36所有的因数。
行程问题 基本行程问题平均速度火车过桥流水行船接送问题电梯行程 数论问题 奇偶分析数的整除约数倍数进位制余数问题完全平方数 几何问题 小学几何五大模型勾股定理与弦图巧求周长立体图形的体积 计数问题 加法原理乘法原理容斥原理排列组合枚举法归纳法 应用题 鸡兔同笼问题年龄问题盈亏问题牛吃草问题工程问题浓度问题 计算问题 分数列项与整数列项繁分数的计算数学计算公式换元法找规律 其他 数阵图与数字谜操作与策略抽屉原理逻辑推理不定方程染色问题 小学六年级奥数基础知识——数论一 一质数和合数 （1）一个数除了1和它本身，不再有别的约数，这个数叫做质数（也叫做素数）。 一个数除了1和它本身，还有别的约数，这个数叫做合数。 （2）自然数除0和1外，按约数的个数分为质数和合数两类。 任何一个合数都可以写成几个质数相乘的形式。 要特别记住：0和1不是质数，也不是合数。 （3）最小的质数是2 ，2是唯一的偶质数，其他质数都为奇数； 最小的合数是4。 （4）质数是一个数，是含有两个约数的自然数。 互质 是指两个数，是公约数只有一的两个数，组成互质数的两个数可能是两个质数（３和５），可能是一个质数和一个合数（３和４），可能是两个合数（４和９）或1与另一个自然数。 （５）如果一个质数是某个数的约数，那么就说这个质数是这个数的质因数。 把一个合数用质因数相乘的形式表示出来，叫做分解质因数。 （６）１００以内的质数有２５个：２、３、５、７、１１、１３、１７、１９、２３、２９、３１、３７、４１、４３、４７、５３、５９、６１、６７、７１、７３、７９、８３、８９、９７． 注意：两个质数中差为1的只有3-2 ；除2外，任何两个质数的差都是偶数。 二整除性 （１）概念 一般地，如a、b、c为整数，b≠0，且a÷b=c，即整数a除以整除b（b不等于0），除得
数的整除 知识框架 一、整除的定义： 当两个整数a和b（b≠0），a被b除的余数为零时（商为整数），则称a被b整除或b整除a，也把a 叫做b的倍数，b叫a的约数，记作b|a，如果a被b除所得的余数不为零，则称a不能被b整除，或b不整除a，记作b a. 二、常见数字的整除判定方法 1.一个数的末位能被2或5整除，这个数就能被2或5整除； 一个数的末两位能被4或25整除，这个数就能被4或25整除； 一个数的末三位能被8或125整除，这个数就能被8或125整除； 2.一个位数数字和能被3整除，这个数就能被3整除； 一个数各位数数字和能被9整除，这个数就能被9整除； 3.如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个数能被11整 除； 4.如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那么这个数能被7、 11或13整除； 5.如果一个数从数的任何一个位置随意切开所组成的所有数之和是9的倍数，那么这个数能被9整除； 6.如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数（如果有偶数位则拆出的数都有 两个数字，如果是奇数位则拆出的数中若干个有两个数字还有一个是一位数）的和是99的倍数，这个数一定是99的倍数。 7.若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被 7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ，59－5×2＝49，所以6139是
第一节 整数的p 进位制及其应用 正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m --，则此数可以简记为：021a a a A m m --=（其中01≠-m a ）。 由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1-m 次多项式，即 012 21 11010 10 a a a a A m m m m +?++?+?=---- ，其中1,,2,1},9,,2,1,0{-=∈m i a i 且 01≠-m a ，像这种10的多项式表示的数常常简记为10021)(a a a A m m --=。在我们的日常 生活中，通常将下标10省略不写，并且连括号也不用，记作021a a a A m m --=，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。 为了具备一般性，我们给出正整数A 的p 进制表示： 012 21 1a p a p a p a A m m m m +?++?+?=---- ，其中1,,2,1},1,,2,1,0{-=-∈m i p a i 且 01≠-m a 。而m 仍然为十进制数字，简记为p m m a a a A )(021 --=。 第二节 整数的性质及其应用（1） 基础知识 整数的性质有很多，这里我们着重讨论整数的整除性、整数的奇偶性，质数与合数、完全平方数及整数的尾数等几个方面的应用。 1．整除的概念及其性质 在高中数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。 定义：设b a ,是给定的数，0≠b ，若存在整数c ，使得bc a =则称b 整除a ，记作a b |，并称b 是a 的一个约数(因子)，称a 是b 的一个倍数，如果不存在上述c ，则称b 不能整除a 记作b a 。 由整除的定义，容易推出以下性质： (1)若c b |且a c |，则a b |(传递性质)；
第一节整数的p进位制及其应用 正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m位的正整数A，其各位上的数字分别记为，则此数可以简记为：（其中）。 由于我们所研究的整数通常是十进制的，因此A可以表示成10的次多项式，即，其中 且，像这种10的多项式表示的数常常简记为。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。 为了具备一般性，我们给出正整数A的p进制表示： ，其中且。而仍然为十进制数字，简记为。 第二节整数的性质及其应用（1） 基础知识 整数的性质有很多，这里我们着重讨论整数的整除性、整数的奇偶性，质数与合数、完全平方数及整数的尾数等几个方面的应用。 1．整除的概念及其性质 在高中数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。 定义：设是给定的数，，若存在整数，使得则称整除，记作，并称是的一个约数(因子)，称是的一个倍数，如果不存在上述，则称不能整除记作。
数论讲义 整除性问题 1 证明算术基本定理 证明：Z b a ∈,,0>b ，则r bq a +=，b r <≤0，r q ,是唯一确定的。 证明：若a|c,b|c,(a,b)=1,则ab|c 若a|bc,(a,b)=1,则a|c (a,b)=1 代表两数互质 2 整数的性质 整数n 与1+n 之间不再有其它整数，从而2 n 与2)1(+n 之间也不再有其它平方数，任一整数有限集必有最大数与最小数，整数b a >等价于1+≥b a 等，都体现了整数的离散性。 例1 求证：不存在正整数b a ,，使b a +2 及2b a +都是完全平方数 例2 求证：五个连续整数的平方和不是完全平方数. 例3 已知： (x+a)(x+b)+(x+b)(x+c)+(x+c)(x+a)是完全平方式. 求证： a=b=c. 例4求证：当k 为整数时，方程4x 2+8kx+(k 2+1)=0没有有理数根 4 数的整除特征 求证： 任何n 个连续整数之积一定能被n 整除. 求证：任何n 个连续整数之积一定能被n !整除. n n 321!??= 0111101010a a a a x n n n n +++=-- *∈N x n n n n n n n n n n n n b ab b a b a a b a C C C C ++++=+----11 222 11 )( n b a )(+被a 除的余数等于n b 被a 除的余数 n b a )(+被b 除的余数等于n a 被b 除的余数 ))((1221----+++-=-n n n n n n b ab b a a b a b a M b a )(-= n 为自然数 n n b a b a --|)( ))((1221----++-+=+n n n n n n b ab b a a b a b a =N b a )(+ n 为正奇数 n n b a b a ++|)( 例5 判断3546725能否被13整除？ 例6 设72679a b |，试求,a b 的值. 例7 求证：n 为正奇数时，1236---n n n 能被60整除
1.数论---- 数的整除和余数 2.1基本概念和基本性质 2.1.1定义 整数a除以整数b （b旳），除得的商是整数而没有余数，我们就说a能被b整除，或者说b能整除a。 2.1.2表达式和读法 b I a,读着b能整除a;或a能被b整除；b i a,不能整除； 2.1.3基本性质 ①传递性：如果a|b,b|c,那么a|c;即b是a的倍数，c是b的倍数，则c肯定是a的 倍数； ②加减性：如果a|b、a|c，那么a|（b c）; ③因数性：如果ab|c，那么a|c, b|c;即如果ab的积能整除c,则a或b皆能整除c; ④互质性，如果a|c，b|c，且（a,b）=1,那么ab|c,即如果a能整除c,b能整除c， 且ab互质，则ab的积能整除c; ⑤a个连续自然数中必恰有一个数能被a整除。 2.2数的整除的判别法
221末位判别法 2.2.2数字和判别法（用以判别能否被3或9整除） 各数位上数字的和是3或9的倍数，则能被3或9整除。 173652乜:1+7+3+6+5+2 的和除以3 或9; 简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x再除以3或9;如果x> 9,则余数为x-9;如果x< 9,则余数为X。 2.2.3奇偶数位判别法（用以判别能否被11整除） 从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位上的数字的和的两者之差是否能被11整除； 81729033-11:奇数位和为6,偶数位和为27;如果奇数位和比偶数位和小， 则奇数位和加1个或多个11，直到够减。余数的判断法与整数位的判断法一致。
224三位一截判别法（用以判别能否被7/11/13整除） 2.2.4.1基本用法 从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除; 女口，86372548，奇数段的和为（548+86 ），偶数段的和为372，求两者差看能否被7整除，同样，不够减前面加1个或多个7,直到够减，余数位的判断法与整数位的判断法一致。 2.2.4.2特殊用法 ①一般求空格数 如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，到最后看7的哪个倍数与缩减后的末位数相同，并看7的哪个倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减7后的这个数也为正确答案。 395864 □ 82365，答案为5 463925 □ 01234，答案为1 和8 ②特殊求空格数 根据整除的因数性，如果1个数能被1001整除，则这个数能被7、11、13、 77、91、143整除，因为： 7X11 X13=1001; 77X13=1001; 99 X11=1001；