第二十章 歐幾里得演算法(第1/1頁)
章節報錯
歐幾里得學生卡農對歐幾里得說：“如果可以可靠的求出兩個數字的最大公約數？”
歐幾里得說：“用輾轉相除法就可以，如果求a和b的最大公約數，如果a大於b，那就是a除以b，然後得到餘數，然後再讓除數b除以餘數，然後一直讓除數除以餘數，最後餘數為0的時候，得到的除數就是a和b的最大公約數。”
卡農說：“假如說1997和615這兩個數字。”
歐幾里得說：“1997除以615，等於3餘出152。”
卡農說：“然後怎麼求？”
歐幾里得說：“除數除以餘數，615除以152等於4餘7.”
卡農說：“然後152除以7等於21餘5.”
歐幾里得接著說：“沒錯，然後7除以5，等於1餘2.”
卡農說：“5除以2，等於2餘1.”
歐幾里得說：“2除以1，等於2餘0.”
卡農說：“不能再往下了，餘數已經為0，所以1997和615的最大公約數為1.”
歐幾里得說：“所以說，相當於沒有最大公約數。”
在以上基礎上，後來數學中發展了環的概念，整環R是符合一下接個要求的：
1、A 關於加法成為一個 Abel 群（其零元素記作 0）；
2、乘法滿足結合律：(a * b)* c = a *(b * c)；
3、乘法對加法滿足分配律：a *(b + c)= a * b + a * c，(a + b)* c = a * c + b * c；
如果環 A 還滿足以下乘法交換律，則稱為“交換環”：
4、乘法交換律：a * b = b * a。
如果交換環 A 還滿足以下兩條件，就稱為“整環”（integral domain）：
5、A 中存在非零的乘法單位元，即存在 A 中的一個元素，記作 1，滿足：1 不等於 0，且對任意 a，有：e* a = a * e= a；
6、ab=0 => a=0 或 b=0。
而後來也引入了歐幾里得整環的概念，這是抽象代數中，這是一種能作輾轉相除法的整環。凡歐幾里得整環必為主理想環。