保障與安全數(shù)論ppt課件-文庫吧資料
2025-01-18 13:12本頁面
【正文】 r2=s2a+t2b 這樣一直下去，最后得 d=rk=s*a+t*b, s,t∈ z 11 歐幾里得（ Euclid）算法 是數(shù)論中的一個(gè)基本技術(shù)，是求兩個(gè)正整數(shù)的最大公因子的簡(jiǎn)化過程。 (k) 10 由于歷次所得的余數(shù) r1 r2 r3 r4 … rk… =0 是嚴(yán)格遞降的一串非負(fù)整數(shù) ， 故最后總會(huì) 出現(xiàn)余數(shù)為 0的情形： rk1=qk+1rk (k+1) 所以，進(jìn)行有限步必停止，此時(shí) d=rk=(a,b)定成立，這是因?yàn)? 1*. 可見 rk為 a和 b的公約數(shù)，只要按倒序分析自然有此結(jié)論。 (3) 等等，這樣一直進(jìn)行下去，可得一系列關(guān)系式： rk3=qk1rk2+rk1,0=rk1rk2。 (2) 如果 r2=0，停止，否則再用 r2去除 r1，得 r1=q3r2+r3。 證明（ 自己看 )不妨設(shè) b0，用輾轉(zhuǎn)相除法，先用 b去除 a，得 a=q1b+r1,0=r1b。 例 z12中： [3]*[4]=[12]=[0] 說明， zm中的元素可分為兩類，一類是零因子 ，即若α∈ zm,α≠[0]存在 β∈ zm且 β≠[0]，有 α*β=[0]，稱 α， β都為zm中的零因子。（從 ax+my=b入手） 8 6*.整數(shù)環(huán) z模正整數(shù) m得到的剩余類集合可以記為 zm(或 z/(m)) zm={[0],[1],…,[m 1]} 在 4中已說明 zm對(duì)剩余類的加法，乘法是封閉的，可列出它們的加乘表。當(dāng)這個(gè)條件滿足時(shí)，恰有 d個(gè)模 m同余類中的整數(shù)是上述方程的解。(224) (mod47) ≡(30) (32) mod(47) ≡(7)(30) 25 ≡90025=(26 解： 注意 53=125≡13(mod56) 于是有 56≡169≡1(mod56) 對(duì)同余式的兩邊同時(shí)升到 10次冪， 即有 56∣ 5601。 b(mod m)] mod m =(a177。 Z模 12的標(biāo)準(zhǔn)剩余系為：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11] 自反性 對(duì)稱性 傳遞性 5 4*. 對(duì)于某個(gè)固定模 m的同余式可以象普通的等式那樣相加相減和相乘 （ 可交換的 、 可結(jié)合的 、 可分配的 ） 而且 ， 簡(jiǎn)化運(yùn)算每個(gè)中間結(jié)果的模 n運(yùn)算 ， 其作用與先進(jìn)行全部運(yùn)算 ， 然后再簡(jiǎn)化模 n運(yùn)算是一樣的 。 k∈ z，每一個(gè)算一類，每一類都可以選一個(gè)代表元，一般選這一類中的最小的非負(fù)整數(shù)。 具有等價(jià)關(guān)系的三點(diǎn)基本性質(zhì)： 對(duì)任意整數(shù) a有 a≡a（ modm） 如果 a≡b(modm)則 b≡a（ modm） 如果 a≡b (modm） ,b≡c（ modm） 則 a≡c(modm) 于是，全體整數(shù)集合 z可按模 m（ m1）分成一些兩兩不交的等價(jià)類?！巴唷倍值膩碓淳驮谟诖?。 (若 r=0則 m∣ a） ? 整數(shù)同余式和同余方程： 定義（同余）稱整數(shù) a模正整數(shù) m同余于整數(shù) b，并寫 a≡b（ mod m）是指 m∣ a－ b, m稱為模數(shù)。整數(shù)環(huán) z對(duì)除法運(yùn)算不封閉。 注 ： 1*. 等價(jià)的定義形式是： gcd（ a,b）＝ max{k∣ k∣ a， k∣ b} 2*．若 gcd（ a,b） =1，稱 a與 b是互素的 。正 整數(shù) d稱為 a和 b的最大公約數(shù)，如果它滿足 ? d是 a和 b的公約數(shù)。 ? 用 Euclid算法求乘法逆元 若 a和 n互素，則 a在模 n下有逆元。1 數(shù)論導(dǎo)引 1 素?cái)?shù)和數(shù)的互素 除數(shù) (因子 )的概念： 設(shè) z為所有全體整數(shù)構(gòu)成的集合，若 b≠0且 使得 a=mb , 此時(shí)稱 b整除 b∣ a,還稱b為 a的除數(shù) (因子 ). 注 :若 a=mb+r且 0rb,此時(shí) b不整除 a,記為 b┼ a 素?cái)?shù) (質(zhì)數(shù) )的概念
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1