3.1

解答题

1

1
2
3
4
5
6
#!/usr/bin/env python2
from sage.all import *

R = IntegerModRing(37) 			# 建立一个模 37 的整数环
p = R(34) 						# 取整数环上的数 34
print(p.multiplicative_order()) # 求次数（http://mathonline.wikidot.com/the-order-of-a-permutation）

1
9

即，我们有 $$34^{9} \equiv 1 \pmod{37}$$

手算可以先计算 37 的欧拉函数：$$\phi(37) = 36$$

根据欧拉定理，与次数的性质，34 对模 37 的次数一定是 36 的因子，穷举可得 9。

2

1
2
3
4
5
6
#!/usr/bin/env python2
from sage.all import *

R = IntegerModRing(37)
p = R(2**12)
print(p.multiplicative_order()) # 3

即，我们有 $$\displaystyle 2^{12*3} \equiv 1 \pmod{37}$$

笔算：

对 2，根据欧拉定理，我们知道：$$2^{36} = 2^{12*3} \equiv 1 \pmod{37}$$

再对 2，考虑次数的性质：$$24 \not| 36$$，所以必有 $$2^{24} = 2^{12*2} \not\equiv 1 \pmod{37}$$

因此 3 是 $$2^{12}$$ 模 37 的次数。

3

1
2
3
4
5
6
7
8
9
#!/usr/bin/env python2
from sage.all import *

R = IntegerModRing(61)
for i in range(61)[1:]:
     p = R(i)
     if p.multiplicative_order() == 4:
             print(p)
# 11 50

笔算：

2 是模 61 的原根 $$\Leftrightarrow 2^{60} \equiv 1 \pmod{61} 且 2^{i} \not\equiv 1 \pmod{61}, i = 1,2,\dots,59$$

显然我们知道 $$2^{60} = (2^{15})^{4} \equiv (11)^4 \equiv (\pm 11)^4 \equiv 1 \pmod{61} $$

然后因为对于任意 $$i < 4, 15i < 60$$，若 4 不是 11 的次数，这与 2 是一个原根矛盾。

因此我们得到了两个次数为 4 的整数 11、50。

然后我们证明它的唯二性，若 $$\exist p \not\equiv \pm 11 \pmod{61}, ord(p) = 4$$

必有 $$p^4 \equiv 11^4 \pmod{61} \Leftrightarrow (p^2 +11^2)(p^2 - 11^2) \equiv 0 \pmod{61}$$

因为我们的假设，必有 $$p^2 + 11^2 \equiv 0 \pmod{61} \Leftrightarrow p^2 \equiv 1 \pmod{61}$$

存在一个 4 的因子 2 使得次数定义式成立，这与 4 是 p 的次数矛盾。

因此 11 与 50 是唯二的次数为 4 的整数。

4

根据下面的定理：

设 m 是大于 1 的整数，则 m 的原根存在的充要条件是 m 为 $$2, 4, p^l, 2p^l$$ 之一，其中 $$l \ge 1,$$ p 是奇素数。

我们通过一下的程序分解这三个数字：

1
2
3
#!/usr/bin/env sage
print(factor(47), factor(55), factor(59))
# (47, 5 * 11, 59)

根据定理可知，仅 55 不满足原根存在的充要条件，47 与 59 都是奇素数。

对于 47：$$\phi(47) = 46 = 2*23, 5^2 \equiv 4 \not\equiv 1 \pmod{47}, 5^{23} \equiv 46 \not\equiv 1 \pmod{47}$$，因此我们得到了 47 的一个原根 5，因此根据以下的程序可以计算出所有的原根：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python2
from sage.all import *

class PrimitiveRoot:
    def __init__(self, integer):
        self.R = IntegerModRing(integer)
        self.phi = euler_phi(self.R.order())
        self.root = self.R(primitive_root(self.R.order()))

    def get_roots(self):
        self.roots = []
        for i in range(euler_phi(self.phi)):
            if gcd(i, self.phi) == 1:
                self.roots.append(self.root ** i)
        return sorted(self.roots)

