1.阶及阶的性质(ord)
原创
已于 2022-04-17 12:06:15 修改
·
6.6k 阅读
·
4
·
12
·
CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
文章标签：
#学习
于 2022-04-16 18:07:54 首次发布
数学
同时被 2 个专栏收录
8 篇文章
订阅专栏
数论
2 篇文章
订阅专栏
本文介绍了数论中的阶概念，包括阶的定义、性质及其重要推论，并通过一系列数学证明展示了阶在模运算中的作用。文章讨论了阶与欧拉函数的关系，以及在求解特定模运算下元素阶的问题。同时，通过具体的例子和证明，阐述了阶在素数和模幂运算中的应用，如证明两个大数的互质性和求解特定模运算下的阶值。
摘要生成于
C知道
，由 DeepSeek-R1 满血版支持，
前往体验 >
阶是数论的一大神器。
阶的定义：若 rrr 是最小的满足ar≡1(modd)a^r \equiv1\pmod dar≡1(modd) 的正整数。则称ordd(a)=rord_d(a)=rordd(a)=r。例如：ord3(5)=4,ord3(11)=5ord_3(5)=4,ord_3(11)=5ord3(5)=4,ord3(11)=5
阶的一些重要性质(以下默认阶存在，即 (a,d)=1(a,d)=1(a,d)=1，默认数是正整数)：
性质1：若 ordd(a)=r,ord_d(a)=r,ordd(a)=r, 且 aq≡1(modd)a^q\equiv1\pmod daq≡1(modd)。则：r∣qr|qr∣q。
证：若 r∤qr\nmid qr∤q，设 q=kr+l(0 ∵l 推论1：r∣φ(d)r|\varphi(d)r∣φ(d)。 推论2：若 u∣d,ordu(a)=v,u|d,ord_u(a)=v,u∣d,ordu(a)=v,则：v∣rv|rv∣r。 证：∵ar≡1(modd),r∣d\because a^r\equiv1\pmod d,r|d∵ar≡1(modd),r∣d。∴ar≡1(modu)∴\quad\therefore a^r\equiv1\pmod u\quad\therefore∴ar≡1(modu)∴ 由性质1得：v∣rv|rv∣r。 性质2：若 (a,m)=1，(a,n)=1，(n,m)=1(a,m)=1，(a,n)=1，(n,m)=1(a,m)=1，(a,n)=1，(n,m)=1，设 x=ordn(a),y=ordm(a),z=ordnm(a)x=ord_n(a),y=ord_m(a),z=ord_{nm}(a)x=ordn(a),y=ordm(a),z=ordnm(a)，则z=lcm(x,y)z=lcm(x,y)z=lcm(x,y)。 证：∵az≡1(modnm)∴az≡1(modn),az≡1(modm)\because a^z\equiv1\pmod {nm}\quad\therefore a^z\equiv1\pmod n,a^z\equiv1\pmod m∵az≡1(modnm)∴az≡1(modn),az≡1(modm)。 由性质1得：x∣z,y∣zx|z,y|zx∣z,y∣z。∴lcm(x,y)∣z\quad\therefore lcm(x,y)|z∴lcm(x,y)∣z。 ∵x∣lcm(x,y),y∣lcm(x,y)∴alcm(x,y)≡1(modn),alcm(x,y)≡1(modm)\because x|lcm(x,y),y|lcm(x,y)\quad\therefore a^{lcm(x,y)}\equiv1\pmod n,a^{lcm(x,y)}\equiv1\pmod m∵x∣lcm(x,y),y∣lcm(x,y)∴alcm(x,y)≡1(modn),alcm(x,y)≡1(modm) ∵(n,m)=1∴\because (n,m)=1\quad\therefore∵(n,m)=1∴ 由同余性质得:alcm(x,y)≡1(modnm)a^{lcm(x,y)}\equiv1\pmod{nm}alcm(x,y)≡1(modnm)。由性质1得：z∣lcm(x,y)z|lcm(x,y)z∣lcm(x,y)。 ∴z=lcm(x,y)\therefore z=lcm(x,y)∴z=lcm(x,y)。 可见性质1很重要。 题目： 1.设Mn=2n−1M_n=2^n-1Mn=2n−1。证明：若p∤qp\nmid qp∤q ( ppp 是素数),则 (Mp,Mq)=1(M_p,M_q)=1(Mp,Mq)=1。 证：若 (Mp,Mq)=d>1(M_p,M_q)=d>1(Mp,Mq)=d>1。则d∣Mp,d∣Mqd|M_p,d|M_qd∣Mp,d∣Mq。设ordd(2)=xord_d(2)=xordd(2)=x。由性质1得：x∣p,x∣qx|p,x|qx∣p,x∣q。 ∵p\because p∵p 是素数。 ∴x=1或p\quad\therefore x=1或p∴x=1或p。 若x=1x=1x=1，则2≡1(modd)⇒d=12\equiv1\pmod d\Rightarrow d=12≡1(modd)⇒d=1。矛盾。 故x=px=px=p。∴p∣q\therefore p|q∴p∣q。矛盾。 ∴(Mp,Mq)=1\therefore (M_p,M_q)=1∴(Mp,Mq)=1 2.求 r=ord22000(193)r=ord_{2^{2000}}(193)r=ord22000(193)。 由性质1推论得：r∣φ(22000)=21999r|\varphi(2^{2000})=2^{1999}r∣φ(22000)=21999。设 r=2k(0 则193r−1≡1932k−1≡(193−1)∗∏i=1k−1(1932i+1)≡0(mod22000)\large193^r-1\equiv193^{2^k}-1\equiv(193-1)*\prod\limits_{i=1}^{k-1}(193^{2^i}+1)\equiv0\pmod {2^{2000}}193r−1≡1932k−1≡(193−1)∗i=1∏k−1(1932i+1)≡0(mod22000) ∵26∥192,2∥1932i+1\because 2^6\parallel192,2\parallel193^{2^i}+1∵26∥192,2∥1932i+1 ∴v2(193r−1)=6+2n\therefore v_2(193^r-1)=6+2n∴v2(193r−1)=6+2n ∵6+k≥2000∴kmin=1994∴r=21994\because 6+k\ge2000\quad\therefore k_{min}=1994\quad\therefore r=2^{1994}∵6+k≥2000∴kmin=1994∴r=21994 3.求 ord10n(3)(n≥4)ord_{10^n}(3)(n\ge4)ord10n(3)(n≥4)。 由性质2得：ord10n(3)=lcm(ord2n(3),ord5n(3))(n≥4)ord_{10^n}(3)=lcm(ord_{2^n}(3),ord_{5^n}(3))(n\ge4)ord10n(3)=lcm(ord2n(3),ord5n(3))(n≥4)。 设 r=ord2n(3)∣2n−1r=ord_{2^n}(3)|2^{n-1}r=ord2n(3)∣2n−1。若 rrr 是偶数，则2n∣3r−1⇔v2(3r−1)=n2^n|3^r-1\Leftrightarrow v_2(3^r-1)=n2n∣3r−1⇔v2(3r−1)=n。 由LTELTELTE定理得：v2(3r−1)=v2(r)+v2(32−12)−1v_2(3^r-1)=v_2(r)+v_2(3^2-1^2)-1v2(3r−1)=v2(r)+v2(32−12)−1。故r=2n−2r=2^{n-2}r=2n−2，当 n≥4n\ge4n≥4 时 rrr 是偶数，满足。 若 rrr 是奇数，则 r=1⇒n=1r=1\Rightarrow n=1r=1⇒n=1，矛盾。 设 u=ord5n(3)∣4∗5n−1u=ord_{5^n}(3)|4*5^{n-1}u=ord5n(3)∣4∗5n−1。通过归纳容易证明：35x≡31(mod5),32∗5x≡32(mod5)3^{5^x}\equiv3^1\pmod5,3^{2*5^x}\equiv3^2\pmod535x≡31(mod5),32∗5x≡32(mod5)。 故u=4∗5k∣4∗5n−1u=4*5^k|4*5^{n-1}u=4∗5k∣4∗5n−1。由LTELTELTE定理得：v5(34∗5k−1)=v5(5k)+v5(34−1)=k+1v_5(3^{4*5^k}-1)=v_5(5^k)+v_5(3^4-1)=k+1v5(34∗5k−1)=v5(5k)+v5(34−1)=k+1。故u=4∗5n−1u=4*5^{n-1}u=4∗5n−1。 ∴ord10n=lcm(2n−2,4∗5n−1)=2n−2∗5n−1\therefore ord_{10^n}=lcm(2^{n-2},4*5^{n-1})=2^{n-2}*5^{n-1}∴ord10n=lcm(2n−2,4∗5n−1)=2n−2∗5n−1 上述思路值得借鉴。 4.若奇素数 ppp,素数 q,rq,rq,r满足：p∣qr+1p|q^r+1p∣qr+1。证明：2r∣p−12r|p-12r∣p−1 或 p∣q2−1p|q^2-1p∣q2−1。 证：设 d=ordq(p)d=ord_q(p)d=ordq(p)。又q2r≡1(modp)q^{2r}\equiv1\pmod pq2r≡1(modp)，由性质1得： d∣2rd|2rd∣2r。又qd≡1(modp)q^d\equiv1\pmod pqd≡1(modp)。由性质1得：d∣p−1d|p-1d∣p−1。 显然，d=1,2,r,2rd=1,2,r,2rd=1,2,r,2r。 当d=1,2d=1,2d=1,2时，q≡±1(modp)⇒p∣q2−1q\equiv \pm1\pmod p\Rightarrow p|q^2-1q≡±1(modp)⇒p∣q2−1。 当d=rd=rd=r时，qd≡qr≡−1(modp)q^d\equiv q^r\equiv-1\pmod pqd≡qr≡−1(modp)。矛盾。 当d=2rd=2rd=2r时，d=2r∣p−1d=2r|p-1d=2r∣p−1。 证毕。