数论
数论
【数学归纳法】 第一数学归纳法
一般地，证明一个与自然数n 有关的命题P(n ），有如下步骤：
（1）证明当n 取第一个值n0时命题成立。n0对于一般数列取值为0或1，但也有特殊情况；
（2）假设当n=k （k≥n0，k 为自然数）时命题成立，证明当n=k+1时命题也成立。
综合（1）（2），对一切自然数n （≥n0），命题P(n ）都成立。
第二数学归纳法
对于某个与自然数有关的命题P(n ），
（1）验证n=n0时P(n ）成立；
（2）假设n0≤n<=k 时P(n ）成立，并在此基础上，推出P(k+1）成立。
综合（1）（2），对一切自然数n （≥n0），命题P(n ）都成立。
倒推归纳法
又名反向归纳法
（1）验证对于无穷多个自然数n 命题P(n ）成立（无穷多个自然数可以是一个无穷数列中的数，如对于算术几何不等式的证明，可以是2^k ，k≥1）；
（2）假设P(k+1）（k≥n0）成立，并在此基础上，推出P(k ）成立，
综合（1）（2），对一切自然数n （≥n0），命题P(n ）都成立；
螺旋归纳法
对两个与自然数有关的命题P(n ），Q(n ），
（1）验证n=n0时P(n ）成立；
（2）假设P(k ）（k>n0）成立，能推出Q(k ）成立，假设 Q(k ）成立，能推出 P(k+1）成立； 综合（1）（2），对一切自然数n （≥n0），P(n ），Q(n ）都成立。
【威尔逊定理】
当且仅当p 为素数时：( p -1 )! ≡ -1 ( mod p )
【欧拉定理】
若n,a 为正整数，且（n,a ）=1，则:
【费马小定理】
若p 是质数，则(mod )p a a p ≡
若p 是质数，且(a,p)=1，则11(mod )p a p -≡
【中国剩余定理】
一般地，若有一些两两互质的整数
，则对任意的整数：，以下联立同
余方程组对模 有公解：
【裴蜀定理】 对任何整数a 、b 和它们的最大公约数d ，关于未知数x 和y 的线性丢番图方程（称为裴蜀等式）： 若a,b 是整数,且（a,b)=d ，那么对于任意的整数x 、y,ax+by 都一定是d 的倍数，
特别地，一定存在整数x,y ，使ax+by=d 成立。
它的一个重要推论是：a,b 互质的充要条件是存在整数x,y 使ax+by=1.
【拉格朗日定理】 １、拉格朗日四平方和定理(费马多边形数定理特例)
每个自然数均可表示成4个平方数之和。3个平方数之和不能表示形式如
4^k(8n+ 7)的数。
如果在一个正整数的因数分解式中，没有一个数有形式如4k+3
的质数次方，该正整数可以表示成两个平方数之和。
2
、设p 是一个素数，f(x)是整系数多项式，模p 的次数为n ，则同余方程f(x)≡0（mod p ）至多有n 个互不相同（即模p 互不同余）的解。
【欧拉判别法】
在数论中，二次剩余的欧拉判别法（又称欧拉准则）是用来判定给定的整数是否是一个质数的二次剩余。若是奇质数且不能整除，则：
是模的二次剩余当且仅当：
是模的非二次剩余当且仅当：
以勒让德符号表示，即为：
【勾股方程】 2222222222()(2
)()x
y z a b ab a b +=?-+=+
【佩尔方程】
*221x dy -=有无穷多组正整数解（d 为大于0的非平方数）
性质1：若(
)11,x y 为其解，则一切解(),n n x y 有 1(n n x y x y +=
+
性质2：若(
)11,x y
为最小正解，则1(
n n x y x y +=+所得的(),n n x y 为一切解
此时((((111112n n n n n n x x y x y y x y x y ???=++-??????????=+--?????? 其中()11,x y 为基本解
性质三：（1）111111n n n n n n x x x dy y y x y y x ++=+??=+? （2）1111
1122n n n n n n x x x x y x y y +-+-=-??=-?
*221x dy -=-若有整数解，则有无穷多组（d 为大于0的非平方数） 性质1：若()11,x y
为其解，令211(n n x y x y ++=+，则()2121,n n x y ++为其解 性质2：若()11,x y
为最小正解，则211(n n x y x y ++=+所得的()2121,n n x y ++为一切解
【阶】
将满足同余式1(mod )n a m ≡的最小正整数n 称为“a 对模m 的阶”记作()m a δ 若1(mod ),n a m n N +≡∈，则()|m a n δ
高中数学竞赛中数论问题的常用方法
高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 1.基本原理 为了使用方便,我们将数论中的一些概念和结论摘录如下: 我们用),...,,(21n a a a 表示整数1a ,2a ,…,n a 的最大公约数.用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的 最小公倍数.对于实数x ,用[x ]表示不超过x 的最大整数,用{x }=x -[x ]表示x 的小数部分.对于整数 b a ,,若)(|b a m -,,1≥m 则称b a ,关于模m 同余,记为)(mod m b a ≡.对于正整数m ,用)(m ?表示 {1,2,…,m }中与m 互质的整数的个数,并称)(m ?为欧拉函数.对于正整数m ,若整数m r r r ,...,,21中任何两个数对模m 均不同余,则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质,且其中任何两个数关于模m 不同余,则称{)(21,...,,m r r r ?}为模m 的简化剩余系. 定理1 设b a ,的最大公约数为d ,则存在整数y x ,,使得yb xa d +=. 定理2(1)若)(mod m b a i i ≡,1=i ,2,…,n ,)(m od 21m x x =,则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； (2)若)(mod m b a ≡,),(b a d =,m d |,则 )(mod d m d b d a ≡； (3)若b a ≡,),(b a d =,且1),(=m d ,则)(mod m d b d a ≡； (4)若b a ≡(i m mod ),n i ,...,2,1=,M=[n m m m ,...,,21],则b a ≡(M mod ). 定理3(1)1][][1+<≤<-x x x x ； (2)][][][y x y x +≥+； (3)设p 为素数,则在!n 质因数分解中,p 的指数为 ∑≥1 k k p n . 定理4 (1)若{m r r r ,...,,21}是模m 的完全剩余系,1),(=m a ,则{b ar b ar b ar m +++,...,,21}也是模 m 的完全剩余系； (2)若{)(21,...,,m r r r ?}是模m 的简化剩余系,1),(=m a ,则{)(21...,,m ar ar ar ?}是模m 的简化剩余系. 定理5(1)若1),(=n m ,则)()()(n m mn ???=. (2)若n 的标准分解式为k k p p p n ααα (2) 121=,其中k ααα,...,21为正整数,k p p p ,...,21为互不相
几何学基础简介
几何学基础简介 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的约数中，最大的三位数是多少?
关于数论函数方程
关于数论函数方程() ()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.带余除法:若a,b是两个整数,b>0,则存在两个整数q,r,使得abq+r(0≤r 4.约数个数定理:设n的标准分解式为(1),则它的正约数个数为: d(n)(a1+1)(a2+1)…(ak+1)。 5.整数集的离散性:n与n+1之间不再有其他整数。因此,不等式x 初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 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整除，它的最后两位数是多少？ 费马小定理数论的证明方法 2007年12月28日星期五 01:29 P.M. 费马小定理数论的证明方法 Mod的简单介绍 (Congruence) a=b(mod m) a和b除以m以后有相同的余数 不失一般性地另a>b 则a=km+b比如7=1 mod 2 9=4 mod 5 简单的Congruence 计算 如果a=b mod m c=d mod m 则a=km+b c=tm+d 直接可推出 a+b=c+d (mod m) a-b=c-d (mod m) ab=cd (mod m) 并且可得存在正整数c 使得ac=bc (mod mc) 当然ac=bc(mod m) 费马小定理如果a,p互质且q是质数则a^(p-1)=1 (mod p) 考虑数列An= a,2a,3a,4a…… (p-1)a 假设An中有2项ma, na 被p除以后的余数是相同的.那么必然有ma=na (mod p) 即a(m-n)=0(mod p) 由于a和p互质,所以m-n=0(mod p) 但是m,n属于集合{1,2,3..p-1} 且m不等于n,所以m-n不可能是p的倍数.和假设产生矛盾所以An中任意2项被p除 得到的余数都是不同的, 并且对于任一个整数被p除以后的余数最多有p-1个,分别是 1,2,3,….p-1 而数列An中恰好有p-1个数,所以数列中的数被p除以后的余数一定正好包含所有的1,2,3,4,5…. p-1 由此我们可以用Congruence的乘法性质, a*2a*3a*…(p-1)a=1*2*3*4..*(p-1) (mod p) 对两边进行化简,即可以得到a^(p-1)=1 (mod p) Euler’s Totient function 定义o(n)是所有比n小且和n互质的数的总数(包括1) 例如o(5)=4 o(10)=8 我们发现引入这个以后费马小定理可以改写为a^o(p)=1 (mod p) 事实上,这个结论对所有的正整数n都成立即a^o(n)=1 (mod n) 欧几里得算法 欧几里德算法又称辗转相除法，用于计算两个正整数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 的所有不同 素因子的个数. 数论短期班100题手册 知识框架体系 一、奇偶性质 1．奇数和偶数的表示方法： 因为偶数是2的倍数，所以通常用2k这个式子来表示偶数(这里k是整数)； 因为任何奇数除以2其余数总是1，所以通常用式子21 k+来表示奇数(这里k是整数)．特别注意，因为0能被2整除，所以0是偶数．最小的奇数是1，最小的偶数是0． 2．奇数与偶数的运算性质： 性质一：偶数+偶数=偶数(偶数-偶数=偶数) 奇数+奇数=偶数(奇数-奇数=偶数) 偶数+奇数=奇数(偶数-奇数=奇数) 可以看出：一个数加上(或减去)偶数，不改变这个数的奇偶性； 一个数加上(或减去)奇数，它的奇偶性会发生变化． (也可以这样记：奇偶性相同的数加减得偶数，奇偶性不同的数加减得奇数．) 性质二：偶数?奇数=偶数(推广开来还可以得到：偶数个奇数相加得偶数) 偶数?偶数=偶数(推广开就是：偶数个偶数相加得偶数) 奇数?奇数=奇数(推广开就是：奇数个奇数相加得奇数) 可以看出：一个数乘以偶数时，乘积必为偶数；几个数的积为奇数时，每个乘数都是奇数．(也可以这样简记：对于乘法，见偶(数)就得偶(数))． 性质三：任何一个奇数一定不等于任何一个偶数． 二、整除 1．整除的定义 所谓“一个自然数a能被另一个自然数b整除”就是说“商a b 是一个整数”；或者换句话说： 存在着第三个自然数c，使得a b c =?．这是我们就说“b整除a”或者“a被b整除”，其中b 叫a的约数，a是b的倍数，记作：“|b a”． 2．整除性质： ⑴传递性若|c b，|b a，则|c a． ⑵可加性若|c a，|c b，则|c a b ± （）． ⑶可乘性若|c a，|d b，则| cd ab． 3．整除的特征 ⑴4,25,8,125,16,625的整除特征 能否被4和25整除是看末两位；能否被8和125整除是看末三位；能否被16和625整除是看末四位(100425 =?,10008125 =?,1000016625 =?,100000323125 =?) ⑵3,9的整除特征 能否被9整除是看数字之和是否是9的倍数，并且这个数除以9的余数和这个数数字之和除以9的余数相同，因此判断一个数除以九余几就可以先把和是9的倍数的数划掉，剩下的数是几就代表高中数学竞赛资料-数论部分 (1)
浅谈数学教学中的哲学思想
小升初数学讲义之——数论
费马小定理数论的证明方法
数论入门
初等数论
数论与解析数论简史
有关数论函数的一些问题
数论班100题手册