注：这就是著名的弗罗贝尼乌斯 （Frobenius）问题。这时n=2的情况， 在19世纪，由西勒维斯特（Sylvester） 证明了这个定理。
如：5x+6y=C无非负整数解的最大整数C=?
第一节 二元一次不定方程
• 思考与练习2.1 • 1、解下列不定方程： （1）15x+25y=100 （2）306x-360y=630 • 2、把100分成两份，使一份可被7整除， • 一份可被11整除。 • 3、设a与b是正整数，(a, b) = 1，则任何大
，tZ，于是由x ，但区间的长度是
0，y 0 N ，故此区来自abab
间内的整数个数为[ N ]或[ N ] 1。 ab ab
第一节 二元一次不定方程
例4：证明：二元一次不定方程 ax by =N
(a, b) = 1，a＞1，b＞1,当N＞ab a b
时有非负整数解，但是N= ab a b时则 不然。（不再给予证明）
于ab a b的整数n都可以表示成n = ax by的形式，其中x与y是非负整数，但是n = ab a b不能表示成这种形式。
第二节 多元一次不定方程
• 设a1, a2, , an是非零整数，N是整数，称 关于未知数x1, x2, , xn的方程
•
a1x1 a2x2 anxn = N (1)
第一节 二元一次不定方程
•
(3)
写出方程(1)的解
x y
x0 y0
b1t a1t
，t
Z
，
其中(a, b)c1
c，a1
a (a, b)
，b1
b (a, b)
。
• 例1：求7x+4y=100的一切整数解
• 解：因（7，4）=1，从而原方程有解。 其特解为x0 =0，y0 =25。
• 故其一切整数解为x=4t，y=25-7t tZ。
tZ。
第一节 二元一次不定方程
• 例3：证明：二元一次不定方程ax by = N，a >
0，b > 0，(a, b) = 1的非负整数解的个数为
• [ N ]或[ N ] 1。
ab
ab
• 证明：二元一次不定方程ax by = N的一切整数
解为 得
x y
y0
x0 bt y0 at
t x0
• 因(a，b) a，(a，b) b，从而(a，b)c
• 充分性：若(a，b)c，则c=c1(a，b)， c1∈Z。由裴蜀恒等式知，存在s,t Z,使
得 as+bt=(a,b)。
• 令x0 =s c1, y0 =t c1 ,即得 a x0 b y0= c 。故 （1）式有整数解（x0, y0）。
第一节 二元一次不定方程
• 是n元一次不定方程。
• 若存在整数x10, x20, , xn0满足方程(1)， 则称(x10, x20, , xn0)是方程(1)的解，或者 说x1 = x10，x2 = x20，，xn = xn0是方程
• 定理2 设a，b，c是整数，若方程ax by
= c有解(x0, y0)，则它的一切解具有
•
x
y
x0 y0
b1t a1t
， tZ
(2)
•
的形式，其中
a1
a (a, b)
，b1
b (a, b)
。
第一节 二元一次不定方程
• 证明 容易验证，由式(2)确定的x与y满足方 程(1)。下面证明，方程(1)的解都可写成式(2) 中的形式。
初等数论(二)
Number Theory （Chap2）
信阳职业技术学院 夏子厚
第二章 不定方程
教学目的和要求 • （1）正确理解不定方程的基本概念。 • （2）熟练掌握二元一次不定方程的解法
和勾股不定方程解的结构，掌握二元一 次不定方程与多元一次不定方程解的关 系，会解三元一次不定方程和简单的高 次不定方程，会应用不定方程解某些实 际问题。 • 本章重点是二元一次不定方程和勾股不 定方程。
• 方程 (1)改写为 a x＋ b y＝ c
•
(a, b) (a, b) (a, b)
• 显然上式与方程(1)同解。
• 若可用观察法得到上式的特解x0，y0，则可进行 下一步；若不易用观察法得到，可利用辗转相
除法先求出a1x b1y =1的特解x0，、y0，，再求 a1x b1y = c1的特解x0，y0 。
第一节 二元一次不定方程
• 二元一次不定方程的形式： • ax by = c a,b,c∈Z,且ab≠0 (1) 不定方程的基本问题是 (1) 方程有没有解？ （2）若有解，怎样求出它的解？ 定理1 方程(1)有解的充要条件是 (a，b)c
第一节 二元一次不定方程
• 证明：必要性：若（1）式有一整数解 （x0, y0），则 a x0 b y0= c
第一节 二元一次不定方程
• 得 1=33-4×8
• =107-37×2-（37-33）×8
• =107-37×10+33×8
• =107-37×10+（107-37×2）×8
• =107×9-37×26
• =37×（-26）-107×（-9）
• 从而x0， = -26、y0， =-9 • 因此 x0 =-26×25，y0 =-9×25。 • 故 x=-26×25-107t，y=-9×25-37t
第一节 二元一次不定方程
• 例2：求111x－321y=75的一切整数解 • 解：因（111，321）=3，3︱75，从而
原方程有解。且其解与37x-107y=25的解 相同。 • 先利用辗转相除法求37x-107y=1的特解 （x0，、y0，）。 • 由107=37×2+33 • 37=33×1+4 • 33=4×8+1
b | x x0，因此存在整数t，使得
(a, b)
•
x
x0
b (a, b)
t，
y
y0
a (a, b)
t
•故
x x0 b1t，
y y0 a1t tZ
第一节 二元一次不定方程
• 注：定理1和定理2说明了解方程(1)的步骤：
• (1) 判断方程是否有解，即(a, b)c是否成立；
• (2) 若方程(1)有解，即(a, b)c成立。则把
• 设(x, y)是方程(1)的解，则ax0 by0 = ax by
= c，得到a(x x0) = b(y y0)，即：
a (a, b)
(x
x0 )
b (a, b)
(y
y0
)
第一节 二元一次不定方程
• 由此，以及( a , b ) 1 和第一章第三节
(a, b) (a, b)
定理4，得到
•