整除与转辗相除法
摘要:整除理论是初等数论的基础,带余数除法及转辗相除法是是建立整除理
论的重要工具,它们也是初等数论的证明最基本、最重要、最直接的工具,因此掌握这两种方法是非常重要的.
关键字:整除、带余除法、转辗相除法
一、整除
1、定义:设a,b是整数,b≠0。如果存在一个整数q使得等式:
a=bq成立,则称b能整除a或a能被b整除,记作b∣a;
如果这样的q不存在,则称b不能整除a。
2、整除的性质
(1)如果b∣a,c∣b,则c∣a.
(2)如果b∣a,则cb∣ca. (c不为零)
(3)如果c∣a,则对任何整数d,c∣da.
(4)如果c∣a,c∣b,则对任意整数m,n,有
c∣ma+nb.
(5)如果a∣b,b∣a,则a=±b.
(6)如果a∣b,则-a∣b或a∣-b
3、学会利用性质证明
例:若3∣n,且7∣n,则21∣n
证明:由3∣n知n=3m,
所以7∣3m,
因7∣7m 得7∣7m-2*3m ,即7∣m
所以21∣n
二、带余数除法
定理1:
设a,b是两个整数,其中b>0,则存在两个唯一的整数q及r,使得a=bq+r,0≤r<b
成立.我们称r是b除a的余数。
可以看出:b整除a的充要条件是r=0。
三、辗转相除法
辗转相除法:又叫欧几里得算法,是一种求两个正整数的最大公因数的古老有效的算法。也可用来求不定方程的整数的特解。
1、用转辗相除法求两个数的最大公因数。
例、求两个正数198和252的最大公因数,并将其表示成198和252的整系数的线性组合。
分析:用转辗相除法来做,将两数相除,用大数a除以小数b,有余数R,在用除数b除以余数R,直至余数为零,到数第二个余数为两数的最大公约数。
最后将最大公约数用这两个数表示出来。
解:因为 252=1*198+54
198=3*54+36
54=1*36+18
36=2*18
所以,18是198和252的最大公因数。
因为 18=54-18
18=54-(198-3*54)=-198+4*54
18=-198+4(252-198)=4*252-5*198
18=4*252-5*198
以上我们求最大公因数的方法就是辗转相除
2、辗转相除法可以求出不定方程的一组整数解。
我们知道,如果未知数的个数多于方程的个数,那么,一般来说,它的解往往是
不确定的,例如方程x-2y=3和方程组
等,它们的解是不确定的.像这类方程或方程组就称为不定方程或不定方程组.
不定方程(组)是数论中的一个古老分支,其内容极其丰富.我国对不定方程的研究已延续了数千年,“百鸡问题”等一直流传至今,“物不知其数”的解法被称为中国剩余定理.近年来,不定方程的研究又有新的进展.掌握不定方程,不仅可以拓宽数学知识面,而且可以培养思维能力,提高数学解题的技能.
当方程的系数较大时,我们还可以用辗转相除法求其特解,其解法结合例题说明.
例4求方程37x+107y=25的整数解.
解107=2×37+33,37=1×33+4,33=8×4+1.
为用37和107表示1,我们把上述辗转相除过程回代,得
1=33-8×4=37-4-8×4=37-9×4
=37-9×(37-33)=9×33-8×37
=9×(107-2×37)8×37=9×107-26×37
=37×(-26)+107×9.
由此可知x1=-26,y1=9是方程37x+107y=1的一组整数解.于是
x0=25×(-26)=-650,y0=25×9=225是方程37x+107y=25的一组整数解.
所以原方程的一切整数解为
大约1500年以前,我国古代数学家张丘建在他编写的《张丘建算经》里,曾经提出并解决了“百钱买百鸡”这个有名的数学问题,通俗地讲就是下例.
今有公鸡每只五个钱,母鸡每只三个钱,小鸡每个钱三只.用100个钱买100只鸡,问公鸡、母鸡、小鸡各买了多少只?
解设公鸡、母鸡、小鸡各买x,y,z只,由题意列方程组
①化简得15x+9y+z=300.③
③-②得14x+8y=200,
即7x+4y=100.
解7x+4y=1得
于是7x+4y=100的一个特解为
由定理知7x+4y=100的所有整数解为
由题意知,0<x,y,z<100,所以
由题意知,0<x,y,z<100,所以
由于t是整数,故t只能取26,27,28,而且x,y,z还应满足
x+y+z=100.
T x y z
26 4 18 78
27 8 11 81
28 12 4 84
即可能有三种情况:4只公鸡,18只母鸡,78只小鸡;或8只公鸡,11只母鸡,81只小鸡;或12只公鸡,4只母鸡,84只小鸡.
通过上述过程的研究和探讨,整除理论是初等数论的基础,它是对小学就学过的整数的算术,主要是涉及除法的运用的内容,现在更进一步研究,加深理解和扩大范围,有一定的难度.
学好初等数论是学好数学的基础,也是数学的关键和难点,把每一个知识点都学透,弄懂里面的每一个知识点,学会应用,应该会对学好有帮助的.
数学与信息学院2009级4班
刘金梅
第一次网络作业 一、填空 1.(525,231)的最大公因数为 1、21 2.2160的正约数的个数为 40个 3. 求所有正约数的和等于15的最小正数为 8 4.自176到545的整数中是13倍数的整数个数为 28个 5.35!的标准分解式为 2^5*3^3*5^2*7*11*13*17*19*23*29*31 二、试证:6|n(n+1)(2n+1),这里n是任意整数。 证明:n(n+1)(2n+1)=n(n+1)(n-1+n+2)=(n-1)n(n+1)+n(n+1)(n+2) 而 n-1 n n+1是连续的三个整数,其中必有一个是3的倍数,至少有一个是2的倍数 所以(n-1)n(n+1)是6的倍数 同理 n(n+1)(n+2)也是6的倍数 他们的和 n(n+1)(2n+1)也是6的倍数 三、假如(a,b)=1,那末(a-b,a+b)=1或2 因为(a,b)=1 所以存在u,v使得ua+vb=1 所以u(a+b)+(u-v)(-b)=1 v(a+b)+(u-v)a=1 把以上两式相加得(u+v)(a+b)+(u-v)(a-b)=2 如果a+b被2整除,那么a-b也被2整除,我们可得(a-b,a+b)=2 如果u+v被2整除,那么u-v也被2整除,我们可得(a-b,a+b)=1; 如果a+b不被2整除,u+v不被2整除,那么a-b也不被2整除,u-v也不被2整除,此时必然u,v,a,b均为奇数,这与ua+vb=1矛盾
四、求证(21n+4)/(14n+3)是不可约分数,这里n是任意正整数。证明:-.-(21n+4)/(14n+3)=1+(7n+1)/(14n+3) 又(14n+3)/(7n+1)=2+1/(7n+1) 则1/(7n+1)不可约 所以(14n+3)/(7n+1)不可约 所以(21n+4)/(14n+3)也是不可约
初等数论练习题一 一、填空题 1、τ(2420)=27;?(2420)=_880_ 2、设a ,n 是大于1的整数,若a n -1是质数,则a=_2. 3、模9的绝对最小完全剩余系是_{-4,-3,-2,-1,0,1,2,3,4}. 4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。 5、不定方程18x-23y=100的通解是x=900+23t ,y=700+18t t ∈Z 。. 6、分母是正整数m 的既约真分数的个数为_?(m )_。 7 8、??? ??10365 =-1。 9、若p 是素数,则同余方程x p - 1 ≡1(mod p )的解数为二、计算题 1、解同余方程:3x 2+11x -20≡0 (mod 105)。 解:因105 = 3?5?7, 同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3), 同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0,3 (mod 5), 同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2,6 (mod 7), 故原同余方程有4解。 作同余方程组:x ≡b 1 (mod 3),x ≡b 2 (mod 5),x ≡b 3 (mod 7), 其中b 1 = 1,b 2 = 0,3,b 3 = 2,6, 由孙子定理得原同余方程的解为x ≡13,55,58,100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解? 11074217 271071107713231071107311072107 710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-)()()()(),()()()(),()())()(( )(解: 故同余方程x 2≡42(mod 107)有解。 3、求(127156+34)28除以111的最小非负余数。
初等数论 初等数论从表面意义来讲,就是作为一门研究数的相关性质的数学学科。准确地按照潘承洞、潘承彪两位数论大师的说法:初等数论是研究整数最基本的性质,是一门十分重要的数学基础课。它不仅是中、高等师范院校数学专业,大学数学各专业的必修课,而且也是计算机科学等相关专业所需的课程。纵观数论发展过程,我国出现了许许多多的数论大师,如:华罗庚的早期研究方向、陈景润、潘承洞等。 第一部分:整除 初接触初等数论,经过《初等数论》课本知整除理论是初等数论的基础。整除理论首先涉及整除。现向上延伸则想到整除的对象,即自然数、整数。从小学、中学再到大学,我们从接触最初的1、2、3再到后来的有理数、无理数、实数再到复数,可谓种类繁多。但数论中的整除运算仅仅局限于自然数及其整数等相关范围内。首先大学数学中绝大多数数学定义中的自然数不包括0 ,这似乎与中学有一点差别,当然整数的定义改变就相对少得多。另外,自然数、整数的相关基本性质需懂得及灵活利用,如分配律、交换律、反对称性等。在初等代数中曾系统地介绍了自然数的起源问题:自然数源于经验,自然数的本质属性是由归纳原理刻画的,它是自然数公理化定义的核心。自然数集合严格的抽象定义是由Peano定理给出的,他刻画了自然数的本质属性,并导出有关自然数的有关性质。 Peano定理:设N是一个非空集合,满足以下条件: (ⅰ)对每一个n∈N,一定有唯一的一个N中的元素与之对应,这个元素记作n+,称为是n的后继元素(或后继); (ⅱ)有元素e∈N,他不是N中任意元素的后继; (ⅲ)N中的任意一个元素至多是一个元素的后继,即从a+=b+ 一定可以推出a=b; (ⅳ)(归纳原理)设S是N的一个子集合,e∈S, 如果n∈S则必有n+ ∈S,那么,S=N. 这样的集合N称为自然数集合,它的元素叫做自然数。 其中的归纳原理是我们常用的数学归纳法的基础。数学归纳法在中学已属重点内容,此处就不作介绍。主要描述一下推广状态下的第二种数学归纳法:(第二种数学归纳法)设P(n)是关于自然数n的一种性质或命题。如果 (1)当n=1时,P(1)不成立; (2)设n>1,若对所有的自然数m 1 浙江省2018年4月高等教育自学考试 初等数论试题 课程代码:10021 一、单项选择题(本大题共5小题,每小题2分,共10分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.20被-30除的余数是( ) A .-20 B .-10 C .10 D .20 2.176至545的正整数中,13的倍数的个数是( ) A .27 B .28 C .29 D .30 3.200!中末尾相继的0的个数是( ) A .49 B .50 C .51 D .52 4.从以下满足规定要求的整数中,能选取出模20的简化剩余系的是( ) A .2的倍数 B .3的倍数 C .4的倍数 D .5的倍数 5.设n 是正整数,下列选项为既约分数的是( ) A . 3144 21++n n B . 121 -+n n C .2 512+-n n D .1 31++n n 二、填空题(本大题共10小题,每小题3分,共30分) 请在每小题的空格中填上正确答案。错填、不填均无分。 1.d(120)=___________。 2.314162被163除的余数是___________。 3.欧拉定理是___________。 4.同余方程3x ≡5(mod13)的解是___________。 5.不定方程10x-8y=12的通解是___________。 2 6.ο ___________)1847 365 ( = 7.[-π]=___________。 8.为使n-1与3n 的最大公因数达到最大的可能值,则整数n 应满足条件___________。 9.如果一个正整数具有21个正因数,问这个正整数最小是___________。 10.同余方程x 3+x 2-x-1≡0(mod 3)的解是___________。 三、计算题(本大题共4小题,每小题10分,共40分) 1.解同余方程组 ???? ?? ?≡≡≡≡) 9(mod 4)7(mod 32)4(mod 23) 25(mod 1x x x x 2.解不定方程15x+10y+6z=19。 3.试求出所有正整数n ,使得2n -1能被7整除。 4.判断同余方程 x 2≡-1457(mod 2389) 是否有解? 四、证明题(本大题共2小题,每小题10分,共20分) 1.证明形如4n+3的素数有无穷多个。 2.证明不定方程 x 2+y 2+z 2=x 2y 2 没有正整数解。 初等数论试卷一 一、 单项选择题:(1分/题×20题=20分) 1.设x 为实数,[]x 为x 的整数部分,则( ) A.[][]1x x x ≤<+; B.[][]1x x x <≤+; C.[][]1x x x ≤≤+; D.[][]1x x x <<+. 2.下列命题中不正确的是( ) A.整数12,,,n a a a 的公因数中最大的称为最大公因数; B.整数12,, ,n a a a 的公倍数中最小的称为最小公倍数 C.整数a 与它的绝对值有相同的倍数 D.整数a 与它的绝对值有相同的约数 3.设二元一次不定方程ax by c +=(其中,,a b c 是整数,且,a b 不全为零)有一整数解 ()00,,,x y d a b =,则此方程的一切解可表为( ) A.00,,0,1,2,;a b x x t y y t t d d =- =+ =±± B.00,,0,1,2, ;a b x x t y y t t d d =+= -=±± C.00,,0,1,2, ;b a x x t y y t t d d =+= -=±± D.00,,0,1,2, ;b a x x t y y t t d d =-= -=±± 4.下列各组数中不构成勾股数的是( ) A.5,12,13; B.7,24,25; C.3,4,5; D.8,16,17 5.下列推导中不正确的是( ) A.()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ B.()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ C.()()111212mod mod ;a b m a a b a m ≡?≡ D.()()112 2 11mod mod .a b m a b m ≡?≡ 6.模10的一个简化剩余系是( ) A.0,1,2, ,9; B.1,2,3,,10; 《竞赛数学中的初等数论》 贾广素编著 2006-8-21 序 言 数论是竞赛数学中最重要的一部分,特别是在1991年,IMO 在中国举行,国际上戏称那一年为数论年,因为6道IMO 试题中有5道与数论有关。 数论的魅力在于它可以适合小孩到老头,只要有算术基础的人均可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想,当然,这一谣言最终被澄清了。可是这也说明了最难的数论问题,适合于任何人去研究。 初等数论最基础的理论在于整除,由它可以演化出许多数论定理。做数论题,其实只要整除理论即可,然而要很快地解决数论问题,则要我们多见识,以及学习大量的解题技巧。这里我们介绍一下数论中必需的一个内容:对于N r q N b a ∈?∈?,,,,满足r bq a +=,其中b r <≤0。 除了在题目上选择我们努力做到精挑细选,在内容的安排上我们也尽量做到讲解详尽,明白。相信通过对本书学习,您可以对数论有一个大致的了解。希望我们共同学习,相互交流,在学习交流中,共同提高。 编者:贾广素 2006-8-21于山东济宁 第一节 整数的p 进位制及其应用 正整数有无穷多个,为了用有限个数字符号表示出无限多个正整数,人们发明了进位制, 这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系,近几年来,国内与 国际竞赛中关于“整数的进位制”有较多的体现,比如处理数字问题、处理整除问题及处理 数列问题等等。在本节,我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m 位的正整数A ,其各位上的数字分别记为021,,,a a a m m --,则此数可以简记为:021a a a A m m --=(其中01≠-m a )。 由于我们所研究的整数通常是十进制的,因此A 可以表示成10的1-m 次多项式,即 012211101010a 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 进制表示: 012211a 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.将一个十进制数字2004(若没有指明,我们也认为是十进制的数字)转化成二进制与 八进制,并将其表示成多项式形式。 分析与解答 分析:用2作为除数(若化为p 进位制就以p 作为除数),除2004商1002,余数为0;再 用2作为除数,除1002商501余数为0;如此继续下去,起到商为0为止。所得的各次余 数按从左到右的顺序排列出来,便得到所化出的二进位制的数。 解: “4-6 初等数论初步”简介 北京师范大学胡永建 初等数论是研究整数的性质和不定方程(组)的整数解的一门学问,它与几何学是最古老的两个数学分支。初等数论中至今仍有许多没有解决的问题,如哥德巴赫(Goldbach)问题,孪生素数猜想,奇完全数的存在性问题等,它们对人类智慧产生了极大挑战。人们在解决一些初等数论问题的过程中所作的贡献,对数论乃至整个数学的发展起了重要的推动作用,产生了一些直接与数学有关的新的重要数学分支。初等数论在计算机科学和信息工程中有许多重大的实际应用。在本专题中,同学们将通过具体的问题,学习初等数论的一些基本知识,如有关整数和整除的知识,用辗转相除法求解一次同余方程(组)和简单的一次不定方程等,初等数论中蕴含的一些思想方法,以及我国古代数学在初等数论的研究方面取得的一些重要成就。 一、内容与课程学习目标 本专题的学习初等数论的一些基本知识,具体包括:整数的整除、同余与同余方程、一次不定方程和数论在密码中的应用四部分内容。通过本专题的学习,要引导学生:1.通过实例,认识带余除法,理解同余和剩余类的概念及意义,探索剩余类的运算性质(加法和乘法),并且理解它的实际意义。体会剩余类运算与传统数的运算的异同(会出现零因子)。 2.理解整除、因数和素数的概念,了解确定素数的方法,如埃拉托斯特尼(Eratoshenes)筛法,知道素数有无穷多个。 3.了解十进制表示的整数的整除判别法,探索整数能被3,9,11,7等整除的判别法。会检查整数加法、乘法运算错误的一种方法,如弃九验算法。 4.通过实例,探索利用辗转相除法求两个整数的最大公约数的方法,理解互素的概念,并能用辗转相除法证明:若a能整除bc,且a,b互素,则a能整除c。探索公因数和公倍数的性质。了解算术基本定理。 5.通过实例,理解一次不定方程的模型,利用辗转相除法求解简单的一次不定方程。并尝试写出算法的程序框图,在条件允许的情况下上机实现。 6.通过实例(如物不知其数问题),理解一次同余方程组的模型。 7.理解大衍求一术和孙子定理的证明。 8.理解费马小定理(当m是素数时,a m-1≡1(mod m))和欧拉定理(aφ(m)≡1(mod m),其中φ(m)是1,2,…,m-1中与m互素的数的个数)及其证明。 9.了解数论在密码中的应用——公开密钥。 二、内容安排 本专题共安排了四讲,其中最后一讲“数论在密码中的应用”可根据教学时间的实际情况机动安排,可由教师讲授,也可作为学生课后的阅读材料。本专题教学时间约需18课时,具体分配如下(仅供参考): 第一讲整数的整除约5课时 一、整除的概念和性质约2课时 二、最大公因数与最小公倍数约2课时 附录1 习题参考答案 第一章习题一 1. (ⅰ) 由a b知b = aq,于是b = (a)(q),b = a(q)及b = (a)q,即a b,a b及a b。反之,由a b,a b及a b 也可得a b; (ⅱ) 由a b,b c知b = aq1,c = bq2,于是c = a(q1q2),即a c; (ⅲ) 由b a i知a i= bq i,于是a1x1a2x2a k x k = b(q1x1 q2x2q k x k),即b a1x1a2x2a k x k;(ⅳ) 由b a知a = bq,于是ac = bcq,即bc ac; (ⅴ) 由b a知a = bq,于是|a| = |b||q|,再由a 0得|q| 1,从而|a| |b|,后半结论由前半结论可得。 2. 由恒等式mq np= (mn pq) (m p)(n q)及条件m p mn pq可知m p mq np。 3. 在给定的连续39个自然数的前20个数中,存在两个自然数,它们的个位数字是0,其中必有一个的十位数字不是9,记这个数为a,它的数字和为s,则a, a 1, , a 9, a 19的数字和为s, s 1, , s 9, s 10,其中必有一个能被11整除。 4. 设不然,n1= n2n3,n2p,n3p,于是n = pn2n3p3,即p3n,矛盾。 5. 存在无穷多个正整数k,使得2k1是合数,对于这样的k,(k1)2 不能表示为a2p的形式,事实上,若(k 1)2= a2p,则(k 1 a)( k 1 a) = p,得k 1 a = 1,k 1 a = p,即p = 2k 1,此与p为素数矛盾。 第一章习题二 1. 验证当n =0,1,2,… ,11时,12|f(n)。 2.写a = 3q1r1,b = 3q2r2,r1, r2 = 0, 1或2,由3a2b2 = 3Q r12r22知r1 = r2 = 0,即3a且3b。 3.记n=10q+r, (r=0,1,…,9),则n k+4-n k被10除的余数和r k+4-r k=r k(r4-1)被10 除的余数相同。对r=0,1,…,9进行验证即可。 4. 对于任何整数n,m,等式n2 (n 1)2 = m2 2的左边被4除的余数为1,而右边被4除的余数为2或3,故它不可能成立。 5 因a4 3a2 9 = (a2 3a 3)( a2 3a 3),当a = 1,2时,a2 3a 3 = 1,a4 3a2 9 = a2 3a 3 = 7,13,a4 3a2 9是素数;当a 3时,a2 3a 3 > 1,a2 3a 3 > 1,a4 3a2 9是合数。 6. 设给定的n个整数为a1, a2, , a n,作 s1 = a1,s2 = a1a2,,s n = a1a2a n, 如果s i中有一个被n整除,则结论已真,否则存在s i,s j,i < j,使得s i与s j 被n除的余数相等,于是n s j s i = a i + 1a j。 《初等数论》期末练习二 一、单项选择题 1、=),0(b ( ). A b B b - C b D 0 2、如果1),(=b a ,则),(b a ab +=( ). A a B b C 1 D b a + 3、小于30的素数的个数( ). A 10 B 9 C 8 D 7 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C (mod )ac bc m ≡/ D b a ≠ 5、不定方程210231525=+y x ( ). A 有解 B 无解 C 有正数解 D 有负数解 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 7、如果a b ,b a ,则( ). A b a = B b a -= C b a ≥ D b a ±= 8、公因数是最大公因数的( ). A 因数 B 倍数 C 相等 D 不确定 9、大于20且小于40的素数有( ). A 4个 B 5个 C 2个 D 3个 10、模7的最小非负完全剩余系是( ). A -3,-2,-1,0,1,2,3 B -6,-5,-4,-3,-2,-1 C 1,2,3,4,5,6 D 0,1,2,3,4,5,6 11、因为( ),所以不定方程71512=+y x 没有解. A [12,15]不整除7 B (12,15)不整除7 C 7不整除(12,15) D 7不整除[12,15] 12、同余式)593(mod 4382≡x ( ). A 有解 B 无解 C 无法确定 D 有无限个解 二、填空题 1、有理数 b a ,0,(,)1a b a b <<=,能写成循环小数的条件是( ). 2、同余式)45(mod 01512≡+x 有解,而且解的个数为( ). 3、不大于545而为13的倍数的正整数的个数为( ). 4、设n 是一正整数,Euler 函数)(n ?表示所有( )n ,而且与n ( )的正整数的个数. 5、设b a ,整数,则),(b a ( )=ab . 6、一个整数能被3整除的充分必要条件是它的( )数码的和能被3整除. 7、+=][x x ( ). 8、同余式)321(mod 75111≡x 有解,而且解的个数( ). 9、在176与545之间有( )是17的倍数. 作业次数:学号姓名作业成绩 第0章序言及预备知识 第一节序言(1) 1、数论人物、资料查询:(每人物写600字左右的简介) (1)华罗庚 2、理论计算与证明: (1 是无理数。 (2)Show that there are infinitely many Ulam numbers 3、用Mathematica 数学软件实现 A Ulam number is a member of an which was devised by and published in in 1964. The standard Ulam sequence (the (1, 2-Ulam sequence starts with U 1=1 and U 2=2 being the first two Ulam numbers. Then for n > 2, U n is defined to be the smallest that is the sum of two distinct earlier terms in exactly one way 。 By the definition, 3=1+2 is an Ulam number; and 4=1+3 is an Ulam number (The sum 4=2+2 doesn't count because the previous terms must be distinct. The integer 5 is not an Ulam number because 5=1+4=2+3. The first few terms are 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 初等数论考试试卷 一、 单项选择题:(1分/题×20题=20分) 1.设x 为实数,[]x 为x 的整数部分,则( A ) A.[][]1x x x ≤<+; B.[][]1x x x <≤+; C.[][]1x x x ≤≤+; D.[][]1x x x <<+. 2.下列命题中不正确的是( B ) A.整数12,, ,n a a a 的公因数中最大的称为最大公因数; < B.整数12,,,n a a a 的公倍数中最小的称为最小公倍数 【有最小的吗】 C.整数a 与它的绝对值有相同的倍数 D.整数a 与它的绝对值有相同的约数 3.设二元一次不定方程ax by c +=(其中,,a b c 是整数,且,a b 不全为零)有一整数解 ()00,,,x y d a b =,则此方程的一切解可表为( C ) A.00,,0,1,2,;a b x x t y y t t d d =- =+=±± B.00,,0,1,2, ;a b x x t y y t t d d =+=-=±± C.00,,0,1,2, ;b a x x t y y t t d d =+=-=±± D.00,,0,1,2, ;b a x x t y y t t d d =-=-=±± ( 4.下列各组数中不构成勾股数的是( D ) A.5,12,13; B.7,24,25; C.3,4,5; D.8,16,17 5.下列推导中不正确的是( D ) A.()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ B.()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ C.()()111212mod mod ;a b m a a b a m ≡?≡ 第一章 §1 1 证明:n a a a ,,21 都是m 的倍数。 ∴存在n 个整数n p p p ,,21使 n n n m p a m p a m p a ===,,,222111 又n q q q ,,,21 是任意n 个整数 m p q p q q p a q a q a q n n n n )(22112211+++=+++∴ 即n n a q a q a q +++ 2211是m 的整数 2 证: )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n )1()1()2)(1(/6+-+++∴n n n n n n 从而可知 )12)(1(/6++n n n 3 证: b a , 不全为0 ∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数,因而 有形如by ax +的最小整数00by ax + Z y x ∈?,,由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+ 则 S b q y y a q x x r ∈-+-=)()(00,由00by ax +是S 中的最小整数知0=r by ax by ax ++∴/00 下证8P 第二题 by ax by ax ++/00 (y x ,为任意整数) b by ax a by ax /,/0000++∴ ).,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 00/),(by ax b a +∴ 故),(00b a by ax =+ 4 证:作序列 ,2 3, ,2 , 0,2 ,,2 3,b b b b b b - -- 则a 必在此序列的某两项之间 100个著名初等数学问题 https://www.wendangku.net/doc/c89859887.html,/xyp 2003-10-26 数学园地 第01题阿基米德分牛问题Archimedes' Problema Bovinum 太阳神有一牛群,由白、黑、花、棕四种颜色的公、母牛组成. 在公牛中,白牛数多于棕牛数,多出之数相当于黑牛数的1/2+1/3;黑牛数多于棕牛数,多出之数相当于花牛数的1/4+1/5;花牛数多于棕牛数,多出之数相当于白牛数的1/6+1/7. 在母牛中,白牛数是全体黑牛数的1/3+1/4;黑牛数是全体花牛数1/4+1/5;花牛数是全体棕牛数的1/5+1/6;棕牛数是全体白牛数的1/6+1/7. 问这牛群是怎样组成的? 第02题德·梅齐里亚克的法码问题The Weight Problem of Bachet de Meziriac 一位商人有一个40磅的砝码,由于跌落在地而碎成4块.后来,称得每块碎片的重量都是整磅数,而且可以用这4块来称从1至40磅之间的任意整数磅的重物. 问这4块砝码碎片各重多少? 第03题牛顿的草地与母牛问题Newton's Problem of the Fields and Cows a头母牛将b块地上的牧草在c天内吃完了; a'头母牛将b'块地上的牧草在c'天内吃完了; a"头母牛将b"块地上的牧草在c"天内吃完了; 求出从a到c"9个数量之间的关系? 第04题贝韦克的七个7的问题Berwick's Problem of the Seven Sevens 在下面除法例题中,被除数被除数除尽: * * 7 * * * * * * * ÷ * * * * 7 * = * * 7 * * * * * * * * * * * * * 7 * * * * * * * * * 7 * * * * * 7 * * * * * * * * * * * * * * * 7 * * * * * * * * * * * * * * 用星号(*)标出的那些数位上的数字偶然被擦掉了,那些不见了的是些什么数字呢? 第05题柯克曼的女学生问题Kirkman's Schoolgirl Problem 初等数论试卷和答案 初等数论考试试卷1 一、单项选择题(每题3分,共18分) 1、如果a b ,b a ,则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3,n 5,则15( )n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数( ). A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分,共18分) 1、素数写成两个平方数和的方法是( ). 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为 ( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ). 试卷1答案 一、单项选择题(每题3分,共18分) 1、D. 2、A 3、C 4、A 5、A 6、B 二、填空题(每题3分,共18分) 1、素数写成两个平方数和的方法是(唯一的). 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是(b m a ),(). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ][b a ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( 与p 互素 ). 5、b a ,的公倍数是它们最小公倍数的( 倍数 ). 6、如果b a ,是两个正整数,则存在( 唯一 )整数r q ,,使r bq a +=,b r ≤0. 三、计算题(每题8分,共32分) 1、 求[136,221,391]=?(8分) 解 [136,221,391] =[[136,221],391] =[391,17221136?] =[1768,391] ------------(4分) = 17391 1768? 第一节 整数的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 |(传递性质); 初等数论考试试卷1 一、单项选择题(每题3分,共18分) 1、如果a b ,b a ,则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3,n 5,则15( )n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数( ). A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分,共18分) 1、素数写成两个平方数和的方法是( ). 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ). 6、如果b a ,是两个正整数,则存在( )整数r q ,,使r bq a +=,b r π≤0. 三、计算题(每题8分,共32分) 1、求[136,221,391]=? 2、求解不定方程144219=+y x . 3、解同余式)45(mod 01512≡+x . 4、求? ?? ??563429,其中563是素数. (8分) 四、证明题(第1小题10分,第2小题11分,第3小题11分,共32分) 第一节整数的p进位制及其应用 正整数有无穷多个,为了用有限个数字符号表示出无限多个正整数,人们发明了进位制,这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系,近几年来,国内与国际竞赛中关于“整数的进位制”有较多的体现,比如处理数字问题、处理整除问题及处理数列问题等等。在本节,我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m位的正整数A,其各位上的数字分别记为,则此数可以简记为:(其中)。 由于我们所研究的整数通常是十进制的,因此A可以表示成10的次多项式,即,其中 且,像这种10的多项式表示的数常常简记为。在我们的日常生活中,通常将下标10省略不写,并且连括号也不用,记作,以后我们所讲述的数字,若没有指明记数式的基,我们都认为它是十进制的数字。但是随着计算机的普及,整数的表示除了用十进制外,还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣,究其原因,主要是二进制只使用0与1这两种数学符号,可以分别表示两种对立状态、或对立的性质、或对立的判断,所以二进制除了是一种记数方法以外,它还是一种十分有效的数学工具,可以用来解决许多数学问题。 为了具备一般性,我们给出正整数A的p进制表示: ,其中且。而仍然为十进制数字,简记为。 第二节整数的性质及其应用(1) 基础知识 整数的性质有很多,这里我们着重讨论整数的整除性、整数的奇偶性,质数与合数、完全平方数及整数的尾数等几个方面的应用。 1.整除的概念及其性质 在高中数学竞赛中如果不加特殊说明,我们所涉及的数都是整数,所采用的字母也表示整数。 定义:设是给定的数,,若存在整数,使得则称整除,记作,并称是的一个约数(因子),称是的一个倍数,如果不存在上述,则称不能整除记作。 《初等数论》A/B 模拟练习题参考答案 1、(15分)设()f x 是整系数多项式,且(1),(2),,()f f f m 都不能被m 整除,证 明方程()0f x =没有整数解。 证明:对任意整数x ,(mod ),1x r m r m ≡≤≤,利用同余可加性和同余可乘性得 ()()(mod ),1f x f r m r m ≡≤≤,因为(1),(2), ,()f f f m 都不能被m 整除,所以 ()0f x ≠,即()0f x =没有整数解 2、(15分)若00ax by +是形如ax by +(,x y 是任意整数,,a b 是两个不全为零的整数)的数中的最小正数,则()()00ax by ax by ++,其中,x y 是任何整数 证明:由题意可知,,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 ++ 由于,x y 为任意整数,则可知0000|,|ax by a ax by b ++ 从而有00|(,).ax by a b +又有(,)|a b a ,(,)|a b b 得证00(,)|a b ax by +,故00(,)ax by a b +=. 3、(10分)若(mod )a b c m +≡,求证(mod )a c b m ≡- 证明:由同余可加性,且(mod )a b c m +≡,从而得 ()()()(mod )c b c b a b b a m -≡+-≡++-≡,得证. 问题一:数学教育专业分为专业基础课:高等代数,数学分析,空间解析几何以及专业课:实变函数论,点集拓扑,复变函数论,微分几何,概率与数理统计,数学建模,初等数论,数学教学论。数学主要的学科首要产生于商业上计算的需要、了解数与数之间的关系、测量土地及预测天文事件。这四种需要大致地与数量、结构、空间及变化(即算术、代数、几何及分析)等数学上广泛的领域相关连著。除了上述主要的关注之外,亦有用来探索由数学核心至其他领域上之间的连结的子领域:至逻辑、至集合论(基础)、至不同科学的经验上的数学(应用数学)、及较近代的至不确定性的严格学习。 一、李永乐:李永乐老师毕业于北京大学数学系,后来在清华大学数学系任教, 他还是前二李全书的代数执笔者,李永乐全书和660题的主编,可以说是考研数学界的权威代表。他的研究方向是线性代数。 二、汤家凤:汤老师是南京大学数学系博士,南京工业大学副教授。他的研究方 向为高等代数。 三、李林:李林老师毕业于北师大数学系,大连理工大学数学科学学院数学研究 所教师,职称为讲师,研究方向为常微分方程。 四、武忠祥:西安交通大学数学系教授,从事高等数学教学和考研辅导23年, 国家高等数学试题库骨干专家。 五、王式安:王式安本人毕业于复旦大学数学系,后来任教于北京理工大学。王 式安老师是前考研命题组的老师,主要是讲概率。 六、方复全:首都师范大学特聘教授,教育部长江学者特聘教授。主要研究方向 为微分几何、微分拓扑学。 七、曹一鸣:北京师范大学数学学科学院教授,博士生导师,贵州师范大学特聘 教授。主要从事数学课程与教学、数学史与数学教育研究。 八、戎小春:首都师范大学数学系硕士毕业,后留校任教。现为美国Rutgers大 学教授。他的研究方向主要为微分几何理论。 九、王贵君:天津师范大学数学学院教授。研究方向:模糊测度与积分,模糊神 经网络,模糊系统逼近。 十、汪晓勤:中国科学院科学技术史博士专业,获哲学博士学位。现任华东师范 大学数学系教授,学科教育(数学)专业博士生导师。研究方向为数学史与数学教育。 问题二:数论的发展史及现状 数论早期称为算术。到20世纪初,才开始使用数论的名称,而算术一词则表示“基本运算”,不过在20世纪的后半,有部份数学家仍会用“算术”一词来表示数论。1952年时数学家Harold Davenport仍用“高等算术”一词来表示数论,戈弗雷·哈罗德·哈代和爱德华·梅特兰·赖特在1938年写《数论介绍》简介时曾提到“我们曾考虑过将书名改为《算术介绍》,某方面而言是更合适的书名,但也容易让读者误会其中的内容”。古希腊数学家——欧几里得 公元前300年,古希腊数学家欧几里德证明了有无穷多个素数,公元前250年古希腊数学家埃拉托塞尼发明了一种寻找素数的埃拉托斯特尼筛法。寻找一个表示所有素数的素数通项公式,或者叫素数普遍公式,是古典数论最主要的问题之一。数论从早期到中期跨越了1000—2000年,在接近2000年时间,数论几乎是空白。中期主要指15-16世纪到19世纪,是由费马,梅森、欧拉、高斯、勒让德、黎曼、希尔伯特、Heegner等人发展的。4月浙江自考初等数论试题及答案解析试卷及答案解析真题
初等数论试卷模拟试题和答案
竞赛数学中的初等数论(精华版)
“4-6 初等数论初步”简介
初等数论 1 习题参考答案
(完整word版)初等数论练习题一(含答案)
初等数论练习册汇总
0初等数论试卷及答案
初等数论第2版习题答案
100个著名初等数论问题
初等数论试卷和答案
初等数论知识点汇总
自考初等数论试题及答案
初等数论知识点汇总
初等数论
初等数论