中學(xué)同余問題解題技巧

中學(xué)同余問題解題技巧同余問題解題是中學(xué)數(shù)學(xué)里面比較重要的一個(gè)部分，也是涉及到許多領(lǐng)域的基礎(chǔ)，如密碼學(xué)、編碼等等，因此，掌握同余問題解題技巧對(duì)于中學(xué)數(shù)學(xué)考試和實(shí)際應(yīng)用都非常重要。一、同余基礎(chǔ)概念同余是指在模意義下兩個(gè)數(shù)的余數(shù)相同，即a≡b(modm)表示a和b除以m所得的余數(shù)相同，稱a與b在模m下同余，m稱為模數(shù)。兩個(gè)數(shù)a和b在模m下同余可以寫作以下三種形式之一：1.a=b+km2.m|(a-b)3.amodm=bmodm其中，k為整數(shù)。同時(shí)，同余關(guān)系是一種等價(jià)關(guān)系，即符合如下條件：設(shè)a，b，c∈Z，若a≡b(modm)，b≡c(modm)，則有a≡c(modm)。二、同余解題方法1.同余方程求解同余方程的形式為ax≡b(modm)，其中a，b，m均為整數(shù)。當(dāng)m與a互質(zhì)時(shí)，同余方程才有唯一解。所以擴(kuò)展歐幾里得算法就可以解決同余方程，同時(shí)，可以通過擴(kuò)展歐幾里得算法求得a關(guān)于m的逆元，使得ax≡1(modm)。例子：解決同余方程3x≡1(mod7)。使用擴(kuò)展歐幾里得算法：7=3x2+13=1x31=3-1x2則，1=3-1x(7-3x2)=4x3-1x7所以，3的逆元為4，所以3x≡1(mod7)的解為x≡4(mod7)。2.同余式的加減乘方在同余式中，加減乘運(yùn)算與普通數(shù)學(xué)中的運(yùn)算法則基本一致，因此使用同余式的加減乘方，也能較容易地解決同余問題。例子：1.求(5×11+6)/7的余數(shù)。5×11+6=61，61÷7=8余5，所以5×11+6≡5(mod7)，∴5×11+6÷7≡5×11÷7+6÷7≡5+0≡5(mod7)。2.求11^23的個(gè)位及十位數(shù)字。11^23≡1^23(mod100)，因?yàn)?1^20≡1(mod100)，所以11^23≡11^3≡1×11^2×11≡31(mod100)，所以十位為3，個(gè)位為1。3.中國(guó)剩余定理中國(guó)剩余定理（CRT），又稱中國(guó)剩余定理問題，是解決一類同余方程組（線性同余方程組）的問題的方法，同時(shí)也是RSA加密算法的重要理論基礎(chǔ)。形式如下：求解同余方程組x≡a1(modb1)x≡a2(modb2)……x≡an(modbn)。其中，b1，b2，……，bn兩兩互質(zhì)。解法如下：設(shè)m=b1b2……bn，mi=m/bi，xi是mi關(guān)于bi的逆元（即mi×xi≡1(modbi)時(shí)，xi就是mi關(guān)于bi的逆元，使用擴(kuò)展歐幾里得算法就能得到），則同余方程組的通解為x≡a1mixi+a2mixi+……+anmixi(modm)。例子：解同余方程組：x≡3(mod5)x≡1(mod7)x≡2(mod9)解法如下：m=5×7×9=315m1=7×9，m2=5×9，m3=5×75×7y1≡1(mod9)，y1=8；5×9y2≡1(mod7)，y2=4；7×9y3≡1(mod5)，y3=8；x≡3×63×8+1×45×4+2×35×8(mod315)≡233(mod315)。所以x=233，是同余方程組的通解。三、總結(jié)同余問題在中學(xué)數(shù)學(xué)中是一個(gè)非常重要的部分，掌握其解題方法，能夠在數(shù)學(xué)考試中輕松應(yīng)對(duì)相關(guān)題目，同時(shí)對(duì)于現(xiàn)代密碼學(xué)與編碼應(yīng)用也有一定的理論指導(dǎo)意義。同