Python在处理初等数论方面有着广泛的应用，它内置了许多用于数学运算的功能，并且可以结合第三方库如`sympy`来进行更复杂的计算。以下是几个重要的知识点及对应的代码示例： ### 1. 素数判断 素数是指大于1并且只能被自身和1整除的自然数。 ```python def is_prime(n): if n <= 1: return False for i in range(2, int(n**0.5)+1): # 只需要检查到根号n即可 if n % i == 0: return False return True print(is_prime(7)) # 输出True ``` ### 2. 最大公约数(GCD) 最大公约数指两个或多个非零整数共有的最大的正因数。 ```python from math import gcd a = 48 b = 60 result = gcd(a,b) print(f"{a} 和 {b} 的最大公因子是 {result}") # 结果为12 ``` ### 3. 欧拉函数φ(n) 欧拉定理指出对于任意互质的a,n有 a^φ(n)%n=1 。其中φ(n)表示小于等于n并与n互质的正整数数目。 ```python import sympy # 使用SymPy求解欧拉phi值 num = 9 euler_phi_value=sympy.totient(num) print(f"小于{num}并与其互质的数量为:{euler_phi_value}") ``` ### 4. 扩展欧几里得算法（exgcd） 该算法不仅可以找到给定两数的最大公约数，还可以得到线性组合表达式ax + by=gcd(a,b). ```python def ex_gcd(a,b,x,y): if b==0 : x[0]=1; y[0]=0; return a else : d = ex_gcd(b,a%b,y,x) y[0] -= (a // b)*x[0] return d if __name__=="__main__": a=int(input("请输入第一个整数:")) b=int(input("请输入第二个整数:")) X=[0]; Y=[0]; result=ex_gcd(a,b,X,Y); print('(',X[0],',',Y[0],')') ``` 以上只是对一些基础内容进行了简单介绍，在实际应用当中还有很多其他有趣的话题值得探索，比如二次剩余、连分数展开等等。