|
"津雲"客戶端 |
|||
餘數問題中的一個重要問題就是同餘問題,在同餘問題解決過程中,推薦代入法和口訣法兩大類。其中口訣法是公倍數做周期,餘同取餘,和同加和,差同減差的應用,但是有時候會出現餘不同,和不同並且差也不同的現象,這就需要我們采用剩餘定理進行解決。下面就由華圖公務員考試研究中心為大家進行詳細講解。
剩餘定理的原理是在“孫子問題”現代數論中的一個一次同餘問題,它最早出現在我國公元四世紀的數學著作《孫子算經》中。《孫子算經》卷下“物不知數”題說:有物不知其數,三個一數餘二,五個一數餘三,七個一數又餘二,問該物總數幾何?顯然,這相當於求不定方程組
N=3x+2,N=5y+3,N=7x+2
的正整數解N,或用現代數論符號表示,等價於解下列的一次同餘組:
《孫子算經》所給答案是N=23。由於孫子問題數據比較簡單,這個答數通過試算也可以得到。但是《孫子算經》並不是這樣做的。“物不知數”題的術文指出解題的方法:三三數之,取數七十,與餘數二相乘;五五數之,取數二十一,與餘數三相乘;七七數之,取數十五,與餘數二相乘。將諸乘積相加,然後減去一百零五的倍數。列成算式就是:
N=70×3+21×3+15×2-2×105。
這裡105是模數3、5、7的最小公倍數,容易看出,《孫子算經》給出的是符合條件的最小正整數。對於一般餘數的情形,《孫子算經》術文指出,只要把上述算法中的餘數2、3、2分別換成新的餘數就行了。以R
1、R
2、R
3表示這些餘數,那麼《孫子算經》相當於給出公式
N=70×R
1+21×R
2+15×R
3-P×105(p是整數)。
孫子算法的關鍵,在於70、21和15這三個數的確定。後來流傳的《孫子歌》中所說“七十稀”、“廿一枝”和“正半月”,就是暗指這三個關鍵的數字。《孫子算經》沒有說明這三個數的來歷。實際上,它們具有如下特性:
也就是說,這三個數可以從最小公倍數M=3×5×7=105中各約去模數3、5、7後,再分別乘以整數2、1、1而得到。假令k
1=2,K
2=1,K
3=1,那麼整數K
i(i=1,2,3)的選取使所得到的三數70、21、15被相應模數相除的時候餘數都是1。由此出發,立即可以推出,在餘數是R
1、R
2、R
3的情況下,
綜合以上三式又可得到
因為M=3×5×7可被它的任一因子整除,於是又有:
這裡P是整數。這就證明了《孫子算經》的公式。應用上述推理,可以完全類似地把孫子算法推廣到一般情形:設有一數N,分別被兩兩互素的幾個數a
1、a
2、……a
n相除得餘數R
1、R
2、……R
n,即
N≡Ri(modai)(i=1、2、……n),
只需求出一組數K
i,使滿足
那麼適合已給一次同餘組的最小正數解是
(P是整數,M=a
1×a
2×……×a
n),這就是現代數論中著名的剩餘定理。如上所說,它的基本形式已經包含在《孫子算經》“物不知數”題的解法之中。不過《孫子算經》沒有明確地表述這個一般的定理。
剩餘定理的原理比較繁瑣,不如直接套用解題方法進行快速解題更能解決行測中的類似問題。下面給出一些例題,對剩餘定理的解題方法加以熟練:
【例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,這個數最小是多少?
在1000內符合這樣條件的數有幾個?
【解析】題中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,就是所求的數。
再用(1000-53)/168得5,所以在1000內符合條件的數有5個。
【例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,就是所求的數。
對剩餘定理問題進行直接套用的方式是解決此類題目最快的方法,希望考生記住解題步驟,進行相關問題的解決。