【正文】 1,177。1,177。2,…【例11】解方程組 。2,…代入方程①得x1＝－(x2＋x3＋x4) ＝－[(1＋2t)＋(2－t)＋1] ＝－4－t故原方程的解為，t＝0,177。（解）方程②－①得 x2＋2x3＋3x4＝8 ④③－2②得 －x2－2x3－7x4＝－12 ⑤再④＋⑤得 －4x4＝－4∴ x4＝1代入④得 x2＋2x3＝5 （注：此時方程④與⑤等價）所以，方程④與⑤聯(lián)立的解為，t＝0,177。（解）方程②－①得 x2＋2x3＋3x4＝5 ④③－②2得 －x2－2x3－7x4＝－6 ⑤再④＋⑤得 －4x4＝－1上方程中x4不可能為整數(shù)（即該方程無解），故原方程組無解。1,177。1,177。（解）方程①－②得（消去x3）14x1＋8x2＝200即 7x1＋4x2＝100 ③觀察得特解 x1＝0，x2＝25，代入方程②得x3＝75。2,…2. 6. 4 （n元）一次不定方程組思路：用消元法，化為多元單個不定方程。2,…所以，原方程的全部解為， u,v＝0,177。2,… 反推有＝(x1＋3x4)＋ x5＝(1＋2x5)＋3x4＋ x5＝1＋3x4＋3x5＝(－x1－2x2＋10)＋x4＝－(1＋2x5) －2(1＋3x4＋3x5)＋10＋3x4＝6－5x4－10x5 ， x4,x5＝0,177。（解）由于 ＝min，故選x3將原方程化為＝(－15x1－10x2＋61)＝(－2x1－2x2＋10)＋(－3x1＋2x2＋1)令 x4＝(－3x1＋2x2＋1) ∈Z，則有＝(3x1＋6x4－1)＝ (x1＋3x4)＋(x1－1)又令 x5＝(x1－1) ∈Z，則有＝2x5＋1＝1＋2x5， x5＝0,177。（證）。(二) 有解的條件【】n元一次（不定）方程（6）有解的充分必要條件為(,…, as)│n且有解時，它的解與不定方程＋…＋＝ （7）的解相同。1,177?！纠?】求方程 6＋10＝22的解。2,…【例8】求方程 21＋117＝38的解。2,…例如 (x5, x6)＝(－5, 0)＝(8,1)＝…因xx6可以同時為整數(shù)，故原方程有解，且其解為 x6＝0,177?；嗊^程回代過程x2＝(－907x1＋2107) /731＝－x1＋3＋(－176x1－86)/731x2＝－x1＋3＋x3＝－(－258＋731x6)＋3＋(62－176x6)＝323－907x6令x3＝(－176x1－86)/731∈Z則x1＝(－731x3－86)/176＝－4x3＋(－27x3－86)/176x1＝－4x3＋x4＝－4(62－176x6)＋( －10＋27x6)＝－258＋731x6令x4＝(－27x3－86)/176∈Z則x3＝(－176x4－86)/27＝－7x4－3＋(13x4－5)/27x3＝－7x4 －3＋ x5＝－7(－10＋27x6) －3＋(13x6－5)＝62－176x6令x5＝(13x4－5)/27∈Z則x4＝(27x5＋5)/13＝2x5＋(x5＋5)/13x4＝2x5＋x6＝2(－5＋13x6)＋x6＝－10＋27x6令x6＝(x5＋5)/13∈Z則x5＝13x6－5方程x5＝13x6－5顯然有解，且有，x6＝0,177。又如(473, －584)←→(473, －114)）特點：方程（*）的系數(shù)的絕對值比原方程小。（解）化原方程為x2＝(－907x1＋2107)/731＝－x1＋3＋(－176x1－86)/731令 x3＝(－176x1－86)/731∈Z，則 x1＝(－731x3－86)/176 ＝－4x3＋(－27x3－86)/176即 176 x1＋731x3＝－86 （*）則方程(*)與原方程同時有解或無解，且二者的解一一對應。做帶余除法由下往上反推36=281+84=28(3628)3 =363+28428=83+44=28838=42+0即363+284=4兩邊同時乘以25得 36(325)+28(425)= 425 36(75)28(100)=100所以，原方程的一個特解為 =75，=100(四) 求特解的方法Ⅳ——再用輾轉相除法同時判斷方程是否有解并求出全部解。2,…）【例6】求方程 36x28y＝100的特解。做帶余除法由下往上反推19=121+71=123(1912)5 =195+12812=71+51=72+(127)3=123757=51+21=5(75)2=72+535=22+11=522即128195=1兩邊同時乘以20得 12(820)+19(520)=20 12160+19(100)=20所以，原方程的一個特解為 =160，=100（全部解為x=160+19t，y=10012t， t＝0,177。【例5】求方程 12x+19y＝20的特解。（解）由原方程知 y＝－(17－10x)/7令x＝0,1,2,…，計算值為整數(shù)的y即可。1,177。1,177。【例3】求方程6x+10y＝22的全部整數(shù)解.（解）(6,10)＝2，2│22，所以方程有解。1,177。(五) 例【例1】求不定方程10x－7y＝17的全部整數(shù)解.（解）(10,－7)＝1，所以方程有解。1,177?！咀ⅰ慨?,)＝d1時，不能用公式（3）求方程（1）的所有解，否則會漏掉某些解。1,177。（證）因為等式（1）成立的充分必要條件是等式（4）成立。1,177。2,… （3）其中，為方程（1）的一組（特）解，t為任意整數(shù)。＝+t，＝－t t＝0,177。(三) (,)＝1時的解首先由有解的條件知，此時方程（1）一定有解。已知方程（1）＝n有解，故d│n。2，177。} }return y特點：由n的高位到低位計算【例1】計算 mod 561（＝31117），計算過程各變量的值如下表i98765432101000110000x1248173570140280560y749157526160241298166671又如n＝77＝ i65432101001101x1249193877y749157526559196268【例2】 （2次平方，1次乘法）， （3次平方，2次乘法），（從n的二進制分解角度，6＋3＋2＝11次平方，3次乘法）＝（從算法角度，6次平方，3次乘法），＝ （實質結果，不算＝0的情形且嵌套起來。if ＝1 then {x＋＋。for ＝k downto 0 do {x＝2*x。常規(guī)計算的乘法運算量為L＝n＋(n－1)＋…＋2＋1＝n(n－1)／2快速算法：P(x)＝運算量：n次乘法，n次加法。則≡ （mod m）運算量：乘法次數(shù)≤(1+2+…+ k)+k＝（計算最多需要i次乘法）。8)6≡10≡－1（mod 7） 模重復平方計算法目的：快速計算a≡ （mod m） （1）(一) 問題常規(guī)思路，遞歸地計算（1）式：≡ （mod m）運算量：n－1次乘法。4) (510≡１(2２9≡1， 76≡1， 34)(3…5≡1 （mod 7）即≡4，≡5，≡2，≡3（mod 7）以及≡1，≡6（mod 7），從而有∴ １【例】設p＝7，則 2已知 (p－1)!≡－1 （mod p），由同余性質知 (p－1)! －(－1)＝ (p－1)!＋1＝c＋1 （*）若p＝ab為合數(shù)，則p，從而由上式知 c＋1又 1＜a＜p（且1＜b＜p），那么，必有 (p－1)!＝c∴ (c＋1)－c＝1 矛盾。２…(p－2)(p－1)≡1所以２，３，…，(p－2)這p－3個數(shù)兩兩互相為逆。設p≥3，由于1≤a≤p－1時，(a，p)≡1，故a的逆（mod p）存在且1,2,…,p－1中任一數(shù)的逆恰好也在中1,2,…,p－1中。若d＝n，則n│a，即 a≡0（mod n），從而c≡≡0（mod n）≡0≡a（mod n）若1＜d＜n ，不失一般性，設1＜a＜n ，則必有a＝kp（1≤k＜q）或a＝kq（1≤k＜p）設a＝kq，此時必有（a，p）＝1，那么有≡≡≡a≡a（mod p）和≡0≡a（mod q）所以 ≡a （mod n）即 ≡≡a （mod n）同理可證當a＝kp時的情況。其中為任意整數(shù)?！纠?】（例5）設p、q是兩個不同的奇素數(shù)，n＝pq，a是與n互素的整數(shù)。又 ≡≡1 mod 15，既不能肯定15是素數(shù)，也不能肯定15是合數(shù)?！纠吭Om＝20，a＝2，則 ＝≡＝≡2【例3】（例3）設m＝11，a＝2，則(2，7)＝1 ，(11)＝10，故≡1 mod 11【例4】（例4）設m＝23，23├a，則(a，23)＝1 ，(23)＝22，故≡1 mod 23（歐拉定理的）另一表示形式：設m是大于1的整數(shù)，若整數(shù)a滿足(a，m)＝1，則有≡a （mod m）(二) 費馬定理【】（Fermat定理）（定理2）設p為素數(shù)，a為任意正整數(shù)，則≡a （mod p）（證）(1) ，則有≡0 （mod