文档介绍：数论基础?数论就是指研究整数性质的一门理论。整数的基本元素是素数,所以,数论的本质是对素数性质的研究。?数论大致上可以分为初等数论(古典数论)和高等数论(近代数论)?初等数论是研究数的规律,特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法,主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。换言之,初等数论就是用初等、朴素的方法去研究数论。?整除的定义? 整除:若整数“a”除以大于0的整数“b”,商为整数,且余数为零。我们就说a能被b整除(或说b能整除a),记作b|a,读作“b整除a”或“a能被b整除”.(b≠0)所得的商是整数或有限小数而余数是零时,我们就说a能被b除尽(或说b能除尽a).因此整除与除尽的区别是,整除只有当被除数、除数以及商都是整数,,被除数、除数以及商可以是整数,也可以是有限小数,.?注:a or b作除数的其一为0则不叫整除同余?数学上,两个整数除以同一个整数,若得相同余数,则二整数同余(英文:Modular arithmetic;德文:Kongruenz)。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。? 同余理论是初等数论的重要组成部分,是研究整数问题的重要工具之一,. ?同余符号? 两个整数a,b,若它们除以整数m所得的余数相等,则称a,b对于模m同余? 记作 a ≡ b (mod m) ? 读作a同余于b模m,或读作a与b关于模m同余。? 比如 26 ≡ 14 (mod 12) ? 【定义】设m是大于1的正整数,a,b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mod m),读作a同余于b模m. ? 显然,有如下事实?(1)若a≡0(mod m),则m|a; ?(2)a≡b(mod m)等价于a与b分别用m去除,余数相同. ? 【证明】充分性:设a=mq1+r1,b=mq2+r2,0<=r1,r2<m ?∵a≡b(mod m),∴m|(a-b),a-b=m(q1-q2)+(r1-r2). ? 则有m|(r1-r2). ?∵0<=r1,r2<m,∴0<=|r1-r2|<m, ? 即r1-r2=0,∴r1=r2. ? 必要性:设a,b用m去除余数为r,即a=mq1+r,b=mq2+r, ?a-b=m(q1-q2) ∴m|(a-b), ? 故a≡b(mod m). ?性质?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) ? 【证明】上述性质很容易证明,下面仅证明(3). ?∵a≡b(mod m)∴m|(a-b) 同理m|(b-c), ?∴m|[(a-b)+(b-c)]∴m|(a-c). ? 故a≡c(mod m). ?4 线性运算如果a ≡ b (mod m),c ≡ d (mod m),那么(1)a ± c ≡ b ± d (mod m),(2)a * c ≡ b * d (mod m) ? 【证明】(1)∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d) ?∴m|[(a-b)±(c-d)] ∴m|[(a±c)-(b±d)] ?∴a ± c ≡ b ± d (mod m) ?(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d) ? 又 m|(a-b) , m|(c-d) ∴m|(ac-bd) ?∴a * c ≡ b * d (mod m) ?5 除法若ac ≡ bc (mod m) c!=0 则 a≡ b (mod m/(c,m)) 其中(c,m)表示c,m的最大公约数? 特殊地(c,m)=1 则a ≡ b (mod m) ?6 乘方如果a ≡ b (mod m),那么a^n ≡ b^n (mod m) ?7 若a ≡ b (mod m),n|m,则 a ≡ b (mod n) ?8 若a ≡ b (mod mi) i=1,2...n 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数?9 欧拉定理? 设a,m∈N,(a,m)=1,则a^(φ(m))≡1(mod m) ?(注:φ(m)指模m的简系个数,φ(m)=m-1, 如果m是素数;φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1