2002
题二最大公约数与最小公倍数问题(20分)
[问题描述]
输入二个正整数x0,y0(2≤x0<100000,2≤y0≤1000000),求出满足下列条件的P,Q的个数:
条件:1. P,Q是正整数
2. 要求P,Q以x0为最大公约数,以y0为最小公倍数。
试求:满足条件的所有可能的两个正整数的个数。
[样例]
输入:x0=3 y0=60
输出:4
说明:(不用输出)此时的 P Q 分别为:
3 60
15 12
12 15
60 3
所以:满足条件的所有可能的两个正整数的个数共4种。
2012
1.质因数分解
(prime.cpp/c/pas)
【问题描述】
已知正整数n是两个不同的质数的乘积,试求出较大的那个质数。
【输入】
输入文件名为prime.in。
输入只有一行,包含一个正整数n。
【输出】
输出文件名为prime.out。
输出只有一行,包含一个正整数p,即较大的那个质数。
【输入输出样例】
prime.in prime.out
21 7
【数据范围】
对于60%的数据,6 ≤ n ≤ 1000。
对于100%的数据,6 ≤ n ≤ 2*109。
2007年
4.Hanoi双塔问题
hanoi.pas/c/cpp
【问题描述】
给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将这些国盘移到C柱上,在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘;
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序;
任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。
【输入】
输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。
【输出】
输出文件hanoi.out仅一行,包含一个正整数,为完成上述任务所需的最少移动次数An。
【限制】
对于50%的数据, 1<=n<=25
对于100% 数据, 1<=n<=200
【提示】
设法建立An与An-1的递推关系式。
2006年
4.数列
(sequence.pas/c/cpp)
【问题描述】
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是:
1,3,4,9,10,12,13,…
(该序列实际上就是:30,31,30+31,32,30+32,31+32,30+31+32,…)
请你求出这个序列的第N项的值(用10进制数表示)。
例如,对于k=3,N=100,正确答案应该是981。
【输入文件】
输入文件sequence.in 只有1行,为2个正整数,用一个空格隔开:
k N
(k、N的含义与上述的问题描述一致,且3≤k≤15,10≤N≤1000)。
【输出文件】
输出文件sequence.out 为计算结果,是一个正整数(在所有的测试数据中,结果均不超过2.1*109)。(整数前不要有空格和其他符号)。
【输入样例】
3 100
【输出样例】
981
2005年noip普及组
循环
(circle.pas/c/cpp)
【问题描述】
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数次幂产生了兴趣。
众所周知,2的正整数次幂最后一位数总是不断的在重复2,4,8,6,2,4,8,6……我们说2的正整数次幂最后一位的循环长度是4(实际上4的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:
循环
循环长度
2
2、4、8、6
4
3
3、9、7、1
4
4
4、6
2
5
5
1
6
6
1
7
7、9、3、1
4
8
8、4、2、6
4
9
9、1
2
这时乐乐的问题就出来了:是不是只有最后一位才有这样的循环呢?对于一个整数n的正
整数次幂来说,它的后k位是否会发生循环?如果循环的话,循环长度是多少呢?
注意:
1.如果n的某个正整数次幂的位数不足k,那么不足的高位看做是0。
2.如果循环长度是L,那么说明对于任意的正整数a,n的a次幂和a + L次幂的最后k 位都相同。
【输入文件】
输入文件circle.in只有一行,包含两个整数n(1 <= n < 10100)和k(1 <= k <= 100),n和k之间用一个空格隔开,表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】
输出文件circle.out包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出-1。
【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据,k <= 4;
对于全部的数据,k <= 100。
2009年noip普及组复赛
3.细胞分裂
(cell.pas/c/cpp)
【问题描述】
Hanks 博士是BT (Bio-Tech,生物技术) 领域的知名专家。现在,他正在为一个细胞实
验做准备工作:培养细胞样本。
Hanks 博士手里现在有N 种细胞,编号从1~N,一个第i 种细胞经过1 秒钟可以分裂为Si 个同种细胞(Si 为正整数)。现在他需要选取某种细胞的一个放进培养皿,让其自由分裂,进行培养。一段时间以后,再把培养皿中的所有细胞平均分入M 个试管,形成M 份样本,用于实验。Hanks 博士的试管数M 很大,普通的计算机的基本数据类型无法存储这样大的M 值,但万幸的是,M 总可以表示为m1 的m2 次方,即2
1
M = m m ,其中m1,m2 均为基本
数据类型可以存储的正整数。
注意,整个实验过程中不允许分割单个细胞,比如某个时刻若培养皿中有4 个细胞,Hanks 博士可以把它们分入2 个试管,每试管内2 个,然后开始实验。但如果培养皿中有5
个细胞,博士就无法将它们均分入 2 个试管。此时,博士就只能等待一段时间,让细胞们继
续分裂,使得其个数可以均分,或是干脆改换另一种细胞培养。
为了能让实验尽早开始,Hanks 博士在选定一种细胞开始培养后,总是在得到的细胞“刚好可以平均分入M 个试管”时停止细胞培养并开始实验。现在博士希望知道,选择哪种细胞培养,可以使得实验的开始时间最早。
【输入】
输入文件名为cell.in,共有三行。
第一行有一个正整数N,代表细胞种数。
第二行有两个正整数m1,m2,以一个空格隔开,2
1
m m 即表示试管的总数M。
第三行有N 个正整数,第i 个数Si 表示第i 种细胞经过1 秒钟可以分裂成同种细胞的个数。
【输出】
输出文件cell.out 共一行,为一个整数,表示从开始培养细胞到实验能够开始所经过的
最少时间(单位为秒)。
如果无论Hanks 博士选择哪种细胞都不能满足要求,则输出整数-1。
【输入输出样例1】
cell.in cell.out
1
2 1
3
-1
【输入输出样例1 说明】
经过1 秒钟,细胞分裂成3 个,经过2 秒钟,细胞分裂成9 个,……,可以看出无论怎么分
裂,细胞的个数都是奇数,因此永远不能分入2 个试管。
2009-11-21 18:58 回复
59.33.120.* 5楼
【输入输出样例2】
cell.in cell.out
2
24 1
30 12
2
【输入输出样例2 说明】
第1 种细胞最早在3 秒后才能均分入24 个试管,而第2 种最早在2 秒后就可以均分(每试管144/(241)=6 个)。故实验最早可以在2 秒后开始。
【数据范围】
对于50%的数据,有2
1
m m ≤30000。
对于所有的数据,有1 ≤N≤10000,1 ≤m1 ≤30000,1 ≤m2 ≤10000,1 ≤Si ≤2,000,000,000。
几何学基础简介 Lex Li 几何原本简介 古希腊大数学家欧几里德是与他的巨著——《几何原本》一起名垂千古的。这本书是世界上最著名、最完整而且流传最广的数学著作,也是欧几里德最有价值的一部著作。欧几里德把人们公认的一些事实列成定义和公理,以形式逻辑的方法,用这些定义和公理来研究各种几何图形的性质,从而建立了一套从公理、定义出发,论证命题得到定理得几何学论证方法,形成了一个严密的逻辑体系——几何学。而这本书,也就成了欧式几何的奠基之作。 作为基础的五条公理和公设 五条公理 1.等于同量的量彼此相等; 2.等量加等量,其和相等; 3.等量减等量,其差相等; 4.彼此能重合的物体是全等的; 5.整体大于部分。 五条公设 1.过两点能作且只能作一直线; 2.线段(有限直线)可以无限地延长; 3.以任一点为圆心,任意长为半径,可作一圆; 4.凡是直角都相等; 5.同平面内一条直线和另外两条直线相交,若在直线同侧的两个内角之和小于180°,则这两条直线经无限延长后在这一侧一定相交。 《几何原本》的主要内容 欧几里得的《几何原本》共有十三卷。 目录 第一卷几何基础 第二卷几何与代数 第三卷圆与角 第四卷圆与正多边形 第五卷比例
第六卷相似 第七卷数论(一) 第八卷数论(二) 第九卷数论(三) 第十卷无理量 第十一卷立体几何 第十二卷立体的测量 第十三卷建正多面体 各卷简介 第一卷:几何基础。重点内容有三角形全等的条件,三角形边和角的大小关系,平行线理论,三角形和多角形等积(面积相等)的条件,第一卷最后两个命题是毕达哥拉斯定理的正逆定理; 第二卷:几何与代数。讲如何把三角形变成等积的正方形;其中12、13命题相当于余弦定理。 第三卷:本卷阐述圆,弦,切线,割线,圆心角,圆周角的一些定理。 第四卷:讨论圆内接和外切多边形的做法和性质; 第五卷:讨论比例理论,多数是继承自欧多克斯的比例理论,被认为是"最重要的数学杰作之一" 第六卷:讲相似多边形理论,并以此阐述了比例的性质。 第五、第七、第八、第九、第十卷:讲述比例和算术的理论;第十卷是篇幅最大的一卷,主要讨论无理量(与给定的量不可通约的量),其中第一命题是极限思想的雏形。 第十一卷、十二、十三卷:最后讲述立体几何的内容. 从这些内容可以看出,目前属于中学课程里的初等几何的主要内容已经完全包含在《几何原本》里了。因此长期以来,人们都认为《几何原本》是两千多年来传播几何知识的标准教科书。 《几何原本》的意义和影响 在几何学发展的历史中,欧几里得的《几何原本》起了重大的历史作用。这种作用归结到一点,就是提出了几何学的“根据”和它的逻辑结构的问题。在他写的《几何原本》中,就是用逻辑的链子由此及彼的展开全部几何学,这项工作,前人未曾作到。《几何原本》的诞生,标志着几何学已成为一个有着比较严密的理论系统和科学方法的学科。 论证方法上的影响 关于几何论证的方法,欧几里得提出了分析法、综合法和归谬法。所谓分析法就是先假设所要求的已经得到了,分析这时候成立的条件,由此达到证明的步骤;综合法是从以前证明过的事实开始,逐步的导出要证明的事项;归谬法是在保留命题的假设下,否定结论,从结论的反面出发,由此导出和已证明过的事实相矛盾或和已知条件相矛盾的结果,从而证实原来命题的结论是正确的,也称作反证法。
揭阳职业技术学院 毕业论文(设计) 题目:浅谈同余定理及其应用 学生姓名黄指导教师某某某 系(部)师范教育系专业数学教育 班级 999 班学号 11211211 提交日期200 年月日答辩日期 200 年月日 200 年月日
浅谈同余定理及其应用 摘要 初等数论是研究数的规律,特别是整数性质的数学分支。它以算术方法为主要研究方法,在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数。同余理论是初等数论中的重要内容之一,其性质及应用研究已引起许多学者的关注。本文归纳总结了同余的若干性质,结合实例,探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。体现了用同余性质解决问题的简洁性。 关键词:同余整除余式方程
绪论 初等数论是研究整数性质的一门学科,它是数学中最古老的分支之一,内容极为丰富,曾被数学家说成是数学的皇后。同余问题在当今中小学乃至大学的数学教学中都有涉及,它作为初等数论的核心内容之一,具有很强的应用价值,很多数学问题都要借助同余理论来解决。同余的应用问题分为很多种类型,每种类型的题目又有一定的解题技巧。掌握了这些题型的技巧,可以提高大家解决问题的能力。本文基于对同余理论的理解,将应用同余理论解决的问题具体整理分类,从中分析出一些借助同余理论解题的技巧与规律。现在初等数论中关于同余的内容主要包括:同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。 到目前为止,古今中外很多学者与数学家,对同余的应用问题都有了一定的研究。在中国,早在宋代,大数学家秦九韶所著的《数书九章》中就记载了求解同余方程的“大衍求一术”。还有,著名的古代数学著作《孙子算经》中也记载能解决“物不知其数”问题的孙子定理,也被称作“中国剩余定理”。以及“韩信点兵”问题的研究,都为解决一次同余方程和同余方程组的问题带来了便利。在西方,除了高斯引入同余的概念之外,欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。希望通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。以便,今后大家在探究同余理论时,能对同余应用问题的类型和解决技巧有一个清晰的认识和理解,更好的解决相关问题。 1 相关性质定理[1] 性质1同余是一种等价关系,即有: (1)反身性 a≡a(mod m). (2)对称性若a≡b(mod m),则b≡a(mod m). (3)传递性若a≡b(mod m), b≡c(mod m), 则a≡c(mod m). 性质2同余式可以相加减,即 若 a≡b(mod m),c≡d(mod m),则 (1) a+c≡b+d(mod m). (2) a-c≡b-d(mod m). 性质3同余式可以相乘,即有:
数论综合练习 五年级奥数:数的整除性试题 一、填空题 1.、四位数“3AA1”是9的倍数,那么A=_____. 2、在“25□79这个数的□内填上一个数字,使这个数能被11整除,方格内应填_____. 3、能同时被2、3、5整除的最大三位数是_____. 4、能同时被2、 5、7整除的最大五位数是_____. 5、1至100以内所有不能被3整除的数的和是_____. 6、所有能被3整除的两位数的和是______. 7、已知一个五位数□691□能被55整除,所有符合题意的五位数是_____. 8、如果六位数1992□□能被105整除,那么它的最后两位数是_____. 9、42□28□是99的倍数,这个数除以99所得的商是_____. 10、有四个数921438、76186、750235、2660161,其中只有_____是完全平方数. 二、解答题 1、在1992后面补上三个数字,组成一个七位数,使它们分别能被 2、 3、5、11整除,这个七位数最小值是多少? 2、在下面的数中,哪些能被4整除?哪些能被8整除?哪些能被9整除? 234,789,7756,8865,3728,8064。 3、被除数,除数,商与余数之和是2143,已知商是33,余数是52,求被除数和除数. 4、(美国长岛小学数学竞赛)写出所有的除109后余数为4的两位数. 5、1013除以一个两位数,余数是12.求出符合条件的所有的两位数. 6、把一个两位数的十位和个位上的数字加以交换,得到一个新的两位数,如果原来的
两位数和交换后的两位数的差是45,试求这样的两位数中最大的是多少? 【质数、合数】和【约数和倍数】和【余数】 7、某个质数加上6或者前去6得到的数仍然是质数,在50以内你能找出几个这样的质数?把它们写出来。 8、甲、乙、丙代表互不相同的3个正整数,并且满足:甲×甲=乙+乙=丙×135.那么甲最小为多少? 9、480有多少个约数? 10、试求出一个最小的整数,它正好有12个约数。 11、四个连续奇数的最小公倍数是6435,这四个数中最大的一个是多少? 12、有一类三位数,它们除以6余5,除以8余5,除以9余5,请问这些三位数中,最小的一个是多少? 13、两个数的积为126,最大公约数为3,则这两个数的最小公倍数是多少? 14、将自然数a和b分解质因数,得到a=2×5×7×m,b=3×5×m,如果a与b的最小公倍数是2730,那么m为多少? 15、一个四位数是一个完全平方数,并且前两位数字相等,后两位数字相等,求这个四位数。 16、在555555的约数中,最大的三位数是多少?
整除 一、常见数字的整除判定方法 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.余数的减法定理
关于数论函数方程() ()2 S n n ?= 李宋宋 (安徽师范大学 安徽芜湖 241000) 摘要:对于任给的正整数n ,()n ?和()S n 分别是Euler 函数和Smarandache 函数,本文根据初等数论的理论以及分类讨论的方法,对数论方程()()2S n n ?=的解进行了讨论并给出了解的表达式以及解的判别条件。 关键词:Euler 函数;Smarandache 函数;阶乘;费马数;方程 On the Arithmetic Functional Equation ()()2S n n ?= Abstract: For any given positive integer n, ()n ? and ()S n are Euler function and Smarandache function respectively, according to the elementary number theory and the method of classification discussion, this article has discussed the arithmetic functional equation ()()2S n n ?=and finally given the expression and the discriminants of solution. Keywords: Euler function ;Smarandache function ;factorial ;Fermat number ;equations 1 引言 对于任意正整数n ,设()n ?和()S n 分别是Euler 函数和Smarandache 函数.其中,()n ?表示不大于n 且与n 互素的正整数的个数;()S n 定义为最小正整数m ,使得 |!n m ,即:!}|,{()min m n m m Z S n +=∈. ()S n 的各种性质是数论及其应用领域中一 个十分引人关注的研究课题[1] .关于这两个 函数之间关系的讨论,一直也是很多学者研 究的对象[2]-[4] , 例如文献[2]中讨论了数论方程()()t n S n ?=的相关性质和求解过程,并且在很多学者努力下,此类型方程的求解结果已经很完善;文献[4]中讨论并给出了方程()()2n n ω?=的解.在诸多文章和结果的启发下,本文提出了一类数论方程 ()()2S n n ?=的求解问题,并通过分类讨论的 方法,在现有的五个费马素数的基础上得到 了此类方程解的表达式和部分解的判别条件.现将本文的主要结果列在下面: 定理 对于任给的正整数n ,()n ?和 ()S n 分别是Euler 函数和Smarandache 函 数,若n 为数论方程() ()2 S n n ?=的解,则n 的标准分解式为: 1 2m s n p p =, 1(3,15)s p p s ≤<<≤≤为素数,其中 22 1k i i p =+,{0,1,2,3,4},(1,,)i k i s ∈=, m 满足: (1)当1s =时,1121k m p =-+, 1{23,4}k ∈,,或者m 满足不等式组:
硕士研究生《应用密码学》课程论文浅谈数论在密码学上的应用 指导教师:王玉柱 专业:计算机应用技术 学号:1010706 姓名:杨玖宏 日期:2011年6月30日
浅谈数论在密码学上的应用 摘要:众所周知.数论是数学中最古老、最纯粹、最优美的一个学科.不过鲜为人知的还是,数论同时也是一门应用性极强的应用数学学科.著名国际数学大师陈省身教授早在1992年精辟地指出:“数学中我愿意把数论看作应用数学。”我想数学中有两个很重要的数学部门,一个是数论,另一个是理论物理。在本文中我将先扼要介绍下数论中的一些基本概念、几个主要难题,紧接着我们要介绍数论在现代密码学与计算机科学中的应用。 关键词:数论;计算数论;密码学; 1 引言 随着现代计算机网络通信的广泛使用,传统密码受到很大挑战,它们已经不能完全适应网络环境下使用密码的需求。于是在上世纪七十年代,提出了公钥密码的概念,并且利用数论方法设计了第一个公钥密码体制(RSA公钥密码),经过二十多年的研究,RSA已得到了广泛的应用。在RSA密码体制中,使用了一个大整数(目前通常取这个数有1024比特长),它是两个素数的乘积,这个大整数是公开的,而它的两个素因子是保密的。如果有人能将这个大整数分解因子而得到它的两个素因子,就能破译这个密码体制,所以RSA的安全性是建立在大整数因子分解问题的基础之上的。这是一个经典的数论问题,RSA的提出大大推动了大整数因子分解算法的研究。在上世纪八十年代,人们又提出了椭圆曲线公钥密码,它应用了更深刻的数论知识,它的安全性也得到了密码界的公认,现在也正逐步推向应用。公钥密码的出现,使数学在密码研究中发挥了更加核心的作用。 2 数论概述 数论,顾名思义,就是关于数的理论,数学,顾名思义,就是关于数的学问.高斯曾说过一句名言:“数学是科学的女王,而数论是数学的女王”。基础数论作为一门古老的数学学科,在很常时间内都属于一种纯数学,随着现代科技的发展,数论在整个科学中的应用非常重要[1]。数论中许多基本内容,如同余理论、中国剩余定理(CRT)、高次剩余理论等,在现代密码体制、密钥分配与管理、数字签名、身份认证等方面有重要的应用。 1 数论概述 1.1 整除理论 1)整除:设 a 和 b 是两个整数,且 b≠0,如果存在一个整数 q,使等式a=bq 成立,那么我们称 a 能被 b 整除或 b 整除 a,记作 b— a,其性质有: (1) 若 b | a,a ≠0,则 | b | ? | a | ; (2) 若 b | a,a | b,a ≠0,则 a=b 或 b=a; (3) 若 c | b,b | a, 则 c | a;(c≠0) (4) 若 b | a,则 cb | ca(c≠0); (5) 若 c | a,c | b,则 c | ma+nb,m,n∈Z(c≠0)。 2) 整除的基本定理:对于任意整数 a,b(b≠0)存在唯一的一对整数 q,r,
第一节 整数的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) 基础知识 整数的性质有很多,这里我们着重讨论整数的整除性、整数的奇偶性,质数与合数、完全平方数及整数的尾数等几个方面的应用。 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. 请看下面的例子: (1) 证明:对于同样的整数x 和y ,表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学竞 赛第一题) (2) ①设n Z ∈,证明213 1n -是168的倍数。 ②具有什么性质的自然数n ,能使123n ++++ 能整除123n ??? ?(1956年上海首届数学竞赛第一题) (3) 证明:3 231 122 n n n + +-对于任何正整数n 都是整数,且用3除时余2。(1956年北京、天津市首届数学竞赛第一题) (4) 证明:对任何自然数n ,分数 214 143 n n ++不可约简。(1956年首届国际数学奥林匹克竞赛第一题) (5) 令(,,,)a b g 和[,,,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数,试证: [][][][]()()()() 2 2 ,,,,,,,,,,a b c a b c a b b c c a a b b c c a =??(1972年美国首届奥林匹克数学竞赛第一题) 这些例子说明历来数论题在命题者心目中首当其冲。 2.再看以下统计数字: (1)世界上历史最悠久的匈牙利数学竞赛,从1894~1974年的222个试题中,数论题有41题,占18.5%。 (2)世界上规模最大、规格最高的IMO (国际数学奥林匹克竞赛)的前20届120道试题中有数论13题,占10.8% 。 这说明:数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内,那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题: (1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是( ) A 、 0 B 、1 C 、3 D 、无穷多 (2007全国初中联赛5) (2)已知,a b 都是正整数,试问关于x 的方程()2 1 02 x abx a b -++=是否有两个整数解? 如果有,请把它们求出来;如果没有,请给出证明。 (2007全国初中联赛12)
浅谈数学教学中的哲学思想 数学是整个自然科学发展的前提条件和存在的依据,又是自然科学和社会科学发展的基础。数学也是一门工具性学科,在数学教学中含有丰富的哲学思想,如辩证法,物质和意识的第一性问题,量变到质变的问题,矛盾双方的依存问题,真理的相对性和绝对性问题等等。因此,本文从五个方面谈数学教学中的哲学思想。 一、物质和意识谁是第一性的哲学思想 马克思主义哲学认为,物质第一性,意识第二性,物质决定意识。 世界的本质是物质。人的意识是客观存在的一种反映。如无理数的产生就是人对客观世界的认识的一个飞跃。古希腊时期,著名的毕达哥拉斯学派倡导“唯数论”,即任何量均可以由两个整数之比来表示。但到公元前五世纪末,希腊数学家们却发现有些量例外。在平面几何中寻找正方形的对角线与边的公共度量,其结果与“唯数论”产生了矛盾。因此发生了第一次数学“危机”,其主要原因是认识上的局限性、片面性和绝对化。人们对“唯数论”产生了怀疑。数学家们后来又发现了更多的不能用两个整数之比表示的数,把它们统称为无理数。能用两个整数之比表示的数叫作有理
数。这说明物质不依赖人的意识而客观存在。物质决定一切,意识反映物质。 二、量变到质变的哲学思想 在哲学中,把事物在数量和程度上的逐渐的、不显著的变化叫作量变。把事物显著的、根本性的变化叫作质变。在数学教学中也有这样的情况。如极限的教学中,每个加数都存在极限且每个加数的极限值都等于0,但的确不等于0,它的正确解法是 又如无理数的发现,它也是人的意识由量变到质变的产物,是人对客观事物的认识发生变化的产物。 三、真理的绝对性的哲学思想 真理是绝对的,但人对真理的反映是片面或存在局限的。意识是客观事物在人脑中的反映。这种反映有正确的,也有歪曲的,还有片面性或存在局限的。由此?a生了真理的相对性。如数学悖论的产生和数学“危机”的发生都是人对客观事物的反映的局限性所造成的。数学对客观事物的反映是真实可靠的。但人的意识总达不到完美无缺的状态。由此产生了三次数学“危机”。导致第一次数学“危机”的根本原因是认识上的片面性和绝对化。一方面未能正确认识“一切均可以归纳为整数之比”这一结论的局限性,由此把它看成是绝对的完善的真理。这样实际上就造成了一种片面的、僵化的概念。另一方面,不可通约量的发现,最终必将导致
小升初——数论 数论是考察学生数感、数字规律的观察能力的重点专题,这一讲我们将熟练运用已经学过的数论知识,解决数论问题。掌握代数式处理数论问题的方法。 1、 六位数□2004□能被99整除,这个六位数是多少? 2、 有一个六位数,前四位是2857,即2857□□,这六位数能被11和13整除,请你算出最后两位数。 3、 若四位数a a 89能被15整除,则a 代表的数字是什么? 4、 一个七位数c b a 9020是33的倍数,那么_______=++c b a 5、 在一个四位数的某位数字前添上一个小数点,再和原来的四位数相减,差的绝对值是1803.6,则原来的四位数是多少?
6、一个两位数除310,余数是37,求这样的两位数。 7、有一个整数,用它去除70、110、160所得到的3个余数和是50,这个整数是多 少? 8、两个整数相除商8,余16,并且被除数、除数、商及余数和是463.那么被除数是 多少? 311,那么这三个质数和是多少? 9、三个质数倒数和是 1001
10、有四个学生,他们的年龄恰好是一个比一个大1岁,而他们的年龄的乘积是5040,那么他们的年龄各是多少? 11、一个正整数与1470的积是一个完全平方数,那么这个数的最小值是多少? 12、求2520、14850、819的最大公因数和最小公倍数(用因数分解法) 13、现有4个自然数,他们的和是1111,如果要使这4个数的公因数尽可能大, 那么4个数的公因数最大是多少? 14、一个三位数正好等于它各位数字之和的18倍,这个三位自然数是多少? 15、六位数2003□□能被99整除,它的最后两位数是多少?
欧几里得算法 欧几里德算法又称辗转相除法,用于计算两个正整数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、定义1 设a ,b 是整数,b ≠ 0,如果存在整数c ,使得 a = bc 成立,则称a 被b 整除,a 是b 的倍数,b 是a 的约数(因数或除数),并且使用记号b ∣a ;如果不存在整数c 使得a = bc 成立,则称a 不被b 整除,记为b |/a . 注: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 ? b a ∣a . 证明:留作习题. 例1 设a 1, a 2, , a n 是整数,且 a 1 + a 2 + + a n = 0,a 1a 2 a n = n , 则4∣n . 解:如果2|/n , 则n , a 1, a 2, , a n 都是奇数. 于是a 1 + a 2 + + a n 是奇数个奇数之和,不可能等于零,这与题设矛盾,所以2∣n ,即在a 1, a 2, , a n 中至少有一个偶数. 如果只有一个偶数,不妨设为a 1,那么2|/a i (2 ≤ i ≤ n ). 此时有等式 a 2 + + a n = -a 1, 在上式中,左端是(n - 1)个奇数之和,右端是偶数,这是不可能的,因此,在a 1, a 2, , a n 中至少有两个偶数,即4∣n . 例2 若n 是奇数,则8∣n 2 - 1. 解:设n = 2k + 1,则 n 2 - 1= (2k + 1)2 - 1 = 4k (k + 1). 在k 和k + 1中有一个是偶数,所以8∣n 2 - 1.
数论与解析数论简史 王志伟200800090156 数学与应用数学 数学王子Gauss曾经说过:数学是科学的女王,而数论是数学的女王。Gauss在数学、物理、天文各方面都取得了非凡的成就,但他却始终对数论情有独钟。数论,以其纯粹的数学本质,常常被认为是最美的数学,数学的中心。 与其他数学分支,比如几何、分析不同,数论并非是源于实际需要而创立的一门学科,其起源很有可能是出自数字游戏和Pythagoras学派以数字为图腾的宗教文化。数论曾经被认为是数学家的游戏、最纯的数学学科、唯一不会有什么应用价值的分支。但是现在随着网络加密技术的发展,数论也找到了自己用武之地——密码学。前几年破解MD5码的王小云老师就是山大数论学派出身。而在其他理论中,数论也表现出了一些意想不到的价值。在量子理论中,Hermite算子是最基本的概念之一,它的思想起源就是19世纪Hermite为解决数论问题而创立的Hermite型。我们在代数中常见的理想、环等概念最开始是出自Dedekind的数论著作中。最近的一个例子,Grothendieck为解决Weil猜想而对代数几何进行了革命性的改造。此类例子还有很多,在此不一一列举。 在古代对数论贡献最大的当属古希腊人。最著名的一些成果大概就是Euclid在《几何原本》中提到的Euclid算法、素数无限多个,算数基本定理等内容,这些我们在初等数论中都可以见到。另一个对数论有重大贡献的古希腊人当属Diophantus,他探讨了很多不定方程,为纪念,我们现在就称这些方程为Diophantus方程,著名的费马大定理就是一个Diophantus 方程问题。当然,中国古代在数论方面也作出了一定的贡献:众所周知、大名鼎鼎的中国剩余定理,被数学界唯一承认的中国的定理。 在经过漫长的中世纪之后,数论进入了一个辉煌的发展时期。推动数论发展的第一个重要人物首推Fermat,一个在数论界享有崇高地位的法国律师、业余数学家。Wiles在1994年证明的Fermat's last theorem,即我们所说的费马大定理,就是Fermat所提出的一个猜想。另外,Fermat小定理,关于多角形数的猜想,Fermat数,Mersenne素数性质,Pell方程都有他的贡献,我们证明中常用的无穷递降法,就是费马在证明费马大定理在n=3时最先发明使用的,除了数论,他在其他方面也有一些突出贡献,比如解析几何、微积分。Fermat之后,另一个重要的人物是Euler,他对Fermat的一个猜想:Fermat数都是素数给出了反例,引进了在数论中一个非常重要的数论函数,即Euler函数,并发现了一个数论中非常重要的Euler 公式。另外,笔者在跟同学在参加大学生科技创新项目中研究整数分拆这个课题时,阅读了Geogre Andrew的《The theory of partitions》,有幸了解到Euler在数论中的整数分拆方面也做出了很大的贡献,提出了母函数法,利用幂级数来研究整数分拆,这导致圆法和指数和方法的产生。 。在Euler之后,两个法国人Lagrange、Legendre也在数论方面做出了重要贡献,比如我们熟悉的二次互反律,Euler和Legendre都曾提出猜想,而公式中的符号我们即称作Legendre符号。他们的贡献就不在此细述。而在数论史上做出贡献最大的,我想大多人会同意是Gauss,一个伟大的数
有关数论函数的一些问题 题目:有关数论函数的一些问题研究生:任荣珍 任课教师:杨海 学科专业:应用数学 学号:2014081034 学院:理学院 时间:2015年1月2日
有关数论函数的一些问题 数论函数是在数论这一门学科中提出的, 在介绍数论函数之前首先来说明有关数论的一些背景知识和数论这一门学科, 数论可以被定义为研究数的一门理论学科, 是数学的一个重要分支, 数论在研究数的方面有着悠久的历史, 它的发展源远流长, 早在远古时代人们就学会使用数字, 而数论在数学中有着很重要的位置, 就如数学家高斯所说”数学是科学-皇后, 而数论就是数学皇冠”. 数论这门学科最早时是从研究整数开始的, 因此叫做整数论, 随着整数论的进一步发展就把整数论叫做数论了[1], 数论在数学中就是研究数的规律, 它与几何学一样是数学中最古老的分支, 在数学中有着悠久的历史, 在现代基础数学研究中占有很重要的位置. 数论函数作为数论其中的一个分支对数学也起了很重要的作用,下面就来介绍一些有关数论函数的研究, 下面就来介绍一下有关数论函数()F n 的背景知识[2], 先介绍一些所需要的符号及定义: 对任意的正整数2n ≥, ()n ?是由满足如下条件的整数数组 12(,,...,)s a a a 所构成的集合: (1)2i a n ≤≤, 1,2,...,i s =; (2)若素数i p a , 则p n , 1,2,...,i s =; (3)2s ≥时, (,)1i j a a =, 1i j s ≤<≤. 定义()F n 为形如12...s a a a +++数的最大值, 其中12(,,...,)()s a a a n ∈? 设1 i k a i i n p ==∏为n 的标准分解式, 我们用()n k ω=表示n 的所有不同 素因子的个数.
“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课时
浅谈数学与哲学 哲学是是自然知识和社会知识的囊括和总结,是研究世界观的学问,是人类思维的结晶和提炼,它作为一种理论思维,在人类进步的漫长过程中,已经形成一系列的基本概念和范畴,构建了博大宽宏的理论体系.它与自然科学是辩证统一的而又有所区别的.它们的统一性在于,所研究的都是不依赖于它们本身的客观世界.它们的区别在于,每门自然科学都是以自然界的一定领域为其研究对象,研究物质某一种运动形式的特殊规律;而哲学则揭示现象中共同的东西,揭示客观世界中各种运动形式所固有的普遍规律和联系.数学,是研究研究客观世界数量关系和空间形式的自然科学.它不仅提供计算的方法,而且还是思维的工具,科学的语言,更是简历辩证唯物主义哲学的科学基础之一.数学通过精细的概念,严密的推理,奇妙的方法,简单的形式,去描绘细节,扩展内容,揭示规律,形成整体认识.数学反映了哲学范畴或基本矛盾的数量方面,数学有其逻辑严密性,高度抽象性,应用广泛性等特点,自然与哲学有很多相近之处,因而就决定了其与哲学必然有更为密切的关系.本文就数学与哲学的关系进行了粗浅的分析. 数学是表述简洁、清晰、歧义较少的逻辑体系。在数学中,不仅各种数字、函数,就连加、减、乘、除,大于、小于、等于,以及指数、导数、积分等符号本身,也都是约定俗成、极少歧义的概念。特别是几何方法,能用清晰、直观的坐标或图形,表达比较复杂的逻辑关系。在学校的学习中,我们常常把各门学科的应用题,用几何的方法描述出来,以便清晰地看出其中各个因素的相互逻辑关系,然后列出适当的数学公式,解出要求的问题。 形式逻辑可以用几何图形,表示各种概念复杂的逻辑关系。哲学也是一门科学,它当然也可以使用这种科学的方法来进行表述。 形式逻辑要求概念都是确定的,以便它进行正常的推理和运算。 辩证法认为,任何概念都是在一定的条件下确定的,不同的条件可能导致不同的结果,所以它必须研究确定概念的不同条件和不同结果。而具体研究几个不同条件和不同结果,也只能是运用有限的手段,遵循形而上学的方法,一个一个去研究。 简单一点说,辩证法的本质就是指出事物在不同条件下的不同结果。 确定概念的条件和被确定的概念之间的关系,类似于数学中的函数关系。 y = f ( x ) 用数学的术语,马克思这样表述。“一个变量的函数是另外一个变量,它的值随着前者的值而变化,也就是依赖于前者。” 我们可以具体举例用公式来表述上述概念。比如 在Y=X+1中,当X大于1时,那么Y大于2。 在Y=X+1中,当X小于1时,那么Y小于2。 在Y=X+1中,当X等于1时,那么Y等于2。 在上述三句话中,每一句都是形而上学的表述,在确定的条件下,表述确定的概念。 当我们把上述三个形而上学的表述放在一起分析时,就有了质的变化。我们说这既是形而上学的表述,又是辩证的表述。因为它指出了事物在不同条件下的不同结果。 我们还可以说,Y 在有的条件下大于2,在有的条件下小于2,在有的条件下等于2。这也是一种辩证的表述。可见有些所谓辩证的表述,不过是省略了几个形而上学表述中具体的条件,而用一个不确定的概念取而代之而已。科学进步正是要通过研究,把这些所谓辩证的、还没有确定的概念,变成确定的、形而上学的形式才能实现。
2017年全国数学竞赛命题研讨会试题汇编 2017年6月
目录 代数 代数1 不等式…………………………………………………人大附中张端阳1 代数2 不等式…………………………………………………人大附中张端阳1 代数3 不等式……………………………复旦附中李朝晖、施柯杰、肖恩利3 代数4 不等式……………………………复旦附中李朝晖、施柯杰、肖恩利4 代数5 不等式……………………………复旦附中李朝晖、施柯杰、肖恩利7 代数6 不等式…………………………………………华东师大二附中唐立华8 代数7 不等式……………………………………………湖南师大附中张湘君9 代数8 不等式……………………………………………湖南师大附中张湘君10 代数9 不等式……………………………………………湖南师大附中汤礼达11 代数10 不等式……………………………………………湖南师大附中汤礼达12 代数11 不等式………………………………………吉大附中石泽晖、王庶赫13 代数12 不等式…………………………………绵阳东辰学校袁万伦、姚先伟14 代数13 不等式……………………………………………绵阳东辰学校袁万伦15 代数14 三角不等式……………………………………………广州二中程汉波16 代数15 不等式……………………………………………大连二十四中邰海峰17 代数16 数列…………………………………………………东北育才学校张雷18 代数17 不等式………………………………………………东北育才学校张雷19 代数18 不等式………………………………………………大连二十四中李响23 代数19 多项式……………………………………学而思培优苏州分校李家夫24 代数20 不等式…………………………………………………华东师大张丽玉24 代数21 不等式……………………………………………………杭州二中赵斌25 几何 几何1……………………………………复旦附中李朝晖、施柯杰、肖恩利28