这个欧几里得算法中的定理我觉得肯定不对啊
在求两个整数的最大公约数要用到欧几里得算法,简单的说就是：
设A,B(A>B)最大公约数为k,则
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C<B)
得到
(A,B) == (C,B)
欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证
欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：
void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
模P乘法逆元
对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元。
定理：a存在模p的乘法逆元的充要条件是gcd(a,p) = 1
证明：
首先证明充分性
如果gcd(a,p) = 1，根据欧拉定理，aφ(p) ≡ 1 mod p，因此
显然aφ(p)-1 mod p是a的模p乘法逆元。
再证明必要性
假设存在a模p的乘法逆元为b
ab ≡ 1 mod p
则ab = kp +1 ，所以1 = ab - kp
因为gcd(a,p) = d
所以d | 1
所以d只能为1
扩展欧几里德算法
扩展欧几里德算法不但能计算(a,b)的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下：
int gcd(int a, int b , int& ar,int & br)
{
int x1,x2,x3;
int y1,y2,y3;
int t1,t2,t3;
if(0 == a)
{//有一个数为0，就不存在乘法逆元
ar = 0;
br = 0 ;
return b;
}
if(0 == b)
{
ar = 0;
br = 0 ;
return a;
}
x1 = 1;
x2 = 0;
x3 = a;
y1 = 0;
y2 = 1;
y3 = b;
int k;
for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)
{
k = x3 / y3;
t2 = x2 - k * y2;
t1 = x1 - k * y1;
x1 = y1;
x1 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
if( y3 == 1)
{
//有乘法逆元
ar = y2;
br = x1;
return 1;
}else{
//公约数不为1，无乘法逆元
ar = 0;
br = 0;
return y3;
}
}
扩展欧几里德算法对于最大公约数的计算和普通欧几里德算法是一致的。计算乘法逆元则显得很难明白。我想了半个小时才想出证明他的方法。
首先重复拙作整除中的一个论断：
如果gcd(a,b)=d，则存在m,n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数(t1,t2,t3)，用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假设前k行都成立，考察第k+1行
对于k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分别满足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根据扩展欧几里德算法，假设t3(k-1) = j t3(k) + r
则：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
则
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得证
因此，当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
参考资料：
http://baike.baidu.com/view/795549.htm
http://image.baidu.com/i?ct=503316480&z=0&tn=baiduimagedetail&word=%B9%B4%B9%C9%B6%A8%C0%ED%B5%C4%D6%A4%C3%F7&in=22084&cl=2&cm=1&sc=0&lm=-1&pn=61&rn=1&di=12624804&ln=129&fr=
上面这个网址是图片。
从图上可以看到，这两个正方形的边长都是a + b，所以面积相等.
1号图的面积可以表示为 (1/2*ab)*4+a^2+b^2
2号图的面积可以表示为 (1/2*ab)*4+c^2
由于这两个正方形面积相等,所以(1/2*ab)*4+a^2+b^2=(1/2*ab)*4+c^2
即可得出a^2+b^2=c^2
得证.
兄弟
不要太冲动。。。。。。
3-2=1,m,n,可以是负整数！
a=3 b=2 m=1 n=-1
希腊数学家欧几里得 对勾股定理的证明方法
答：我的 希腊数学家欧几里得 对勾股定理的证明方法 是对毕达哥拉斯失传方法的一个很好的证明快点,在线等哦需要几何图形... 是对毕达哥拉斯失传方法的一个...原书没有对勾股定理进行证明,其证明是三国时东吴人赵爽在《周髀注》一书的《勾股圆方图注》中给出的。 《周髀算经》使用了相当繁复的分数算法和开平方法...
欧几里得算法解线性方程
答：对于欧几里得算法的递归式展开后的各行，都有如下表的规律：由上表可知， 总能表示为 的线性组合，上述过程中的 就是线性方程的解 。求 的整数解。的地位相同，故可以置换 的位置，设 ，则有 。最后得到 ，故线性方程的一个特解是 。利用线性方程定理，得通解为：可以验证一些特解...
什么是欧几里得算法,它有什么意义?
答：欧几里得算法即辗转相除法，用以求两个数的最大公约数（或者最小公倍数）证明如下 假设x,y的最大公约数为d 且设x=k1*d，y=k2*d;则有z=x-y=(k1-k2)*d;也必定能被d整除，所以通过两个数不断辗转，直到其中一个变为0为止，以此最终快速得出两个数的最大公约数。在算法的应用上是用求余...
欧几里得对数学界的贡献有哪些?
答：2.公理化方法：欧几里得在《几何原本》中首次使用了公理化方法，即从一组不证自明的公理出发，通过逻辑推理得出一系列的定理。这种方法后来成为西方数学的基本研究方法，对整个数学领域产生了深远影响。3.欧几里得算法：这是求解两个整数最大公约数的一种有效方法，也被称为辗转相除法。虽然这个方法在...
如何用欧几里得算法求解253,449的最大公约数?
答：可以使用扩展欧几里得算法来求解这个问题。首先，我们需要计算出253和449的最大公约数，即(253,449)。使用欧几里得算法可以得到：因此，(253,449)=1。接下来，我们可以使用扩展欧几里得算法来计算s和t。该算法可以求得两个数的最大公约数和其对应的系数s和t，满足以下方程式：(253, 449) = 1 = 253s...
勾股定理的证明及其规律
答：原因是余弦定理的证明来自勾股定理。 人们对勾股定理感兴趣的原因还在于它可以作推广。 欧几里得在他的《几何原本》中给出了勾股定理的推广定理:“直角三角形斜边上的一个直边形,其面积为两直角边上两个与之相似的直边形面积之和”。 从上面这一定理可以推出下面的定理:“以直角三角形的三边为直径作圆,则以...
数论中的计算方法有哪些?
答：扩展欧几里得算法：这是欧几里得算法的一个扩展，不仅可以计算出两个整数的最大公约数，还可以找到一对整数，使得它们的乘积等于最大公约数。费马小定理：这是一个关于素数的重要定理，它表明如果p是一个素数，那么对于任何整数a，a的p次方减a可以被p整除。中国剩余定理：这是一个关于同余方程组的定理，...
高等数学中的经典算法有什么?
答：高等数学中有许多经典算法，这些算法在解决各种数学问题和实际应用中发挥着重要作用。以下是一些常见的经典算法：欧几里得算法（Euclidean algorithm）：这是一种用于计算两个整数的最大公约数（GCD）的经典算法。它基于这样一个事实：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。通过...
ged在数论中是什么意思
答：GED，即古典欧几里德算法，是一种用于求两个正整数的最大公约数的算法。当我们需要计算两个数的最大公约数时，可以使用GED算法，该算法基于欧几里得定理，即两个正整数的最大公约数等于其中较小数和两数相除余数的最大公约数。GED算法可以用于较小的输入数字，以及在编程中比较常用。GED算法的优点是简单...
