標籤: 暫無標籤

數論中的重要概念。給定一個正整數m,如果二整數α、b)滿足m│α-b)(α-b)被m整除),就稱整數α、b)對模m同餘,記作α呏b)(mod m)。對模m同餘是整數的一個等價關係。

1簡介

數學上,兩個整數除以同一個整數,若得相同餘數,則二整數同餘(英文:Modular arithmetic;德文:Kongruenz)。同餘理論常被用於數論中。最先引用同餘的概念與符號者為德國數學家高斯。
同餘

  同餘

同餘理論是初等數論的重要組成部分,是研究整數問題的重要工具之一,利用同餘來論證某些整除性的問題是很簡便的.同餘是數學競賽的重要組成部分.

2同餘符號

兩個整數a,b,若它們除以整數m所得的餘數相等,則稱a與b對於模m同餘或a同餘於b模m
記作a ≡ b (mod m)
讀作a同餘於b模m,或讀作a與b關於模m同餘。
比如 26 ≡ 2 (mod 12)
【定義】設m是大於1的正整數,a,b是整數,如果m|(a-b),則稱a與b關於模m同餘,記作a≡b(mod m),讀作a與b對模m同餘.
顯然,有如下事實
(1)若a≡0(mod m),則m|a;
(2)a≡b(mod m)等價於a與b分別用m去除,餘數相同.
【證明】 充分性:設a=mq1+r1,b=mq2+r2,0<=r1,r2<m
∵ m|(a-b),a-b=m(q1-q2)+(r1-r2).
則有m|(r1-r2).
∵0<=r1,r2<m,∴0<=|r1-r2|<m,
即r1-r2=0,∴r1=r2.
必要性:設a,b用m去除餘數為r,即a=mq1+r,b=mq2+r,
a-b=m(q1-q2) ∴m|(a-b),
故a≡b(mod m).

3性質

