关于中国剩余定理的一个应用一个数除以5余3,除以3余2,除以4余1.求该数的最小值?
关于中国剩余定理的一个应用
一个数除以5余3,除以3余2,除以4余1.求该数的最小值?
一个数能被5整除末尾必是0或5,余3,就加3,则为3或8;同理能被3整除末尾必是1,2,3,4,5,6,7,8,9或0.加2,没变;能被4整除末尾必是0,2,4,6,8.加1,为1,3,5,7,9.找出共有的,就一个3。末位是3,你从最小的13开始,找。最后结果是 53.这是笨办法。我不知道你说的剩余定理。
一个数除以5余3,除以3余2,
8满足以上2个条件
8÷4=2...0
增加5×3=15的倍数
15÷4=3...3
15×3÷4=11...1
8+45=53
除以4余1.
53
最小公倍数-7
设这个数为M,易知M>
除以4余1可知M=4a+1
M=4a+1=4(a-1)+5,因为M除以3余2,所以a-1是3的倍数
那么M可表示为M=12b+5,(这时a-1=3b)
M=12(b-4)+53,因为M除以5余3,所以b-4是5的倍数,
b最小为4时 M为满足条件的最小值,即M=53.
除以5余3,末位是3或8,除以4余1,是奇数,末位必须是3,最小,考察能否为两位数,如果十位是偶数,除以四一定会余三,因为十位是偶数除以二仍为整十(3暂不算),还可以再除以二,此时就余了3,所以只能是13,33,53,73,93,经检验,是53.
5和3的最小公倍数是15
3和4的最小公倍数是12
5和4的最小公倍数是20
3、4、5的最小公倍数是60
15×3除以4余1
12×3除以5余1
20×2除以3余
15×3×1+12×3×3+20×2×2-60×3=53
这个数最小是53