講義答案隨堂筆記第9階與原根

1例題例題1證明：若m2α，αN?，α3，則對任意奇數(shù)設(shè)a2k則 =(2k+ ≡1+2α?2?(2k)+=1+2α?1?k+2α?1?(2α?2?1)=1+2α?1(k+(2α?2?1)≡1最后一步用到k與(2α?21)k2同奇偶，從而其和為偶數(shù)．這時，命題成則可設(shè)m=rt，這里2<r<t且(r,t)=1．這時，若(a,m)=1， 定理可aφ(r)≡1modr)，aφ(t1modt)．注意到當(dāng)n2時，φ1a2φ(r≡1(modrt，進(jìn)而δm(a1φ(r)φ(t) φ(rt) φ(m)<φ11 2答 見解 證明：先建立一個引理：設(shè)a，b是與p互素的兩個整數(shù)，則存在c∈Z，使得δp(c)=[δp(a),δp(b)]．亊實(shí)上，記δp(ar，δp(bt，并設(shè)rdx，這里drt)，則[δp(a),δp(b)]=xt．由本節(jié)性質(zhì)2．知 (ad) δp = (δp(a), (r,而δp(b)=t，(x,t)=1，由性質(zhì)1即有δp(adb)=xt．引理獲證．回到原命題．利用上述引理，結(jié)合數(shù)學(xué)歸納法，可知存在g∈Z，使得δp(g)=[δp(1δp(2δp(p?1)]．這表明，δp(jδp(g)，j=1，2，?，p所以，j1，2，?，p1都是同余方程xδp(g)1modp)由由日定理，可知δp(g?p另一方面，由費(fèi)馬小定理知gp?11(modp)，故應(yīng)有δp(g)∣(p?1)．綜上可知，δp(gp1，3答 見解解 先證明：存在模p的原根g，使得 ≡1p的原根g，若g不滿足(1)，我們說g+p是滿足(1)的模p的一個原g為模p的原根，可知g+p是模p的一個原根．其次，我們有(gp)p?1gp?1p(p1)1pgp?2 1再證明：若g為模p的滿足(1)的原根，則對任意αN?，g是模pn的原根．首先，我們有下面的結(jié)論：對任意β∈N?，都可設(shè)βgφ(pβ)=1+pβ?kβ這里p?kβ，事實(shí)上，當(dāng)β1時，由g的選擇可知(2)成立．現(xiàn)設(shè)(2)對β則pφ(pβ+1則p

=

φ(pβ))

=(1+

?kβ1pβ+1kβ(modpβ+2)，結(jié)合p?kβ，可知(2)對β1成立．所以，(2)對βN?都成立．∣其次，記δ=δpα(g)，則 定理，可知δ∣pα?1(p?∣而由g為模p的原根，及gδ≡1(modpα)(當(dāng)然，更有g(shù)δ≡1(modp))，可知(p?∣δ．所以可設(shè)δpβ?1(p1)，這里1βφ(φ(p 現(xiàn)在利用(2)，可知 ≡1 即 ≡1結(jié)合gδ1modpα)，可知β?綜上可知，βα，即δpα(g)=pα?1(p1)φ(pα)，從而，g是模pα的原根．4答 見解 證明：設(shè)g是模pα的原根，則g+pα也是模pα的原根．在g和g+pα中有一個為奇數(shù)，~,于是， (~)(2pα．而~)α2pα(g~)1mod2pα)，故(~)δ2pα(g~1modpα)．利用~為模pα的原故故φ(pαδ2pα(g~．結(jié)合φ(pαφ(2pα)，即可知是模2pα的原根．例題1例題1證明：注意到，n是滿足下述同余an1modan1)的最小正整數(shù)(因?yàn)閍1)，即δan?1(a)=n． ≡1(modan?1)，因此結(jié)合指數(shù)的性質(zhì)，就有n∣φ(an?1)．n∣n就有q≡12∣所以，對F的素因子q，我們有q +1)．利用引理的結(jié)論≡?1(modF≡n=(22)≡++== +nFn證明：先證一個引理：設(shè)a為大于1的正整數(shù)，q為數(shù)a21的奇素因子，則q≡1(mod2n+1)．事實(shí)上，由a2≡?1(modq)知a2 ≡1(modq)，這表明δq(a)?2n，但δq(a)∣2n+1．所以，δq(a)=2n+1(注意，這里已用到q>2)．然后由費(fèi)馬小定理知aq?1≡1(modq)，故2n+1∣(q?1)，即q≡1(mod2n+1)．回到原題．當(dāng)n>1n1例題例題例題1答 見解1 ?1,n)=1，并設(shè)n= ? 1 ?1,n)=1，并設(shè)n= ? 這里p1<p2<?<pk為素?cái)?shù)，αi∈N?，1?i?k．進(jìn)一步，設(shè)pβ∣(n1)，但pβ+1?(n?1)，這里β∈N． 由條件，mp(n?1)≡1modpi)，記δiδp(m)i1?i?k．則δi∣p(n?1)．又由(mn?11n1，知pi?(mn?1故δi?(n因此，p∣δi．進(jìn)一步，我們還能得到pβ+1∣δi事實(shí)上，若pβ+1?δi，則可設(shè)pγ∥δi，這里1?γ?于是，由β的定義可知p∣(n1)．再由δi∣p(n1)，知pγ∣p(nγ結(jié)合(p,δi1，知δi∣(n1)．再由(pγ,δi1，可得δipγ?δi為n1的·所以，pβ+1i定理，mpi?11modpi)，故δi∣(pi因此，pi1modpβ+1)，1i?n= ?α1 k≡1 β，與β·立p?pp?從而， 有一個素因子q，滿足 p?下面證明：這個q是一個符合要求的素因子．2事實(shí)上，若存在nZ，使得npp(modq)，則np≡pp≡1(modq)，2而由費(fèi)定理，知nq?1≡1(modq)，所以，n(p2,q?1)1modq)． ≡1故(p2,q?1)∣p，因此np1modq)，進(jìn)而pnp1modq)．，0≡pp?1=1+p+?+pp?1≡1+1+?+1≡p，p?p個要求q∣1， 例題例題例題例題1證明：當(dāng)j=0j12p2}的情形．取模p的原根g，則當(dāng)x遍經(jīng)模p的完系時，gx也遍經(jīng)模p 故xj(gx)j∣即p∣(gj1xj．而g為模p∣故1jp2時，都有p?(gj?1)，∣所以，p∣xj∣例題例題1答 見解解 p2p+p+證明：我們只要證明 的任一個素約數(shù)q滿足q≡1(mod4pp+p2p+ 首先注意p2故q=設(shè)r是p模q的階

= ? +?? +因p2p1modq)，②故p4p≡1(modq)，所以r∣4p于是r=1，2，4，p，2p或若r=1，2，p，2p，將導(dǎo)出p2p≡1modq)，結(jié)合②得到q=2若r=4，則因q是素?cái)?shù)，我們推出q∣(p21或q∣(p21)．前者已證明為不可能．若后者成立，即p2≡?1 而右邊≡(?1)p?1?(?1)p?2+??(?1)+1≡(modq)．因此pq，這不可能故r=因此只能r=最后，因(pq)=故由費(fèi)定理得pq?1≡1(modq)，于是r∣(q?1)，即即4p∣(q1因此q≡1例題例題1解：只要證明Fk的任一個素因子p滿足p≡1(mod2k+1)．顯然設(shè)2模p的階為r，由p∣Fk得22≡?1(k故 ≡1(modp)，從而r∣2k+1所以r是2∣·設(shè)r=2l，其中0?l?k+若l?k，則由22≡1(modp)可推出22≡1modp)，結(jié)合①得p=2，這不可能，故必須l?=k+1．又2p?1≡1(modp)從而有r∣(p?1)，故2k+1∣(p1即p≡1(mod2k+1lk例題例題1答 見解解 引理：設(shè)p是一個給定的奇素?cái)?shù)，整數(shù)u>1且p?∥設(shè)d是u模p的階，并設(shè)pv∥(ud1)．則對任意與p互素的正整數(shù)m及任意整數(shù)t?有pt+v∥(udmpt?1)．∥引理的證明：對t歸納，當(dāng)t=0時，由v的定義知ud=1+pvk(其中p?k)， 由于p?km及v故上式右端可表示為1+pvk1的形式，其中k1是一個與p互素的整數(shù)，從而引理在t=0t立．假設(shè)引理對t已成立，即設(shè)udmp=1ptt+vk?

=(1+pt+vk)p=1+pt+1+v(k+C2pv+t?1k2+?t=1+pt+1+vkt+1

∣其中p?kt+1(注意p是奇素?cái)?shù)，故

C2∣當(dāng)u=1時結(jié)論顯然立．對u1，將方程化n!=ur(us?其中r、s為正取定一個奇素?cái)?shù)p?u，可設(shè)np(否則結(jié)論已成立)，并設(shè)pα∥n，則α1．由①及p?u知pα∥(us?1)，特別地有p∣(us?1)．設(shè)d是u模p的階，則有d∣s設(shè)sdmpt，其