tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 理学 >>

第五节初等数论中的几个重要定理


第五节
基础知识

初等数论中的几个重要定理

定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的 定义

1 ≤ j ≤ s ,( x j , m) = 1 且对于任意的 a ∈ Z ,若 (a, m) =1,则有且仅有一个 x j 是 a 对模 m
的剩余, a ≡ x j (mod m) 。 即 并定义 ( m) = s = {1,2,L , m} 中和 m 互质的数的个数, ( m) 称为欧拉(Euler)函数。 而对于 m > 1 , (m) 就是 1,2, …, 这是数论中的非常重要的一个函数, 显然 (1) = 1 ,

m 1 中与 m 互素的数的个数,比如说 p 是素数,则有 ( p ) = p 1 。
引理: ( m ) = m ;可用容斥定理来证(证明略) 。 ∏(1- P )

1

P|m P为质数

(欧拉(Euler)定理)设 (a, m) =1,则 a ( m ) ≡ 1(mod m) 。 定理 1: 证明: 取模 m 的一个既约剩余系 b1 , b2 ,L , bs , ( s = ( m)) , 考虑 ab1 , ab2 ,L , abs , 由于 a 与

m 互质,故 ab j (1 ≤ j ≤ s ) 仍与 m 互质,且有 abi

ab j (1 ≤ i < j ≤ s ) ,于是对每个

1 ≤ j ≤ s 都能找到唯一的一个 1 ≤ σ ( j ) ≤ s , 使得 ab j ≡ bσ ( j ) (mod m) , 这种对应关系 σ 是
一一的,从而

∏(abj ) ≡ ∏bσ ( j) (modm) ≡ ∏bj (modm) ,∴ a s (∏bj ) ≡ (∏bj )(modm) 。
j =1 j =1 j =1 j =1 j =1

s

s

s

s

s

Q (m, ∏ b j ) = 1 ,∴ a s ≡ 1(mod m) ,故 a ( m ) ≡ 1(mod m) 。证毕。
j =1

s

分析与解答:要证 a ( m ) ≡ 1(mod m) ,我们得设法找出 ( m) 个 n 相乘,由 ( m) 个数我们 想 到 1,2,L , m 中 与 m 互 质 的 ( m) 的 个 数 : a1 , a 2 ,L , a ( m ) , 由 于 (a, m) = 1 , 从 而

aa1 , aa 2 ,L , aa ( m ) 也 是 与 m 互 质 的 (m) 个 数 , 且 两 两 余 数 不 一 样 , 故 a1 a 2 L a ( m ) ≡ aa1 , aa 2 ,L , aa ( m ) ≡ a (m ) a1 a 2 L a ( m ) ( mod m ), 而
( a1 a 2 L a ( m ) m )=1,故 a ( m ) ≡ 1(mod m) 。 这是数论证明题中常用的一种方法, 使用一组剩余系, 然后乘一个数组组成另外一组剩 余系来解决问题。

定理 2: 费尔马(Fermat)小定理)对于质数 p 及任意整数 a 有 a (费尔马(Fermat)小定理)

p

≡ a (mod p ) 。

若 则 p 若 则 设 p 为质数, a 是 p 的倍数, a ≡ 0 ≡ a (mod p ) 。 a 不是 p 的倍数, (a, p) =1 由引理及欧拉定理得 ( p) = p 1, a
*

( p)

≡ 1(modp) ,∴a p1 ≡1(mod ),a p ≡ a(mod ) ,由此即得。 p p
p 1

推论:设 p 为质数, a 是与 p 互质的任一整数,则∴a 定理 2 推论

≡ 1(mod p) 。

定理 3: 威尔逊(Wilson)定理)设 p 为质数,则 ( p 1)! ≡ 1(mod p ) 。 (威尔逊(Wilson)定理) 分析与解答:受欧拉定理的影响,我们也找 p 1 个数,然后来对应乘法。 证明:对于 ( x, p ) = 1 ,在 x,2 x,L , ( p 1) x 中,必然有一个数除以 p 余 1,这是因为

x,2 x,L , ( p 1) x 则好是 p 的一个剩余系去 0。
从而对 x ∈ {1,2,L p 1}, y ∈ {1,2,L , p 1} ,使得 xy ≡ 1(mod p ) ; 若 xy1 ≡ xy 2 (mod p ) , ( x, p ) = 1 ,则 x( y1 y 2 ) ≡ 0(mod p ) , p | ( y1 y 2 ) ,故 对于 y1 , y 2 ∈ {1,2,L , p 1} ,有 xy1

xy 2 (mod p) 。即对于不同的 x 对应于不同的 y ,即

1,2,L , p 1 中数可两两配对,其积除以 p 余 1,然后有 x ,使 x 2 ≡ 1(mod p ) ,即与它自
己配对,这时 x 2 1 ≡ 0(mod p ) , ( x + 1)( x 1) ≡ 0(mod p ) , x ≡ 1 或 x ≡ 1(mod p ) ,

