關(guān)于數(shù)論中歐拉函數(shù)和歐拉定理的簡短證明 收藏
一.歐拉函數(shù)的證明
1) p^k的歐拉函數(shù)
對(duì)于給定的一個(gè)素?cái)?shù)p，我們知道φ(p) = p-1。
假設(shè)一個(gè)整數(shù)n是p的k次冪，也就是 n = p^k，k∈N+
容易證明 φ(n) = p^k - p^(k-1)
證明： 已知少于小于p^k的正整數(shù)個(gè)數(shù)為p^k-1個(gè)，其中
和p^k不互質(zhì)的正整數(shù)有{p×1,p×2,...,p×(p^(k-1)-1)}共計(jì)p^(k-1)-1個(gè)
所以φ(n) = p^k -1 - (p^(k-1)-1) = p^k - p^(k-1)
2) pq的歐拉函數(shù)
假設(shè)p,q是兩個(gè)互質(zhì)的正整數(shù)，則pq的歐拉函數(shù)為
φ(pq) = φ(p)φ(q)，gcd(p,q)=1
證明：
∵M(jìn)= pq, gcd(p,q) =1
∴根據(jù)中國余數(shù)定理，有 Zm和Zp×Zq之間存在一一映射
所以M的完全余數(shù)集中元素的個(gè)數(shù)等于集合Zp×Zq元素的個(gè)數(shù)
而后者的元素個(gè)數(shù)為φ(p)φ(q)，所以有 φ(pq) = φ(p)φ(q)
3) 任意正整數(shù)的歐拉函數(shù)
φ(n)=n∏(1-1/p)，其中p為能夠被n整除的質(zhì)數(shù)
二.歐拉定理的證明
對(duì)于互質(zhì)的整數(shù)a和n，有a^φ(n) ≡ 1 (mod n)
證明：
首先證明下面這個(gè)命題：
對(duì)于集合Zn={x_1,x_2,...,x_φ(n)}，考慮集合
S = {ax_1 mod n,ax_2mod n,...,ax_φ(n)mod n}
則S = Zn
1) 由于a,n互質(zhì)，x_i也與n互質(zhì)，則ax_i也一定于n互質(zhì)，因此
任意x_i，ax_i mod n 必然是Zn的一個(gè)元素
2) 對(duì)于Zn中兩個(gè)元素x_i和x_j，如果x_i ≠ x_j
則ax_i mod n ≠ ax_j mod n，這個(gè)由a、n互質(zhì)和消去律可以得出。
所以，很明顯，S=Zn
既然這樣，那么
（ax_1 × ax_2×...×ax_φ(n)）mod n
= （ax_1 mod n × ax_2 mod n × ... × ax_φ(n) mod n）mod n
= （x_1 × x_2 × ... × x_φ(n)）mod n
考慮上面等式左邊和右邊
左邊等于(a^φ(n) × （x_1 × x_2 × ... × x_φ(n)）mod n) mod n
右邊等于x_1 × x_2 × ... × x_φ(n)）mod n
而x_1 × x_2 × ... × x_φ(n)）mod n和n互質(zhì)
根據(jù)消去律，可以從等式兩邊約去，就得到：
a^φ(n) ≡ 1 (mod n)
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
