中國剩餘定理應用詳解

2020-12-11 小學初中數學學習

中國剩餘定理又稱孫子定理,數學著作《孫子算經》卷下第二十六題,叫做「物不知數」問題,原文如下:

有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?即,一個整數除以三餘二,除以五餘三,除以七餘二,求這個整數。《孫子算經》中首次提到了同餘方程組問題,以及以上具體問題的解法,因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。其實,南宋數學家秦九韶在其著作《數書九章》中,系統的提出並證明了這一類問題的解法,因此這個定理也可以稱為孫子秦九韶定理。

明朝數學家程大位將解法編成易於上口的《孫子歌訣》:

三人同行七十稀,五樹梅花廿一支,七子團圓正半月,除百零五使得知

這個歌訣給出了模數為3、5、7時候的同餘方程的秦九韶解法。意思是:將除以3得到的餘數乘以70,將除以5得到的餘數乘以21,將除以7得到的餘數乘以15,全部加起來後除以105(或者105的倍數),得到的餘數就是答案。比如說在以上的物不知數問題裡面,按歌訣求出的結果就是23。

中國剩餘定理的理論證明比較複雜,這裡就不做敘述,只就如何應用中國剩餘定理做講解。首先,中國剩餘定理應用的題型必須要求除數兩兩互質,這樣才能方便的用中國剩餘定理,否則要做一些變化處理。

例1、一個數被5除餘2,被6除餘4,被7除餘3,這個數最少是多少?

解:第一步:判斷5,6,7兩兩互餘。

第二步:計算5,6,7的最小公倍數,得5×6×7=210。

第三步:計算各除數的逆元。將5去掉,計算6×7=42,42÷5=8……2,將餘數2適當的擴大倍數,使除以5的餘數是1,很顯然這個倍數是3,也就是逆元是3;將6去掉,計算5×7=35,35÷6=5……5,將餘數5適當的擴大倍數,使除以6的餘數是1,很顯然這個倍數是5,也就是逆元是5;將7去掉,計算5×6=30,30÷7=4……2,將餘數2適當的擴大倍數,使除以7的餘數是1,很顯然這個倍數是4,也就是逆元是4;

第四步:將餘數和逆元和最小公倍數除以該數的商相乘,然後將各個結果相加,再除以最小公倍數所得的餘數即為所求。計算42×3×2+35×5×4+30×4×3=1312,1312÷210=6……52,因此這個最小的數就是52。

例2、一個數被3除餘1,被5除餘2,被7除餘3,被8除餘4,這個數最少是多少?

解:第一步:判斷3,5,7,8兩兩互餘。

第二步:計算3,5,7,8的最小公倍數,得3×5×7×8=840。

第三步:計算各除數的逆元。將3去掉,計算5×7×8=280,280÷3=93……1,餘數已經是1了,就不用擴大倍數了,或者說倍數是1,也就是逆元是1;將5去掉,計算3×7×8=168,168÷5=33……3,將餘數3擴大適當的倍數,使除以5的餘數是1,很顯然這個倍數是2,也就是逆元是2;將7去掉,計算3×5×8=120,120÷7=17……1,餘數已經是1了,就不用擴大倍數了,或者說倍數是1,也就是逆元是1;將8去掉,計算3×5×7=105,105÷8=13……1,餘數已經是1了,就不用擴大倍數了,或者說倍數是1,也就是逆元是1;

第四步:將餘數和逆元和最小公倍數除以該數的商相乘,然後將各個結果相加,再除以最小公倍數所得的餘數即為所求。計算280×1×1+168×2×2+120×1×3+105×1×4=1732,1732÷840=52,因此這個最小的數是52。

例3、一個數被5除餘1,被6除餘5,被7除餘4,被11除餘9,這個數最小是多少?

解:第一步:判斷5,6,7,11兩兩互餘。

第二步:計算5,6,7,11的最小公倍數,得5×6×7×11=2310。

第三步:計算各除數的逆元。將5去掉,計算6×7×11=462,462÷5=92……2,將餘數2適當的擴大倍數,使除以5的餘數是1,很顯然這個倍數是3,也就是逆元是3;將6去掉,計算5×7×11=385,385÷6=64……1,餘數已經是1了,這樣逆元就是1;將7去掉,計算5×6×11=330,330÷7=47……1,餘數已經是1了,這樣逆元就是1;將11去掉,計算5×6×7=210,210÷11=19……1,餘數已經是1了,這樣逆元就是1。