1 反身性 a ≡ a (mod m)
2 對稱性 若a ≡ b(mod m) 則b ≡ a (mod m)
3 傳遞性 若a ≡ b (mod m),b ≡ c (mod m),則a ≡ c (mod m)
4 同餘式相加若a ≡ b (mod m),c≡d(mod m),則a+-c≡b+-d(mod m)
5 同餘式相乘 若a ≡ b (mod m),c≡d(mod m),則ac≡bd(mod m)
證明】上述性質很容易證明,下面僅證明(3).
∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),
∴m|[(a-b)+(b-c)]∴m|(a-c).
故a≡c(mod m).
4 線性運算如果a ≡ b (mod m),c ≡ d (mod m),那麼(1)a ± c ≡ b ± d (mod m),(2)a * c ≡ b * d (mod m)
【證明】(1)∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d)
∴m|[(a-b)±(c-d)] ∴m|[(a±c)-(b±d)]
∴a ± c ≡ b ± d (mod m)
(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)
又 m|(a-b) , m|(c-d) ∴m|(ac-bd)
∴a * c ≡ b * d (mod m)
5 除法若ac ≡ bc (mod m) c!=0 則 a≡ b (mod m/(c,m)) 其中(c,m)表示c,m的最大公約數
特殊地 (c,m)=1 則a ≡ b (mod m)
6 乘方如果a ≡ b (mod m),那麼a^n ≡ b^n (mod m)
7 若a ≡ b (mod m),n|m,則 a ≡ b (mod n)
8 若a ≡ b (mod mi) i=1,2...n 則 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍數
9 歐拉定理
設a,m∈N,(a,m)=1,則a^(φ(m))≡1(mod m)
(注:φ(m)指模m的簡系個數, φ(m)=m-1, 如果m是素數;φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))
推論: 費馬小定理: 若p為質數,則a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)
(但是當p|a時不等價)
10 中國剩餘定理
設整數m1,m2,m3,......,mn 兩兩互素,令m=m1m2m3m4m5...mn(mi的連乘)。則對於任意的J在(1,n)整數,下列聯立的同餘式有解:
{xj≡1(mod mj)
{xj≡0(mod mi) i不等於j
令x為從1到najxj的和,則x適合下列聯立同餘式
x≡aj(mod mj), j=1,2,3,.....,n
另:求自然數a的個位數字,就是求a與哪一個一位數對於模10同餘

4相關定理

一次同餘式和孫子定理 同餘式的求解中,一次同餘式是最基本的。設整係數n次(n>0)多項式ƒ(x)=αnx+…+α1x+α0,m是一個正整數且不能整除αn,則
同餘

  同餘

(1)叫做模m 的n次同餘式。如果整數α是(1)的解且αα┡(mod m),那麼α┡也是(1)的解,因此,(1)的不同解是指滿足(1)的模 m互不同餘的數。對於一次同餘式 αxb(mod m)有解的充分必要條件是(α,m)│b),若有解則有(α,m)個解。一次同餘式組是指
同餘

  同餘

同餘

  同餘

。 (2)
在中國古代《孫子算經》中,對某些具體的一次同餘式組已有解法,把這一解法加以推廣,就是著名的孫子剩餘定理:設m1, m2,…, mk是k個兩兩互素的正整數
同餘

  同餘

,
則同餘式組(2)的解是
同餘

  同餘

,
式中。孫子剩餘定理又被稱之為中國剩餘定理,是數論中一個重要的定理,除了數論本身,數學的許多其他分支以及一些應用學科都要用到它。例如,設m=m1m2…mk,m1, m2,…,mk兩兩互素,利用孫子剩餘定理可將同餘式(1)的求解問題化為同餘式組ƒ(x)≡0(mod mi)(i=1,2,…,k)的求解問題,於是就只需要研究(1)中m是素數方冪的情形了。又如,可將0≤x<m中的一切整數表示,這叫做模係數記數法,這裡m=m1m2…mk,m1,m2,…,mk兩兩互素,而x嗎示x模mi的最小非負剩餘。
如果已知x的模係數記數法,就可用孫子定理找出x。這個記數法的優點是加法和乘法無須進位,它在計算機方面有應用。
素數為模的同餘式  關於素數為模的同餘式,1770年,J.-L.拉格朗日證明了如下定理:設p是素數,那麼模pn次同餘式的解數不大於n(重解也計算在內)。人們稱之為拉格朗日定理。由此立即可以得威爾森定理:如果p是素數,那麼(p-1)!+1≡0(modp)。因為x-1≡0(modp)有p-1個解1,…,p-1,故由拉格朗日定理可得
x^p-1-1≡(x-1)(x-2)…(x-(p-1))(modp),
x=0代入上式得-1≡(-1)(p-1)!(modp),這就證明了威爾森定理。威爾森定理的逆定理也是成立的,可用反證法簡單證出。用拉格朗日定理還可證明:當p≥5是一個素數時,則有
同餘

  同餘

。這個定理是1862年,由J.沃斯頓霍姆證明的。
ƒ(x1,x2,…,xn)是n元整係數多項式,p是一個奇素數,對於同餘式ƒ(x1,x2,…,xn) ≡0(mod p)的解(x1,x2,…,xn)(0≤xj<p,j=1,2,…,n)的個數N的研究,是數論的重要課題之一。
早在1801年,C.F.高斯就研究了同餘式αx-b)y≡1(modp)的解的個數,這裡p≡1(mod 3)和同餘式αx-b)y≡1(modp)的解的個數,這裡p≡1(mod 4)。
ƒ(x)模p無重因式,1924年,E.阿廷猜想同餘式yƒ(x)(modp),在ƒ(x)的次數為3和4時,N分別滿,1936年,H.哈塞證明了這一猜想,並且還證明了對於一般含q個元的有限域,把以上兩式中p換成q,也是對的。1948年,韋伊對於一般的ƒ(x,y)=0在有限域上得到類似的結果, 他猜想對於ƒ(x1,x2,…,xn)=0也有類似的結果。1973年,P.德利涅證明了韋伊猜想。他的傑出工作獲得了1978年的國際數學家會議的費爾茲獎。
上一篇[p進數]    下一篇 [阿列夫數]

相關評論

同義詞:暫無同義詞