模線性方程與模線性方程組.ppt

模線性方程 模線性方程組,henu 08wangnan,今天要解決的問題：,axb (mod n) a0 n0 x=? 如：4x2(mod 5),xa1 (mod n1) xa2 (mod n2) a0 n0 x=?,如：x2(mod 5) x3(mod 13),求解模線性方程？,axb (mod n) a0 n0 x=? 如：4x2(mod 5),1.是否有解？ 2.有幾個解？ 3.這些解分別是多少？,？,分析,首先明確一點(diǎn), 如果x是解(0<=x<n), 則對于任意整數(shù)k, x+kn也是解, 所以解應(yīng)表示成一些剩余類xxi axb(mod n)等價于存在整數(shù)y, 使得 ax-ny=b 這是一個線性同余方程, 首先判斷d=(a,n)是不是b的約數(shù), 如果是, 等價于方程ax-ny=b, 相當(dāng)于求解 axb(mod n), (a,n)=1,分析,這個方程有兩種解法 直接解ax-ny=d, 再兩邊同時乘以b/d. 注意這只是一個解, 一共應(yīng)該有d個, 間隔為n/d(因為對于模n/d來說解是唯一的) 在模n的縮系中a是存在逆a-1的. 因此解為xa-1b(mod n), 同樣擴(kuò)展得d個解. 在縮系中求逆也有兩種方法 求ax-ny=1的解, 和方法一等價 利用歐拉定理a-1a(n)-1(mod n),求解模線性方程,axb(mod n) 方法一：利用Euler函數(shù) a*a(n)-1 1 a(b*a(n)-1) b 關(guān)鍵: 求abmod n a, a2, a4, a8, a16, 同余方程可以做乘法，b做二進(jìn)制展開選擇 方法二：擴(kuò)展的Euclid算法 存在整數(shù)y，使得ax-ny=b 記d=(a,n)，a=a/d, n=n/d，必須有d|b ax-ny=1*(b/d) 注意：x不唯一, 所有x相差n/d的整數(shù)倍,歐拉定理與費(fèi)馬定理,歐拉函數(shù): 1n中和n互素的元素個數(shù)(n) Euler定理 若gcd(a, n)=1則a(n) 1 (mod n) 意義：當(dāng)b很大時ab ab mod (n)(mod n)，讓指數(shù)一直比較小 歐拉函數(shù)是積性函數(shù)，即當(dāng)(m,n)=1時f(mn)=f(m)*f(n) 費(fèi)馬定理是歐拉定理在n為素數(shù)時的特殊情況： ap-1 1 (mod p) 其中p為素數(shù),MODULAR-LINEAR-EQUATION-SOLVER(a, b, n),MODULAR-LINEAR-EQUATION-SOLVER(a, b, n) 1 (d, x, y) EXTENDED-EUCLID(a, n) 2 if d | b 3 then x0 x(b/d) mod n 4 for i 0 to d - 1 5 do print (x0 + i(n/d) mod n 6 else print no solutions,MODULAR-LINEAR-EQUATION-SOLVER(a, b, n),MODULAR-LINEAR-EQUATION-SOLVER(4, 2, 5) 1 (1, 4, -3) EXTENDED-EUCLID(4 , 5 ) 2 if 1 | 2 3 then 3 4 (2/1) mod 5 4 for i 0 to 1- 1 5 do print (3 + i (5/1) mod 5 6 else print no solutions,4x2(mod 5),4x2(mod 5) x有唯一解，x=3,MODULAR-LINEAR-EQUATION-SOLVER(a, b, n),MODULAR-LINEAR-EQUATION-SOLVER(14, 30, 100) 1 (2, -7, 1) EXTENDED-EUCLID(14, 100 ) 2 if 2 | 30 3 then 95 (-7) * (30/2 ) mod 100 4 for i 0 to 2 - 1 5 do print (95 + i (100/2) mod 100 6 else print no solutions,14x30 (mod 100),14x30(mod 100) x有兩個解，x=95 ，x=45,練習(xí)：Poj 1061 青蛙的約會,接下來要解決的問題：,xa1 (mod n1) xa2 (mod n2) a0 n0 x=?,如：x2(mod 5) x3(mod 13),韓信點(diǎn)兵！,在中國數(shù)學(xué)史上，廣泛流傳著一個“韓信點(diǎn)兵”的故事： 韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝的建立了卓絕的功勞。據(jù)說韓信的數(shù)學(xué)水平也非常高超，他在點(diǎn)兵的時候，為了保住軍事機(jī)密，不讓 敵人知道自己部隊的實力，先令士兵從1至3報數(shù)，然后記下最后一個士兵所報之?dāng)?shù)；再令士兵從至報數(shù)，也記下最后一個士兵所報之?dāng)?shù)；最后令士兵從1至7 報數(shù)，又記下最后一個士兵所報之?dāng)?shù)；這樣，他很快就算出了自己部隊士兵的總?cè)藬?shù)，而敵人則始終無法弄清他的部隊究竟有多少名士兵。,韓信點(diǎn)兵！,在中國數(shù)學(xué)史上，廣泛流傳著一個“韓信點(diǎn)兵”的故事： 這個故事中所說的韓信點(diǎn)兵的計算方法，就是現(xiàn)在被稱為“中國剩余定理”的一次同余式解法。它是中國古代數(shù)學(xué)家的一項重大創(chuàng)造，在世界數(shù)學(xué)史上具有重要的地位。,孫子算經(jīng)？解模線性方程組！,最早提出并記敘這個數(shù)學(xué)問題的，是南北朝時期的數(shù)學(xué)著作孫子算經(jīng)中的“物不知數(shù)”題目。這道“物不知數(shù)”的題目是這樣的： “今有一些物不知其數(shù)量。如果三個三個地去數(shù)它，則最后還剩二個；如果五個五個地去數(shù)它，則最后還剩三個；如果七個七個地去數(shù)它，則最后也剩二個。問：這些物一共有多少？” 用簡練的數(shù)學(xué)語言來表述就是：求這樣一個數(shù)，使它被除余，被除余，被除余。,x 2(mod 3) x 3(mod 5) x 2(mod 7) X=?,中國剩余定理,考慮方程組xai(mod mi), mi兩兩互素 在0i時ei0(mod mj) 則e1a1+e2a2+ekak就是一個解, 調(diào)整得到0,m)內(nèi)的唯一解（想一想，如何調(diào)整）,整理一下,一般線性方程組aixibi(mod ni) axb(mod n) xb1(mod n1) xb1(mod n1) xb1(mod p1,i) 用中國剩余定理 其他規(guī)則同余方程 二項方程: 借助離散對數(shù)(本身?) 高次方程: 分解n, 降冪 單個多變元線性方程: 消法,求解模線性方程組步驟：,找到模線性方程組中每個方程的ai ，ni 求出相對應(yīng)的 mi , mi-1 求出相應(yīng)的 ci =mi (mi-1 mod ni ) 最后一步：a (a1c1+a2c2+akck) (mod n),x 2(mod 3) x 3(mod 5) x 2(mod 7) x=?,a1=2 n1=3 a2=3 n2=5 a3=2 n3=7 n=n1*n2*n3=105 m1=35 m1-1=2 m2=21 m2-1=1 m3=15 m3-2=1 a=23+k*n(k=0,1,2),練習(xí)：Poj 1006,