數論中的基礎概念

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

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

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

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

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

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

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

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