sagemath初等数论

SageMath是一个覆盖许多数学功能的应用软件，包括代数、组合数学、图论、计算数学、数论、微积分和统计。

安装sagemath（ubuntu）

sudo apt install sagemath

在命令行输入sage启动sagemath

输入tutorial或manual()打开离线文档

素数测试

sage: inverse_mod(3,2005)
1337
sage: is_prime(5)
True
sage: next_prime(2005)
2011
sage: previous_prime(2005)
2003

模幂运算

计算51²⁰⁰⁶ (mod 97)

sage: R = IntegerModRing(97)    ##模数
sage: a = R(51)
sage: a^2006

例：计算3在模2005下的乘法逆元3^-1

sage: inverse_mod(3,2005)
1337

欧几里得算法

求两个整数的最大公约数

sage: gcd(515,2005)
5

扩展欧几里得算法

as+bt=gcd(a,b)，求其中的gcd(a,b)，s，t

sage: g,s,t = xgcd(12,15)
sage: print(g,s,t)
3 -1 1

欧拉函数

φ(n)表示1到n-1中与n互素的整数个数

sage: euler_phi(2005)
1600

中国剩余定理

当模数两两互素时，一元同余方程组有解

其中：

　　r=a₁a₂a₃ ... a_n

　　r_i=r/a_i

sage: crt(2,1,3,5)      ##crt(a,b,m,n)，寻找 x 满足 x ≡ a (mod m) 且 x ≡ b (mod n)
11

计算三个及三个以上方程组
sage: crt([2,3,2],[3,5,7])　　##求解物不知数问题
23