请问LZ: 363,X,Y是整数,14X+25Y最小正数可能值? ANS:1 怎么算的啊? -- by 会员 sanbaomao (2009/11/5 23:45:48)
363 & 379 14x+25y= 15x+24y= 能取到的最小值就是两数的最大公约数 因为14,25最大公约数为1,所以等号右边必能取到1,这个容易看出来但不好证明
我简单尝试一下: 不妨取x为正y为负,也就是要找到一个14x除以25余1,它即可满足14x+25y=1 而当x由1开始顺次取1,2,3,...,25时,14x除以25会余0~24所有的可能(在这只能列举说明了,余数分别是14,3,17,6,20,9,23,12,1,15,4,18,7,21,10,24,13,2,16,5,19,8,21,11,0,实在没有找到很好的证明方法,只能列举一下了)要满足14x+25y=1,取余1那个x即可,做题时没必要算出来
而对于15x+24y,则只能等于3的倍数,最小则是3,证明如下 设15x+24y=k,等号两端同除以3,得 5x+8y=k/3 由于等号左边是整数,所以等号右边必然也是整数,由此证明k一定是3的倍数
所以,这道题的结果就是两数的最大公约数 P.S.算了一下,14*9+25*(-5)=1 |