x = p 1 或 x = 1。
除 x = 1, p 1 外, 别的数可两两配对, 积除以 p 余 1。 ( p 1)!≡ ( p 1) 1 ≡ 1(modp) 。 故 定 义 : 设 f j (x) 为 整 系 数 多 项 式 ( 1 ≤ j ≤ k ) 我 们 把 含 有 x 的 一 组 同 余 式 ,

f j ( x) ≡ 0(mod m j ) ( 1 ≤ j ≤ k )称为同余方组程。特别地, ,当 f i (x ) 均为 x 的一次整系数
多项式时,该同余方程组称为一次同余方程组.若整数 c 同时满足: f j (c ) ≡ 0(mod m j )

1 ≤ j ≤ k ,则剩余类 M c = {x | x ∈ Z , x ≡ c(mod m)} (其中 m = [m1 , m2 ,L, mk ] )称为同
余方程组的一个解,写作 x ≡ c (mod m) 定理 4 : 中国剩余定理 ) 设 m1 , m2 ,L, mk 是两两互素的正整数,那么对于任意整数 (

a1 , a2 , L , ak ,一次同余方程组 x ≡ a j (mod m j ) , 1 ≤ j ≤ k 必有解,且解可以写为:

x ≡ M 1 N1a1 + M 2 N 2 a 2 + L + M k N k ak (mod m)
这里 m = m1m2 L mk , M i =

m (1 ≤ i ≤ k ) ,以及 N j 满足 M j N j ≡ 1(mod m j ) , 1 ≤ j ≤ k mi

(即 N j 为 M j 对模 m j 的逆) 。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解,而对于解的 形式并不重要。 (拉格郎日定理 定理 5: 拉格郎日定理)设 p 是质数, n 是非负整数,多项式 f ( x ) = a n x + L + a1 x + a0 (拉格郎日定理)
n

是一个模 p 为 n 次的整系数多项式(即 p a n ) ,则同余方程 f ( x ) ≡ 0(mod p ) 至多有 n 个 解(在模 p 有意义的情况下) 。
s 定理 6:若 l 为 a 对模 m 的阶, s 为某一正整数,满足 a ≡ 1(mod m) ,则 s 必为 l 的倍数。

以上介绍的只是一些系统的知识、方法,经常在解决数论问题中起着突破难点的作用。另外 还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用,有时也会起到
1(mod 8) n为奇数时 0(mod 9) 3整除n时 。这里我们 意想不到的作用,如: n 2 ≡ , n2 ≡ 0(mod 4) n为偶数时 0(mod 3) 3不整除n时 只介绍几个较为直接的应用这些定理的例子。

典例分析
1.设 例 1. (91, ab) = 1 ,求证: 91 | ( a
12

b12 ) 。

证明:因为 91 = 7 × 13 ,故由 (91, ab) = 1 知 (91, a ) = 1 ,从而 (7, a ) = 1, (13, a ) = 1 ,但是

(7) = 6, (13) = 12 ,故由欧拉定理得: a12 ≡ (a 6 ) 2 ≡ 12 ≡ 1(mod 7) , a12 ≡ 1(mod 13) ,
从而 a
12

≡ 1(mod 91) ;同理, b12 ≡ 1(mod 91) 。
12

于是, a

b12 ≡ 1 1 ≡ 0(mod 91) ,即 91 | (a12 b12 ) 。
n

注明:现考虑整数 a 的幂 a 所成的数列: a, a ,L, a ,L 若有正整数 k 使 a ≡ 1(mod m) ,
2
n k

则有 a ≡ a (mod m) ,其中 n = kq + r ,0 ≤ r < k ;
n r

因而关于 mod(m) , 数列 a, a ,L, a ,L 的项依次同余于 a, a ,L, a , a, a ,L, a , a, L 这 个数列相继的 k 项成一段,各段是完全相同的,因而是周期数列。如下例: 例 2.试求不大于 100,且使 11 | (3 + 7 + 4) 成立的自然数 n 的和。
n n

2

n

2

k

2

k

解:通过逐次计算,可求出 3 关于 mod 11 的最小非负剩余(即为被 11 除所得的余数)为:

n

3 ≡ 3(mod11),32 ≡ 9(mod11),33 ≡ 5(mod11), 34 ≡ 5 × 3 ≡ 4(mod11),35 ≡ 4 × 3 = 1(mod11)
因而通项为 3 的数列的项的最小非负剩余构成周期为 5 的周期数列: 3,9,5,4,1,3,9,5,4,1,……… 类似地,经过计算可得 7 的数列的项的最小非负剩余构成周期为 10 的周期数列: 7,5,2,3,10,4,6,9,8,1,……… 于是由上两式可知通项为 3 + 7 + 4 的数列的项的最小非负剩余,构成周期为 10(即上两
n n n n

式周期的最小公倍数)的周期数列: 3,7,0,0,4,0,8,7,5,6,……… 这就表明, 1 ≤ n ≤10时, 当 当且仅当 n = 3,4,6 时, + 7 + 4 ≡ 0(mod ) , 11 | (3n + 7 n + 4) ; 3 11 即
n n

又由于数列的周期性,故当 10k +1 ≤ n ≤ 10(k +1) 时,满足要求的 n 只有三个,即

n = 10k + 3,10k + 4,10k + 6
从而当1 ≤ n ≤ 100时,满足要求的 n 的和为:

∑(10k + 3) + (10k + 4) + (10k + 6) = ∑30k +13 = 30∑ k +10×13 = 30× 45 +130 = 1480.
k =0 k =0 k =0

9

9

9

小定理及其应用来举例: 下面我们着重对 Fetmat 小定理及其应用来举例

1 5 1 3 7 x + x + x 是一个整数。 5 3 15 1 5 1 3 7 证明:令 f (x ) = x + x + x ,则只需证 15 f ( x) = 3 x 5 + 5 x 3 + 7 x 是 15 的倍数即可。 5 3 15
例 3.求证:对于任意整数 x , 由 3,5 是素数及 Fetmat 小定理得 x 5 ≡ x(mod 5) , x 3 ≡ x(mod 3) ,则

3 x 5 + 5 x 3 + 7 x ≡ 3 x + 7 x ≡ 0(mod 5) ; 3 x 5 + 5 x 3 + 7 x ≡ 2 x + x ≡ 0(mod 3)
而(3,5)=1,故 3x + 5x + 7x ≡ 0(mod ) ,即 15 f ( x) 是 15 的倍数。所以 f ( x) 是整数。 15
5 3 13 。 例 4.求证: 2730 | n n ( n 为任意整数)

证明:令 f ( n) = n

13

n ,则 f (n) = n(n 1)(n + 1)(n 2 + n + 1)(n 2 n + 1)(n 6 + 1) ;

所以 f ( n) 含有因式 n 7 n, n 5 n, n 3 n, n 2 n 由 Fetmat 小定理,知 13| n13 n, 7| n 7 n,5 | n 5 n,3 | n 3 n,2 | n 2 n 又 13,7,5,3,2 两两互素,所以 2730= 13 × 7 × 5 × 3 × 2 能整除 n
13

n。

例 5.设 a, b, c 是直角三角形的三边长。如果 a, b, c 是整数,求证: abc 可以被 30 整除。

证明:不妨设 c 是直角三角形的斜边长,则 c = a + b 。
2 2 2

若2

a ,2 b ,2 c,则 c 2 = a 2 + b 2 ≡ 1 + 1 ≡ 0(mod 2) ,又因为 c 2 ≡ 1(mod 2) 矛盾!

所以 2| abc . 若 3

a ,3

b ,3

c ,因为 (3k ± 1) 2 ≡ 1(mod 3) ,则 a 2 + b 2 ≡ 1 + 1 ≡ 2(mod 3) ,又

c 2 ≡ 1(mod 3) ,矛盾!从而 3| abc .
若 5

a ,5 b ,5 c,因为 (5k ± 1) 2 ≡ 1(mod 5) , (5k ± 2) 2 ≡ 1(mod 5) ,
2 2

所以 a + b ≡ ±2 或 0(mod5)与 c 2 ≡ ±1(mod 5) 矛盾! 从而 5| abc . 又(2,3,5)=1,所以 30| abc . 下面讲述中国剩余定理的应用 例 6.证明:对于任意给定的正整数 n ,均有连续 n 个正整数,其中每一个都有大于 1 的平 方因子。 证明:由于素数有无穷多个,故我们可以取 n 个互不相同的素数 p1 , p2 ,L, p n ,而考虑同余 组 x ≡ i (mod p 2 ), i = 1,2,L , n
2 2 2



因为 p1 , p2 , L , pn 显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解。 于是,连续 n 个数 x + 1, x + 2,L, x + n 分别被平方数 p1 , p2 , L , pn 整除。
2 2 2

注: (1)本题的解法体现了中国剩余定理的一个基本功效,它常常能将“找连续 n 个正整数 ,而后者往往是比较容 具有某种性质”的问题转化为“找 n 个两两互素的数具有某种性质” 易解决的。 (2)本题若不直接使用素数,也中以采用下面的变异方法:由费尔马数

Fk = 2 2 + 1(k ≥ 0) 两两互素,故将①中的 pi2 转化为 Fi 2 (i = 1,2,L , n) 后,相应的同余式也
k

有解,同样可以导出证明。 例 7.证明:对于任意给定的正整数 n ,均有连续 n 个正整数,其中每一个都不是幂数。 分析:我们来证明,存在连续 n 个正整数,其中每一个数都至少有一个素因子,在这个数的 标准分解中仅出现一次,从而这个数不是幂数。 证明:取 n 个互不相同的素数 p1 , p2 ,L, p n ,考虑同余组 x ≡ i (mod p 2 ), i = 1,2,L , n 因为 p1 , p2 , L , pn 显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解。 对于 1 ≤ i ≤ n 因为 x + i = pi (mod pi ) ,故 pi | ( x + i ) ,但由①式可知 pi
2 2 2 2 2 2

( x + i ) ,即 pi 在

( x + i ) 的标准分解中恰好出现一次,故 x + 1, x + 2,L, x + n 都不是幂数。

例 8. 设 n, k 是给定的偶数, n > 0 且 k ( n 1) 是偶数。 证明:存在整数 x, y 使得 ( x, n) = ( y , n) = 1 ,且 x + y ≡ k (mod n) 。 证明:我们先证明,当 n 为素数幂 p 时结论成立。实际上,能够证明,存在 x, y 使
α

p xy 且 x + y = k :
若 p = 2 ,则条件表明 k 为偶数,此时可取 x = 1, y = k 1 ; 若 p > 2 ,则 x = 1, y = k 1 与 x = 2, y = k 2 中有一对满足要求。 一般情形下,设 n = p1 1 p 2 2 L p r r , i = 1,2, ,L, r 是 n 的一个标准分解,上面已经证明,对每
a a a

个 pi 存在整数 xi , yi 使得 pi xi yi 且 xi + yi = k (i = 1,2,L r ) ,而由中国剩余定理, 同余式 x ≡ xi (mod pi i )(i = 1,2,L , r ) 同余式 y ≡ yi (mod pi i )(i = 1,2,L, r )
α α

①有解 x , ②有解 y 。

现不难验证解 x, y 符合问题中的要求:因 pi xi yi ,故 pi xy (i = 1,2,L r ) , 于是 ( xy , n) = 1 ,又由①②知 x + y ≡ xi + yi (mod pi i )(i = 1,2,L , r ) , 故 x + y ≡ k (mod n) 。 注:此题的论证表现了中国剩余定理最为基本的作用:将一个关于任意正整数 n 的问题,化 为 n 为素数幂的问题,而后者往往是比较好处理的。 练习: 1.设 p 是给定的素数,证明:数列 {2 n n}( n ≥ 1) 中有无穷多项被 p 整除。 2.求证: f (x ) =
α

1 5 1 4 1 3 1 x + x + x x 为整值多项式。 5 2 3 30

3.数列:1,31,331,3331,………中有无穷多个合数。 4.设 n 为任意给定的正整数,证明:存在连续 n 个正整数,其中每一个都不是素数的幂。 5.设 m, n 为正整数,具有性质:等式 (11k 1, m) = (11k 1, n) 对所有的正整数 k 成立。 证明: m = 11 n ,其中 r 是某个整数。
r

第六节

不定方程

所谓不定方程,是指未知数的个数多于方程个数,且未知数受到某些(如要求是有理 数、整数或正整数等等)的方程或方程组。不定方程也称为丢番图方程,是数论的重要分支 学科,也是历史上最活跃的数学领域之一。不定方程的内容十分丰富,与代数数论、几何数

论、 集合数论等等都有较为密切的联系。 不定方程的重要性在数学竞赛中也得到了充分的体 现,每年世界各地的数学竞赛吉,不定方程都占有一席之地;另外它也是培养学生思维能力 的好材料,数学竞赛中的不定方程问题,不仅要求学生对初等数论的一般理论、方法有一定 的了解,而且更需要讲究思想、方法与技巧,创造性的解决问题。在本节我们来看一看不定 方程的基础性的题目。

基础知识
1.不定方程问题的常见类型: (1)求不定方程的解; (2)判定不定方程是否有解; (3)判定不定方程的解的个数(有限个还是无限个) 。 2.解不定方程问题常用的解法: (1)代数恒等变形:如因式分解、配方、换元等; (2)不等式估算法:利用不等式等方法,确定出方程中某些变量的范围,进而求解; (3)同余法:对等式两边取特殊的模(如奇偶分析) ,缩小变量的范围或性质,得出不定方 程的整数解或判定其无解; (4)构造法:构造出符合要求的特解,或构造一个求解的递推式,证明方程有无穷多解; (5)无穷递推法。 以下给出几个关于特殊方程的求解定理: 二元一次不定方程( (一)二元一次不定方程(组) 定义 1.形如 ax + by = c ( a, b, c,∈ Z , a, b 不同时为零)的方程称为二元一次不定方程。 定理 1.方程 ax + by = c 有解的充要是 (a, b) | c ; 定理 2.若 ( a, b) = 1 ,且 x0 , y 0 为 ax + by = c 的一个解,则方程的一切解都可以表示成

b x = x0 + t ( a , b) (t 为任意整数)。 a y = y0 t ( a, b )
定理 3. n 元一次不定方程 a1 x1 + a 2 x2 + L + a n xn = c ,( a1 , a2 , L , an , c ∈ N )有解的充要 条件是 (a1 , a2 , L , an ) | c . 方法与技巧: 1.解二元一次不定方程通常先判定方程有无解。若有解,可先求 ax + by = c 一个特解,从 而写出通解。当不定方程系数不大时,有时可以通过观察法求得其解,即引入变量,逐渐减 小系数,直到容易得其特解为止; 2. n 元一次不定方程 a1 x1 + a2 x2 +L+ an xn = c 时, 解 可先顺次求出 (a1, a2 ) = d2 , (d2 , a3 ) = d3 , ……, (dn1 , an ) = dn .若 d n c ,则方程无解;若 d n | c ,则方程有解,作方程组:

a1 x1 + a 2 x2 = d 2 t 2 d 2 t 2 + a 3 x3 = d 3 t 3 LLLL 求出最后一个方程的一切解,然后把 t n 1 的每一个值代入倒数 d t + a x = d t n 1 n 1 n 1 n 1 n 2 n 2 d n1t n1 + a n xn = c
第二个方程,求出它的一切解,这样下去即可得方程的一切解。 3. m 个 n 元一次不定方程组成的方程组,其中 m < n ,可以消去 m 1 个未知数,从而消 去了 m 1 个不定方程,将方程组转化为一个 n m + 1 元的一次不定方程。 高次不定方程( (二)高次不定方程(组)及其解法 1.因式分解法:对方程的一边进行因式分解,另一边作质因式分解,然后对比两边,转而 求解若干个方程组; 2. 同余法:如果不定方程 F(x1,L, xn ) = 0 有整数解,则对于任意 m∈N , 其整数解 (x1,L xn ) 满 , 足 F(x1 ,L, xn ) ≡ 0(mod ) , m 利用这一条件, 同余可以作为探究不定方程整数解的一块试金石; 3.不等式估计法:利用不等式工具确定不定方程中某些字母的范围,再分别求解; 4.无限递降法:若关于正整数 n 的命题 P (n) 对某些正整数成立,设 n0 是使 P (n) 成立的最 小正整数,可以推出:存在 n1 ∈ N ,使得 n1 < n0 成立,适合证明不定方程无正整数解。
*

方法与技巧: 1.因式分解法是不定方程中最基本的方法,其理论基础是整数的唯一分解定理,分解法作 为解题的一种手段,没有因定的程序可循,应具体的例子中才能有深刻地体会; 2.同余法主要用于证明方程无解或导出有解的必要条件,为进一步求解或求证作准备。同 余的关键是选择适当的模,它需要经过多次尝试; 3.不等式估计法主要针对方程有整数解,则必然有实数解,当方程的实数解为一个有界集, 则着眼于一个有限范围内的整数解至多有有限个,逐一检验,求出全部解;若方程的实数解 是无界的,则着眼于整数,利用整数的各种性质产生适用的不等式; 4.无限递降法论证的核心是设法构造出方程的新解,使得它比已选择的解“严格地小” ,由 此产生矛盾。 (三)特殊的不定方程 1.利用分解法求不定方程 ax + by = cxy ( abc ≠ 0) 整数解的基本思路: 将 ax+by = cxy abc≠ 0) 转化为 (x a)(cy b) = ab后,若 ab 可分解为 ab = a1b1 = L = ai bi ∈ Z , (

ai + a x = c 则解的一般形式为 ,再取舍得其整数解; bi + b y = c
2.定义 2:形如 x 2 + y 2 = z 2 的方程叫做勾股数方程,这里 x, y, z 为正整数。 定义 对于方程 x 2 + y 2 = z 2 ,如果 ( x, y ) = d ,则 d 2 | z 2 ,从而只需讨论 ( x, y ) = 1 的情形,

此时易知 x, y, z 两两互素,这种两两互素的正整数组叫方程的本原解。 定理 3.勾股数方程 x + y = z 满足条件 2 | y 的一切解可表示为:
2 2 2

x = a 2 b 2 , y = 2ab, z = a 2 + b 2 ,其中 a > b > 0, (a, b) = 1 且 a, b 为一奇一偶。
推论:勾股数方程 x + y = z 的全部正整数解( x, y 的顺序不加区别)可表示为:
2 2 2

x = (a 2 b 2 )d , y = 2abd , z = (a 2 + b 2 )d 其中 a > b > 0 是互质的奇偶性不同的一对正整
数, d 是一个整数。 勾股数不定方程 x + y = z 的整数解的问题主要依据定理来解决。
2 2 2 2 2 * 2 2 3.定义 3.方程 x dy = ±1,±4( x, y ∈ Z , d ∈ N 且不是平方数)是 x dy = c 的一种特 定义

殊情况,称为沛尔(Pell)方程。 这种二元二次方程比较复杂,它们本质上归结为双曲线方程 x 2 dy 2 = c 的研究,其中 c, d 都是整数, d > 0 且非平方数,而 c ≠ 0 。它主要用于证明问题有无数多个整数解。对于具 体的 d 可用尝试法求出一组成正整数解。如果上述 pell 方程有正整数解 ( x, y ) ,则称使

x + d y 的最小的正整数解 ( x1 , y1 ) 为它的最小解。
2 2 * 定理 4.Pell 方程 x dy = 1( x, y ∈ Z , d ∈ N 且不是平方数)必有正整数解 ( x, y ) ,且若设

它的最小解为 ( x1 , y1 ) ,则它的全部解可以表示成:

1 n n x n = 2 ( x1 + d y1 ) + ( x1 d y1 ) (n ∈ N * ) . 1 n n yn = ( x1 + d y1 ) ( x1 d y1 ) 2 d

[

[

]

]

上面的公式也可以写成以下几种形式: (1) xn + y n d = ( x1 + y1 d ) ; (2)
n

xn+1 = x1 xn + dy1 y n xn+1 = 2 x1 xn yn1 ; (3) . y n+1 = x1 y n + y1 xn y n+1 = 2 x1 y n yn1

2 2 * 定理 5.Pell 方程 x dy = 1( x, y ∈ Z , d ∈ N 且不是平方数)要么无正整数解,要么有无

穷多组正整数解 ( x, y ) ,且在后一种情况下,设它的最小解为 ( x1 , y1 ) ,则它的全部解可以

1 2 n 1 + ( x1 d y1 ) 2 n1 xn = 2 ( x1 + d y1 ) 表示为 (n ∈ N * ) 1 2 n 1 2 n 1 yn = ( x1 + d y1 ) ( x1 d y1 ) 2 d

[

[

]

]

n n n 费尔马(Fermat) 定理) 定理 6. (费尔马(Fermat)大定理)方程 x + y = z ( n ≥ 3 为整数)无正整数解。

费尔马(Fermat)大定理的证明一直以来是数学界的难题,但是在 1994 年 6 月,美国 普林斯顿大学的数学教授 A.Wiles 完全解决了这一难题。至此,这一困扰了人们四百多年的 数学难题终于露出了庐山真面目,脱去了其神秘面纱。

典例分析
例 1.求不定方程 37 x + 107 y = 25 的整数解。 解:先求 37 x + 107 y = 1 的一组特解,为此对 37,107 运用辗转相除法:
107 = 2 × 37 + 33 , 37 = 1 × 33 + 4 , 33 = 4 × 8 + 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 是方程 37 x + 107 y = 1 的一组特解,于是 x0 = 25 × (26) = 650 , y0 = 25 × 9 = 225 是 方 程 37 x + 107 y = 25 的 一 组 特 解 , 因 此 原 方 程 的 一 切 整 数 解 为 :
x = 650 + 107t 。 y = 225 37t

例 2.求不定方程 7 x + 19 y = 213 的所有正整数解。 解: 用原方程中的最小系数 7 去除方程的各项, 并移项得: = x 因为 x, y 是整数,故

3 5y = u 也一定是整数,于是有 5 y + 7u = 3 ,再用 5 去除比式的两 7 3 7u 3 2u 3 2u 边,得 y = = u + ,令 v = 为整数,由此得 2u + 5v = 3 。 5 5 5
经观察得 u = 1, v = 1 是最后一个方程的一组解,依次回代,可求得原方程的一组特解:

213 19 y 3 5y = 30 2 y + 7 7

x = 25 19t x0 = 25, y 0 = 2 ,所以原方程的一切整数解为: 。 y = 2 + 7t
例 3.求不定方程 3 x + 2 y + 8 z = 40 的正整数解。 解:显然此方程有整数解。先确定系数最大的未知数 z 的取值范围,因为 x, y , z 的最小值为 1,所以 1 ≤ z ≤

40 3 2 = 4。 8 32 3 x , 由上式知 x 是偶数且 2 ≤ x ≤ 10 2

当 z = 1 时, 原方程变形为 3 x + 2 y = 32 , y = 即 故方程组有 5 组正整数解,分别为

x = 2 x = 4 x = 6 x = 8 x = 10 , , , , ; y = 13 y = 10 y = 7 y = 4 y = 1 24 3 x ,故方程有 3 组正整数解,分别 2

当 z = 2 时,原方程变形为 3 x + 2 y = 24 ,即 y = 为:

x = 2 x = 4 x = 6 , , ; y = 9 y = 6 y = 3

当 z = 3 时,原方程变形为 3 x + 2 y = 16 ,即 y = 为:

16 3 x ,故方程有 2 组正整数解,分别 2

x = 2 x = 4 , ; y = 5 y = 2 x = 2 8 3x , 故方程只有一组正整数解, 为 。 2 y =1
2 9 2 4 6 2 6 3 2 2 5 3 4 2 3 2 1 4

当 z = 4 时, 原方程变形为 3 x + 2 y = 8 , y = 即 故原方程有 11 组正整数解(如下表) :

x y z

2 13 1

4 10 1

6 7 1

8 4 1

10 1 1

2 2 例 4.求出方程 x 7 y = 1 的所有正整数解。

解:先求最小解 ( x1 , y1 ) 。令 y = 1,2,3,L 当 y = 1 时, 1 + 7 y 2 = 8 ;当 y = 2 时, 1 + 7 y 2 = 29 ;当 y = 3 时, 1 + 7 y 2 = 64 = 8 2 。 所以 x 2 7 y 2 = 1 的最小解为 (8,3) ,于是:

1 1 n n n n x n = 2 ( x1 + d y1 ) + ( x1 d y1 ) = 2 [(8 + 3 7 ) + (8 3 7 ) ] (n ∈ N * ) 1 1 n n n n ( x1 + d y1 ) ( x1 d y1 ) = [(8 + 3 7 ) (8 3 7 ) ] yn = 2 d 2 7
例 5.在直角坐标平面上,以(199,0)为圆心,以 199 为半径的圆周上的整点的个数为多 少个? 解:设 A( x, y ) 为圆 O 上任一整点,则其方程为: y 2 + ( x 199) 2 = 199 2 ; 显然 (0,0), (199,199), (199,199), (389,0) 为方程的 4 组解。 但当 y ≠ 0,±199 时, ( y ,199) = 1 (因为 199 是质数) ,此时,199, y , | 199 x | 是一组勾股 数,故 199 可表示为两个正整数的平方和,即 199 = m + n 。
2 2

[ [

] ]

因为 199 = 4 × 49 + 3 ,可设 m = 2k , n = 2l + 1 ,则 199 = 4k 2 + 4l 2 + 4l + 1 = 4(k 2 + l 2 + l ) + 1 这与 199 为 4d + 3 型的质数矛盾! 因而圆 O 上只有四个整点 (0,0),(199199 (199199 (3890) 。 , ), , ), , 例 6.求所有满足 8 + 15 = 17 的正整数三元组 ( x, y , z ) 。
x y z

解:两边取 mod 8 ,得 ( 1) y ≡ 1(mod 8) ,所以 y 是偶数,再 mod 7 得 2 ≡ 3 z (mod 7) ,所 以 z 也是偶数。此时令 y = 2m, z = 2t ( m, t ∈ N )

于是,由 8 + 15 = 17 可知: 2
x y z

3x

= (17 t 15 m ) (17 t + 15 m ) ;
t m 3xs

由唯一分解定理:(17 15 ) = 2 ,(17 +15 ) = 2
t m s

,从而 17t =

1 s (2 + 23xs ) = 2 s1 + 23xs1 2

注意到 17 是奇数,所以要使 17t = 于是 17 15 = 2 。
t m

1 s (2 + 23xs ) = 2 s1 + 23xs1 成立,一定有 s = 1 。 2

当 m ≥ 2 时,在 17 15 = 2 的两边取 mod 9 ,得 ( 1) ≡ 2(mod 9) ,这显然是不成立的,
t m t

所以 m = 1 ,从而 t = 1, x = 2 。 。 故方程 8 + 15 = 17 只有唯一的一组解(2,2,2)
x y z 3 例 7. a 是一个给定的整数,当 a 为何值时, x, y 的方程 y + 1 = a ( xy 1) 有正整数解?在

有正整数解时,求解该不定方程。 解;若有质数 p | x 3 , p | xy 1 ,则 p | x ,从而 p | 1 ,矛盾!所以 ( x 3 , xy 1) = 1 。 因此 xy 1 | y 3 + 1 当且仅当 xy 1 | x 3 ( y 3 + 1) 。因为 x 3 ( y 3 + 1) = ( x 3 y 3 1) + ( x 3 + 1) , 显然 xy 1 | x 3 ( y 3 + 1) ,所以 xy 1 | y 3 + 1 当且仅当 xy 1 | x 3 + 1 。 (*) (1)若 y = 1 时, a =

2 ∈ Z ,所以 x = 2 或 x = 3 , a = 2 或 a = 1 ; x 1 2 ∈ Z ,所以 y = 2 或 y = 3 , a = 9 或 a = 14 ; y 1

(2)类似地,若 x = 1 ,则

(3)由于条件(*) ,不妨设 x ≥ y > 1 ; 若 x = y ,则 a =

y3 +1 1 = y+ ∈ Z ,所以 x = y = 2, a = 3 ; 2 y 1 y 1

若 x > y ,则因为 y 3 + 1 ≡ 1(mod y ), xy 1 ≡ 1(mod y ) ,所以存在 b ∈ N ,使得:

y3 +1 y3 +1 1 1 y + 1 = ( xy 1)(by 1) ,所以 by 1 = < 2 = y+ , by 1 < +1。 xy 1 y 1 y 1 y 1
3

因 为 y ≥ 2, b ∈ N , 所 以 必 有 b = 1 。 所 以 y 3 + 1 = ( xy 1)( y 1) , 故

y 3 = xy 2 xy y, y 2 = xy y 1
所以 x =

y2 +1 2 = y +1+ ∈ N ,所以 y = 2 或 y = 3 y 1 y 1

当 y = 2 时, x = 5 ; 当 y = 3 时, x = 5 ,对应的 a 为 1 或 2。 由条件(*)知 x = 2, y = 5 以及 x = 3, y = 5 也是原方程的解,对应的整数 a 为 14 或 9。 综上,当 a = 1,2,3,9,14 时原方程有整数解,它们分别是: (3,1)(5,2)(2,1)(5,3) , ; , , (2,2)(1,2)(3,5)(1,3)(2,5) ; , ; , 。 例 8.求证:边长为整数的直角三角形的面积不可能是完全平方数。 证明:假设结论不成立,在所有的面积为平方数勾股三角形中选取一个面积最小的,设其边 长为 x < y < z ,则

1 xy 是平方数,则必有 ( x, y ) = 1 。 2

因为 x 2 + y 2 = z 2 ,故存在整数 a > b > 0, a, b 中一奇一偶, ( a, b) = 1 ,使得(不妨设 y 是 偶数) x = a b , y = 2ab, z = a + b 。
2 2 2 2

由于

1 xy = (a b)(a + b)ab 是完全平方数,而知 a b, a + b, ab 两两互素,故它们是平方 2

数,即 a = p 2 , b = q 2 , a + b = u 2 , a b = v 2 ,所以 u 2 v 2 = 2q 2 即 (u + v)(u v) = 2q 2 因为 u , v 是奇数,易知 (u + v, u v) = 2 ,于是 u v 与 u + v 中有一个是 2r 2 ,另一个是

(2 s ) 2 ,而 q 2 = 4r 2 s 2 ;
另一方面, a = p 2 , b = q 2 , a + b = u 2 , a b = v2 得 p2 = a = (u 2 + v 2 ) = [(u + v) 2 + (u v) 2 ]

1 2

1 4

1 = [(2r 2 ) 2 + ( 2 s ) 4 ] = r 4 + 4 s 4 4
所以, r 2 ,2 s 2 , p 为边的三角形都是直角三角形, 以 其面积等于 但是 (rs ) =
2

1 2 r × 2 s 2 = ( rs ) 2 是平方数, 2

q2 b 1 = < ( a 2 b 2 ) ab = xy ,于是构造出了一个面积更小的勾股三角形,矛 4 4 2

盾!


推荐相关:

第五节初等数论中的几个重要定理.doc

第五节初等数论中的几个重要定理 - 第五节 基础知识 初等数论中的几个重要定理


初等数论中的几个重要定理.doc

初等数论中的几个重要定理 - 初等数论中的几个重要定理 基础知识 定义 (欧拉(


初等数论中的几个重要定理 高中数学竞赛.doc

初等数论中的几个重要定理 高中数学竞赛 - 初等数论中的几个重要定理 基础知识


第五节初等数论中的几个重要定理.doc

第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数


初等数论中的几个重要定理(竞赛必备).doc

初等数论中的几个重要定理(竞赛必备) - 初等数论中的几个重要定理 基础知识 定


初等数论中的几个重要定理.doc

初等数论中的几个重要定理 - 初等数论中的几个重要定理 基础知识 定义(欧拉(E


初等数论中的几个重要定理.doc

初等数论中的几个重要定理 - 初等数论中的几个重要定理 基础知识 定义(欧拉(E


初等数论中的几个重要定理.doc

初等数论中的几个重要定理 - 有关初等数论中的几个定理,费马小定理,剩余定理等等。... 初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 定义 的...


初等数论中的几个重要定理.doc

初等数论中的几个重要定理 - 初等数论中的几个重要定理 基础知识 定义(欧拉(E


初等数论中的几个重要定理 引理 和推论.doc

初等数论中的几个重要定理 引理 和推论 - 初等数论中的几个重要定理 基础知识


第四讲-几个定理.doc

第四讲-几个定理 - 高中竞赛初等数论选讲,共6讲... 初等代数选讲---第四讲 第四讲定义(欧拉(Euler)函数) 初等数论中的几个重要定理 一组数 x1 , x2 ,?...


初等代数几个重要理论.doc

初等代数几个重要理论 - 初等数论中的几个重要定理 基础知识 定义(欧拉(Eul


初等数论.doc

在本节我们来看一看不定方程的基础性的题目。 基础...初等数论中的几个重要定理基础知识 定义(欧拉(Euler...,所以 从而, 这样,星期一后的第 天将是星期五。...


初等数论定理.doc

初等数论(四)-几个著名的... 2页 1下载券 第五节初等数论中的几个......初等数论中的欧拉定理 7页 免费 初等数论中的几个重要定... 8页 1下载券...


初等数论中一些命题的多种证法.doc

按照验证群的五个方面 G 非空集合,g 为 G ...非常重视构造技巧的,好的 构造对于问题解决十分重要...【总结】初等数论中很多定理的证明不止一种方法,...


初等数论1整除性.doc

迷人的一个分支,目前我们仅学习初等数论中较浅的...地运用最基本、最重要的数论基础知识和重要定理来...(1) 第五讲 数论初步(2) 第六讲 基本初等函数:...


初等数论中的欧拉定理.doc

(mod n) 费马定理: a 是不能被质数 p 整除的正整数,则有 a^(p-1) ≡...第五节初等数论中的几个... 13页 5下载券 初等数论中的几个重要定......


最小自然数原理在初等数论中的几个应用_孙学功.pdf

阐述了最小自然数原理的重要性和应用问题. 定理(最小自然数原理) [1] 设 T...初等数论 是研究数的规律... 14页 免费 第五节初等数论中的几个... 13页...


初等数论中蕴含的数学思想.doc

初等数论中蕴含的数学思想 摘要: 摘要:通过对初等数论中的某些问题的解决思路的总结概括,以及对其中重要定理或引理的证明过程的回顾,探讨了数论中蕴含的几类数学思想...


初等数论(四)-几个著名的数论定理.doc

初等数论(四)-几个著名的数论定理_学科竞赛_高中教育_教育专区。初等数论(四)...初等数论中的几个重要定... 7页 1下载券 第五节初等数论中的几个... ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com