數(shù)論中的基礎(chǔ)概念

1、1群、環(huán)、域概念A(yù)1：加法的封閉性：如果a和b屬于G，則a+b也屬于GA2：加法結(jié)合律：對(duì)G中的任意元素a,b,c,a+(b+c)=(a+b)+cA3：加法單位元：G中存在一個(gè)元素0，使得對(duì)于G中的任意元素a，有a+0=0+aA4：加法逆元：對(duì)于G中的任意元素a，G中一定存在一個(gè)元素a,使得 a+(-a)=(-a)+a=0A5：加法交換律：對(duì)于G中的任意元素a和b，有a+b=b+aM1：乘法的封閉性：如果a和b屬于G，則ab也屬于GM2：乘法結(jié)合律：對(duì)于G中的任意元素a,b,c有a(bc)=(ab)cM3：乘法分配了：對(duì)于G中的任意元素a,b,c，有a(b+c)=ab+ac和(a+b)c=ac

2、+bcM4：乘法交換律：對(duì)于G中的任意元素a,b有ab=baM5：乘法單位元：對(duì)于G中的任意元素a,在G中存在一個(gè)元素1，使得a1=1a=aM6：無(wú)零因子：對(duì)于G中的元素a,b，若ab=0，則必有a=0或b=0M7：乘法逆元：如果a屬于G，且a不為0,則G中存在一個(gè)元素，使得 滿足A1-A4稱為群滿足A1-A5稱為可交換群滿足A1-M3稱為環(huán)滿足A1-M4稱為可交換換滿足A1-M6稱為整環(huán)滿足A1-M7稱為域2循環(huán)群：如果群中的每一個(gè)元素都是一個(gè)固定元素的冪（k為整數(shù)）， 則稱群G是循環(huán)群。我們認(rèn)為元素a生成了群G，或者說(shuō)a是群G的 生成元。 循環(huán)群總是交換群3模運(yùn)算則稱整數(shù)a和b是模n同余的

3、，可以表示為：若b整除a。則用符號(hào)：表示。其性質(zhì)可表示如下：如果a|1,那么a=-1或1。如果a|b，且b|a，那么a=b或a=-b任何不等于零的數(shù)整除0如果b|g且b|h，那么對(duì)任意整數(shù)m,n都有b|（mg+nh）證明性質(zhì)： 如果b|g，那么,g為整數(shù)。 如果b|h，那么，h為整數(shù)。 于是： 因此b整除mg+nh.同余的性質(zhì)：1如果n|（a-b），那么2隱含3，隱含性質(zhì)2和性質(zhì)3證明是我自己證的。性質(zhì)1證明： 如果，那么，為整數(shù)。使得， 則有即得。性質(zhì)2證明： 由得：即，滿足 由可推出,由性質(zhì)1可知成立則得證。性質(zhì)3證明：由性質(zhì)2證明過程知：滿足：由可以推出，由性質(zhì)1可知模算術(shù)運(yùn)算有如下性質(zhì)

4、：123性質(zhì)2性質(zhì)2是我自己證明的。性質(zhì)1證明： 設(shè)，則，使得 那么有： 即得證。性質(zhì)2證明： 由性質(zhì)1證明過程知使得 那么有：性質(zhì)3證明： 前半段證明如上， 定義比n小的非負(fù)整數(shù)集合為。這個(gè)集合稱為剩余類集，或模n的剩余類。 中每一個(gè)整數(shù)都代表一個(gè)剩余類，我們可以將模n的剩余類表示為：，其中。 如果，那么若a與n互素，如果，那么 中整數(shù)模運(yùn)算性質(zhì)：交換律： 結(jié)合律： 分配律：?jiǎn)挝辉?加法逆元（-w）：對(duì)于中的任意w，存在一個(gè)z使得以下部分摘自劉嘉勇編P231加法逆元：對(duì)每一個(gè)，存在一個(gè)u,使得w+u=0 mod n，記為u=-w,顯然在模 n下，-w=n-w。如果，則有 ， 特例， 更一般

