数论之指标介绍及其应用（基于阶与原根的应用）

文章目录

• 一、定义
• • 内容
• 二、性质
• • 1. a ≡ b ( m o d a≡b (mod a≡b(mod n ) ⇐ ⇒ I ( a ) ≡ I ( b ) ( m o d n)\Leftarrow \Rightarrow I(a)≡I(b)(mod n)⇐⇒I(a)≡I(b)(mod φ ( n ) ) φ(n)) φ(n))
  • 2. I ( a b ) ≡ I ( a ) + I ( b ) ( m o d I(ab)≡I(a)+I(b) (mod I(ab)≡I(a)+I(b)(mod φ ( n ) ) φ(n)) φ(n))
  • • 证明
    • 推论一： I ( a k ) ≡ k I ( a ) ( m o d I(a^k)≡kI(a) (mod I(ak)≡kI(a)(mod φ ( n ) ) φ(n)) φ(n))
    • 推论二： I ( ∏ i = 1 k a i ) ≡ ∑ i = 1 k I ( a i ) ( m o d I(\prod_{i=1}^ka^i )≡\sum_{i=1}^kI(a^i) (mod I(∏i=1k​ai)≡∑i=1k​I(ai)(mod φ ( n ) ) φ(n)) φ(n))
  • 3.当 g c d ( a , n ) = 1 gcd(a,n)=1 gcd(a,n)=1，且有两个原根 g 1 , g 2 g_1,g_2 g1​,g2​时, i n d g 1 a ≡ i n d g 1 g 2 ∗ i n d g 2 a ( m o d ind_{g_1}a≡ind_{g_1}{g_2}*ind_{g_2}a(mod indg1​​a≡indg1​​g2​∗indg2​​a(mod φ ( n ) ) φ(n)) φ(n))
  • • 证明
• 三、简单应用·解方程 3 x 5 ≡ 1 （ m o d 3x^5≡1（mod 3x5≡1（mod 23 ) 23) 23)

一、定义

内容

设正整数 n ≥ 2 n\geq2 n≥2并且有原根 g g g，那么 g 0 , g 1 … … g φ ( n ) − 1 g^0,g^1……g^{φ(n) -1} g0,g1……gφ(n)−1可以构成模 n n n的既约剩余系，对于任意满足 g c d ( a , n ) = 1 gcd(a,n)=1 gcd(a,n)=1的 a a a，均有 g x ≡ a ( m o d g^x≡a (mod gx≡a(mod n ) n) n) ( 0 ≤ x < φ ( n ) ) (0\leq x<φ(n)) (0≤x<φ(n))。

将解 x x x记作： i n d g a ind_ga indg​a m o d mod mod φ ( n ) φ(n) φ(n)

称为：a的以g为底模n的指标

在不会混淆的情况下可以将其简记为: I ( a ) I(a) I(a)

属于集合 ∈ { 0 , 1 , 2 … … φ ( n ) − 1 } \in\{0,1,2……φ(n) -1\} ∈{0,1,2……φ(n)−1}

二、性质

1. a ≡ b ( m o d a≡b (mod a≡b(mod n ) ⇐ ⇒ I ( a ) ≡ I ( b ) ( m o d n)\Leftarrow \Rightarrow I(a)≡I(b)(mod n)⇐⇒I(a)≡I(b)(mod φ ( n ) ) φ(n)) φ(n))

2. I ( a b ) ≡ I ( a ) + I ( b ) ( m o d I(ab)≡I(a)+I(b) (mod I(ab)≡I(a)+I(b)(mod φ ( n ) ) φ(n)) φ(n))

证明

当 g c d ( a , n ) = g c d ( b , n ) = 1 gcd(a,n)=gcd(b,n)=1 gcd(a,n)=gcd(b,n)=1时，同时存在 g c d ( a b , n ) = 1 gcd(ab,n)=1 gcd(ab,n)=1，根据定义，有:

g I ( a b ) ≡ a b ( m o d g^{I(ab)}≡ab(mod gI(ab)≡ab(mod n ) n) n)

由于 a b ≡ g I ( a ) g I ( b ) ( m o d ab≡g^{I(a)}g^{I(b)}(mod ab≡gI(a)gI(b)(mod n ) n) n)

最终可以得到： g I ( a b ) ≡ g I ( a ) g I ( b ) ( m o d g^{I(ab)}≡g^{I(a)}g^{I(b)}(mod gI(ab)≡gI(a)gI(b)(mod n ) n) n)

在结合之前介绍阶时用到的

定理三： g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a x ≡ a y ( m o d a^x ≡a^y(mod ax≡ay(mod n ) n) n)的充要条件为 x ≡ y ( m o d x ≡y(mod x≡y(mod o r d n a ) ord_na) ordn​a)

由于 g g g为 n n n的原根，那么 o r d n a ord_na ordn​a就等于 φ ( n ) φ(n) φ(n)

最后得到了： I ( a ) ≡ I ( a ) + I ( b ) ( m o d I(a)≡I(a)+I(b) (mod I(a)≡I(a)+I(b)(mod φ ( n ) ) φ(n)) φ(n))

推论一： I ( a k ) ≡ k I ( a ) ( m o d I(a^k)≡kI(a) (mod I(ak)≡kI(a)(mod φ ( n ) ) φ(n)) φ(n))

推论二： I ( ∏ i = 1 k a i ) ≡ ∑ i = 1 k I ( a i ) ( m o d I(\prod_{i=1}^ka^i )≡\sum_{i=1}^kI(a^i) (mod I(∏i=1k​ai)≡∑i=1k​I(ai)(mod φ ( n ) ) φ(n)) φ(n))

