当前位置:首页 >> 学科竞赛 >>

第五讲-不定方程


初等代数选讲-----第五讲

第五讲

不定方程

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

都有较为密切的联系。 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 , y0 为 ax ? by ? c 的一个解,则方程的一切解都可以表示成

b ? x ? x0 ? t ? ? ( a, b) ( t 为任意整数)。 ? a ? y ? y0 ? t ? ( a, b) ?
定理 3. n 元一次不定方程 a1 x1 ? a2 x2 ? ? ? an xn ? c ,( a1 , a2 ,?, an , c ? N )有解的充要 条件是 (a1 , a2 ,?, an ) | c . 方法与技巧:

1

初等代数选讲-----第五讲

1.解二元一次不定方程通常先判定方程有无解。若有解,可先求 ax ? by ? c 一个特解,从 而写出通解。当不定方程系数不大时,有时可以通过观察法求得其解,即引入变量,逐渐减 小系数,直到容易得其特解为止; 2. 解 n 元一次不定方程 a1 x1 ? a2 x2 ? ? ? an xn ? c 时, 可先顺次求出 (a1 , a2 ) ? d 2 , (d 2 , a3 ) ? d3 , ……, (d n?1 , an ) ? d n .若 d n c ,则方程无解;若 d n | c ,则方程有解,作方程组:

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

方法与技巧: 1.因式分解法是不定方程中最基本的方法,其理论基础是整数的唯一分解定理,分解法作 为解题的一种手段,没有因定的程序可循,应具体的例子中才能有深刻地体会; 2.同余法主要用于证明方程无解或导出有解的必要条件,为进一步求解或求证作准备。同 余的关键是选择适当的模,它需要经过多次尝试; 3.不等式估计法主要针对方程有整数解,则必然有实数解,当方程的实数解为一个有界集, 则着眼于一个有限范围内的整数解至多有有限个,逐一检验,求出全部解;若方程的实数解

2

初等代数选讲-----第五讲

是无界的,则着眼于整数,利用整数的各种性质产生适用的不等式; 4.无限递降法论证的核心是设法构造出方程的新解,使得它比已选择的解“严格地小” ,由 此产生矛盾。 (三)特殊的不定方程 1.利用分解法求不定方程 ax ? by ? cxy(abc ? 0) 整数解的基本思路: 将 ax ? by ? cxy(abc ? 0) 转化为 ( x ? a)(cy ? b) ? ab 后,若 ab 可分解为 ab ? a1b1 ? ? ? 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 2 ? y 2 ? z 2 满足条件 2 | y 的一切解可表示为:

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

3.定义 3.方程 x ? dy ? ?1,?4( x, y ? Z , d ? N 且不是平方数)是 x ? dy ? c 的一种特
2 2 * 2 2

殊情况,称为沛尔(Pell)方程。 这种二元二次方程比较复杂,它们本质上归结为双曲线方程 x ? dy ? c 的研究,其中 c, d
2 2

都是整数, d ? 0 且非平方数,而 c ? 0 。它主要用于证明问题有无数多个整数解。对于具 体的 d 可用尝试法求出一组成正整数解。如果上述 pell 方程有正整数解 ( x, y ) ,则称使

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

3

初等代数选讲-----第五讲

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

1 ? n n ? xn ? 2 ( x1 ? d y1 ) ? ( x1 ? d y1 ) ? (n ? N * ) . ? 1 ( x1 ? d y1 ) n ? ( x1 ? d y1 ) n ? yn ? ? 2 d ?

?

?

?

?

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

? xn ?1 ? x1 xn ? dy1 y n ? xn?1 ? 2 x1 xn ? yn?1 ; (3) ? . y ? 2 x y ? y ? y n ?1 ? x1 y n ? y1 xn n ? 1 1 n n ? 1 ?

定理 5.Pell 方程 x 2 ? dy2 ? ?1( x, y ? Z , d ? N * 且不是平方数)要么无正整数解,要么有无 穷多组正整数解 ( x, y ) ,且在后一种情况下,设它的最小解为 ( x1 , y1 ) ,则它的全部解可以

1 ? xn ? ( x1 ? d y1 ) 2 n?1 ? ( x1 ? d y1 ) 2 n ?1 ? 2 表示为 ? (n ? N * ) ? 1 2 n ?1 2 n ?1 ( x1 ? d y1 ) ? ( x1 ? d y1 ) ? yn ? ? 2 d ?

