中国剩余定理在数论题中的应用
(2012-06-22 21:13:08)
标签:
数论整除连接自然数中国剩余定理剩余定理教育 |
分类: 杂谈 |
中国剩余定理在数论题中的应用
例题:
分析:
中国剩余定理
原文
算理
解释
1、分别找出能被两个数整除,而满足被第三个整除余一的最小的数。
k1%b==k1%c==0 && k1%a==1;
k2%a==k2%c==0 && k2%b==1;
k3%a==k3%b==0 && k3%c==1;
2、将三个未知数乘对应数字的余数再加起来,减去这三个数的最小公倍数的整数倍即得结果。
Answer = k1×m1 + k2×m2 + k3×m3 - P×(a×b×c);
P为满足Answer > 0的最大整数;
或者 Answer = (k1×m1 + k2×m2 + k3×m3)%(a×b×c) ;
证明
令T1=k1×m1,T2=k2×m2,T3=k3×m3;
因为 k1%a==1 ;所以 T1%a==m1;
对于 a,已知: T2%a==0,T3%a==0,T1%a==m1;
所以: Answer%a==m1;
因为:T1%b==0,T3%b==0,T2%b==m2 => Answer%b==m2
同理:Answer%c==m3;
又因为 a×b×c能同时整除 a b c,所以Answer ± P×(a×b×c)也是题目的解;
所以Answer是题目的解,又Answer = Answer % (a×b×c),所以Answer为最小解.
推广
例1:一个数被3除余1,被4除余2,被5除余4,这个数最小是几?题中3、4、5三个数两两互质。则〔4,5〕=20;〔3,5〕=15;〔3,4〕=12;〔3,4,5〕=60。为了使20被3除余1,用20×2=40;使15被4除余1,用15×3=45;使12被5除余1,用12×3=36。然后,40×1+45×2+36×4=274,因为,274>60,所以,274-60×4=34,就是所求的数。
例2:一个数被3除余2,被7除余4,被8除余5,这个数最小是几?题中3、7、8三个数两两互质。则〔7,8〕=56;〔3,8〕=24;〔3,7〕=21;〔3,7,8〕=168。为了使56被3除余1,用56×2=112;使24被7除余1,用24×5=120。使21被8除余1,用21×5=105;然后,112×2+120×4+105×5=1229,因为,1229>168,所以,1229-168×7=53,就是所求的数。
例3:一个数除以5余4,除以8余3,除以11余2,求满足条件的最小的自然数。题中5、8、11三个数两两互质。则〔8,11〕=88;〔5,11〕=55;〔5,8〕=40;〔5,8,11〕=440。为了使88被5除余1,用88×2=176;使55被8除余1,用55×7=385;使40被11除余1,40×8=320。用然后,176×4+385×3+320×2=2499,因为,2499>440,所以,2499-440×5=299,就是所求的数。
例4:有一个年级的同学,每9人一排多5人,每7人一排多1人,每5人一排多2人,问这个年级至少有多少人?题中9、7、5三个数两两互质。则〔7,5〕=35;〔9,5〕=45;〔9,7〕=63;〔9,7,5〕=315。为了使35被9除余1,用35×8=280;使45被7除余1,用45×5=225;使63被5除余1,用63×2=126。然后,280×5+225×1+126×2=1877,因为,1877>315,所以,1877-315×5=302,就是所求的数。
例5:有一个年级的同学,每9人一排多6人,每7人一排多2人,每5人一排多3人,问这个年级至少有多少人?题中9、7、5三个数两两互质。则〔7,5〕=35;〔9,5〕=45;〔9,7〕=63;〔9,7,5〕=315。为了使35被9除余1,用35×8=280;使45被7除余1,用45×5=225;使63被5除余1,用63×2=126。然后,280×6+225×2+126×3=2508,因为,2508>315,所以,2508-315×7=303,就是所求的数。(例5与例4的除数相同,那么各个余数要乘的“数”也分别相同,所不同的就是最后两步。)
练习:
1、一个数除以7余1,除以8余2,除以9余3,求满足条件的最小的自然数。
2、在10000以内,除以3余2,除以7余3,除以11余4的数有多少个?
3、满足除以5余1,除以7余3,除以8余5的最小自然数。
4、求满足除以6余3,除以8余5,除以9余6的最小自然数。
5、在小于1000的自然数中,除以4余3,除以5余2,除以7余4的最大自然数是多少?
6、有一个两位数,除以2与除以3都余1,除以4与除以5都余3,求这个数。