[python算法] 测试尼克彻斯定理
时间: 2023-12-19 19:59:12 浏览: 63
尼克彻斯定理,也称为“欧拉定理”,指的是当正整数n和m互质时,有:
$$
n^{\varphi(m)} \equiv 1 \pmod{m}
$$
其中,$\varphi(m)$表示欧拉函数,表示小于等于m的正整数中与m互质的数的个数。
下面是一个Python代码实现,用于测试尼克彻斯定理是否成立:
```python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def phi(n):
res = n
for i in range(2, int(n**0.5)+1):
if n % i == 0:
res = res // i * (i-1)
while n % i == 0:
n //= i
if n > 1:
res = res // n * (n-1)
return res
def test_nichols_theorem(n, m):
if gcd(n, m) != 1:
return False
return pow(n, phi(m), m) == 1
```
其中,`gcd`函数用于求两个数的最大公约数,`phi`函数用于求欧拉函数,`test_nichols_theorem`函数用于测试尼克彻斯定理是否成立。
我们可以通过以下代码来测试:
```python
n = 3
m = 7
print(test_nichols_theorem(n, m)) # True
n = 2
m = 8
print(test_nichols_theorem(n, m)) # False
```
可以看到,当n和m互质时,尼克彻斯定理成立,否则不成立。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)