《初一寒假第3讲 不定方程》由会员分享,可在线阅读,更多相关《初一寒假第3讲 不定方程(6页珍藏版)》请在金锄头文库上搜索。
1、 第三讲 不定方程不定方程定义略。我们只关心整系数不定方程的整数解。若无特殊说明,默认 出现的方程是此类方程。 本讲讨论几种简单而且重要的不定方程 板块 1 一次不定方程像 ax+by=c ab0 这样的不定方程叫做二元一次不定方程 先给出有解条件:ax+by=c 存在整数解的条件是(a,b)|c (a,b)|c 不成立显然不定方程无整数解,以下证明(a,b)|c 成立则方程有 整数解。 设 a=kp b=kq c=km k=(a,b)则有(p,q)=1 代入原方程,px+qy=1 我们只要证明这个方程有整数解 移项得到 px =1-qy ,我们只要证明 p 的倍数可以除以 q 余 m 即可。
2、 考虑 p 2p 3p 4p 5p (q-1)p 这些数,其中没有 q 的倍数,并且除以 q 余数各不 相同。所以余数遍历 1,2,3q-1,其中必有 p 的 k 倍除以 q 余 m。 下面举例说明如何写出通解 【例】4x+7y=1 【解析】最简单易行的方法是先找到一个解。比如(2,-1) 然后 x 的值增加 7t,y 的值减少 4t,方程左边大小不变,等号成立。 所以得到方程的参数解(x,y)=(2+7t,-1-4t) t 是任意整数 再举一个常数项不是 1 的例子。 【例】31x+23y=185 【解析】3123=18 18523=81 我们需要 8 的倍数,除以 23 余 1。24 满足
3、条件。 所以原方程化为 31x=23(8-y)+1 类比 313=234+1 得到特解 x=3 8-y=4 (x,y)=(3,4) 进而得到通解(x,y)=(3+23t,4-31t) 其中 t 是任意整数 【例】4x+5y=21 【解析】 4|5y-21 4|y-1 y=4t+1 代入得到解其中 t 是任意整数5441xtyt 三元一次不定方程的例子 【例】2x+3y+7z=35 【解析】观察到 3y+7z 是偶数 也就是说 y,z 有相同的奇偶性设 y=a+b z=a-b 代入,得到参数解1725xbayabzab 其中 a,b 是任意整数【例】2x+3y+7z=35 【解析】观察到 3y+
4、7z 是奇数 也就是说 y,z 有不同的奇偶性 设 y=a+b+1 z=a-b 代入,得到参数解16251xbayabzab 其中 a,b 是任意整数再看三元一次不定方程组【例】100 1050500xyz xyz【解析】把 x 看成常数 10t,解出方程若要根是整数,t 是除以 4 余 2 的。45049 4 950 4tytz设 t=4k+2,得到原方程组的解 其中 k 是任意整数。4020 8849 98xk yk zk 从上面看出,一般做法就是把其中一个未知数当成常数,把不定方程看做有唯 一解的方程。求出解之后看看被当做常数的未知数必须满足什么同余条件。 【例】有两堆小石子,若第一堆给
5、第二堆 100 个,那么第二堆是第一堆的二倍。 相反,若从第二堆拿一些放到第一堆,第一堆就是第二堆的 6 倍。问至少多少 石子? 【解析】设两堆分别是 k+100,2k-100。这样就满足第一个条件。 第一堆就是第二堆的 6 倍说明总数是 7 的倍数。7|k还能看出第二堆超过总数的。1 77(2k-100)3k 7|k满足条件的最小 k 是 70。代入验算,满足条件。所以石子的最小数目是 210下面这个结论很经典 【例】a,b 是大于 1 的两个互质整数,ax+by 取不到 ab-a-b,可以取到大于 ab- a-b 的所有整数。其中 x,y 是非负整数。 【解析】若 ab-a-b=ax+by
6、 移项得到 ab=a(x+1)+b(y+1) (a,b)=1 所以 a|(y+1) y+1 至少是 a,这是不可能的。也就是说 ab-a-b 是取 不到的。 下面证明超过 ab-a-b 的任何整数都可以取到。首先,用 a 与若干个 b 凑成的不超过 ab 的最大整数记为。1k易知达不到 ab,并且不小于 ab-b+1。这是因为 a,b 互质。1k用 2a 和若干个 b 凑成的不超过 ab 的最大整数记为。2k同理达不到 ab,并且不小于 ab-b+1。2k同样的方法得到。这 b-1 个数各不相同。因为 a,b 互质。341,.bk kk这 b-1 个数的值都取自 ab-b+1,ab-b+2ab
7、-1 这 b-1 个数。 所以这 b-1 个数取遍 ab-b+1,ab-b+2ab-1 这 b-1 个数。 这 b-1 个数都至少用了一个 a,所以这些数分别减去 a,仍然是可以取到的。 这样我们得到了 ab-a-b+1,ab-a-b+2ab-a-1。 还得到了 ab-b+1,ab-b+2ab-1,ab。 同理能得到 ab-a-b+1,ab-a-b+2ab-b-1:ab-a+1,ab-b+2ab-1,ab。 所以得到了 ab-a-b+1 到 ab 这些数。至于那些大于 ab 的数,我们可以在已经得 到的数基础上,加上若干个 a 得到。这是因为我们得到了超过 a 个连续的整数。所以得不到的最大数
8、是 ab-a-b。利用这个结论看下面这道题。 【例】小华玩某种游戏,每局可随意玩若干次,每次的得分是 8, ,0 这三a 个自然数中的一个,每局各次得分的总和叫做这一局的总积分小华曾得到过 这样的总积分:103,104,105,106,107,108,109,110又知道他不可能 得到“83 分”这个总积分问:是多少?a 【解析】首先 a 应该是奇数,(a,8)=1。另外 103,104,105,106,107,108,109,110 都可以得到,他们是 8 个连续整数, 所以超过 102 的整数都能得到。 由上面结论得到8388102,1315aaa a 不是 15,因为 155+8=83。
9、.所以 a=13。若(p,q)=1,则存在整数 x,y 使得 px+qy=1。 这个结果叫裴蜀定理裴蜀定理。他是二元一次不定方程有解条件的特例。以下举例看看 有什么用。【例】用一个 19角的模具,还有一支铅笔,如何得到 1的角? 【解析】除了模具之外,我们还有周角=360。 (19,360)=1 这就为作图创造了条件1919-360=1可见只要作 19 个 19的角,使他们顶点重合,相邻两个角有一条公共边,那 么第 19 个角有一个边与第一个角的一条边夹角是 1。【例】m 个盒子中放着若干个球,每次在其中 n 个盒子中加一个球(nm 且 m 与 n 互质) ,求证一定可以在若干次操作后,使得每
10、个盒子中的小球数目相等。 【解析】因为(m,n)=1 由裴蜀定理,存在正整数 a,b 使得 an=bm+1 这个式子表明每操作 a 次,可以使 m-1 个盒子分别增加 b 个球,另外一个盒子 增加 b+1 个球。这样相当于我们可以把这 a 次操作定义为一次大操作,效果是 在任意盒子里加上一个球。 有了这个操作,可以在有限步之内使每个盒子中的小球数目相等。板块 2 其它不定方程我们来求的正整数解。其实只要求两两互质的解。222xyz观察到 x,y 一奇一偶,z 是奇数。不妨设 y 是奇数。移项得到2( )()()222xzyzy右边是两个互质数的乘积,左边是平方数。所以右边两项都是平方数。设,得
11、到22,22zyzyab其中 a,b 一奇一偶且互质(否则不满足 x,y,z 两两互质)22222xabybazab 所有两两互质的勾股数组都有此形式。【例】求的正整数解321xxy【解析】首先用较小的 x 试验,发现 x 取 1,2,3,4,5,6 时存在明显解 (x,y)=(1,1),(2,2),(4,5) 对于其他情况,只要两边对 4 取模,能看出 x 应该是偶数。 设 x=2t,代入得到22(31)(31)ttty右边是连续的偶数,不全是 4 的倍数。 所以右边的两个括号有一个是的倍数212t实际上时,两个括号都小于,不可能有解。3t 212t所以(x,y)=(1,1),(2,2),(
12、4,5)就是全部正整数解。【总结】这个方程从形式上看,很可能至多只对有限个正整数成立,也就是说 对足够大的正整数 n,方程是不成立的。所以我们采用的方法是“用大数破坏 条件” 。【例】x,y 都是正整数,求证不能都是平方数。221,43xyyx【解析】 化简得到221(1)xyx 2yx化简得到2243(1)yxy21xy 所以 y=2x 或 2x+1若 y=2x,是平方数,不是平方数。21xy243yx若 y=2x+1 不是平方数。21xy【例】m,n 都是 1 到 99 之间的整数。并且是平方数,这样的数2()3mnmn对(m,n)有几个? 【解析】22222()()3(2)()3(1)
13、1mnmnmnmnmnmnmn mn 这样的数对(m,n)有 98 个。 【例】求出任何一组满足方程 x2-51y2=1 的自正整数解 x 和 y。 【解析】2222251149141214(71)2 (7)xyyyyyyy y x=50 y=7 满足题意 【例】求方程 x+y=x2-xy+y2的整数解. 【解析】根据原式的对称性,设 x+y=a x-y=b 代入 这样可以消掉 xy 项222243(2)34aababa,b 的奇偶性是相同的 (a,b)=(3,1) (3,-1) (1,1) (1,-1) (4,0) (0,0)(x,y)=(2,1) (1,2) (1,0) (0,1) (2,
14、2) (0,0) 练习题练习题1n50,4n+5 和 7n+6 不互质,求正整数 n。解析:(4n+5,7n+6)|7(4n+5)-4(7n+6)(4n+5,7n+6)|11 如果 4n+5 和 7n+6 不互质,最大公约数只能是 11。.11|4n+5 解得7(mod11)n 满足条件的正整数 n 共有 4 个:7,18,29,40。 2有 10 个互不相同的自然数,证明他们的最小公倍数不小于最小数的 10 倍。解析:设这 10 个数是1210.aaa这个最小公倍数至少是的 1 倍,10a910aa所以至少是的 2 倍,的 3 倍9a8a以此类推,至少是最小数的 10 倍。 3求证:两个即约
15、分数之和是整数,那么这两个分数分母相同。解析:即约分数是整数acadbc bdbd所以 b|(ad+bc) b|ad 因为(a,b)=1 所以 b|d 同理 d|b 所以 b=d4a,b,c,d 是 4 个正整数,并且。证明 a+b+c+d 是合数。2222abcd解析:平方不改变奇偶性,所以 a+b+c+d 是个偶数。5 求证无整数解2286abc解析:平方数除以 8 的余数只能是 0,1,4 两个数的平方和除以 8 不可能是余 6 的。6 满足方程 x2+y2=x3的正整数对(x,y)的个数是( ).(A)0 (B)1(C)2(D)无限个(E)上述结论都不对解析由 x2+y2=x3得 y2=x2(x-1),所以只要 x-1 为自然数的平方,则方程必有正整数解.令 x-1=k2(k 为自然数),则为方程的一组通解.由于自然数有无限多个,故满足方程的正整数对(x,y)有无限多个,应选(D).