07原根(編輯修改稿)
2024-09-28 00:20 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的簡(jiǎn)化剩余系中，恰有 ?(d)個(gè)指數(shù)為 d 的整數(shù)，并由此推出模 m的簡(jiǎn)化剩余系中恰有 ?(?(m))個(gè)原根 。 4. 設(shè) m ? 3， g是模 m的原根， x1, x2, ? , x?(m)是模 m的簡(jiǎn)化剩余系，證明： (ⅰ ) 2)(mg? ? ?1 (mod m)； (ⅱ ) x1x2? x?(m) ? ?1 (mod m)。 5. 設(shè) p = 2n ? 1是一個(gè)奇素?cái)?shù)，證明：模 p的全部二次非剩余就是模 p的 全部原根 。 6. 證明： (ⅰ ) 設(shè) p奇素?cái)?shù)，則 Mp = 2p ? 1的素因數(shù)必為 2pk ? 1型； (ⅱ ) 設(shè) n ? 0，則 Fn = n2 ? 1的素因數(shù)必為 2n + 1k ? 1型 。 第二節(jié) 原 根 對(duì)于什么樣的正整數(shù) m， 模 m的原根是存在的？這是本節(jié)要研究的問(wèn)題 。 為了敘述方便 ， 對(duì)于正整數(shù) n，設(shè)它的標(biāo)準(zhǔn)分解式是 n = kkppp ???? ?21 212 ， 其中 pi（ 1 ? i ? k）是奇素?cái)?shù) ， 記 ?(n) = [ )(,),(),(),2( 21 21 kkppp ???? ???? ?]。 定理 1 模 m有原根的必要條件是 m = 1， 2， 4， p?或 2p?， 其中p是奇素?cái)?shù) ， ? ? 1。 證明 若 m不具備定理中所述形式 ， 則必是 m = 2?（ ? ? 3） ， (1) m = kkppp ???? ?21 212 （ ? ? 2， k ? 1）， (2) 或 m = kkppp ???? ?21 212 （ ? ? 0， k ? 2）， (3) 159 其中 pi（ 1 ? i ? k）是奇素?cái)?shù)， ? i（ 1 ? i ? k）是正整數(shù) 。 如果 m是形如式 (2)的數(shù) ， 那么對(duì)于任意的 a， (a, m) = 1， 有 ，，，kipaakipaaiiiiimmip????????1)(m od1)2(m od11)(m od1)2(m od1)()()()2(?????????? a?(m) ? 1 (mod m)。 (4) 容易驗(yàn)證 ?(m) ?(m)。 因此，由式 (4)可知，任何與 m互素的數(shù) a不是模 m的原根 。 同樣方法可以證明，若 m 是形如式 (1)或式 (3)中的數(shù)，模 m 也沒(méi)有原根 。 證畢。 下面我們要證明，定理 1 中的條件也是充分條件 。 為此，先要證明幾個(gè)引理 。 引理 1 設(shè) m 是正整數(shù) 。 對(duì)任意的整數(shù) a， b，一定存在整數(shù) c，使得 ?m(c) = [?m(a), ?m(b)]。 證明 由第一章第六節(jié)習(xí)題 6，存在正整數(shù) ?1， ?2， ?1， ?2，使得 ?m(a) = ?1?2， ?m(b) = ?1?2， (?2, ?2) = 1， [?m(a), ?m (b)] = ?2?2 。 (5) 由第一節(jié)定理 3，有 22 )()( 11 ???? ?? ?? ba mm ， ， 因此，由第一節(jié)定理 4得到 )()()( 1111 ???? ??? baba mmm ? = ?2?2 = [?m(a), ?m(b)]。 取 c = 11 ??ba 即可得證 。 證畢。 引理 2 若 p是奇素?cái)?shù) ， 則模 p有原根 。 證明 由引理 1及歸 納法容易證明，存在整數(shù) g， (g, p) = 1，使得 ? = ?p(g) = [?p(1), ?p(2), ? , ?p(p ? 1)]。 顯然 ??p ? 1， ?p(j)??， 1 ? j ? p ? 1。 (6) 另一方面 ， 由 式 （ 6
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1