def solve():
    PR = PrimitiveRoot(47)
    print(PR.get_roots())
    # [5, 10, 11, 13, 15, 23, 31, 38, 40, 41, 43]

同样我们可以得到：59 的所有原根：

[2, 8, 10, 11, 14, 23, 32, 33, 40, 42, 44, 47, 50, 56]

5

1
2
#!/usr/bin/env sage
print(primitive_root(113)) # 3

6

指数表：

1
2
3
4
5
#!/usr/bin/env sage
N = 19
R = IntegerModRing(N)
R(primitive_root(N)).powers(euler_phi(N))
# [1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10]

对于 $$8 x^4 \equiv 3 \pmod{19}$$

1
2
3
#!/usr/bin/env sage
solve_mod([8 * x**4 == 3], 19)
# [(5,), (14,)]

另外也可以，计算 8 的模 19 逆元 12，有等式 $$x^4 \equiv 17 \pmod{19}$$，取离散对数 $$ind_2 x^4 \equiv ind_2 17 \pmod{18} \Rightarrow 2ind_2 x \equiv 5 \pmod{9}$$，显然我们得到 $$\pm 5$$

对于 $$5 x^3 \equiv 2 \pmod{19}$$

1
2
3
#!/usr/bin/env sage
solve_mod([5 * x **3 == 2], 19)
# [(2,), (3,), (14,)]

另外，计算 5 关于模 19 的逆元 4，有等式 $$x^3 \equiv 8 \pmod{19} \Rightarrow 3 ind_2 x \equiv ind_2 8 \pmod{18} \Rightarrow ind_2 x \equiv 1 \pmod{6}$$，得到三个解 2,3,14

对于 $$x^7 \equiv 1 \pmod{19}$$

1
2
3
#!/usr/bin/env sage
solve_mod([x ** 7 == 1], 19)
# [(1,)]

$$x^7 \equiv 1 \pmod{19} \Rightarrow 7 ind_2 x \equiv \phi(19) \pmod{\phi(19)} \Rightarrow x = 1 \pmod{19}$$

7

1
2
3
#!/usr/bin/env sage
solve_mod([x**22 == 5], 41)
# [(6,), (35,)]

证明题

1

令 $$x = ord_m a, y = ord_m b$$，显然我们有 $$a^x \equiv b^y \equiv 1 \pmod{m}$$

不是一般性我们设 $$x \ge y$$，那么 $$a^x b^y \equiv a^{x-y} (ab)^y \equiv 1 \pmod{m}$$

根据 $$ab \equiv 1 \pmod{m}$$，我们可以得到 $$a^{x-y} \equiv 1 \pmod{m}$$

很显然若 x-y 是一个比 x 更小且不为 1 的正整数，这与 x 为 a 的次数条件相悖。

只有可能 x=y，亦即 $$ord_m a = ord_m b$$

2

对于 $$a^s$$，我们有 $$(a^{s})^t = a^{st} \equiv 1 \pmod{m}$$

然后我们证明 t 的最小性，我们知道 $$\forall k < t$$ 若满足 $$(a^s)^k \equiv 1\pmod{m}$$，必有存在这样的 $$ks < st$$，$$a^{ks} \equiv 1 \pmod{m}$$，这与 st 是次数相悖。所以 t 是最小的。

即 t 就是 $$a^s$$ 的次数。

3

$$g^k$$ 是 m 的原根$$\Leftrightarrow (g^k)^{\phi(m)} \equiv 1 \pmod{m}$$ 且 $$(g^k)^{t} \not\equiv 1 \pmod{m}, t < \phi(m)$$

对于 $$\forall t < \phi(m)$$，若 $$g^t \equiv 1 \pmod{m}$$，那么必然有 $$g^{kt} \equiv 1 \pmod{m}$$，这与之前的论证是矛盾的，因此必然有 g 也是一个原根。

4