?

?

?

?

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

典例分析
1.求不定方程 37x ? 107y ? 25的整数解。 解:先求 37x ? 107y ? 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 是方程 37x ? 107y ? 1 的一组特解,于是 x0 ? 25? (?26) ? ?650,

y0 ? 25? 9 ? 225 是 方 程 37x ? 107y ? 25 的 一 组 特 解 , 因 此 原 方 程 的 一 切 整 数 解 为 :
? x ? ?650? 107t 。 ? ? y ? 225? 37t 2.求不定方程 7 x ? 19y ? 213的所有正整数解。

x? 解: 用原方程中的最小系数 7 去除方程的各项, 并移项得:
因为 x, y 是整数,故

3 ? 5y ? u 也一定是整数,于是有 5 y ? 7u ? 3 ,再用 5 去除比式的两 7
4

213 ? 19 y 3 ? 5y ? 30 ? 2 y ? 7 7

初等代数选讲-----第五讲

边,得 y ?

3 ? 7u 3 ? 2u 3 ? 2u ? ?u ? ,令 v ? 为整数,由此得 2u ? 5v ? 3 。 5 5 5

经观察得 u ? ?1, v ? 1 是最后一个方程的一组解,依次回代,可求得原方程的一组特解:

? x ? 25 ? 19t 。 x0 ? 25, y0 ? 2 ,所以原方程的一切整数解为: ? ? y ? 2 ? 7t
3.求不定方程 3x ? 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 时, 原方程变形为 3x ? 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 时,原方程变形为 3x ? 2 y ? 24 ,即 y ? 为: ?

?x ? 2 ?x ? 4 ?x ? 6 ,? ,? ; ?y ? 9 ?y ? 6 ?y ? 3
16 ? 3 x ,故方程有 2 组正整数解,分别 2

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

?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 时, 原方程变形为 3x ? 2 y ? 8 , 即y? 故原方程有 11 组正整数解(如下表) :

x
y

2 13 1

4 10 1

6 7 1

8 4 1

10 1 1

z
2 2

4.求出方程 x ? 7 y ? 1的所有正整数解。 解:先求最小解 ( x1 , y1 ) 。令 y ? 1,2,3,?
2 2 2 2 当 y ? 1 时, 1 ? 7 y ? 8 ;当 y ? 2 时, 1 ? 7 y ? 29 ;当 y ? 3 时, 1 ? 7 y ? 64 ? 8 。

所以 x ? 7 y ? 1的最小解为 (8,3) ,于是:
2 2

5

初等代数选讲-----第五讲

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 ? 1992 ; 显然 (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), (199,199), (199,?199), (389,0) 。 6.求所有满足 8 ? 15 ? 17 的正整数三元组 ( x, y, z ) 。
x y z

解:两边取 mod 8 ,得 (?1) y ? 1(mod 8) ,所以 y 是偶数,再 mod 7 得 2 ? 3 z (mod7) ,所 以 z 也是偶数。此时令 y ? 2m, z ? 2t (m, t ? N )
3x t m t m 于是,由 8 ? 15 ? 17 可知: 2 ? (17 ? 15 ) (17 ? 15 ) ;
x y z

由唯一分解定理:(17 ? 15 ) ? 2 ,(17 ? 15 ) ? 2
t m s t m
t 注意到 17 是奇数,所以要使 17 ?

3 x?s

t ,从而17 ?

1 s (2 ? 2 3 x ? s ) ? 2 s ?1 ? 2 3 x ? s ?1 2

1 s (2 ? 2 3 x ? s ) ? 2 s ?1 ? 2 3 x ? s ?1 成立,一定有 s ? 1 。 2

于是 17 ? 15 ? 2 。
t m

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

所以 m ? 1 ,从而 t ? 1, x ? 2 。 故方程 8 ? 15 ? 17 只有唯一的一组解(2,2,2) 。
x y z

7. a 是一个给定的整数,当 a 为何值时, x, y 的方程 y ? 1 ? a( xy ? 1) 有正整数解?在有
3

正整数解时,求解该不定方程。
3 3 解;若有质数 p | x , p | xy ? 1 ,则 p | x ,从而 p | 1 ,矛盾!所以 ( x , xy ? 1) ? 1。

因此 xy ? 1 | y ? 1 当且仅当 xy ? 1 | x ( y ? 1) 。因为 x ( y ? 1) ? ( x y ? 1) ? ( x ? 1) ,
3 3 3 3 3 3 3 3

