• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0
            源地址: http://www.shnenglu.com/zoyi-zhang/articles/43456.html 
            歐拉函數(shù) :
            歐拉函數(shù)是數(shù)論中很重要的一個(gè)函數(shù),歐拉函數(shù)是指:對(duì)于一個(gè)正整數(shù) n ,小于 n 且和 n 互質(zhì)的正整數(shù)(包括 1)的個(gè)數(shù),記作 φ(n) 。 

            完全余數(shù)集合:
            定義小于 n 且和 n 互質(zhì)的數(shù)構(gòu)成的集合為 Zn ,稱呼這個(gè)集合為 n 的完全余數(shù)集合。 顯然 |Zn| =φ(n) 。

            有關(guān)性質(zhì):
            對(duì)于素?cái)?shù) p ,φ(p) = p -1 。
            對(duì)于兩個(gè)不同素?cái)?shù) p, q ,它們的乘積 n = p * q 滿足 φ(n) = (p -1) * (q -1)  。
            這是因?yàn)?Zn = {1, 2, 3,  ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} , 則 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1)  =φ(p) * φ(q) 。

            歐拉定理 :
            對(duì)于互質(zhì)的正整數(shù) a 和 n ,有 aφ(n)  ≡ 1 mod n  。

            證明:
            ( 1 ) 令 Zn = {x1, x2, ..., xφ(n), S = {a * x1 mod n, a * x2 mod n, ... , a * xφ(n) mod n} 
                    則 Zn = S 。
                    ① 因?yàn)?a 與 n 互質(zhì), xi (1 ≤ i ≤ φ(n)) 與 n 互質(zhì), 所以 a * xi  與 n 互質(zhì),所以 a * xi  mod n ∈ Zn 。
                    ② 若 i ≠ j , 那么 xi ≠ xj,且由 a, n互質(zhì)可得 a * xi mod n ≠ a * xj mod n (消去律)。

            ( 2 )     aφ(n) * x* x2 *... * xφ(n) mod n 
                   (a * x1) * (a * x2) * ... * (a * xφ(n)) mod n
                   (a * x1 mod n) * (a * xmod n) * ... * (a * xφ(n) mod n) mod n
                    x* x* ... * xφ(n) mod n
                  對(duì)比等式的左右兩端,因?yàn)?nbsp;xi  (1 ≤ i ≤ φ(n)) 與 n 互質(zhì),所以 aφ(n)  ≡  1 mod n (消去律)。
            注:
            消去律:如果 gcd(c,p) = 1 ,則 ac ≡ bc mod p ⇒ a ≡ b mod p 。

            費(fèi)馬定理 :
            若正整數(shù) a 與素?cái)?shù) p 互質(zhì),則有 ap - 1 ≡ 1 mod p 。
            證明這個(gè)定理非常簡(jiǎn)單,由于 φ(p) = p -1,代入歐拉定理即可證明。
            *****************************************************************************
            補(bǔ)充:歐拉函數(shù)公式

            ( 1 ) pk 的歐拉函數(shù)

            對(duì)于給定的一個(gè)素?cái)?shù) p , φ(p) = p -1。則對(duì)于正整數(shù) n = pk ,

             φ(n) = pk - pk -1

            證明:
            小于 pk 的正整數(shù)個(gè)數(shù)為 pk - 1個(gè),其中
            和 pk 不互質(zhì)的正整數(shù)有{p * 1,p * 2,...,p * (pk - 1-1)} 共計(jì) pk - 1 - 1 個(gè)
            所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1

            ( 2 ) p * q 的歐拉函數(shù)

            假設(shè) p, q是兩個(gè)互質(zhì)的正整數(shù),則 p * q 的歐拉函數(shù)為

            φ(p * q) = φ(p) * φ(q) , gcd(p, q) = 1 。

            證明:
            令 n = p * q , gcd(p,q) = 1
            根據(jù)中國(guó)余數(shù)定理,有
            Zn 和 Zp × Zq 之間存在一一映射
            (我的想法是: a
            ∈ Zp , b ∈ Zq ⇔ b * p + a * q ∈ Zn 。
            所以 n 的完全余數(shù)集合的元素個(gè)數(shù)等于集合 Zp × Zq 的元素個(gè)數(shù)。
            而后者的元素個(gè)數(shù)為 φ(p) * φ(q) ,所以有
            φ(p * q) = φ(p) * φ(q) 。

            ( 3 ) 任意正整數(shù)的歐拉函數(shù)

            任意一個(gè)整數(shù) n 都可以表示為其素因子的乘積為:

                  I
            n = ∏ piki (I 為 n 的素因子的個(gè)數(shù))
            i=1

            根據(jù)前面兩個(gè)結(jié)論,很容易得出它的歐拉函數(shù)為:


            I I
            Φ(n) = ∏ piki -1(pi -1) = n
            (1 - 1 / pi)
            i=1
            i=1

            對(duì)于任意 n > 2,2 | Φ(n) ,因?yàn)楸卮嬖?nbsp; p-1 是偶數(shù)。

            posted on 2012-04-11 07:11 luis 閱讀(973) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 組合數(shù)學(xué)
            <2012年4月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            亚洲日本va午夜中文字幕久久| 久久无码AV一区二区三区| 色偷偷久久一区二区三区| 精品国产99久久久久久麻豆| 狠狠色综合网站久久久久久久高清| 日韩美女18网站久久精品| 久久精品人人做人人爽97| 国产高潮国产高潮久久久91 | 看全色黄大色大片免费久久久| 久久综合九色欧美综合狠狠| 久久久精品国产免大香伊| 99久久99久久精品国产片果冻| 性做久久久久久久久| 国产成人久久AV免费| 久久国产精品无| 99久久www免费人成精品| 久久精品国产久精国产思思| 香蕉久久久久久狠狠色| 亚洲成人精品久久| 久久久女人与动物群交毛片| 久久一区二区三区免费| 久久精品这里热有精品| 亚洲国产二区三区久久| 无码人妻久久久一区二区三区| 久久精品国产亚洲Aⅴ香蕉 | 久久精品国产亚洲av高清漫画| 亚洲精品WWW久久久久久| 精品国产热久久久福利| 国产亚洲欧美成人久久片| 久久久av波多野一区二区| 亚洲中文久久精品无码| 青草久久久国产线免观| 久久精品国产99久久丝袜| 国产免费久久精品丫丫| 久久综合狠狠色综合伊人| 精品国产福利久久久| 国产精品嫩草影院久久| 久久精品?ⅴ无码中文字幕| 久久久久综合国产欧美一区二区| 久久九色综合九色99伊人| 久久一本综合|