五年级奥数春季实验班第12讲 计算综合之不定方程

第十二讲计算综合之不定方程模块一、基础不定方程的解法例1．不定方程x+y=2有组解，有组自然数解，有组正整数解。解：不定方程x+y=2有无穷组解，对于自然数有0+2=2，1+1=2，2+0=2，所以自然数解有3组，正整数解有1组。例2．求不定方程的正整数解：2x+3y=8.解：不定方程2x+3y=8，两边取模2的运算得，y≡0(mod2)，取y=2，x=1，所以方程的解是12xy。例3．求不定方程的正整数解：3x+5y=31.解：方程3x+5y=31，两边取模3运算，2y≡1(mod3)，得到y=2，x=7所以方程的解是72xy或25xy。例4．已知5x−14y=11，x和y都是正整数，x+y的最小值是。解：方程5x−14y=11，两边取模5的运算，y≡1(mod3)，解得x=5，所以方程的解是51xy，196xy，……，51415xkyk（k为自然数）。所以x+y的最小值是6.模块二、复杂不定方程的解法例5．小张带了5元钱去买橡皮和圆珠笔，橡皮每块3角，圆珠笔每支1元1角，问5元钱刚好买块橡皮和支圆珠笔。解：设买了x块橡皮，y支圆珠笔，所以3x+11y=50，两边取模3的运算得2y≡2(mod3)，所以y=1，x=13，或x=2，y=4，即方程的解是131xy或24xy。所以买13块橡皮和1支圆珠笔或2块橡皮和4支圆珠笔。例6．今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，凡百钱买鸡百只，则鸡翁、鸡母、鸡雏各只。解：设买到x只鸡翁，y只鸡母，则有100−x−y只鸡雏，则5x+3y+1003xy=100，整理得7x+4y=100，两边取模4的运算3x≡0(mod4)，所以x=0，y=25，方程的解为418xy，解得z=100−x−y=78，或811xy，z=81，或124xy，z=84.例7．现有一架天平和很多3克和4克的砝码，用这些砝码，不能称出的最大整数克质量是克。（砝码只能放在天平的一边）解：由于4−3=1，3×3−4×2=1，即如果称出的重量中有1个3，则将3换成4，则能称出下一个重量；如果称出的重量中有2个4，则可以将2个4换成3个3，也能称出下一个重量，从6以后的所有重量都可以称出来，所以不能称出的最大重量是5克。123456789101112131415……其中第三列中都能被3整除的都可以称出来；对第一列中4可以称出来，4往下的各数，只要再加若干个3克就能称出；对第二列中4的倍数8可以称出来，8往下的各数，只要再加若干个3克就能称出；所以不能称出的最大克重数是5克。例8．现有一架天平和很多17克和19克的砝码，用这些砝码，不能称出的最大整数克质量是克。（砝码只能放在天平的一边）解：解方程17x−19y=1，解得98xy，解方程19m−17n=1，解得910mn，所以17×9−19×8=1，19×16−17=287，287+b=17×(9b−1)+19×(16−8b)，(b≥1)，或287+b=17×18−19+(19×9b−17×10b)=19×(9b−1)+17×(18−10b)，即大于287的整数都可以写成17与19的线性组合，因此当b=0时，用这些砝码不能称出的最大克重是287克。物体质量b的值19的个数17的个数物体质量b的值19的个数17的个数2881882969124289201729710413290397298111332914116299125122925106300131422936215301146112947115302151512958314303167101、2、3、4、……16、1718、19、20、21、……33、3435、36、37、38、……50、51……其中第17列中都能被若干个17克的砝码称出来；对第2列中19可以称出来，19往下的各数，只要再加若干个17克就能称出；对第4列中38可以用2个19可以称出来，38往下的各数，只要再加若干个17克就能称出；……由此可以看出，在前16列中，分别可以找到19、38、57、……、19×(17−1)克数，它们都可以称出来，它们往下排列的各数，也都可以称出来，于是无法称出的最大整数是19×(17−1)−17.所以不能称出的最大克重数是19×(17−1)−17=19×17−19−17=287克。一般情况：现有一架天平和很多m克和n克的砝码（m，n互质），用这些砝码，不能称出的最大整数克质量是克。（砝码只能放在天平的一边）答案：mn−m−n；设不能称出的最大克质量为M克，即对于不定方程mx+ny=M没有自然数解，即求得的整数解为1xay，或11xanym，所以a=n−1，把x=n−1，y=−1，代入得到M=m×(n−1)−n，即方程mx+ny=mn−m−n无自然数解。研究不定方程mx+ny=mn−m−n有无正整数解，0x1mnmnnnmmn−1，又mx=mn−m−n−ny，所以x=n−1−(1)nym，m−1是整数，m，n互质，所以为使x为整数，只有1+y=m、m2、……，当1+y=m时，x=n−1−n=−1，不符合要求，当1+y=m2时，x=n−n−mn0，……，所以该不定方程没有正整数解，再研究不定方程mx+ny=mn−m−n+1的正整数解，有无m，n互质，存在大于1的p、q都小于m、n，使得pm−qn=1，则mx+ny=mn−m−n+pm−qn，ny=mn−m−n+pm−qn−mx，y=m−1−q+(1)mpxn，为使y为整数，则x+1−p=n，y=m−1−p+m，这样x、y都是正整数，符合条件。因为4×13−3×17=1（克），13×17=221（克），所以用这些砝码，不能称出的最大整数克不超过221克；然后根据191+b=13×(4b−1)+17×(12−3b)，可得191+b（b≥1）都可以写成17和13的线性组合，因此当b=0时，用这些砝码，不能称出的最大整数克重量是：17×(12−0)−13=191（克），据此解答即可．解答：根据分析，不能称出的最大整数克重量是：17×(12−0)−13=17×12−13=204-13=191（克）答：用这些砝码，不能称出的最大整数克重量是191克．随堂测试1．不定方程2x+3y=9有组正整数解。解：方程2x+3y=9，两边取模2运算得y≡1(mod2)，解得x=3，所以方程的解是31xy或03xy（舍去），所以原方程只有1组正整数解。2．求不定方程的正整数解：30x+11y=350，x=，y=。解：方程30x+11y=350，两边取11的模，8x≡9(mod11)，x=8，解得y=10，所以方程的解是810xy。3．求不定方程的正整数解：19x+9y=100，x=，y=。解：方程19x+9y=100，两边取模9运算，得x≡1，y=9，所以方程的解是19xy。4．已知12x−13y=25，x、y都是正整数，则x+y的最小值是。解：方程12x−13y=25，两边取模12的运算，得−y≡1，所以y=11，x=14，所以方程的解为1411xy或2723xy……，所以x+y的最小值是25.5．小丽计划用31元买2元、3元、4元三种不同价格的圆珠笔，每种至少买1支，那么她最多能买支。解：小丽可以买1支3元，1支4元的圆珠笔，剩余的24元都买2元一支的，这样一共可以买14支圆珠笔。6．有堆成一堆的100个小砝码，总重量为500克，已知只有1克、10克和50克三种砝码，在这堆砝码中，每一种砝码各有个、个、个。解：设50克的砝码有x个，10克的砝码有y个，1克的砝码有100−x−y个。则50x+10y+100−x−y=500，即49x+9y=400，取模9的运算，得4x≡4，解得x=1，y=39，z=60.所以有1克砝码60个，10克砝码39个，50克砝码1个。7．现有一架天平和很多个5克和8克的砝码，用这些砝码，不能称出的最大整数克质量是克。（砝码只能放在天平的一边）解：5x−8y=1，解得x=5，y=3，所以5×5−3×8=1，8×4−5=27，27+b=5×(5b−1)+8×(4−3b)，b0，这说明对于任意的b0，27+b一定可以写成5和8的线性组合。当b=0时，得到27就是不能称出的最大整数克质量。物体质量b的值5的个数8的个数281412921330360314323250433651……………………8．现有一架天平和很多个6克和8克的砝码，用这些砝码，不能称出的最大整数克质量是克。（砝码只能放在天平的一边）解：答案是无穷大的奇数克重；