2013年浙江省考:同餘問題中的剩餘定理

2020-12-15 人民網教育

餘數問題中的一個重要問題就是同餘問題，在同餘問題解決過程中，推薦代入法和口訣法兩大類。其中口訣法是公倍數做周期，餘同取餘，和同加和，差同減差的應用，但是有時候會出現餘不同，和不同並且差也不同的現象，這就需要我們採用剩餘定理進行解決。下面就由華圖公務員考試研究中心為大家進行詳細講解。

剩餘定理的原理是在「孫子問題」現代數論中的一個一次同餘問題，它最早出現在我國公元四世紀的數學著作《孫子算經》中。《孫子算經》卷下「物不知數」題說：有物不知其數，三個一數餘二，五個一數餘三，七個一數又餘二，問該物總數幾何？顯然，這相當於求不定方程組

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分別換成新的餘數就行了。以R1、R2、R3表示這些餘數，那麼《孫子算經》相當於給出公式

N＝70×R1＋21×R2＋15×R3－P×105（p是整數）。

孫子算法的關鍵，在於70、21和15這三個數的確定。後來流傳的《孫子歌》中所說「七十稀」、「廿一枝」和「正半月」，就是暗指這三個關鍵的數字。《孫子算經》沒有說明這三個數的來歷。實際上，它們具有如下特性：

也就是說，這三個數可以從最小公倍數M＝3×5×7＝105中各約去模數3、5、7後，再分別乘以整數2、1、1而得到。假令k1＝2，K2＝1，K3＝1，那麼整數Ki（i＝1，2，3）的選取使所得到的三數70、21、15被相應模數相除的時候餘數都是1。由此出發，立即可以推出，在餘數是R1、R2、R3的情況下，

綜合以上三式又可得到

因為M＝3×5×7可被它的任一因子整除，於是又有：

這裡P是整數。這就證明了《孫子算經》的公式。應用上述推理，可以完全類似地把孫子算法推廣到一般情形：設有一數N，分別被兩兩互素的幾個數a1、a2、……an相除得餘數R1、R2、……Rn，即

N≡Ri（modai）（i＝1、2、……n），

只需求出一組數Ki，使滿足

那麼適合已給一次同餘組的最小正數解是

（P是整數，M＝a1×a2×……×an），這就是現代數論中著名的剩餘定理。如上所說，它的基本形式已經包含在《孫子算經》「物不知數」題的解法之中。不過《孫子算經》沒有明確地表述這個一般的定理。

剩餘定理的原理比較繁瑣，不如直接套用解題方法進行快速解題更能解決行測中的類似問題。下面給出一些例題，對剩餘定理的解題方法加以熟練:

【例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，就是所求的數。

對剩餘定理問題進行直接套用的方式是解決此類題目最快的方法，希望考生記住解題步驟，進行相關問題的解決。

來源：華圖教育

