数论基础

辗转相除法正确性证明

设G=gcd(a,b)G=gcd(a,b)

有 a%G=0a\%G=0 , b%G=0b\%G=0

有 (a−⌊a/b⌋∗b)%G=0(a- \lfloor a/b\rfloor*b)\%G =0

G=gcd(a,b)=gcd(b,a%b)G=gcd(a,b)=gcd(b,a\%b)

exgcd:exgcd:

ax+by=cax+by=c

其中 c%gcd(a,b)=0c\%gcd(a,b)=0

设我们递归的求出来以一组解 xn,ynx_n,y_n

bxn+(a−⌊a/b⌋∗b)yn=Gbx_n+(a-\lfloor a/b\rfloor*b)y_n=G

axn−1+byn−1=Gax_{n-1}+by_{n-1}=G

对$ a ,b$ 系数整理

ayn+b(xn−⌊a/b⌋yn)=axn−1+byn−1ay_n+b(x_n-\lfloor a/b \rfloor y_n)= ax_{n-1}+by_{n-1}

有

xn−1=yn,yn−1=xn−⌊a/b⌋∗ynx_{n-1}=y_n,y_{n-1}=x_n- \lfloor a/b \rfloor *y_n 

1
2
3
4
5
6
7
8
9
10
def gcd(x,y):
    if y==0:
        return x
    return gcd(y,x%y)
def exgcd(a,b):
    if b==0 :
        return (1,0)
    else :
        (x,y)=exgcd(b,a%b)
        return y,x-(int)(a/b)*y