辗转相除法和更相减损术的原理？
辗转相除法又叫欧几里得辗转相除法，最早出现在公元前300年古希腊著名数学家欧几里得的《几何原本》》(第VII卷,命题i和ii)中。而在中国则可以追溯至东汉出现的《九章算术》。而在现代数学中，这应该是属于数论的部分的。
要想解释辗转相除法的原理，需要先知道以下两点：
一、一个一般定理：
如果a是任一整数而b是任一大于零的整数，则我们总能找到一整数q，使
a=bq+r
这里r是满足不等式0<=r<b的一个整数。
二、最大公因子的表示方法：
如果整数a和b的最大公因子是d，则表示为d=(a,b) （不知道现在教科书上是怎么表示的）
给定a和b（a>=b)两个整数，求最大公因子d。
根据上边给的定理，可以将a写成
a=bq+r
辗转相除法是告诉我们
(a,b)=(b,r)
即a和b的最大公因数和b和r（r是a除以b的余数）的最大公因数是相等的。
原理：因为对任意同时整除a和b的数u，有
a=su，b=tu，
它也能整除r，因为r=a-bq=su-qtu=(s-qt)u。
反过来每一个整除b和r的整数v，有
b=s'v , r=t'v
它也能整除a，因为a=bq+r=s'vq+t'v=(s'q+t')v.
因此a和b的每一个公因子同时也是b和r的一个公因子，反之亦然。这样由于a和b的全体公因子集合与b和r的全体公因子集合相同，所以a和b的最大公因子必须等于b和r的最大公因子，这就证明了上边的等式。即(a,b)=(b,r)。
更相减损术的原理
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。
具体见：http://baike.baidu/view/1431259.htm
更相减损法是什么?原理是什么?
更相减损术,或称“辗转相除法”是用来求最大公约数的． 给出两个正整数a和b，用b除a得商a0，余数r，写成式子：a=a0b+r，0≤r＜b． ..........(1) 这是最基本的式子．如果r等于0，那么b可以除尽a，而a、b的最大公约数就是b． 如果r≠0，再用r除b，得商a1，余数r1，即：b=a1r+r1，0≤r1＜r．............ (2) 如果r1=0，那么r除尽b，由(1)也除尽a，所以r是a、b的公约数．反之，任何一个除尽a、b的数，由(1)，也除尽r，因此r是a、b的最大公约数． 如果r1≠0，则用r1除r得商a2，余数r2，即：r=a2r1+r2，0≤r2＜r1． ...........(3) 如果r2=0，那么由(2)可知r1是b、r的公约数，由(1)，r1也是a、b的公约数．反之，如果一数除得尽a、b，那末由(1)，它一定也除得尽b、r，由(2)，它一定除得尽r、r1，所以r1是a、b的最大公约数． 如果r2≠0，再用r2除r1，如法进行．由于b＞r＞r1＞r2＞......逐步小下来，而又都是正整数，因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1)．这就是有名的辗转相除法，在外国称为欧几里得算法． 例子:求42897与18644的最大公约数： 42897=2×18644+5609， (i) 18644=3×5609+1817， (ii) 5609=3×1817+158， (iii) 1817=11×158+79， (iv) 158=2×79． 所以，42897与18644的最大公约数=79
辗转相除法的原理？
原理：
设两数为a、b(a>b)，用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，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
证毕。
以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。
解释：
辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。
来源：
设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下：用a除以b，得a÷b=q......r1(0≤r1)。若r1=0，则(a，b)=b；若r1≠0，则再用b除以r1，得b÷r1=q......r2 (0≤r2）.若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个余数为0的除数即为(a, b)的最大公约数。
例如：a=25,b=15，a/b=1......10,b/10=1......5,10/5=2.......0,最后一个余数为0d的除数就是5, 5就是所求最大公约数。
举例说明：
不定方程为326x+78y=4，求出一组整数解x,y
求（326,78）的算式为：
326=4*78+14
14=326-4*78
78=5*14+8
8=78-5*14
14=1*8+6
6=14-1*8
8=1*6+2
2=8-1*6
6=3*2
所以
2=8-6=8-（14-8）
=2*8-14=2*（78-5*14）-14
=2*78-11*14=2*78-11*（326-4*78）
=46*78-11*326
即2=(-11)*326+46*78
所以4=(-22)*326+92*78
所以x = - 22, y = 92是不定方程326x+78y=4的一组解。