第十二讲不定方程的整数解

上海市中学生数学业余学校讲义第十二讲不定方程的整数解【例题】例1、求方程5x－9y=18整数解的通解.例2、求方程90226yx非负整数解.例3、求方程213197yx的所有正整数解.（练习：求方程2510737yx的整数解）例4、将所有分母不大于99的最简分数从小到大排列，求与7617相邻且排在7617之前的一个数.例5、求方程162852100zyx的整数解.例6、某校举行数学竞赛，优胜者分一、二、三等奖三种，奖品为数学课外读物。如果一等奖每人奖5本，二等奖每人奖3本，三等奖每人奖2本，就共奖了34本。如果一等奖每人奖6本，二等奖每人奖4本，三等奖每人奖1本，就共奖了28本，求获得各奖的人数.例7、求不定方程2196313029cba正整数解的组数.【练习】1、下列方程中没有整数解的是哪几个？答：（填编号）①4x＋2y=11,②10x-5y=70,③9x+3y=111,④18x-9y=98,⑤91x-13y=169,⑥120x+121y=324.2、求方程5x+6y=100的正整数解.3、甲种书每本3元，乙种书每本5元，38元可买两种书各几本？4、一张试巻有20道选择题，选对每题得5分，选错每题反扣2分，不答得0分，小军同学得48分，他最多答对几道题？（答案：最多答对12题）5、第五世纪末，我国古代数学家张丘建在他编写的《算经》里提出了一个世界数学史上有名的“百鸡问题”.（答案：75250zyx或78184zyx或81118zyx或84412zyx）上海市中学生数学业余学校讲义第十二讲不定方程的整数解（教师用）我们知道，如果未知数的个数多于方程的个数，那么，一般来说，它的解往往是不确定的。例如方程32yx，或方程组235432zyxzyx，它们的解都是不确定的。象这类的方程或方程组就称为不定方程或方程组。如何求解整系数二元一次方程cbyax的整数解？一、二元一次方程整数解存在的条件：在整系数方程cbyax中，若ba,的最大公约数能整除c,则方程有整数解。即如果（a,b）|c则方程cbyax有整数解，显然ba,互质时一定有整数解。例如方程3x+5y=1,5x-2y=7,9x+3y=6都有整数解。返过来也成立，方程9x+3y=10和4x-2y=1都没有整数解，∵（9，3）＝3，而3不能整除10；（4，2）＝2，而2不能整除1。一般我们在正整数集合里研究公约数，（a,b）中的a,b实为它们的绝对值。二、二元一次方程整数解的求法：若方程cbyax有整数解，一般都有无数多个，常引入整数t来表示它的通解（即所有的解）。t叫做参变数。整数解的通解的表达方式不是唯一的。方法一，整除法：求方程5x+11y=1的整数解解：x=5111y=yyyy2515101(1),设kky(51是整数），则y=1-5k(2),把（2）代入（1）得x=k-2(1-5k)=11k-2∴原方程所有的整数解是kykx51211（k是整数）方法二，公式法：设cbyax①有整数解，其中ba,互质，且方程有一组整数解00yyxx，则通解是atyybtxx00其中t为整数证明：因为00,yx是方程①的整数解，当然满足cbyax00②，因此cbyaxatybbtxa0000)()(，这表明btxx0，atyy0也是方程①的解。反过来，若','yx是方程①的解，则有cbyax''③，③-②得)'()'(00yybxxa④，由于1),(ba，所以0'|yya，即atyy0'，其中t为整数，代入④得btxx0'，因此','yx都可以表示为btxx0，ayy0的形式，所以atyybtxx00表示方程①的一切整数解。用公式法求解二元一次方程组的关键是找到一组特殊解。例1、求方程5x－9y=18整数解的通解解：特解2,000yx，所以通解为tytx529（t为整数）例2、求方程90226yx非负整数解解：因为2)22,6(，所以方程两边均除以2得45113yx，特解3,400yx，所以通解为tytx33114（t为整数）由0330114tytx（t为整数），得01t当0t时，3,4yx；当1t时，0,15yx例3、求方程213197yx的所有正整数解。分析：这个方程的系数较大，用观察法去求其特殊解比较困难，碰到这种情况我们可用逐步缩小系数的方法使系数变小，最后再用观察法求得其解。解：用方程213197yx①的最小系数7除方程中的各项，并移项得753230719213yyyx，因为yx,为整数，故uy753也是整数，于是有375uy。再用5除以此式的两边得523573uuuy此时，由观察知2,1yu是方程的解。从而25x。于是方程①有一组解2,2500yx，所以它的一切解为tytx721925由于yx,为正整数，所以1,0t，因此原方程的正整数解为225yx或96yx（课内练习：求方程2510737yx的整数解）（答案：tx1078，ty373，t为整数）例4、将所有分母不大于99的最简分数从小到大排列，求与7617相邻且排在7617之前的一个数。解：设pq是与符合条件的数，且pq7617，其中nmqp,,,为正整数，则07617qp，于是17617qp，先考虑17617qp中满足99p且使p最大的正整数解。为此需先找到它的一个特解2,9qp，于是不定方程的通解为tqtp172,769，t为整数。这时在条件99p下，p最大为85，此时19q。另一方面pqpqp7676177617，可知，若27617qp，则8519761785761993813817627617ppqp所以在所给条件下，比7617小且最接近它的数为8519。例5、求方程162852100zyx的整数解。解：原方程化简为471325zyx，（1）把方程①分为两个方程(3)47(2)1325zuuyx对于方程（2），由观察得uuu213)(25于是方程（2）的解为1125213tuytux（I）对于方程（3），不难看出417)3(1于是方程（3）的解为22173tytu（II）由（I）（II）消去u得221211142567133tzttyttx（21,tt为整数）例6、某校举行数学竞赛，优胜者分一、二、三等奖三种，奖品为数学课外读物。如果一等奖每人奖5本，二等奖每人奖3本，三等奖每人奖2本，就共奖了34本。如果一等奖每人奖6本，二等奖每人奖4本，三等奖每人奖1本，就共奖了28本，求获得各奖的人数。解：设获得一、二、三等奖的人数分别为zyx,,人，于是由题意有)2()1(284634235zyxzyx从（1），（2）中消去z，得2257yx（3）由观察可得3,1yx是方程（3）的一组特解，所以（3）的解为uyux7351（4），将（4）代入（2）得102uz（5）而10,0zu是方程（5）的一组特解，所以（5）的解为tutz210，将tu代入（4），得tztytx2107351（t为整数）由于zyx,,都是正整数，所以t只能取0，于是得10,3,1zyx，因此获得一、二、三等奖的人数分别为1人，3人，10人。例7、求不定方程2196313029cba正整数解的组数。解：将原方程变为)2()1(2196)2()(312196)2()(29bacbacbcba因为cba,,是正整数，由方程（1）得)2(2196)(29cbcba2193)121(2196，所以291875cba（3）由方程（2）得2199)112(2196)2(2196)(31bacba所以，312970cba，由（3）（4）得71cba或72或73或74或75当71cba时，与原方程组合，解得,66,25acab由1b，得125a，解得1a或2。此时原方程有2组正整数解。同理，当75,74,73,72cba时，分别可得出原方程有17，33，24，10组正整数解。因此，原方程的正整数解共有86102433172组。练习1、下列方程中没有整数解的是哪几个？答：（填编号）②4x＋2y=11,②10x-5y=70,③9x+3y=111,④18x-9y=98,⑤91x-13y=169,⑥120x+121y=324.2、求方程5x+6y=100的正整数解。3、甲种书每本3元，乙种书每本5元，38元可买两种书各几本？4、一张试巻有20道选择题，选对每题得5分，选错每题反扣2分，不答得0分，小军同学得48分，他最多答对几道题？（答案：最多答对12题）5、第五世纪末，我国古代数学家张丘建在他编写的《算经》里提出了一个世界数学史上有名的“百鸡问题”。（答案：75250zyx或78184zyx或81118zyx或84412zyx）