讲义答案随堂笔记第9阶与原根

1例题例题1证明：若m2α，αN∗，α3，则对任意奇数设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同奇偶，从而其和为偶数．这时，命题成则可设m=rt，这里2<r<t且(r,t)=1．这时，若(a,m)=1， 定理可aφ(r)≡1modr)，aφ(t1modt)．注意到当n2时，φ1a2φ(r≡1(modrt，进而δm(a1φ(r)φ(t) φ(rt) φ(m)<φ11 2答 见解 证明：先建立一个引理：设a，b是与p互素的两个整数，则存在c∈Z，使得δp(c)=[δp(a),δp(b)]．亊实上，记δp(ar，δp(bt，并设rdx，这里drt)，则[δp(a),δp(b)]=xt．由本节性质2．知 (ad) δp = (δp(a), (r,而δp(b)=t，(x,t)=1，由性质1即有δp(adb)=xt．引理获证．回到原命题．利用上述引理，结合数学归纳法，可知存在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另一方面，由费马小定理知gp−11(modp)，故应有δ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的原根．首先，我们有下面的结论：对任意β∈N∗，都可设βgφ(pβ)=1+pβ⋅kβ这里p∤kβ，事实上，当β1时，由g的选择可知(2)成立．现设(2)对β则pφ(pβ+1则p

=

φ(pβ))

=(1+

⋅kβ1pβ+1kβ(modpβ+2)，结合p∤kβ，可知(2)对β1成立．所以，(2)对βN∗都成立．∣其次，记δ=δpα(g)，则 定理，可知δ∣pα−1(p−∣而由g为模p的原根，及gδ≡1(modpα)(当然，更有gδ≡1(modp))，可知(p−∣δ．所以可设δpβ−1(p1)，这里1βφ(φ(p 现在利用(2)，可知 ≡1 即 ≡1结合gδ1modpα)，可知β⩾综上可知，βα，即δpα(g)=pα−1(p1)φ(pα)，从而，g是模pα的原根．4答 见解 证明：设g是模pα的原根，则g+pα也是模pα的原根．在g和g+pα中有一个为奇数，~,于是， (~)(2pα．而~)α2pα(g~)1mod2pα)，故(~)δ2pα(g~1modpα)．利用~为模pα的原故故φ(pαδ2pα(g~．结合φ(pαφ(2pα)，即可知是模2pα的原根．例题1例题1证明：注意到，n是满足下述同余an1modan1)的最小正整数(因为a1)，即δan−1(a)=n． ≡1(modan−1)，因此结合指数的性质，就有n∣φ(an−1)．n∣n就有q≡12∣所以，对F的素因子q，我们有q +1)．利用引理的结论≡−1(modF≡n=(22)≡++== +nFn证明：先证一个引理：设a为大于1的正整数，q为数a21的奇素因子，则q≡1(mod2n+1)．事实上，由a2≡−1(modq)知a2 ≡1(modq)，这表明δq(a)∤2n，但δq(a)∣2n+1．所以，δq(a)=2n+1(注意，这里已用到q>2)．然后由费马小定理知aq−1≡1(modq)，故2n+1∣(q−1)，即q≡1(mod2n+1)．回到原题．当n>1n1例题例题例题1答 见解1 −1,n)=1，并设n= ⋯ 1 −1,n)=1，并设n= ⋯ 这里p1<p2<⋯<pk为素数，αi∈N∗，1⩽i⩽k．进一步，设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．进一步，我们还能得到pβ+1∣δi事实上，若pβ+1∤δi，则可设pγ∥δi，这里1⩽γ⩽于是，由β的定义可知p∣(n1)．再由δi∣p(n1)，知pγ∣p(nγ结合(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事实上，若存在nZ，使得npp(modq)，则np≡pp≡1(modq)，2而由费定理，知nq−1≡1(modq)，所以，n(p2,q−1)1modq)． ≡1故(p2,q−1)∣p，因此np1modq)，进而pnp1modq)．，0≡pp−1=1+p+⋯+pp−1≡1+1+⋯+1≡p，p−p个要求q∣1， 例题例题例题例题1证明：当j=0j12p2}的情形．取模p的原根g，则当x遍经模p的完系时，gx也遍经模p 故xj(gx)j∣即p∣(gj1xj．而g为模p∣故1jp2时，都有p∤(gj−1)，∣所以，p∣xj∣例题例题1答 见解解 p2p+p+证明：我们只要证明 的任一个素约数q满足q≡1(mod4pp+p2p+ 首先注意p2故q=设r是p模q的阶

= − +⋯− +因p2p1modq)，②故p4p≡1(modq)，所以r∣4p于是r=1，2，4，p，2p或若r=1，2，p，2p，将导出p2p≡1modq)，结合②得到q=2若r=4，则因q是素数，我们推出q∣(p21或q∣(p21)．前者已证明为不可能．若后者成立，即p2≡−1 而右边≡(−1)p−1−(−1)p−2+⋯−(−1)+1≡(modq)．因此pq，这不可能故r=因此只能r=最后，因(pq)=故由费定理得pq−1≡1(modq)，于是r∣(q−1)，即即4p∣(q1因此q≡1例题例题1解：只要证明Fk的任一个素因子p满足p≡1(mod2k+1)．显然设2模p的阶为r，由p∣Fk得22≡−1(k故 ≡1(modp)，从而r∣2k+1所以r是2∣·设r=2l，其中0⩽l⩽k+若l⩽k，则由22≡1(modp)可推出22≡1modp)，结合①得p=2，这不可能，故必须l∗=k+1．又2p−1≡1(modp)从而有r∣(p−1)，故2k+1∣(p1即p≡1(mod2k+1lk例题例题1答 见解解 引理：设p是一个给定的奇素数，整数u>1且p∤∥设d是u模p的阶，并设pv∥(ud1)．则对任意与p互素的正整数m及任意整数t⩾有pt+v∥(udmpt−1)．∥引理的证明：对t归纳，当t=0时，由v的定义知ud=1+pvk(其中p∤k)， 由于p∤km及v故上式右端可表示为1+pvk1的形式，其中k1是一个与p互素的整数，从而引理在t=0t立．假设引理对t已成立，即设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是奇素数，故

C2∣当u=1时结论显然立．对u1，将方程化n!=ur(us−其中r、s为正取定一个奇素数p∤u，可设np(否则结论已成立)，并设pα∥n，则α1．由①及p∤u知pα∥(us−1)，特别地有p∣(us−1)．设d是u模p的阶，则有d∣s设sdmpt，其