我们中学时学过这道题：已知非零正整数a和b，如何求a和b的最大公约数？答案是欧氏公式，表示为gcd(a,b)=gcd(b,amodb)python写的是defgcd(a,b):ifb==0:returnareturngcd(b,a%b)接下来讨论引理：a在模b中有逆元素，当且仅当引理gcd(a,b)=1指出有逆元素的条件，让我们证明它的充分性如果有整数x,y使得ax+by=1(modb)，则x是a的倒数，因为ax=1(modb)我们可以用扩展欧几里德算法求解x,yax+by=gcd(a,b)bx1+(a%b)y1=gcd(b,a%b)可以推断出x=y1y=x1-(a/b)*xwritedefexgcdusingpython(a,b):ifb==0:return1,0x1,y1=exgcd(b,a%b)returny1,x1-int(a/b)*y1可以求解x,y当a,b互质时,ax+by=gcd(a,b)=1.充分性被证明。这里不证明必然性。比较简单。x是a的倒数
