分类： 数论

当我们遇到关于x的形如ax\equiv 1 (\mod p)的同余方程时(gcd(a,p)=1)，我们可以将其转化为求解方程ax+py=1的整数解。这个方程我们可以使用扩展欧几里得算法求解。但是当我们…

裴祖定理是求解未知数为p,q的pa+qb=gcd(a,b)的方程必然有整数解，那么求解这个方程就需要使用扩展欧几里得了。