哇⊙∀⊙！

虽然稍稍玩过数电但是看不懂

lz是不是要把辗转反除的数学原理解释一下？然后再提红石是怎么实现的就会精彩多了吧？

顶

好吧，这里讲一下辗转相除法的原理（上面讲成辗转反除了）
设两数为a、b(b<a)，用gcd(a,b)表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
第一步:令c=gcd(a,b)，则设a=mc，b=nc
第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互质【否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
证毕。
那这时我们就可以使b=a，r=b，然后一直用a÷b，得到余数r，然后一直重复。因为上面的证明我们可以知道n是与m-kn互质的，一直算下去，当m-kn=1时，a正好能被b整除，而余数恰好为0，这时的b也等于c，所以使用辗转相除判定b是否为最大公约数的标准就是r是否等于0

5年级

julao

大触，大触