下载文档原格式
欧拉定理数论欧拉定理是数论中的一个非常重要的公式，也称欧拉费马定理或欧拉-费马定理。
它表示若a、n为两个整数，且满足a和n互质，则有$a^{\varphi(n)}\equiv 1(\mod n)$。
其中，$\varphi(n)$表示小于或等于n的正整数中与n互质的数的个数。
欧拉定理可以用于求解一些求模运算问题，例如求解$a^b\bmod p$，其中a、b、p均为正整数。
如果p是质数，则欧拉定理可以简化为费马小定理，即$a^{p-1}\equiv 1 (\mod p)$。
如果p不是质数，则我们可以通过欧拉定理的公式来计算$a^b\bmod p$。
欧拉定理是以瑞士数学家欧拉命名的，他是18世纪最著名的数学家之一，被公认为巴塞尔大学数学系的创始人之一。
欧拉在他的著作中提出了许多数学问题，并取得了显著的成果。
欧拉定理是他比较重要的贡献之一。
在使用欧拉定理的过程中，我们需要首先求出$\varphi(n)$。
我们可以通过以下公式来计算$\varphi(n)$：$\varphi(n)=n\prod_{p|n}(1-\frac{1}{p})$其中，p|n表示p是n的因数，并且$\prod_{p|n}$表示对n的每个因数p都进行乘积运算。
这个公式还可以写成下面的形式：$\varphi(p^k)=p^k-p^{k-1}$其中，p是质数，k是一个正整数。
这个公式可以计算小于p的k次幂的正整数中与p互质的数的个数。
在实际应用中，欧拉定理常常用作数据加密和解密算法。
例如，RSA（RSA is a public-key cryptographic algorithm）加密算法就是基于欧拉定理的。
RSA算法是一种非对称加密算法，即加密和解密使用不同的密钥。
它主要用于数字签名、数据加密等方面。
总的来说，欧拉定理是一个非常重要的定理，它不仅可以用于求解一些数论问题，还可以应用于实际的数据加密和解密算法中。
因此，学习欧拉定理对于理解数论的基本概念和应用具有很重要的意义。
1 费马大定理费马大定理：（1）当整数n > 2时，关于x, y, z的不定方程x^n + y^n = z^n.（(x , y) = (x , z) = (y , z) = 1［n是一个奇素数］x>0,y>0,z>0,且xyz≠0）无整数解。
这个定理，本来又称费马最后定理，由17世纪法国数学家费马提出，而当时人们称之为“定理”，并不是真的相信费马已经证明了它。
虽然费马宣称他已找到一个绝妙证明，但经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国数学家安德鲁·怀尔斯和他的学生理查·泰勒于1995年成功证明。
证明利用了很多新的数学，包括代数几何中的椭圆曲线和模形式，以及伽罗华理论和Hecke代数等，令人怀疑费马是否真的找到了正确证明。
而安德鲁·怀尔斯(Andrew Wiles)由于成功证明此定理，获得了1998年的菲尔兹奖特别奖以及2005年度邵逸夫奖的数学奖。
（2）证明方法五十年代日本数学家谷山丰首先提出一个有关椭圆曲线的猜想，后来由另一位数学家志村五郎加以发扬光大，当时没有人认为这个猜想与费马定理有任何关联。
在八十年代德国数学家佛列将谷山丰的猜想与费马定理联系在一起，而安德鲁·怀尔斯所做的正是根据这个关联论证出一种形式的谷山丰猜想是正确的，进而推出费马最后定理也是正确的。
这个结论由威利斯在1993年的6月21日於美国剑桥大学牛顿数学研究所的研讨会正式发表，这个报告马上震惊整个数学界，就是数学门墙外的社会大众也寄以无限的关注。
不过怀尔斯的证明马上被检验出有少许的瑕疵，于是怀尔斯与他的学生又花了十四个月的时间再加以修正。
1994年9月19日他们终於交出完整无瑕的解答，数学界的梦魇终於结束。
1997年6月，怀尔斯在德国哥庭根大学领取了佛尔夫斯克尔奖。
当年的十万马克约为两百万美金，不过怀尔斯领到时，只值五万美金左右，但安德鲁·怀尔斯已经名列青史，永垂不朽了。
一、引言在数学及许多分支中都可以见到很多以欧拉命名的常数、公式和定理。
在数论中，欧拉定理（Euler Theorem ，也称费马-欧拉定理或 欧拉函数定理）是一个关于同余的性质。
欧拉定理得名于瑞士数学家 莱昂哈德·欧拉，该定理被认为是数学世界中最美妙的定理之一，欧拉定理实际上是 费马小定理的推广.二、内容在数论中， 欧拉定理,（也称 费马--欧拉定理）是一个关于同余的性质。
欧拉定理表明，若n,a 为正整数，且n,a 互质，则： () 1( )n amod n ϕ≡. 1.知识准备：（1）欧拉函数 ：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括1）的个数，记作 φ(n) .（2）完全余数集合：定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。
显然 |Zn| ＝φ(n) 。
其中，“ |A |”表示这个集合中元素的个数，比如A=｛a,b} 则|A|=2.（3）有关性质：①对于素数 p ，φ(p) = p -1 。
②对于两个不同素数 p ， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1). 因为Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} ， 则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ＝φ(p) * φ(q) .2.证明方法：证明：( 1 ) 首先证明下面这个命题：对于集合Zn = {x1, x2, ..., xφ(n)} ， S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} ，其中xi(i=1,2,…φ(n))是不大于n 且与n 互素的数，即n 的一个化简剩余系，或称简系，或称缩系)，则Zn = S .1) 由于a,n 互质，xi 也与n 互质，则a*xi 也一定于n 互质，因此 任意xi ，a*xi(mod n) 必然是Zn 的一个元素2) 对于Zn 中两个元素xi 和xj ，如果xi ≠ xj 则a*xi(mod n) ≠ a*xj(mod n)，这个由a 、n 互质和消去律可以得出。
欧拉-费马⼩定理定理（证明及推论）欧拉定理：若正整数a , n 互质，则aφ(n)≡1(mod n)其中φ(n) 是欧拉函数（1~n) 与n 互质的数。
证明如下：不妨设X1，X2 ...... Xφn是1~n与n互质的数。
⾸先我们先来考虑⼀些数：aX1，aX2 ...... aXφn 这些数有如下两个性质： （1）任意两个数模n余数⼀定不同：（反证）若存在aX1≡aX2（mod n），则 n |（ aX1 - aX2 ），⽽a，n互质且（X1 -X2）< n，所以n不可能整除（ aX1 - aX2 ），也就是说不存在aX1≡aX2（mod n）。
归纳法：对于任意的与n互质的X i均成⽴。
故得证。
那么因为有φn个这样的数，X i mod n（i=1~φn）所以就有φn 个不同的余数，并且都是模数⾃然是（0~n-1）。
（2）对于任意的aX i（mod n）都与n互质。
这不难想，因为a与n互质这是欧拉函数的条件，X i是（1~n）与n互质的数的集合中的元素。
所以如果a*X i做为分⼦，n做为分母，那么他们构成的显然就是⼀个最简分数，也就是aX i和n互质。
接下来就可以⽤欧⼏⾥得算法：因为：gcd（aX i，n）==1所以：gcd（aX i，n）== gcd（n，aX i%n）== 1 这样，我们把上⾯两个性质结合⼀下来说，aX1（mod n），aX2（mod n） ...... aXφn（mod n）构成了⼀个集合（性质1证明了所有元素的互异性），并且这些数是1~n与n互质的所有数构成的集合（性质1已说明）。
这样，我们巧妙的发现了，集合{ aX1（mod n），aX2（mod n） ...... aXφn（mod n）}经过⼀定的排序后和集合{ X1，X2 ...... Xφn }完全⼀⼀对应。
那么：aX1（mod n）* aX2（mod n）* ...... * aXφn（mod n）= X1 * X2 * ...... * Xφn 因此：我们可以写出以下式⼦：aX1 * aX2 * ...... * aXφn ≡ X1 * X2 * ...... * Xφn（mod n），即：（aφn -1）X1 * X2 * ...... * Xφn≡ 0 （mod n） ⼜因为X1 * X2 * ...... * Xφn与n互质，所以，（aφn -1）| n，那么aφn ≡ 1（mod n）。
欧拉定理、费马定理、威尔逊定理1、欧拉函数：φ(m )是1, 2, …, m 中与m 互质的个数，称为欧拉函数.①欧拉函数值的计算公式：若m ＝p 1α1p 2α2…p n αn , 则φ(m )＝m (1－1p 1)(1－1p 2)…(1－1p n) 例如，30＝2·3·5，则.8)511)(311)(211(30)30(=---=ϕ②若p 为素数，则1()1,()(1),k k p p p p p ϕϕ-=-=-若p 为合数，则()2,p p ϕ≤-③不超过n 且与n 互质的所有正整数的和为1()2n n ϕ；④若(,)1()()(),a b ab a b ϕϕϕ=⇒= 若()()a b a b ϕϕ⇒⑤设d 为n 的正约数，则不大于n 且与n 有最大公因数d 的正整数个数为()ndϕ， 同时()()d nd nn d n dϕϕ==∑∑；例1、证明：φ(n )＝14n 不可能成立.不可能成立假设不成立上式不成立，左边是一个奇数，上式右边是一个偶数，又即：即：为奇质数，则：设成立，则证：若不可能成立；【练习】证明：n p p p p p p p p p p p p p p p p p p p p p p p p p p p n p p p p p p n n n n k k k k k kk k k k k k k k k k 41)4()1()1)(1(4)1()1)(1(22)1()1)(1(2241)(,,),2(,2|441)4(41)4(212121112112122211212121212121212121=∴∴∴---=---=---==≥===----ϕϕαϕϕααααααααααααααααααααΘΛΛΛΛΛΛΛΛΛΛ例2、证明：数列{2n －3}中有一个无穷子数列，其中任意两项互质.}{}32{1,,,1),(mod 1321),(mod 122)(32,,,,}32{}32{21211)()((()(1)(12121212121i n k k i u u u i u u u u u u u u u k k n n u k u u u u ki u ki u x u u u u k k k k k 互素的无穷子数列中一定有一个任意两项数列依此方法一直下去项两两互素的子数列，是、数列＝理有：是欧拉函数，由欧拉定其中作项是两两互素的，记为中已有证明：设数列其中任意两项互素；中有一个无穷子数列，、证明：数列例））-+∴≤≤-≡-∴≤≤≡-=--++++ΛΛΛΛΛΛϕϕϕϕϕϕϕ例3、已知p 为质数，在1, 2, …, p α中有多少个数与p α互质？并求φ(p α). 直接用性质②例4 将与105互素的所有正整数从小到大排成数列，求出这个数列的第2010项.解：1~105的所有正整数中共有(105)(3)(5)(7)48ϕϕϕϕ==个与105互素，他们从小到排列为：12345481,2,4,8,11,,104a a a a a a ======L . 对于任一的n a ，由带余除法存在唯一的q , r 使得 105,0,0105n a q r q r =+≥≤<，由(a n ，105)＝1，可得(r ，105)＝1，即1248{,,,}r a a a ∈L .反之，对于任意固定非负整数q , 1248{,,,}r a a a ∈L 有(105q ＋r ，105)＝1，于是105q ＋r 都是数列的项， 从而存在正整数n ，使得105n a q r =+. 因此数列{}n a 仅由105(1,2,,48)n q a n +=L 的数由小到大排列而成的.因为2010＝48*41＋42，所以有2010424842201010541,104,89,4394a a a a a =⨯+===而由求得所以. 2、(欧拉定理) 若(a , m )＝1，则a φ(m )≡1(mod m ).证明：设r 1，r 2，…，r φ(m )是模m 的简化剩余系，又∵(a , m )＝1，∴a ·r 1，a ·r 2，…，a ·r φ(m )是模m 的简化剩余系， ∴a ·r 1×a ·r 2×…×a ·r φ(m )≡r 1×r 2×…×r φ(m )(mod m )，又∵(r 1·r 2·…·r φ(m ), m )＝1，∴a φ(m )≡1(mod m ). 注：这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题. 应用：设(a , m )＝1, c 是使得a c ≡1(mod m )的最小正整数, 则c |φ(m ).2、(定义1) 设m ＞1是一个固定的整数, a 是与m 互质的整数，则存在整数k (1≤k ≤m )，使a k ≡1(mod m )， 我们称具有这一性质的最小正整数(仍记为k )称为a 模m 的阶，由a 模m 的阶的定义，可得如下性质： ⑴ 设(a , m )＝1，k 是a 模m 的阶，u , v 是任意整数，则a u ≡a v (mod m )的充要条件是u ≡v (mod k )， 特别地，a u ≡1 (mod m )的充要条件是k |u 证明：充分性显然.必要性：设,u l u νν>=-，由(mod )ua a m ν≡及(,)1a m =知1(mod )la m ≡. 用带余除法，,0,l kq r r k =+≤<故1(mod )kqra a m ⋅≡，∴1(mod )ra m ≡，由k 的定义知，必须0r =，所以(mod ).u v k ≡⑵ 设(a , m )＝1，k 是a 模m 的阶，则数列a , a 2, …, a k , a k ＋1,…是模m 的周期数列，最小正周期为k ， 而k 个数a , a 2,…, a k 模m 互不同余.⑶ 设(a , m )＝1，k 是a 模m 的阶，则k |φ(m )，特别地，若m 是素数p ，则a 模p 的阶整除p －1. (4) 设(a , p )＝1, 则d 0是a 对于模p 的阶⇔0da ≡1(mod p ), 且1, a , …, a do −1对模p 两两不同余. 特别地, d o ＝φ(p )⇔1, a ,…, a φ(p )−1构成模p 的一个简化剩余系. 定理：若l 为a 对模m 的阶，s 为某一正整数，满足)(m od 1m a s≡，则s 必为l 的倍数. 例5、设a 和m 都是正整数，a ＞1. 证明：).1(|-ma m ϕ证明：实上，显然1-m a a 与互素，且1-m a a 模的阶是m ，所以由模阶的性质③导出).1(|-ma m ϕ 例6：设m , a ,b 都是正整数，m ＞1，则(.1)1,1),(-=--b a bam m m证明：记).1,1(--=bam m d 由于(a , b )|a 及(a , b )|b ，易知1|1),(--a b a m m及1|1),(--b b a m m ，故d mb a |1),(-， 另一方面设m 模d 的阶是k ，则由)(m od 1),(m od 1d m d m b a ≡≡推出，k |a 及k |b ，故k |(a ，b ). 因此.1|),(m od 1),(),(-≡b a b a m d d m 即综合两方面可知，.1),(-=b a md 证毕.3、(费尔马小定理) 若p 是素数，则a p ≡a (mod p ) 若另上条件(a ，p )＝1，则a p −1≡1(mod p ) 证明：设p 为质数，若a 是p 的倍数，则)(m od 0p a a p≡≡.若a 不是p 的倍数，则1),(=p a 由欧拉定理得：)(mod 1,1)()(p ap p p ≡-=ϕϕ，)(mod ),(mod 11p a a p a p p ≡≡∴-，由此即得.4、(威尔逊定理) p 为质数 ⇔ (p －1)!≡－1 (mod p )证明：充分性：若p 为质数，当p ＝2，3时成立，当p ＞3时，令x ∈{1, 2, 3, …, p −1}，则1),(=p x ，在x p x x )1(,,2,-Λ中，必然有一个数除以p 余1， 这是因为x p x x )1(,,2,-Λ则好是p 的一个剩余系去0. 从而对}1,,2,1{},1,2,1{-∈∃-∈∀p y p x ΛΛ，使得)(mod 1p xy ≡；若)(m od 21p xy xy ≡，1),(=p x ，则)(m od 0)(21p y y x ≡-，)(|21y y p -，这不可能. 故对于不同的}1,,2,1{,21-∈p y y Λ，有1xy ≡／)(m od 2p xy .即对于不同的x 对应于不同的y ， 即1,,2,1-p Λ中数可两两配对，其积除以p 余1，然后有x ，使)(m od 12p x ≡，即与它自己配对， 这时)(m od 012p x ≡-，)(mod 0)1)(1(p x x ≡-+，∴1-=p x 或1=x .除1,1-=p x 外，别的数可两两配对，积除以p 余1.故)(mod 11)1()!1(p p p -≡⋅-≡-.必要性：若(p －1)!≡－1 (mod p )，假设p 不是质数，则p 有真约数d ＞1，故(p －1)!≡－1 (mod d )，另一方面，d ＜p ，故d |(p －1)!，从而(p －1)!≡0 (mod d )，矛盾！ ∴p 为质数.5、算术基本定理：任何一个大于1的整数都可以分解成质数的乘积. 如果不考虑这些质因子的次序，则这种分解法是唯一的. 即对任一整数n ＞1，有n ＝p 1α1p 2α2…p k αk ，其中p 1＜p 2＜…＜p k 均为素数， α1、α2、…、αk 都是正整数.①正整数d 是n 的约数⇔ d ＝p 1β1p 2β2…p k βk ，(0≤βi ≤αi , i ＝1, 2, …, k )② 由乘法原理可得：n 的正约数的个数为r (n )＝(α1＋1)(α2＋1)…(αk ＋1) ③ n 的正约数的和为S (n )＝(1＋p 1＋…＋p 1α1)(1＋p 2＋…＋p 2α2)…(1＋p k ＋…＋p k αk )④ n 的正约数的积为T (n )＝1()2r n n⑤ n 为平方数的充要条件是：r (n )为奇数.(2) 判断质数的方法：设n 是大于2的整数，如果不大于n 的质数都不是n 的因子，则n 是质数. (3) n !的标准分解：设p 是不大于n 的质数，则n !中含质数p 的最高次幂为：).]([][][][)!(132+<≤++++=m m m p n p pnp n p n p n n P Λ 从而可以写出n !的标准分解式.例7、证明：当质数p ≥7时，240|p 4－1.1|2401|531653161|51|31),5(,1),3(16422)1)(1)(1(1111,1,1)1)(1)(1(1,72401744442242244-∴-⋅⋅--∴==⋅⋅++-=-+-++-++-=-∴≥-≥p p p p p p p p p p p p p p p p p p p p p p p 两两互素，则与，又费马小定理有：又整除＝能被是相邻的偶数，则：和均为偶数，且又是奇数素数证：整除；能被时，、证明当素数例ΘΘΘΘ例8、求20052003被17除所得的余数.解：()2005200520052003171141414(mod17),=⨯+≡因为(17,14)1,=所以由费马小定理得16141(mod17),≡ 故()()()()()5420052005161255520031414143334312(mod17),⨯+≡≡≡≡-≡--≡--≡所以20052003被17除所得的余数是14.变式拓展：已知a 为正整数，a ≥2，且(a , 10)＝1，求a 20的末两位数字.解：∵(a , 10)＝1，∴a 为奇数，∴a 20＝a φ(25)≡1(mod 25)，又∵a 2≡1(mod 4)⇒ a 20≡1(mod 4)， 又∵(25, 4)＝1，∴a 20≡1(mod 100)，∴a 20的末两位数字01.例9、证明：方程325y x =+无整数解.解：若y 是偶数，则8 |3y ，x 2≡3(mod 8)不可能. 故必有y 一定是奇数，从而x 是偶数.令x ＝2s ，y ＝2t ＋1得t t t s 36422232++=+, 知t 是偶数，令t ＝2j ，代入得s 2＋1＝j (16j 2＋12j ＋3) 由(16j 2＋12j ＋3)≡3(mod 4) 知存在4k ＋3型的奇素数p ，使得p |(16j 2＋12j ＋3)，从而p | s 2＋1，即s 2≡－1(mod p )，有(s ，p )＝1, 21212)1()(---≡p p s (mod p )，于是 1-p s ≡－1(mod p )与费尔马小定理矛盾.例10、 试证：对于每一个素数p ，总存在无穷多个正整数n ，使得p |2n －n.. 证明：若p ＝2，则n 为偶数时结论成立.若p ＞2，则(2，p )＝1，由费尔马小定理2 p －1≡1(mod p )，故对于任意m ，有2 m (p −1)≡1(mod p ). ∴2 m (p −1)－m (p －1)≡1＋m (mod p )，令1＋m ≡0(mod p )，即m ＝kp －1， 则对于n ＝m (p －1)＝(kp －1)(p －1)(k ∈N *)，均有2 n －n 被p 整除例11、设a , b 为正整数，对任意的自然数n 有n na nb n ++，则a ＝b . 证明：假设a 与b 不相等. 考虑n ＝1有11a b ++，则a ＜b .设p 是一个大于b 的素数，设n 是满足条件的正整数：1(mod(1)),(mod ),n p n a p ≡-≡- 由孙子定理这样的n 是存在的，如 n ＝(a ＋1)(p －1)＋1. 由费马定理(1)1(mod ),nk p a aa p -+=≡所以0(mod ),n a n p +≡也即,(mod )n n p b n bn ba p ++≡-再由费马定理，所以pb a -，矛盾. 例12、设p 是奇素数，证明：2 p －1的任一素因了具有形式x px ,12+是正整数.证明：设q 是2 p －1的任一素因子，则q ≠2. 设2模q 的阶是k ，则由)(m od 12q p≡知k |p ，故k ＝1或p (因p 是素数，这是能确定阶k 的主要因素).显然k ≠1，否则),(m od 121q ≡这不可能，因此k ＝p .由费马小定理)(mod 121q q ≡-推出.1|,1|--q p q k 即因p 、q 都是奇数，故q －1＝2px (x 是个正整数).例13、设p 是大于5的素数, 求证：在数列1, 11, 111, …中有无穷多项是p 的倍数.证明： 因5p >是素数, 故(,10) 1.p =由费马小定理1101(mod ),p p -≡故对每一个正整数l 有()11010(mod ),l p p --≡ 而()()(){1111019999111,l p l p l p ----==⨯L L 123个个因()1(,9)1,101,l p p p -=- 故(){111 1.l p p -L 个例14、证明：若0(mod ),ppm n p +≡则20(mod ),ppm n p +≡这里p 是奇素数.证明：因p 是奇素数，故由费马定理得，(mod ),(mod ).ppm m p n n p ≡≡于是，(mod ).ppm n m n p +≡+ 故可由已知条件0(mod )ppm n p +≡得0(mod ).m n p +≡故存在整数k 使得,.m n pk n pk m +==- 因此()()()()()()()12122111210(mod ).p p p p p p p p p rp rrrp p ppm n m pk m pk C pk m C pk m Cpk m Cpk m p -----+=+-=-+++-++≡LL例15、(2004第36届加拿大奥林匹克) 设p 是奇质数，试证：∑-=-+≡11212)(mod 2)1(p k p p p p k例16、(第44届IMO ) 设p 是质数，试证：存在一个质数q ，使对任意整数n ，数n p −p 不是q 的倍数.例17、已知p是给定的质数，求最大正整数m满足：⑴1≤m≤p−1；⑵∑-=≡11) (modpkm p k.例18、(2006国家集训队测试题) 求所有的正整数对(a, n)，使得n|(a＋1)n−a n课外练习题：1、①证明：f (x )＝15x 5＋13x 3＋715x 是一个整值多项式. ②求证：f (n )＝15n 5－32n 2＋1310n －1被3除余2.①则只需证=)(15x f x x x 75335++是15的倍数即可. 由3，5是素数及Fetmat 小定理得)5(mod 5x x ≡，)3(mod 3x x ≡，则)5(m od 07375335≡+≡++x x x x x ；)3(m od 0275335≡+≡++x x x x x而(3，5)＝1，故)15(mod 075335≡++x x x ，即)(15x f 是15的倍数, 所以)(x f 是整数. 2、 证明：2730|n 13－n (n ∈N *))(|2730137532),(137532)(|2),(|3),(|5),(|7)(,)(,)(,)(,)()1)(1)(1)(1)(1()1)(1)(1()1)(1(),(|13),(,)(1375322730)(,|273043212433527162263366131313n f n f n f n f n f n f n f n n n f n n n f n n n f n n n f n n n n n n n n n n n n n n n n n n f N n n n n f N n n n 两两互素，故，，，，且均整除，，，，即由费马小定理可知：的因式都是故由于可知则由费马小定理，，若记＝证明：【练习】证明：-=-=-=-=++-+++-=++-=+-=-∈-=⋅⋅⋅⋅∈-Θ3、 已知有正整数b a b a ab ba b a ++++的最大公约数不超过与是整数，求证：使得11,.证明：由于a ＋1b ＋b ＋1a ＝a 2＋b 2＋a ＋b ab……①，设(a , b )＝d ，则d 2|a 2＋b 2，显然d 2|ab ，由①得，d 2|a ＋b于是a ＋b ≥d 2，a ＋b ≥d ，即 (a , b )≤a ＋b .4、求最小的正整数k ，使得存在非负整数m ，n 满足k ＝19m －5n5、将与105互素的所有正整数从大到小排列，试求出这个数列的第1000项；法一：由105=3×5×7；故不超过105而与105互质的正整数有105×(1－13)(1－15)(1－17)=48个.1000=48×20＋48－8， 105×20=2100. 而在不超过105的与105互质的数中第40个数是86． ∴ 所求数为2186. 法二：6．设n m ,为正整数，具有性质：等式(171,)(171,)k m k n -=-对所有的正整数k 成立. 证明：17rm n =，其中r 是某个整数.。
欧拉定理是数论中的一个重要定理，它描述了数论中的一种特殊关系。
欧拉定理由瑞士数学家欧拉于18世纪首次提出，并对数论的发展起到了重要的推动作用。
欧拉定理的表述为：对于任意正整数a和m，若a与m互质，则aϕ(m)≡1( mod m)其中，ϕ(m)表示小于m且与m互质的正整数的个数，也被称为欧拉函数。
要理解欧拉定理的含义，首先需要了解什么是互质。
互质是指两个或多个正整数的最大公因数为1。
例如，2和3互质，而6和15不互质。
欧拉定理表明，当两个正整数a和m互质时，对a进行欧拉函数次方之后再对m取余，得到的结果一定等于1。
欧拉定理的一个重要推论是费马小定理。
费马小定理是欧拉定理的一个特殊情形，当m为质数时成立。
费马小定理表述为：对于任意正整数a和质数p，若a与p 互质，则a p−1≡1( mod p)欧拉定理及其推论在密码学、数论和计算机科学等领域有广泛的应用。
其中，欧拉定理的应用非常突出。
利用欧拉定理，可以通过快速幂算法高效地计算出a b( mod m)的结果，其中a、b和m均为正整数。
一个典型的应用场景是RSA算法，一种非对称加密算法。
RSA算法利用欧拉定理中的一个重要性质，即将两个质数相乘得到一个大整数n，并找到一个与n的欧拉函数的乘积等于1的整数e，再找到另一个整数d，满足e⋅d≡1( modϕ(n))。
其中，e被称为公钥，d被称为私钥。
对于要加密的明文m，可以通过公式c≡m e( mod n)计算出密文c，并通过c d≡m( mod n)计算出原始明文。
这样，只有持有私钥的人才能解密密文，保证了通信的安全性。
除了在密码学中的应用，欧拉定理还经常出现在数论中的证明中。
数论是研究整数性质的学科，而欧拉定理提供了一个重要的数论工具。
通过欧拉定理，我们能够更加深入地研究整数的性质，推导出更多的结论。
总之，欧拉定理是数论中的一颗明珠，它在密码学、数论和计算机科学等领域发挥了重要的作用。
欧拉定理不仅有着广泛的应用，而且相关的证明过程也能够帮助我们更好地理解数论中的其他定理。
费马小定理讲解费马小定理是数论中的一条重要定理，它由法国数学家费尔马在17世纪提出，并由欧拉进行证明。
这个定理的内容是关于模运算的性质，它可以在很多数论问题中发挥重要作用。
费马小定理的表述是：如果p是一个质数，a是任意整数，且a不是p的倍数，那么a的p-1次方与p相除的余数等于1。
换句话说，a的p-1次方模p的余数等于1。
例如，我们可以取p=7，a=3，根据费马小定理，3的6次方模7的余数等于1。
我们可以计算一下，3的6次方等于729，而729除以7的余数确实是1。
费马小定理有许多重要的应用。
首先，它可以用来判断一个数是否是质数。
如果对于给定的数n，对于所有不是n的倍数的a，a的n-1次方模n的余数都等于1，那么我们可以认为n是一个质数。
因为如果n是合数，那么一定存在一个不是n的倍数的a，使得a的n-1次方模n的余数不等于1。
费马小定理可以用来求解模方程。
例如，我们可以考虑求解x的2次方模p的余数等于a的问题。
根据费马小定理，我们知道x的p-1次方模p的余数等于1，所以x的2次方模p的余数等于a，可以转化成求解x的p-1次方模p的余数等于a的问题。
费马小定理还可以用来简化大数的幂运算。
例如，我们可以考虑计算2的100次方模7的余数。
根据费马小定理，2的6次方模7的余数等于1，所以2的100次方模7的余数等于2的(6*16+4)次方模7的余数，即2的4次方模7的余数，等于16。
费马小定理的证明较为复杂，这里就不展开了。
但是可以看出，费马小定理在数论中具有重要的地位，它为我们解决很多问题提供了有力的工具。
无论是在判断质数还是在求解模方程，费马小定理都能发挥重要的作用。
因此，我们在学习数论的过程中，不可忽视费马小定理的重要性。
兰州成功私立中学高中奥数辅导资料（内部资料）欧拉定理、费马小定理、孙子定理函数；互质的个数，称为欧拉中与，，，是个有互质，这样的同余类共中每一个数均与互质，那么与如果个剩余类有，则模、设m m m m m M m i m i Z k km i M m m m i i 21)(,)(1,,2,1,0},|{01ϕϕ-=∈+=>);(mod 1,1),(12)(m am a m m ≡=>ϕ则，、欧拉定理：设ki m MM m b M M b M M b M M x m b x m b x m b x m m m m m Mk i M m m m m m m k m m m p p p n n p p p n n p a ap m ax m x m a i i m a a m a a a m m a a a m m i ii k k k k k k i i ii i k k kk pi i m m k ,,2,1),(mod 1)(mod )(mod )(mod )(mod ,),,,2,1(,,6)11()11)(11()(5);(mod 4,1),()3();(),(mod )()2()()1(3''22'211'12211112121212121212121=≡+++≡≡≡≡====---==≡=≠≡+-其中有唯一解则同余方程组设个两两互质的正整数，是、、、孙子定理：设，则：的标准分解为：、若为素数，则、费马小定理：若的缩系；也是通过模的缩系，则是通过模且、若的充要条件是的一组缩系是模、、互质的整数，则个与是、、、若个数；的一组缩系含有、模、缩系的几种性质：）（ϕϕϕαααϕ原命题成立；上式不成立，则有：也是一组完全剩余系，另一方面又同理有：：的一组完全剩余系，则是、、证：的一组完全剩余系。
不是、、求证：，的一组完全剩余系，且分别是、、和、、、设例∴∴<<⇒≡++≡≡+∴≡≡+=≡+++∑∑∑∑∑=====,20|2)(mod 2)()()(mod 0)(mod )()(mod 2)(mod 22)1(|21111112122112121n n n n n b a b a n n n b an n b n n n n i a n a a a n b a b a b a n n b b b a a a ni i i i i ni i ini i ni ni i n n n n n}{}32{1,,,1),(mod 1321),(mod 122)(32,,,,}32{}32{21211)()((()(1)(12121212121i nk k i u u u i u u u u u u u u u k k nnu k u u u u ki u ki u x u u u u k k k k k 互素的无穷子数列中一定有一个任意两项数列依此方法一直下去项两两互素的子数列，是、数列＝理有：是欧拉函数，由欧拉定其中作项是两两互素的，记为中已有证明：设数列其中任意两项互素；中有一个无穷子数列，、证明：数列例））-+∴≤≤-≡-∴≤≤≡-=--++++ ϕϕϕϕϕϕϕ)11()(321,2,1)(,2,1),(,2,13111pp ppp p ppp p p p p p p p p p p p p p -=-=∴⋅⋅⋅⋅∴---ααααααααααααϕϕϕ互质其他的数均与个共有，，，，的倍数有：中是在又互质，并求中有多少个数是与问题即为：为素数解为素数。
欧拉定理在数学和许多分支中可以看到以欧拉命名的许多常数，公式和定理。
在数论中，Euler定理（也称为Fermat Euler定理或Euler 函数定理）是关于同余的性质。
欧拉定理以瑞士数学家莱昂哈德·欧拉（Leonhard Euler）的名字命名，被认为是数学界最精彩的定理之一。
欧拉定理实际上是费马小定理的推广。
此外，在平面几何中有欧拉定理，在多面体上有欧拉定理（在凸多面体中，顶点数-边数+面数= 2，即V-E + F = 2）。
在西方经济学中，欧拉定理也称为产出分配的净耗竭定理，这意味着在完全竞争的条件下，假设规模收益长期保持不变，则所有产品都足以分配给每个产品因子。
还有欧拉公式。
在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。
欧拉定理表明，若n,a为正整数，且n,a互质，则:证明将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （显然，共有φ(n)个数）我们考虑这么一些数：m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)1）这些数中的任意两个都不模n同余，因为如果有mS≡mR (mod n) （这里假定mS更大一些），就有：mS-mR=a(xS-xR)=qn，即n能整除a(xS-xR)。
但是a与n互质，a 与n的最大公因子是1，而xS-xR<n，因而左式不可能被n整除。
也就是说这些数中的任意两个都不模n同余，φ(n)个数有φ(n)种余数。
2）这些数除n的余数都与n互质，因为如果余数与n有公因子r，那么a*xi=pn+qr=r(……)，a*xi与n不互质，而这是不可能的。
(因为a*xi=pn+qr=r(……)，说明a*xi含有因子r，又因为前面假设n 含有因子r，所以a*xi和n含有公因子r，因此a*xi与n不互质)那么这些数除n的余数，都在x1,x2,x3……xφ(n)中，因为这是1~n中与n互质的所有数，而余数又小于n.由1）和2）可知，数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).故得出：m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)或者说a^[φ(n)]*(x1*x2*x3......xφ(n))≡x1*x2*x3......xφ(n)(mod n) 或者为了方便：K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3 (x)φ(n)。
欧拉定理，又称费马-欧拉定理或欧拉函数定理，是同余的一个性质，以瑞士数学家莱昂哈德·欧拉的名字命名。
这个定理被认为是数学界最精彩的定理之一。
在西方经济学中也被称为产出分配的穷竭定理。
这意味着在完全竞争的条件下，假设长期和中期的回报不变，所有的产品刚好足够分配给各种要素。
在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。
欧拉定理表明，若n,a为正整数，且n,a互质，则:证明将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （显然，共有φ(n)个数）我们考虑这么一些数：m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)1）这些数中的任意两个都不模n同余，因为如果有mS≡mR (mod n) （这里假定mS更大一些），就有：mS-mR=a(xS-xR)=qn，即n能整除a(xS-xR)。
但是a与n互质，a与n的最大公因子是1，而xS-xR2）这些数除n的余数都与n互质，因为如果余数与n有公因子r，那么a*xi=pn+qr=r(……)，a*xi与n不互质，而这是不可能的。
那么这些数除n的余数，都在x1,x2,x3……xφ(n)中，因为这是1~n 中与n互质的所有数，而余数又小于n.由1）和2）可知，数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).故得出：m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)或者为了方便：K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。
可知K{a^[φ(n)]-1}被n整除。
但K中的因子x1,x2……都与n 互质，所以K与n互质。
那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 （mod n），即a^[φ(n)]≡1 （mod n），得证。
数论定理一. 知识要点1. 欧拉定理和费尔马小定理缩系的定义：设m 为正整数，一个模m 的剩余类称为与模m 互素的余类，如果它中的数与m 互素．在与模m 互素的各个剩余类中分别取一个代表所构成的集合称为模m 的一组缩系．很显然，缩系具有以下性质：（1）模m 的缩系中含有ϕ（m ）个数（ϕ（m ）是小于m 的正整数中且与m 互素的个数）．（2）设()m r r ϕ ,1是ϕ（m ）个与m 互素的整数，则()m r r ϕ ,1模m 两两不同余．（3）设()1,=m a ，且()m r r ϕ ,1是模m 的一组缩系，则()m ar ar ar ϕ,,,21 是模m 的一组缩系．欧拉（Euler ）定理：设m 是大于1的整数，a 为整数，且()1,=m a ，则()()m a m mod 1≡ϕ．For personal use only in study and research; not for commercial use解：设()m x x x ϕ,,,21 是模m 的缩系．因为()1,=m a ，所以()m ax ax ax ϕ,,,21 也是模m 的缩系．这两个缩系分别乘起来得()()()m x x x ax ax ax m m mod ·2121ϕϕ ≡，且()()1,21=m x x x m ϕ ．从而()()m a m mod 1≡ϕ )()m a m mod 1≡ϕ．特别地，取m 为质数p ，有费尔马（Fermat ）小定理：设p 为质数，a 为整数，p a ，则()p a p mod 11≡-．它也常常写成()p a a p mod ≡．这里不需假定p a ，但p 应为素数．For personal use only in study and research; not for commercial use2. 中国剩余定理（孙子定理）中国剩余定理：设k m m m ,,21是两两互质的正整数，k a a a ,,,21 是任意整数，则同余方程组()()()⎪⎪⎩⎪⎪⎨⎧≡=≡.mod ,mod ,mod 2211k k m a x m a x m a x 对模k m m m 21有唯一解． 解：设()k i m m m m M iki ,,2,121 ==．依题设，有()1,=i i m M ，由裴蜀定理知，存在整数i b ，使得()i i i m b M mod 1≡，k i ,2,1=．对k k k M b a M b a M b a x +++= 222111，其中i i i M b a 能被k i i m m m m ,,,,111+-整除，而被i m 除的余数恰为i a ．从而∑==ki i i i M b a x 1是同余方程组的解．又设x ，y 均为同余方程组的解，则有y x m -1，y x m -2，…，y x m k -，即y x m m m k - 21，亦即()k m m m y x 21mod ≡．所以同余方程组对模k m m m 21有唯一解．3. 威尔逊（wilson ）定理威尔逊（wilson ）定理：设p 为质数，则()()p p mod 1!1-≡-．解：对于任意整数a ，且1≤a ≤p －1，由裴蜀定理知，存在整数a ’，使得()p aa mod 1'≡．称a ’为a 的数论倒数，且不妨设1≤a ’≤p －1．若有整数b ，满足()p ba mod 1'≡，则将此式两边同乘以a ，有()p a b mod ≡．这说明对于不同整数a ，1≤a ≤p －1，对应着不同的数论倒数a ’．又若整数a 的数论倒数是它自身，则()p a a mod 1≡⋅，亦即()()()p a a mod 011≡-+，故1≡a 或()p mod 1-．当2=p 时，显然有()()p p mod 1!1-≡-．当p ＞2时，有2，3，…，p －2这p －3个数恰好配成互为数论倒数的23-p 对数，故它们的积()()p p p mod 1123223≡≡-⨯⨯⨯- ．于是()()()p p p mod 1111!1-≡-⨯⨯≡-．4. 拉格朗日定理设p 为质数，n 是非负整数，多项式()01a x a x a x f n n +++= 是一个模p 为n 次的整系数多项式（即p a n ），则同余方程()()p x f mod 0≡ （※），至多有n 个解（在模p 的意义下）．证明：我们对n 用归纳法．当0=n 时，()0a x f =，因为p a 0，故同余方程（※）无解，命题成立．设当l n =时命题成立，则当1+=l n 时，若命题不成立，即同余方程（※）至少有2+l 个解，设为()p c c c x l mod ,,,221+≡ ①，我们考虑多项式()()()()()11111111c x a c x a c x a c f x f l l l l l l -++-+-=-+++ )()111c x a c l l-++- ()()()()x h c x x a c x l l 111-=+-=+ ②，其中()x h 是l 次多项式并且首项系数1+l a ，满足1+l a p ，从而由归纳假设知l 次同余方程()()p x h mod 0≡ ③，至多有个l 个解，但由①，②可知同余方程③至少有l ＋1个解．()p c c c x l mod ,,,232+≡ ，矛盾！故当1+=l n 时命题成立．综上所述，命题得证．二. 典型例题例1. 已知正整数k ≥2，k p p p ,,,21 为奇质数，且()1,21=k p p p a ．证明：()()()111121----k p p p a 有不同于k p p p ,,21的奇质因数．证明：由()1,21=k p p p a ，有()1,1=p a ．由费尔马小定理，()11mod 11p ap ≡-．又k ≥2，p p p ,,,32 k p p p ,,,32 为奇质数，则()()()211121---k p p p 为正整数，从而()()()()12111mod 121p ak p p p ≡--- ，即()()()12111121----k p p p ap .同理，()()()1211121--⋯--k p p p a能被P 2，P 3，…P k 整除，从而()()()1211121+-⋯--k p p p a不能被k p p p p ,,,,321 整除．注意到()()()211121---k p p p 是一个偶数，则()()()0211121≡---k p p p a或1（mod4），因此4不整除()()()1211121+---k p p p a，故()()()1211121+---k p p p a异于k p p p ,,,21 的奇质因数．所以()()()()()()⎪⎪⎭⎫ ⎝⎛-=-------1121111112121k k p p p p p p a a()()()⎪⎪⎭⎫⎝⎛+---1211121k p pp a有异于k p p p ,,,21 的奇质因数．例2. 对于自然数n ，如果对于任何整数a ，只要1-n a n ，就有12-na n ，则称n 具有性质P ．（34届IMO预）（1）求证：每个素数n 都具有性质P ． （2）求证：有无穷多个合数也都具有性质P ．证：（1）设p n =为素数且1-p a p ，于是()1,=p a ．由费尔马小定理知11--p a p ，而()()1111-+-=--a a a a p p ．故1-a p ，即()p a m o d 1≡．因此，()p a i mod 1≡，1,,2,1,0-=p i ．上述p 个同余式累和，得()p p a a a p p mod 0121≡≡++++-- ．故()()11212++++---a a a a p p p ，即12-pa p ．（2）设n 是具有性质P 的合数．若1-na n ，则()1,=a n ．由欧拉定理，有()()n a n mod 1≡ϕ，又因()n a n mod 1≡，由阶的性质知，()()()n a n n mod 1,≡ϕ．如果()()1,=n n ϕ，则()n a mod 1≡，于是利用（1）中证明可得12-na n ．因此，问题化为求无穷多个合数n ，使()()1,=n n ϕ．对任何素数p ≥5，取p －2的素因数q ，并令pq n =．这时()()()11--=q p n ϕ．因为()2-p q ，所以q (p －1)．又因q ≤p －2＜p ，故p (q －1)．因此，有()()1,=n n ϕ．对于每个这样的合数n ，若()1-na n ，则()1-a n ，因而()n a k mod 1≡，,2,1,0=k ．故()12-n a n ．因为对于每个素数p ≥5都可按上述程序得到具有性质P 的相应合数()p n ，且p ＜()p n ＜p 2，所以，有无穷多个合数n 具有性质P ．例3. 求所有整数n ≥2，满足：对所有的整数a ，b ，且()()1,,==n b n a ，()n b a mod ≡的充分必要条件是()n ab mod 1≡．（第41届IMO 预选题）解：若n 有奇素因子p ，设n p a||，记1n p n a⋅=，N a ∈．由中国剩余定理知，存在Z x ∈，使()n x mod 1≡，()a p x mod 2≡，则()1,=n x ．取x b a ==，即知()n x mod 12≡，从而()a p mod 14≡，故3=p ，且1=a ．因此()1,5=n ．取5==b a ，即知()n mod 125≡，从而24n ，故,12,8,6,4,3,2=n 24,12,8,6,4,3,2．下证：当n 取上述值时，满足条件．注意到，当2 a 时，有()8mod 12≡a ；当3 a 时，有()3mod 12≡a ，又24n ，32243⨯=，故必有()n a mo d 12≡（因为()1,=n a ）．对Z b a ∈,，且()()1,,==n b n a ，()n b a mod ≡，则()n ab mod 1≡．对Z b a ∈,，且()()1,,==n b n a ， ()n ab mod 1≡，则()n ab a mod 12≡≡．从而()a b a n -又()1,=n a ，有()b a n -，即()n b a mod ≡．综上，所求n 的值为2，3，4，6，8，12，24．例4. 求所有正整数n ，满足对所有的正整数n ，存在一个整数m ，使12-n是92+m 的因子．（第39届IMO 预选题）解：引理1：若p 为4k －1（k ≥2）型质数，则不存在Z m ∈，使()p m mod 92-≡．证明：设)p m m mod 31≡()p m m mod 31≡（∵()13,=p ，∴m 1存在），N m ∈1．又∵()p m mod 912-≡, ∴)(mod 121p m -≡．由费马小定理知，()()()p m m p p p mod 11121212111-=-≡=≡---，矛盾．引理2：当1≤i ＜j 时，有()112,1222=++ji )112,12=++j，且()13,122=+i ．证明：∵()()()()12mod 211121222222+≡+-≡+=+--i i j ij ij ，∴()()12,1212,12222=+=++ij i )()12,1212,122=+=++i j．又∵()()3mod 2111222≡+-≡+i i ，∴()()13,23,122==+i．对于原题，若()()9122+-m n，n ≥2．设t n S ⋅=2，2 t ．若t ≥3，则()()1212-+n t ，从而()()9122+-m t ．又必存在4k －1型素数p ，且3≠p ，()12-tp （否则，()4mod 1111121≡⨯⨯⨯≡-≡- t ，矛盾）．此时()92+m p ，与引理1矛盾．故t =1，从而S n 2=，且()()()1212123121212222+++⋅=--S S．由引理2及中国剩余定理知，存在N m ∈1，使()()12m o d 22211+≡-ii m ，i =1，2，…，s －1．故()((2m o d0121222211≡+≡+-i m )()()12mod 0122221+≡+≡-ii ．令13m m =，有()()()12mod 013922122-≡+=+Sm m ．因此，()()9122+-m n ．综上，所求正整数n 为2的幂次2i （i =1，2，…）．数论中存在性问题是最常见的，除了运用数论存在性定理来解决外，还需要有直接构造的能力．例5. 证明：每个正有理数能被表示成3333d c b a ++的形式，且其中a ，b ，c ，d 是正整数．（40届IMO 预选题）证明：设该正有理数为p ．（1）当⎪⎭⎫⎝⎛∈2,21p 时，()()()()333321121p p p p p -++-++=，其中2p －1，2－p ，p ＋1+∈Q ．（2）当p ≥2时，由于⎪⎭⎫ ⎝⎛∈⎪⎭⎫ ⎝⎛1,41323，故有N n ∈，使⎪⎭⎫ ⎝⎛∈⋅⎪⎭⎫ ⎝⎛2,21323p n，由（1）有333333333322132132213223⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⋅⎪⎭⎫ ⎝⎛=p p p p p n n n n n ．（3）当⎥⎦⎤ ⎝⎛∈21,0p 时，由于()4,1233∈⎪⎭⎫ ⎝⎛，故有N n ∈，使⎪⎭⎫ ⎝⎛∈⋅⎪⎭⎫ ⎝⎛2,21233p n ，由（1）有333333333232123123212332⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⎪⎪⎭⎫⎝⎛-⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛⋅⎪⎭⎫ ⎝⎛=p p p p p n n n n n ．综上，总有+∈Q d c b a m 1111,,,,，使()()31313131313131313d c mb ma d c b a m p ++=++⋅=,设ma 1，mb 1，c 1，d 1的分母公倍数为n ，则取N mna a ∈=1，N mnb b ∈=，N nc c ∈=1，N nd d ∈=1，且3333dc b a p ++=．结论成立． 说明：这里是直接构造证明，首先发现恒等式()()()()333321121p p p p p -++-++=，进一步对p ≥2，或0＜p ≤21构造．例6. 证明：不存在非负整数k 和m ，使得()mk k ！14848+=+．证明：注意到0=k 或0=m 时，上述不定方程无解，于是，可设满足上述方程的k ，m 为正整数．（1）若1+k 为合数，设pq k =+1，2≤p ≤q ，注意到，应有48 | k ！．故k≥6，于是1＜2p ≤k ，故（1+k ）| k ！，进而（1+k ）| 48，结合1+k ≥7，可知1+k =8，12，24或48，分别代入，两边约去48后，可得矛盾．（2）若1+k 为质数，由威尔逊定理，可知k ！()1mod 1+-≡k ，于是，1+k | 47，进而1+k =47，这要求46！＋48=48×47m ①，从而m ＞1，两边除以48可知m 47148!46=+，两边模4，可知()()4mod 11≡-m ，故m 为偶数．设m =2k ，则由①可知2()()14714748!46+-=k k ，由232 |48!46，而()23mod 2147≡+k，故232 | 147-k，利用二项式定理()()223mod 146123247+≡+⨯=k k，从而23 | k ，进而m ≥46，这时，①式右边比左边大．矛盾．注：一般地，若n ＞4，且n 为合数，则n |（n －1）！，依此可以证明威尔逊定理的逆定理也成立． 例7. 设p 是质数，证明：存在一个质数q ，使得对任意整数n ，数p n p-不是q 的倍数．（第44届IMO 试题）证明：由于()212mod 1111p p p p p p p p p +≡++++=--- ．则11--p p p 中至少有一个质因子q ，满足q 对2p 的模不等于1。
求解高中数学常见的数论问题数论是数学的一个分支，也是高考中的必考内容之一。
数论作为数学领域最古老的分支之一已经发展了几千年，而且在当今科技日益发展的时代，仍然有着广泛的应用，不仅仅停留在纯理论层面。
在高中中学习数论常见的问题可以帮助我们深入理解数学知识并为日后深入数学领域打下基础。
本文将着重讲述在高中数学中常见的数论问题及其求解。
一、质数判断质数是指只能被1和本身整除的自然数。
判断一个数是否为质数有两种方法。
第一种是试除法。
即从2开始，一直试到这个数本身-1，如果都除不尽，则是质数。
这种方法的时间复杂度较高。
在这里，我们介绍一种更为快捷的方法：对于一个数n，如果存在a，b两个数，a*b=n并且a≤√n，则n不是质数。
反之，如果经过√n内的所有数试除都无法完全整除n，则n是质数。
二、最大公约数和最小公倍数在数论中，最大公约数和最小公倍数是非常重要的概念。
最大公约数是指多个数中能够同时整除的最大自然数，最小公倍数则是指多个数中能够整除这些数的最小自然数。
求解最大公约数和最小公倍数有多种方法。
以下是两种常见的方法：1.辗转相除法：这是一种简单易用的方法。
假设求m和n的最大公约数。
先用m去除n，得到余数r1，如果r1=0，则n是m的因数，m和n的最大公约数是n。
否则，用n去除r1，得到余数r2，如此下去，直到余数为0。
此时，最大公约数就是上一个余数。
2.枚举法：将两个整数中的较小者从1开始，依次往下枚举，若能够同时被两个整数整除，则就找到了最小公倍数。
最大公约数也可以用相同的方法枚举，然后再寻找它们的公共约数中的最大值。
这种方法的时间复杂度较高，一般不常用。
三、同余方程和中国剩余定理同余方程是指形如ax≡b(mod m)的方程，其中a，b，m为给定的整数，而x是未知量。
解同余方程是数论的重要内容之一。
一种简便的解法是用扩展欧几里得算法，这种算法不仅可以求解同余方程，还可以解决很多其他数论问题。
同余方程还经常与中国剩余定理一起使用。
