您的位置: 首页 > 文章 > 数论小结 数论小结 分类: 文章 • 2024-06-25 14:10:16 1.欧几里得算法(辗转相除法) gcd(a,b) = gcd(b,a mod b) 2.扩展欧几里得算法 用来在已知a,b求解一组x,y使得a*x+b*y=gcd(a,b) (解一定存在) 扩展欧几里得常用在求解模线性方程即方程组中 3.逆元 (1)费马小定理 m为素数是费马小定理的前置条件。 (2)扩展gcd求逆元 (3)欧拉定理 3.斯特灵公式 ps:整数n的位数=[log10(n)]+1