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

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為整數(shù)）， 則稱群G是循環(huán)群。我們認為元素a生成了群G，或者說a是群G的 生成元。 循環(huán)群總是交換群3模運算則稱整數(shù)a和b是模n同余的

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

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

5、式：， 特例： 其中f(x)為任意給定的一個整系數(shù)多項式以上部分摘自劉嘉勇P231最大公約數(shù)：歐幾里得算法：對于任意非負整數(shù)a和任意正整數(shù)b有算法描述如下：設整數(shù) （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代表伽羅瓦域。 給定一個素數(shù)p，元素個數(shù)為p的有限域GF(p)被定義

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

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

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