5、式：， 特例： 其中f(x)為任意給定的一個(gè)整系數(shù)多項(xiàng)式以上部分摘自劉嘉勇P231最大公約數(shù)：歐幾里得算法：對(duì)于任意非負(fù)整數(shù)a和任意正整數(shù)b有算法描述如下：設(shè)整數(shù) （1）； （2）如果Y=0，返回X=gcd(a,b)，否則繼續(xù)； （3）R=XmodY （4）； （5）; （6）返回（2）擴(kuò)展的歐幾里得算法描述如下：Extended EUCLID(a,n) （1）； （2）如果，返回，無(wú)逆元；否則繼續(xù)； （3）如果，返回； （4）； （5）； （6）； （7）； （8）返回（2）。 有限域GF(P): 階為的有限域一般記為，GF代表伽羅瓦域。 給定一個(gè)素?cái)?shù)p，元素個(gè)數(shù)為p的有限域GF(p)被定義

6、為整數(shù)的集合，其運(yùn)算為模p的算術(shù)運(yùn)算。 乘法逆元：任意，存在使得求最大公因式：我們可以通過定義最大公因式來(lái)擴(kuò)展域上的多項(xiàng)式和整數(shù)運(yùn)算之間的類比。如果：1.c(x)能同時(shí)整除a(x)和b(x)。 2.a(x)和b(x)的任何因式都是c(x)的因式。 就稱多項(xiàng)式c(x)為a(x)和b(x)的最大公因式。 此定義等價(jià)定義與：gcda(x),b(x)是能同時(shí)整數(shù)a(x)和b(x)的多項(xiàng)式中次數(shù)最高的一個(gè)。多項(xiàng)式模運(yùn)算： 如果定義了合適的運(yùn)算，那么每一個(gè)這樣的集合S都是一個(gè)有限域。定義由 如下幾條組成：1. 該運(yùn)算遵循基本代數(shù)規(guī)則中的普通多項(xiàng)式運(yùn)算規(guī)則2. 系數(shù)運(yùn)算以P為模，即遵循有限域上的運(yùn)算規(guī)則3.

7、 如果乘法運(yùn)算結(jié)果是次數(shù)大于n-1的多項(xiàng)式，那么必須將其除以某個(gè)次數(shù)為n的既約多項(xiàng)式m(x)并取余式。對(duì)于多項(xiàng)式f(x)，這個(gè)余式可表示為r(x)=f(x) mod m(x)素?cái)?shù)任意整數(shù)都可以惟一地因子分解為：，其中均為素?cái)?shù)，且指數(shù)皆為正整數(shù)。費(fèi)馬定理：p是素?cái)?shù)，a是與p互素的正整數(shù)，則 或者 顯然有歐拉函數(shù)：歐拉函數(shù)是一個(gè)定義在正整數(shù)集上的函數(shù)，的值等于小于n 且與n互素的正整數(shù)的個(gè)數(shù)。歐拉函數(shù)有性質(zhì)如下： 1.如果n是素?cái)?shù)，則 2.如果，p和q是素?cái)?shù)，且p不等于q則 歐拉定理：對(duì)任何互素的兩個(gè)整數(shù)a和n，有。歐拉定理有如下推論。1. n為素?cái)?shù)時(shí)，有，即費(fèi)馬定理。2. 由歐拉定理，有進(jìn)一步有

8、，3. 若n=pq，p和q是素?cái)?shù)，p不等于q，則有。4. 若n=pq，p和q是素?cái)?shù)，p不等于q，而，仍有中國(guó)剩余定理：設(shè)正整數(shù)兩兩互素，記，則同余在模M同余的意義下，有唯一解，其中：如果，則至少有一個(gè)整數(shù)m（即）滿足。滿足上式的最小正整數(shù)m為模n下a的階（又稱次數(shù)）。本原根：如果a的階等于，則稱a為n的本原根（又稱素根）有些材料上稱本原元性質(zhì)：如果a是n的本原根，則在模n下互不相同，且均與n互素。注意：模n下的本原根并不具備唯一性，且并非所有的整數(shù)n都有本原根，只有以下形式的整數(shù)才有本原根：，其中a為整數(shù)，p為奇素?cái)?shù)。離散對(duì)數(shù)：設(shè)p為以素?cái)?shù)，a是p的本原根，則在模p下產(chǎn)生1到p-1之間的所有值，且每一個(gè)值僅出現(xiàn)一次。因此：對(duì)于任意，都存在唯一的正整數(shù)，使得這樣，模p下a的方冪運(yùn)算為：，稱x為模p下以a為底y的對(duì)數(shù)，記為：，以上運(yùn)算定義在模p有限域上的，所以稱為離散對(duì)數(shù)運(yùn)算。性質(zhì)