余數(shù)巧解：小學(xué)數(shù)學(xué)奧妙教案

第頁(yè)共頁(yè)余數(shù)巧解：小學(xué)數(shù)學(xué)奧妙教案小學(xué)數(shù)學(xué)奧妙教案在小學(xué)數(shù)學(xué)中，我們經(jīng)常會(huì)遇到一些關(guān)于余數(shù)的題目，有時(shí)候我們還需要用到一些巧妙的方法來(lái)解決問(wèn)題。下面我們就來(lái)一起探討一下余數(shù)巧解的奧妙。一、整數(shù)和余數(shù)在初學(xué)余數(shù)概念時(shí)，我們需要了解什么是整數(shù)，什么是余數(shù)。整數(shù)是用來(lái)稱(chēng)述事物數(shù)量或順序的數(shù)，而余數(shù)是在除法運(yùn)算中得到的與被除數(shù)相對(duì)應(yīng)的小于除數(shù)的一個(gè)數(shù)。例如，9÷4=2……1，這里2就是商，1就是余數(shù)。在整除中，如果余數(shù)等于0，那么就稱(chēng)為完全除盡。例如，10÷5=2，這里余數(shù)為0，就是完全除盡。二、解決同余方程同余方程是我們經(jīng)常遇到的一種問(wèn)題。在求解同余方程時(shí)，我們需要先說(shuō)一下我們所掌握的定理。定理1（質(zhì)數(shù)求逆定理）：設(shè)p是質(zhì)數(shù)，且x是這個(gè)質(zhì)數(shù)的整數(shù)倍，那么有x≡0（modp）。并且，如果x不是這個(gè)質(zhì)數(shù)的倍數(shù)，那么有：x·(x的逆元)≡1（modp）。其中，x的逆元可以表示為x^-1（modp）。例如，有3·7≡1（mod10），因?yàn)?是10的逆元，而3和10互質(zhì)。定理2：如果a≡b（modm），c≡d（modm），那么：a+c≡b+d（modm）;a-c≡b-d（modm）;ac≡bd（modm）;a^k≡b^k（modm）。定理3：如果ax≡b（modm），那么，ax≡b（modm）的充要條件是gcd(a,m)整除b。綜合這些定理，我們可以輕松地解決同余方程，例如：1、x≡2（mod3），x≡1（mod4）由定理2可得：x-2≡0（mod3），x-1≡0（mod4）即x-2=3k，x-1=4m再由定理2可得：x=3k+2，x=4m+1即有：3k+2=4m+1或m=3n+1因此，我們可以得到：x=3k+2=4(3n+1)+1=12n+5因此x=5（mod12）。2、x≡1（mod3），x≡2（mod5），x≡3（mod7）同樣由定理2可得：x-1≡0（mod3），x-2≡0（mod5），x-3≡0（mod7）即x-1=3k，x-2=5m，x-3=7n再由定理2可得，x=3k+1=5m+2=7n+3也就是3k=5m+1，4m+1=7n+4也就是m=2+3d，n=3+5d這里d是一個(gè)整數(shù)。因此，我們可以得到：x=3k+1=5(2+3d)+2也就是x=31+15d=7(3+5d)+3因此x=31（mod105）。三、挑戰(zhàn)題目假設(shè)我們需要逆向求出所有的x，使得x≡1（mod2），x≡2（mod3），…，x≡9（mod10）。如何解決這個(gè)問(wèn)題呢？我們可以用擴(kuò)展歐幾里得算法來(lái)解決。在擴(kuò)展歐幾里得算法中，我們需要求出最大公約數(shù)（gcd）以及對(duì)應(yīng)系數(shù)。如果a和b是任意兩個(gè)整數(shù)，那么擴(kuò)展歐幾里得算法可以得到下面的結(jié)果：1）如果b=0，那么gcd(a,b)=a，而系數(shù)x=1，y=0。2）否則，gcd(a,b)=gcd(b,amodb)，而系數(shù)x和y代表滿(mǎn)足ax+by=gcd(a,b)的一組整數(shù)。值得注意的是，在擴(kuò)展歐幾里得算法中，我們需要保證a>b?；氐轿覀兊膯?wèn)題，x在1到10的范圍內(nèi)，所以我們可以列出下列方程組。如何解決這個(gè)方程組呢？對(duì)于mod2=0,mod3=0,mod5=0，我們知道，需要求出一個(gè)b，使得b=1（mod2），b=2（mod3），b=3（mod5）其中b的值可以為23。因?yàn)?3是最小的正整數(shù)，能夠滿(mǎn)足這三個(gè)條件。接下來(lái)，我們需要求出b，使得b=x（mod7），b=x（mod11），b=x（mod13），b=x（mod17），b=x（mod19）如何求解這個(gè)問(wèn)題呢？我們可以采用一種叫做中國(guó)剩余定理（CRT）的技巧。在中國(guó)剩余定理中，我們需要求解下列方程組：x=a1（modm1）x=a2（modm2）…x=an（modmn）其中，ai和mi為任意正整數(shù)，而且mi互質(zhì)。CRT告訴我們，如果將所有的mi相乘（稱(chēng)為M），那么對(duì)于所有的i，都有M/mi與mi互質(zhì)。這時(shí)，我們可以將每個(gè)方程改寫(xiě)成一個(gè)形式，使得它們只包含公共的因數(shù)M/mi。我們可以將這些方程組合起來(lái)，得到下列方程：x=a1(M/m1)g1+a2(M/m2)g2+…+an(M/mn)gn（modM）其中g(shù)1、g2、…gn是滿(mǎn)足(gi)(M/mi)≡1（modmi）的整數(shù)?？梢允褂脭U(kuò)展歐幾里得算法來(lái)計(jì)算它們。這個(gè)方法非常有用，因?yàn)镸/mi與mi互質(zhì)，所以用擴(kuò)展歐幾里得算法來(lái)求解gi和M/mi的逆元是比較簡(jiǎn)單的?；氐轿覀兊膯?wèn)題，在我們的例子中，m1=7，m2=11，m3=13，m4=17，m5=19。因此，我們可以計(jì)算出M=7×11×13×17×19=46189。我們可以將每個(gè)方程改寫(xiě)成適合中國(guó)剩余定理的形式。因此b需要滿(mǎn)足以下條件：b=9×13×17×19z1+1×7×11×19z2+6×7×11×13z3+4×7×11×13×17z4+5×7×13×17×19z5這里z1…z5是我們要求解的系數(shù)。我們只需要找到一個(gè)系數(shù)z，使得b在1到10之間，