第四步:將餘數和逆元和最小公倍數除以該數的商相乘,然後將各個結果相加,再除以最小公倍數所得的餘數即為所求。計算462×3×1+385×1×5+330×1×4+210×1×9=6521,6521÷2310=2……1901,因此這個數就是1901。

總結:應用中國餘數定理時,思路簡單,按照題目所示步驟進行計算就可以了,但計算過程稍顯複雜,若題目具有一定的特殊性,我們也可以採用其他的方法。

相關焦點

  • 漫談中國剩餘定理
    中國剩餘定理又稱孫子定理,《孫子算經》中給出了其簡單形式的表述及解答:問題:今有物不知其數,三三數之,剩二。
  • 數學教育定理--中國剩餘定理
    孫子定理是中國古代求解一次同餘式組(見同餘)的方法。是數論中一個重要定理。又稱中國餘數定理。
  • 公務員考試行測中關於剩餘定理的巧妙應用
    行測考試中關於剩餘定理的巧妙應用  中國古代著名數學著作<孫子算經>記載,"今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?"此問題為中國剩餘定理的原型。
  • 中國剩餘定理
    這個遊戲運用的數學原理就是著名的中國剩餘定理。我以前某期講過中國剩餘定理。您可以去那裡閱讀。上面公式中3個數715、364和924是怎麼回事?您可能會這樣問。首先,我們必須再次明確:7×11×13=1001其中的7、11、13這三個數非常重要,它們兩兩互素。
  • 我看中國剩餘定理
    中國剩餘定理有一堆玻璃球,三個三個數餘2,五個五個數餘4,七個七個數餘5。問這堆玻璃球有多少個?不講中國剩餘定理的一般形式。想探索一下中國剩餘定理能被人們想出來一定是有某種很棒的思維在其中。我從我本人內在想法來對中國剩餘定理進行一番簡單易懂的解讀。力求把定理寫得深入淺出,人人都能看懂。設玻璃球數量為N。
  • 2020軍隊文職考試技巧:中國剩餘定理
    【導讀】華圖寧夏軍隊文職考試網同步未知發布:2020軍隊文職考試技巧:中國剩餘定理,詳細信息請閱讀下文!下面寧夏華圖整理的中國剩餘定理,希望大家學習記憶。   什麼是中國剩餘定理呢,中國剩餘定理最早出現在《孫子算經》中,又名「物不知數問題」,有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?即,一個整數除以三餘二,除以五餘三,除以七餘二,求這個整數。
  • NOIP考點中國剩餘定理
    這就牽涉到一個最基本數學定理,如果有a%b=c,則有(a+k∗b)%b=c(k為非零整數),換句話說,如果一個除法運算的餘數為c,那麼被除數與k倍的除數相加(或相減)的和(差)再與除數相除,餘數不變。這個是很好證明的。  以此定理為依據,如果n2是3的倍數,n1+n2就依然滿足除以3餘2。同理,如果n3也是3的倍數,那麼n1+n2+n3的和就滿足除以3餘2。
  • 一周一定理No.1 中國剩餘定理
    作者 | 林開亮在最近推出的兩篇文章①微積分之前奏1:高階等差數列的求和②算命是胡扯,猜姓卻不然中,我們都提到了中國剩餘定理我們期待,本文作為好玩的數學開創的頭一個專欄——一周一定理——的開篇,能夠打響第一炮。本專欄的開創,學習和借鑑了下述網頁(感謝上海交通大學數學系吳耀琨教授向我們推薦)
  • 2020銀保監會考試行測備考:淺析剩餘定理的應用
    2020銀保監會考試行測備考:淺析剩餘定理的應用 今天,山東中公教育小編整理了:2020銀保監會考試行測備考:淺析剩餘定理的應用,供各位考生參考。
  • 2021北京公務員考試行測技巧:中國剩餘定理
    本文整理2021北京公務員考試行測技巧:中國剩餘定理。 2020北京公務員考試招錄專題 京考信息匯總各位考生,很多同學在備考的過程中遇到中國剩餘定理的題目除了代入排除這一種方法就有些不知所措,其實,中國剩餘定理問題備考起來還是比較容易掌握的,下面就跟著中公教育來一塊學習這部分的內容吧。
  • 「中國剩餘定理」的開創者
    原標題:南宋數學家秦九韶:「中國剩餘定理」的開創者他所著《數書九章》,被稱為「算中寶典」他善於創新,用數學解決百姓的實際問題德國數學家高斯提出的同餘理論,是數論的重要內容之一他之前五百多年的中國古代,有一位名叫秦九韶的數學家就提出了同樣的解法。他的理論被西方稱為「中國剩餘定理」,也代表著當時世界上數學研究的先進水平。秦九韶是南宋四川人,是我國古代宋元數學研究高峰時期的主要代表人物,也是古代數學集大成者,被譽為「宋元數學四大家」之一。在第二批四川歷史名人中,秦九韶是唯一一位來自科學領域的歷史名人。
  • 韓信點兵,物不知數和中國剩餘定理
    為了統計剩餘士兵的個數,韓信令士兵3人一排,多出2人;5人一排,多出4人;7人一排,多出6人。韓信據此很快說出人數:1049人。漢軍本來就十分信服韓信大將軍,經此之後就更加相信韓信是「天神下凡,神機妙算",於是士氣大振,鼓聲喧天,在接下來的戰役中漢軍步步緊逼,楚軍亂作一團,大敗而逃。韓信由此名揚天下,被後世譽為「兵仙「,「神帥」。
  • 中國古代史上最完美和最值得驕傲的數學成果:中國剩餘定理
    文將介紹中國古代最完美和最值得驕傲的數學成果「中國剩餘定理」,希望能有更多的讀者和學生能重視我們國家的傳統文化,並通過對中國剩餘定理的了解和學習喜歡上數論。在中外幾乎每一本基礎數論的教課書中,都會介紹一個被稱之為「中國剩餘定理」(Chinese Remainder Theorem)的知識。在我的印象裡,自己是在小學四五年級的時候接觸到這個知識的,並知道如何去應用它,但要等到初中後才真正明白其原理。中
  • 2020福建公務員考試行測數量關係:中國剩餘定理
    各位考生,很多同學在備考的過程中遇到中國剩餘定理的題目除了代入排除這一種方法就有些不知所措,其實,中國剩餘定理問題備考起來還是比較容易掌握的,下面就跟著中公教育來一塊學習這部分的內容吧。什麼是中國剩餘定理呢,中國剩餘定理最早出現在《孫子算經》中,又名「物不知數問題」,有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?
  • 中國剩餘定理!唯一以中國名字命名的數學定理
    名字確立--中國剩餘定理眾所周知,中國古代數學經常出現比較尷尬的情形,有些定理在中國叫一個名字,在外國卻叫另一個名字,比如中國叫「祖𣈶原理」,西方叫「卡瓦列利原理」,好像總是有爭議的樣子,一旦出現沒爭議的情況,大部分的定理都是西方人的名字,比如「韋達定理」,「泰勒公式」。
  • 「韓信點兵法」和中國剩餘定理
    中國古代數學有幾項研究曾經遠遠領先於世界,被西方稱為「中國剩餘定理」的算法就是其中之一。
  • 草根學習|中國剩餘定理
    若x=2a+3b+2c符合條件且x>[3,5,7]則x'=2a+3b+2c-[3,5,7]也符合條件如本題,x=233符合條件,那233-105=128,128-105=23也為符合條件的數,其中23為符合條件的最小值(「以二百一十減之」即減兩倍的105)草根理解:中國剩餘定理是先運用一種通用的算法篩選出一個符合條件的數
  • 2020甘肅省考行測數量關係備考技巧:淺析剩餘定理的應用
    2020甘肅省考行測數量關係備考技巧:淺析剩餘定理的應用 甘肅公務員考試科目主要《行政職業能力測驗》和《申論》兩科,其中行政職業能力測試包含的內容比較廣泛,下面甘肅中公教育為大家準備了數量關係:淺析剩餘定理的應用,
  • 2021京考行測數量關係之中國剩餘定理
    本文整理2021京考行測數量關係之中國剩餘定理。 北京公務員考試招錄專題 京考信息匯總餘數問題在歷年的公考行測中,經常會出現它的身影。但對於大家來說,難度並不是很高。今天,中公教育就帶大家來了解一下關於餘數問題中一個很重要的知識點,它就是中國剩餘定理。
  • 「中國剩餘定理」到底是如何算出來的?
    (給算法愛好者加星標,修煉編程內功)作者:_Warning_blog.csdn.net/destiny1507/article/details/81751168看了很多博客始終沒弄明白中國剩餘定理到底是怎麼算出來的