相關焦點

  • 數學教育定理-同餘定理
    同餘理論常被用於數論中。最先引用同餘的概念與符號者為德國數學家高斯。同餘理論是初等數論的重要組成部分，是研究整數問題的重要工具之一，利用同餘來論證某些整除性的問題是很簡便的。同餘是數學競賽的重要組成部分。公元972年，在一份阿拉伯手稿中，提出了這樣一個問題：一個正整數n何時能成為一個由三個有理平方數形成的等差數列的公差，也就是說x-n，x，x+n都是平方數。
  • 數學教育定理--中國剩餘定理
    孫子定理是中國古代求解一次同餘式組（見同餘）的方法。是數論中一個重要定理。又稱中國餘數定理。
  • 數學運算之同餘定理
    數學運算中常用的四大思想中講到了整除思想。今天筆者給大家講解一下餘數和同餘定理：一、餘數被除數/除數=商……餘數正負餘數絕對值加和=除數二、同餘定理幾個整數除以同一個除數，若餘數相同，則這幾個整數同餘。
  • 數論之三大餘數定理及同餘問題
    許多孩子都接觸過餘數的有關問題，並有不少孩子說「遇到餘數的問題就基本暈菜了！」餘數問題主要包括了帶餘除法的定義，三大餘數定理（加法餘數定理，乘法餘數定理，和同餘定理），及中國剩餘定理和有關棄九法原理的應用。
  • 2019甘肅省考行測數量關係答題技巧:同餘定理靈活應用
    2019甘肅省考行測數量關係答題技巧：同餘定理靈活應用 2019甘肅省公務員考試已進入備考階段，為了幫助廣大考生比較好的備考甘肅省考，甘肅中公教育為各位考生準備了豐富的行測和
  • 公務員考試行測中關於剩餘定理的巧妙應用
    行測考試中關於剩餘定理的巧妙應用　　中國古代著名數學著作<孫子算經>記載，"今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？"此問題為中國剩餘定理的原型。
  • 行測數學運算難點擊破之"同餘與剩餘"
    行測數學運算難點擊破之"同餘與剩餘" 　　在整數的除法中，只有能整除與不能整除兩種情況。當不能整除時，就產生餘數。其中，餘數總是小於除數，即0≤d　　一、同餘　　兩個整數a、b，若它們除以整數m所得的餘數相等，則稱a、b對於m同餘。　　例如，3除以5的餘數是3，18除以5的餘數也是3，則稱23與18對於5同餘。　　對於同一個除數m，兩個數和的餘數與餘數的和同餘，兩個數差的餘數與餘數的差同餘，兩個數積的餘數與餘數的積同餘。
  • 「中國剩餘定理」的開創者
    原標題：南宋數學家秦九韶：「中國剩餘定理」的開創者他所著《數書九章》，被稱為「算中寶典」他善於創新，用數學解決百姓的實際問題德國數學家高斯提出的同餘理論，是數論的重要內容之一他的理論被西方稱為「中國剩餘定理」，也代表著當時世界上數學研究的先進水平。秦九韶是南宋四川人，是我國古代宋元數學研究高峰時期的主要代表人物，也是古代數學集大成者，被譽為「宋元數學四大家」之一。在第二批四川歷史名人中，秦九韶是唯一一位來自科學領域的歷史名人。
  • 2020安徽農商行行測備考技巧:數量關係題目中同餘定理的應用
    2020安徽農商行行測備考技巧：數量關係題目中同餘定理的應用 同餘在考試的時候也會經常性的出現，它一般都是與整除思想相結合的，在備考的過程中要分清楚同餘的幾種情況，同餘特性經常會與中國剩餘定理混淆，所以在備考時要抓住兩者的區別點，避免考試時出錯。
  • 漫談中國剩餘定理
    中國剩餘定理又稱孫子定理，《孫子算經》中給出了其簡單形式的表述及解答：問題：今有物不知其數，三三數之，剩二。
  • 同餘定理
    這一期，我們來學習同餘定理。「同餘」這個概念最初是由德國數學家高斯發明的，在數學上，尤其是數論上，有著非常廣泛的應用。首先我們還是從例題講起。
  • 2015年黑龍江公務員考試行測備考:剩餘定理問題(2)
    2.一般情況 　　用同餘特性解題 　　【例題4】三位數的自然數P滿足：除以3餘2，除以7餘3，除以11餘4，則符合條件的自然數P有多少個?根據同餘特性可知，等式左邊的餘數10n-4應與等式右邊的餘數4,15,26等數值相等。因為n要取整數，所以取10n-4=26可以得到n=3代入①式得到P=59，所求的59這個數是滿足題幹三個條件的最小數，所以，滿足題幹三個條件的數 P=231n+59(n=1,2,3……)，所以在三位數以內的數有290,521,752,983四個數。選擇B項。
  • 一周一定理No.1 中國剩餘定理
    我們都提到了中國剩餘定理，雖然我曾在從射鵰到九章——在天大理學院物理系的通俗報告介紹過，但有點浮光掠影，我們想在此詳細介紹一下。中國剩餘定理：設正整數m1，m2，…，mn兩兩互素，則下述同餘方程組事實上，方程 (*) 的通解為x=r1M1x1+…+rnMnxn+kM，k∈Z  (#)其中Mi=M/mi，而xi是同餘方程Mixi≡1(mod mi)    (*i)的一個特解，因而可以用求一術得出。簡單地說，中國剩餘定理將一個同餘方程組（*）的求解，歸結為多個一次同餘方程（*i)的求解，而後者可以用求一術來求解。
  • 2015黑龍江公務員考試行測備考:數量關係之剩餘定理問題
    公考命題庫丨行測備考丨申論備考丨直播講座丨QQ群：259442655 丨關注微信：hljhtjy 　　2015年黑龍江公務員考試即將啟動，黑龍江省公務員考試網（http://hlj.huatu.com/）整理了行測各模塊技巧
  • 2018廣東公務員考試之數量關係同餘定理靈活應用
    > 廣東公務員考試：2018廣東公務員即將開始布，廣東中公教育為廣大參加省考的考生準備了2018廣東公務員考試之數量關係同餘定理靈活應用。
  • 2018軍轉幹行測備考:中國剩餘定理
    為了幫助考生熟悉行測複習內容，中公教育軍考網為您提供【數量關係】答題技巧，供廣大考生學習。更多有關軍轉幹考試資料請關注北京軍轉幹考試網。 (一)通用公式一元線性同餘方程組問題最早可見於中國南北朝時期(公元5世紀)的數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下：有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何?即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。
  • 中國剩餘定理應用詳解
    中國剩餘定理又稱孫子定理，數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下：有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。
  • EXCEL軟體 | 中國剩餘定理 | 一次同餘方程組
    上一期深入淺出地講述了中國剩餘定理。玻璃球的實例用語言敘述很簡單，數學家提升了它的理論高度，把它歸結為一次同餘方程的求解問題。上一期我還總結出了計算公式。本期在這個公式的基礎上利用EXCEL進行計算，很簡單方便。涉及EXCEL中的內置函數——取整函數 INT( )。我們會把公式埋入EXCEL單元格中。本期其實是教您把數學計算與計算機軟體操作結合起來。
  • 韓信點兵,物不知數和中國剩餘定理
    為了統計剩餘士兵的個數，韓信令士兵3人一排，多出2人；5人一排，多出4人；7人一排，多出6人。韓信據此很快說出人數：1049人。漢軍本來就十分信服韓信大將軍，經此之後就更加相信韓信是「天神下凡，神機妙算"，於是士氣大振，鼓聲喧天，在接下來的戰役中漢軍步步緊逼，楚軍亂作一團，大敗而逃。韓信由此名揚天下，被後世譽為「兵仙「，「神帥」。
  • 數量關係常考知識第三關——同餘定理
    同餘定理：核心口訣：餘同取餘，和同加和，差同減差，公倍數作周期餘同：「一個數除以4餘1，除以5餘1，除以6餘1」，則取1，表示為60+1和同：「一個數除以4餘3，除以5餘2，除以6餘1」，則取7，表示為