6

初等代数选讲-----第五讲

显然 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)类似地,若 x ? 1 ,则

2 ? Z ,所以 y ? 2 或 y ? 3 , a ? 9 或 a ? 14 ; y ?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(mody), xy ? 1 ? ?1(mody) ,所以存在 b ? N ,使得:

1 y3 ?1 y3 ?1 1 ?1。 , by ? 1 ? y ? 1 ? ( xy ? 1)(by ? 1) ,所以 by ? 1 ? ? 2 ? y? y ?1 xy ? 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 ,则
2 2 2

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

因为 x ? y ? z ,故存在整数 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
2 2 2 2 2 2 2 2

数,即 a ? p , b ? q , a ? b ? u , a ? b ? v ,所以 u ? v ? 2q 即 (u ? v)(u ? v) ? 2q
7

初等代数选讲-----第五讲

因为 u , v 是奇数,易知 (u ? v, u ? v) ? 2 ,于是 u ? v 与 u ? v 中有一个是 2 r ,另一个是
2

(2s) 2 ,而 q 2 ? 4r 2 s 2 ;
2 另一方面, a ? p 2 , b ? q 2 , a ? b ? u 2 , a ? b ? v 2 得 p ? a ?

1 2 2 1 (u ? v ) ? [( u ? v) 2 ? (u ? v) 2 ] 2 4

1 ? [( 2r 2 ) 2 ? (2s ) 4 ] ? r 4 ? 4s 4 4
所以, 以 r 2 ,2s 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

盾!

8


相关文章:
第五讲-不定方程
第五讲-不定方程_学科竞赛_高中教育_教育专区。高中竞赛初等数论选讲,共6讲初等代数选讲---第五讲 第五讲 不定方程 所谓不定方程, 是指未知数的个数多于方...
5第五讲 不定方程 学生版
5第五讲 不定方程 学生版_学科竞赛_高中教育_教育专区。第五讲 不定方程本讲概述一次不定方程 (1)a,b 是非零整数,d=(a,b),则对每个整数 c,不定方程 ...
第5讲、简单的不定方程
六年级(下)数学 3 月第 2 周 好爸爸文化教育 好爸爸文化教育 六年级数学特训资料第五讲、简单的不定方程学习导航: 1、 概念:所谓的不定方程,是指未知数的...
第九讲 不定方程
(http://www.sp910.com/) 第九讲 不定方程一、 二、 二元不定方程的解法...3、箱子里有乒乓球若干个,其中 25%是一级品,五分之几是二级品,其余 91 个...
奥数同余不定方程
奥数同余不定方程_数学_自然科学_专业资料。五年级奥数下册:第五讲 同余数的概念和性质 五年级奥数下册:第六讲 不定方程解应用题 五年级奥数下册:第五讲 同余数...
第六讲 不定方程解应用题
第五讲 同余的概念和性质 第六讲 能被30以下质数整... 第七讲 行程问题 第...第六讲 不定方程解应用题 大家已经学过简单的列方程解应用题, 一般都是未知数...
§5 不定方程2 Lecture 5 Indeterminate equation
34 费尔马 机密 第 2 页共 35 页 2012-3-25 第5讲 不定方程 Lecture 5...明朝程大位用歌谣给出了该题的解法:“三人同行七十稀, 五树梅花廿一枝,七...
6年级奥数-不定方程
【本讲重点】 求一次不定方程(组)的整数解 【...“百钱买百鸡”问题:鸡翁一,值钱五;鸡母一,值钱...【实践】已知有两堆水泥,若从第一堆中取出 100 ...
奥数
五年级: 五年级: *** (以下内容为五颗星) 第一讲速算与巧算、第十一讲小数...第三讲圆柱与圆锥、第四讲时钟问题 ** (以下内容为两颗星) 第五讲不定方程...
常渭鑫-按步骤求解不定方程问题
按步骤求解不定方程问题华图西安师资中心常渭鑫 如果未知数的个数多于方程的个数,这类问题就叫做不定方程。在考试中,部分考生认 为所有的不定方程组难度都非常高...
更多相关标签:
不定方程 | 不定方程的解法 | 不定方程的整数解 | 二元一次不定方程 | 不定方程的正整数解 | 不定方程解法 | 小学奥数不定方程 | 解不定方程 |