• <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)論排行榜

            久久电影网一区| 久久频这里精品99香蕉久| 亚洲AV无码成人网站久久精品大| 伊人久久综合成人网| 99久久99这里只有免费费精品| 精品久久一区二区三区| 久久综合九色欧美综合狠狠| 亚洲成色www久久网站夜月| 久久噜噜电影你懂的| 久久久午夜精品福利内容| 精品国产91久久久久久久| 亚洲人成无码网站久久99热国产| 亚洲国产精品无码成人片久久| 99久久精品久久久久久清纯| 97久久国产露脸精品国产| 免费观看久久精彩视频| 亚洲AV无码久久寂寞少妇| 久久e热在这里只有国产中文精品99 | 久久人妻少妇嫩草AV蜜桃| 无码AV波多野结衣久久| 日日狠狠久久偷偷色综合0| 免费精品99久久国产综合精品| 无码人妻久久一区二区三区免费丨 | 久久国产视频网| 久久精品国产91久久综合麻豆自制| 亚洲国产成人久久一区久久| 秋霞久久国产精品电影院| 久久夜色精品国产网站| 久久久久免费精品国产| 亚洲人成网站999久久久综合| 激情综合色综合久久综合| 777久久精品一区二区三区无码 | 国内精品久久久久国产盗摄| 久久精品国产99国产电影网| 久久99精品久久久久久久不卡| 狠狠色丁香婷婷久久综合五月| 久久久中文字幕日本| 久久99热这里只有精品国产| 久久精品中文字幕一区| 久久久噜噜噜久久| 亚洲国产视频久久|