【学习笔记】关于最大公约数(gcd)的定理
结论1gcd(xa−1,xb−1)=xgcd(a,b)−1\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1gcd(xa−1,xb−1)=xgcd(a,b)−1证明:采用数学归纳法。令a=kb+pa=kb+pa=kb+p, 则有gcd(xa−1,xb−1)=gcd(xkb+p−1,xb−1)=gcd(xp(xkb−1)+xp−1,xb−1)=gcd(xp−1,x...