3.当 g c d ( a , n ) = 1 gcd(a,n)=1 gcd(a,n)=1，且有两个原根 g 1 , g 2 g_1,g_2 g1​,g2​时, i n d g 1 a ≡ i n d g 1 g 2 ∗ i n d g 2 a ( m o d ind_{g_1}a≡ind_{g_1}{g_2}*ind_{g_2}a(mod indg1​​a≡indg1​​g2​∗indg2​​a(mod φ ( n ) ) φ(n)) φ(n))

证明

由两个原根，首先可以得到两个式子：

( 1 ) g 1 i n d g 1 a ≡ a ( m o d (1)g_1^{ind_{g_1}a}≡a (mod (1)g1indg1​​a​≡a(mod n ) n) n)

( 2 ) g 2 i n d g 2 a ≡ a ( m o d (2)g_2^{ind_{g_2}a}≡a (mod (2)g2indg2​​a​≡a(mod n ) n) n)

当然， g 2 g_2 g2​同样满足 g c d ( g 2 , a ) = 1 gcd(g_2,a)=1 gcd(g2​,a)=1，所以同时存在式子：

( 3 ) g 1 i n d g 1 g 2 ≡ g 2 ( m o d (3)g_1^{ind_{g_1}g_2}≡g_2 (mod (3)g1indg1​​g2​​≡g2​(mod n ) n) n)

将式子（2）、（3）结合，

得： ( g 1 i n d g 1 g 2 ) i n d g 2 a ≡ a ( m o d {(g_1^{ind_{g_1}g_2})}^{ind_{g_2}a}≡a (mod (g1indg1​​g2​​)indg2​​a≡a(mod n ) n) n)

再与（1）结合，

得： g 1 i n d g 1 g 2 i n d g 2 a ≡ g 1 i n d g 1 a ( m o d g_1^{ind_{g_1}g_2ind_{g_2}a}≡g_1^{ind_{g_1}a} (mod g1indg1​​g2​indg2​​a​≡g1indg1​​a​(mod n ) n) n)

再次使用前介绍阶时用到的

定理三： g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a x ≡ a y ( m o d a^x ≡a^y(mod ax≡ay(mod n ) n) n)的充要条件为 x ≡ y ( m o d x ≡y(mod x≡y(mod o r d n a ) ord_na) ordn​a)

由于 g g g为 n n n的原根，那么 o r d n a ord_na ordn​a就等于 φ ( n ) φ(n) φ(n)

此时就得到了： i n d g 1 a ≡ i n d g 1 g 2 ∗ i n d g 2 a ( m o d ind_{g_1}a≡ind_{g_1}{g_2}*ind_{g_2}a(mod indg1​​a≡indg1​​g2​∗indg2​​a(mod φ ( n ) ) φ(n)) φ(n))

三、简单应用·解方程 3 x 5 ≡ 1 （ m o d 3x^5≡1（mod 3x5≡1（mod 23 ) 23) 23)

可以用数论之阶与原根中的方法求出23的最小原根5

再求出对应的指标表：指数由0到 φ ( n ) − 1 φ(n)-1 φ(n)−1

指数	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
模23的结果	1	5	2	10	4	20	8	17	16	11	9	22	18	21	13	19	3	15	6	7	12	14

由于 g c d ( 3 x 5 , 23 ) = g c d ( 1 , 23 ) = 1 gcd(3x^5,23)=gcd(1,23)=1 gcd(3x5,23)=gcd(1,23)=1,所以 3 x 5 、 1 3x^5、1 3x5、1有指标，

记作： i n d 5 ( 3 x 5 ) ind_5{(3x^5)} ind5​(3x5)和 i n d 5 1 ind_5{1} ind5​1

再次使用前介绍阶时用到的

定理三： g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a x ≡ a y ( m o d a^x ≡a^y(mod ax≡ay(mod n ) n) n)的充要条件为 x ≡ y ( m o d x ≡y(mod x≡y(mod o r d n a ) ord_na) ordn​a)

由于 g g g为 n n n的原根，那么 o r d n a ord_na ordn​a就等于 φ ( n ) φ(n) φ(n)

可以得到： i n d 5 ( 3 x 5 ) ≡ i n d 5 1 ( m o d ind_5{(3x^5)} ≡ind_5{1}(mod ind5​(3x5)≡ind5​1(mod 22 ) 22) 22)

使用性质二

可以得到： i n d 5 ( 3 ) + 5 i n d 5 ( x ) ≡ i n d 5 1 ( m o d ind_5{(3)}+5 ind_5{(x)}≡ind_5{1}(mod ind5​(3)+5ind5​(x)≡ind5​1(mod 22 ) 22) 22)

5 i n d 5 ( x ) ≡ − 16 ( m o d 5 ind_5{(x)}≡-16(mod 5ind5​(x)≡−16(mod 22 ) 22) 22)

5 i n d 5 ( x ) ≡ 50 ( m o d 5 ind_5{(x)}≡50(mod 5ind5​(x)≡50(mod 22 ) 22) 22)

再使用消去律，

得到： i n d 5 ( x ) ≡ 10 ( m o d ind_5{(x)}≡10(mod ind5​(x)≡10(mod 22 ) 22) 22)

就是说: x ≡ 5 i n d 5 ( x ) ( m o d x≡5^{ind_5{(x)}}(mod x≡5ind5​(x)(mod 23 ) 23) 23) ≡ 5 10 ( m o d ≡5^{10}(mod ≡510(mod 23 ) ≡ 9 ( m o d 23)≡9(mod 23)≡9(mod 23 ) 23) 23)

查表可知