互質和扩展欧几里得算法

快捷方式: 差异，相似，杰卡德相似系数，参考。

互質和扩展欧几里得算法之间的区别

互質 vs. 扩展欧几里得算法

互质（英文：coprime，符號：⊥，又稱互素、relatively prime、mutually prime、co-prime）。在數論中，如果兩個或兩個以上的整數的最大公因數是 1，則稱它們為互质。依此定義：. 扩展欧几里得算法（Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足貝祖等式 如果a是负数，可以把问题转化成 通常談到最大公因數時，我們都會提到一個非常基本的事實：給予二个整數a、b，必存在整數x、y使得ax + by.

貝祖等式

在数论中，裴蜀等式（Bézout's identity）或貝祖定理（Bézout's lemma）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整數a、b和m，关于未知数x和y的線性丟番圖方程（称为裴蜀等式）： 有整数解时当且仅当m是a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都稱為裴蜀數，可用擴展歐幾里得演算法求得。 例如，12和42的最大公因數是6，则方程12x+42y.

互質和貝祖等式 · 扩展欧几里得算法和貝祖等式 · 查看更多 »

輾轉相除法

在数学中，辗转相除法，又称欧几里得算法（Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（）；因为，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如。这个重要的結論叫做貝祖定理。 辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理自然数和几何长度（相當於正實數），但在19世纪，辗转相除法被推广至其他类型的數學對象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同時這也標誌著计算复杂性理论的開端。.

互質和輾轉相除法 · 扩展欧几里得算法和輾轉相除法 · 查看更多 »

最大公因數

数学中，兩個或多個整數的最大公因數（greatest common factor，hcf）指能够整除这些整数的最大正整数（这些整数不能都为零）。例如8和12的最大公因数为4。最大公因数也称最大公约数（greatest common divisor，gcd）。 整数序列a的最大公因数可以記為(a_1, a_2, \dots, a_n)或\gcd(a_1, a_2, \dots, a_n)。 求兩個整數最大公因數主要的方法：.

互質和最大公因數 · 扩展欧几里得算法和最大公因數 · 查看更多 »