令 $$x = ord_m a, y = ord_m b$$，显然我们有 $$a^x \equiv b^y \equiv 1 \pmod{m}$$

那么 $$a^{xy} \equiv b^{xy} \equiv 1 \pmod{m} \Rightarrow (ab)^{xy} \equiv 1 \pmod{m}$$

下面证明 xy 的最小性：

设 $$\exist m < xy, (ab)^m \equiv 1 \pmod{m}$$，那么必有 $$m | xy$$。

因为 $$gcd(x, y) = 1$$，那么 m 必然是 x、y 的因子或其本身；

因为 x、y 分别是 a、b 的次数，所以一定不存在一个因子满足幂余一的性质；

又因为 $$gcd(x, y) = 1$$，x、y 的因子必然彼此互素；

因此不存在这样的 m，所以 xy 的最小性得证。

5

根据下面的定理：

设 m 是大于 1 的整数，则 m 的原根存在的充要条件是 m 为 $$2, 4, p^l, 2p^l$$ 之一，其中 $$l \ge 1,$$ p 是奇素数。

对 12 进行素因子分解 $$12 = 2^2 * 3$$，很显然并不存在原根。

6

设 $$k = ord_{F_n}(2)$$，即证明 $$k \le 2^{n+1}$$

因为我们发现 $$2^{2^{n+1}} = 2^{2^{n} * 2} \equiv 1^2 \equiv 1 \pmod{2^{2^{n}} + 1}$$

因此 k 一定是 $$2^{n+1}$$ 或者其因子，即一定有 $$k \le 2^{n+1}$$

7

（1）

首先我们有 $$2^{2^{n+1}} = 2^{2^{n} * 2} \equiv 1^2 \equiv 1 \pmod{2^{2^{n}} + 1}$$

因为 $$p | 2^{2^{n}} + 1$$，所以我们必然有 $$2^{2^{n+1}} \equiv 1 \pmod{p}$$

然后我们证明其最小性，因为我们有上面的等式 $$ord_p (2)$$ 一定是 $$2^{n+1}$$ 或其因子，而后者的因子仅有 $$2^t, t \le n+1 $$

$$(2^{2^t})^{2^{n-t}} \equiv 2^{2^{n}} \equiv -1 \pmod{2^{2^n} + 1} \Rightarrow (2^{2^t})^{2^{n-t}} \equiv -1 \pmod{p} $$

而如果 $$2^t$$ 是一个原根的话，那么必然会有 $$2^{2^t} \equiv 1 \pmod{p} \Rightarrow (2^{2^t})^{2^{n-t}} \equiv 1 \pmod{p} $$

以上两点是矛盾的，因此 $$2^t$$ 不可能是一个原根。

（2）

p 形如 $$2^{n+1} k + 1 \Leftrightarrow p \equiv 1 \pmod{2^{n+1}}$$

因为 p 是奇素数，我们又有 $$2^{p-1} \equiv 1 \pmod{p}$$

而又根据第一问我们有 $$ord_p (2) = 2^{n+1}$$，所以我们必然有 $$2^{n+1} | (p-1)$$

即必然有 $$p-1 \equiv 0 \pmod{2^{n+1}} \Rightarrow p \equiv 1\pmod{2^{n+1}}$$

8

p 以 g 为原根 $$\Rightarrow g^{\phi(p)} \equiv 1 \pmod{p}$$ 且 $$g^{t} \not\equiv 1 \pmod{p}, t < \phi(p)$$

而因为 p 是奇素数，所以很显然我们有 $$\phi(p) = p -1$$

所以我们知道 $$g^{\frac{p-1}{2}} \equiv 1^{\frac{1}{2}} \pmod{p}$$

而对于 p-1，恰好满足 $$(p-1)^2 = p^2 -2p + 1 \equiv 1 \pmod{p}$$

所以 $$\displaystyle g^{\frac{p-1}{2}} \equiv p - 1 \pmod{p} \Rightarrow ind_g (p-1) = \frac{p-1}{2}$$