原根

博主： admin
发布时间：2021 年 03 月 03 日
333次浏览
2 条评论
2396字数
分类：定理

## 循环小数

列竖式计算时什么时候会出现无限循环的情况？当前然是后面的余数在前面出现过时。比如计算 $\frac 1 7$ 时：起初余数为 $1$，在计算到 $0.142857$ 时余数又为 $1$ ，又回到了一开始的状态，开始循环。

## 可旋转数

观察$\frac 1 7 =0.142857142857...$的列竖式计算过程：余数分别是$1,3,2,6,4,5,1,3,2,6,4,5...$覆盖了比7小的1，2，3，4，5，6。因此1/7的分子 $1$ 换成 $1~6$ 中的任何数，所得的一定也是无限循环小数，并且循环节的长度和 $\frac 1 7$ 的一样。因此我们称 $142857$ 为可旋转数，即：
$$
\frac 1 7 =0.\dot1\dot4\dot2\dot8\dot5\dot7
$$

$$
\frac 2 7 = 0.\dot2\dot8\dot5\dot7\dot1\dot4
$$

$$
\frac 3 7 = 0.\dot4\dot2\dot8\dot5\dot7\dot1
$$

$$
\frac 4 7 = 0.\dot5\dot7\dot1\dot4\dot2\dot8
$$

$$
\frac 5 7 = 0.\dot7\dot1\dot4\dot2\dot8\dot5
$$

$$
\frac 6 7 = 0.\dot8\dot5\dot7\dot1\dot4\dot2
$$

$\frac 1 7=0.\dot1\dot4\dot2\dot8\dot5\dot7$ 等价于 $10^6\equiv 1\pmod7$ 。

## 欧拉 $\varphi$ 函数定理

### $\varphi$ 函数

$\varphi(n)=|\{i|i\in Z^*,1\leq i\leq n,gcd(i,n)=1 \}|$

显然，对于任意质数 $p$ ，有$\varphi(p)=p-1$

### 欧拉 $\varphi$ 函数定理

若 $a$ 与 $m$ 互质，那么：
$$
a^{\varphi(m)}\equiv 1 \pmod m
$$
证明略。

显然，对于任意质数 $p$ ，且 $a$ 与 $p$ 互质，有$a^{p-1}\equiv 1\pmod p$

## 原根

如果我们想得到一个 $n$ 位的可旋转数，根据列竖式的过程，必须要有 $10^n \equiv 1\pmod {n+1} $ ，对照欧拉 $\varphi$ 函数定理可知 $10$ 与 $n+1$ 互质，并且 $n+1$ 为质数。此外，必须要有$\forall x<n,10^x \not\equiv 1\pmod {n+1}$，这也是为了保证循环节长度等于 $n$ 。

实际上我们要求的就是使得 `10是模 n+1 的原根` 的 $n$ 。

### 原根定义

在 $gcd(a,m)=1$ 时，定义 $a$ 对模 $m$ 的指数 $\delta _{m}(a)$ 为使 $a^{d}\equiv 1{\pmod {m}}$ 成立的最小的正整数 $d$ 。由前知 $\delta _{m}(a) \leq \varphi(m)$ ，若$\delta _{m}(a) = \varphi(m)$ ，则称 $a$ 是 模 $m$ 的原根。

## 代码

求 $1000$ 以内原根为 $10$ 的数

### Python

```python
#快速幂(模m)
def fastpower(b, h, m):
    ans = 1
    while h > 0:
        if h&1 == 1:
            ans = (ans * b) % m;
        h >>= 1
        b = b * b % m
    return ans
    
    
#判断是否是质数
def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

#判断base是不是模m的原根
def isRoot(base, m):
    #m为质数
    if isPrime(m) == False:
        return False
    #base与m互质
    if base % m == 0:
        return False
    #欧拉函数定理
    #判断阶等于m-1时
    if fastpower(base, m-1, m) != 1:
        return False
    for i in range(1,int((m-1)**0.5)+1):
        #判断阶小于m-1时
        if (m-1) % i == 0:
            if i < m - 1 and fastpower(base, i, m) == 1:
                return False
            if (m - 1) // i < m - 1 and fastpower(base, (m-1)//i, m) == 1:
                return False
    return True

res=[]
for m in range(1,1000):
    if isRoot(10, m):
        res.append(m)
```

结果

```
[7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167,
 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 
 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 
 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 
 823, 857, 863, 887, 937, 941, 953, 971, 977, 983] 共60个
```

最后修改：2021 年 03 月 04 日 11 : 32 AM

如果觉得我的文章对你有用，请随意赞赏

2 条评论

caskwvaglf
November 28th, 2024 at 10:33 pm

《酷儿们》欧美剧高清在线免费观看：https://www.jgz518.com/xingkong/111714.html

回复
wqeampidxq
November 21st, 2024 at 11:30 pm

《生死牌》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/12417.html

回复