帶餘除法

帶餘除法，也稱為歐幾里德除法是數學中的一種基本算術計算方式。給定一個被除數formula_1和一個除數formula_2，帶餘除法給出一個整數formula_3和一個介於一定範圍的餘數formula_4，使得下面等式成立：formula_5一般限定餘數的範圍在0與formula_2之間，也有限定在formula_7與formula_8之間。這樣的限定都是為了使得滿足等式的formula_3有且僅有一個。這時候的formula_3稱為帶餘除法的商。帶餘除法一般表示為：formula_11表達為：“formula_1除以formula_2等於formula_3，餘formula_4”。最常見的帶餘除法是整數與整數的帶餘除法，但實數與整數乃至實數與實數的帶餘除法也有應用。對一般的抽象代數系統，能夠進行帶餘除法的都是具有歐幾里德性質的系統。如果餘數為零，則稱formula_2整除formula_1。一般約定除數formula_2不能為0.帶餘除法的計算有長久的歷史，有各種計算工具和計算方法。最常用的是長除法。帶餘除法在數論中有不少用途，比如說輾轉相除法的基本步驟就是帶餘除法。例子.以下是整數帶餘除法的例子：依照公曆，一年中的四月份有30天。每星期有7天，從四月的第一天開始，可以數出有四個星期，此外還有2天。如果要數出5個星期，則還差了5天。帶餘除法表示，就是：formula_19裡面的30是被除數，7是除數，4是帶餘除法得到的商，2是帶餘除法得到的餘數。日常生活中說：“四月份有四個多星期”，是帶餘除法的結果。另一個例子是分配問題。假設有30個蘋果要分給7個人，每人分的要一樣多，那麼可以使用帶餘除法：formula_19這說明每人可以分到4個，還剩餘2個。如果每人分5個，則是不夠的。每人如果只分3個，則還剩餘9個，可以繼續分。帶餘除法說明了在人人分到的要一樣多的條件下，每人可以分到的最多蘋果數目。不同的帶餘除法.最基本的帶餘除法是整數與整數的帶餘除法，這時商和餘數都是整數。實數與整數的帶餘除法，或實數與實數的帶餘除法，餘數是實數，但不一定是整數。比如說討論使用正弦函式構造的數列formula_21時，就需要使用除數為formula_22的帶餘除法，來討論每一項具體的取值。基本定理.帶餘除法限定了餘數的範圍，使得商唯一存在。整數與整數的帶餘除法中，餘數的範圍通常是formula_23這樣的formula_2個元素的集合。被除數為實數的帶餘除法中，常常會使用介於0和除數formula_25之間的半開閉區間作為餘數的範圍；另一種常見的範圍是大於等於formula_27，嚴格小於formula_28。帶餘除法的基本定理說明：整數與整數的帶餘除法中，只要餘數的範圍是formula_25個整數，並且任何兩個數之差都不是b的倍數，那麼帶餘除法的商唯一存在；被除數為實數的除法中，只要餘數的範圍是一個如同長度為formula_25的半開半閉區間，那麼帶餘除法的商唯一存在。:25最常見的帶餘除法中用到的是整數除以整數的一個版本：對任何給定的整數formula_1和非零整數formula_2，都存在唯一的整數formula_3以及屬於集合formula_23的整數formula_4，使得formula_5證明.定理的證明是將整數集合或實數軸分割成長度為|b|的區間段。證明由兩部分組成 - 首先證明formula_3和formula_4的存在性，其次證明formula_3和formula_4的唯一性。整數除以整數的情況：假設餘數的範圍是formula_41，其中任兩個數的差都不是formula_2的倍數。那麼可以將全體整數分割成以下集合的不交併集：formula_43其中的formula_44指兩兩不相交的並集。這樣的劃分方式下，不會有兩個集合有交集。反設有兩個集合formula_45和formula_46有交集：formula_47那麼formula_48這說明有兩個元素的差是formula_2的倍數。矛盾。另一方面，任何一個整數都必然屬於某個formula_45。設有整數formula_51，那麼存在整數formula_52使得formula_53，也就是說存在formula_23裡的一個數formula_55，使得formula_56 同樣地，對formula_57裡的每一個數formula_58，也各自存在formula_23的一個數formula_60和一個整數formula_61，使得formula_62 由於有formula_63個屬於集合formula_23的整數，根據抽屜原理，必然有兩個整數相同。而由前所證，不可能有formula_65的情況，所以只能是存在某個formula_66使得formula_67，所以：formula_68formula_69因此，任何一個整數都唯一地屬於某個formula_45。而對應的這個整數formula_71就是帶餘除法唯一確定的商。:18-22被除數是實數的情況：假設餘數的範圍是formula_72，那麼將實數軸formula_73分割為：formula_74這個分割方式構成了實數的一個分劃，每個實數都唯一地屬於其中的某一個區間段，所以被除數formula_1也必然唯一地屬於其中的某一個區間段。假設formula_1屬於區間段：formula_77，則說明formula_78所以帶餘除法的商唯一確定，就是formula_79。計算.計算帶餘除法和計算除法的手段基本相同。手工計算時常常使用長除法，與除法不同之處是到個位即停止，剩餘的即是餘數。計算機運算中使用的帶餘除法一般耗費的時間比相同位數的乘法更久，所以程式設計時為了減少機器運算量，常常會盡力避免除法運算。一般的程式語言和數學、統計軟體中，帶餘除法運算子可能是分開的，也可能是合併的。如在進行帶餘除法時儘管預設返回的是商，但實際上餘數也儲存在運算結果中。除數是2的冪次的時候，可以使用右移的位移運算代替帶餘除法。這是因為計算機儲存資料使用的是二進位制，取一個長度為formula_80的二進位制數的前formula_71位，實際上就是它除以2的formula_82次冪後的商，而後formula_82位則是其餘數。演算法.原始演算法.原始的帶餘除法演算法可以視為是重複使用減法的過程。設要計算formula_1除以formula_2，則在formula_1裡面不斷地扣除formula_2，直到不能繼續扣除為止。以formula_1、formula_2都是正整數，餘數範圍為formula_90的除法為例，虛擬碼如下：function Division(a, b)q ← 0; r ← a;while r &gt;= b dor ← r - b;q ← q + 1;end whilereturn q, r;這樣的演算法複雜度是formula_91的級別。使用二分法.更為最佳化的演算法是使用二進位制以及二分法的結合。演算法大致分為兩個部分：首先用不斷倍增的方式找出一個formula_1所屬的區間，然後用二分法不斷收窄區間，直到將formula_1限制在一個長度為formula_2的區間為止。舉例來說，要計算237除以9，可以首先列出如下表格：也就是從小到大逐個列出2的冪次與9的乘積，直到超過237為止。其中，24 × 9 = 144 是小於等於237的最大數，之後的288就比237更大了。接下來反過來利用2的冪次與9的乘積來計算237除以9。過程如下：function QuickDivision(a, b)counter ← 0; power ← 1; mid ← 0; appr ← 0;//-{zh-hans:找到2的冪次與除數b的乘積中比被除數a大的最小數對應的冪次;zh-hant:找到2的冪次與除數b的乘積中比被除數a大的最小數對應的冪次}-while power * b &lt;= a docounter ← counter + 1;power ← power * 2 ;end whilep ← power; q ← power / 2;//p和q乘以b以後分別是a的上界和下界，以下用二分法不斷收窄上下界，直到上下界之差等於b為止for k from 1 to counter - 1 do//計算上下界的平均值comp ← (p + q) / 2;mid ← comp * b;//如果平均值小於等於a，則調高下界，同時記錄平均值，否則調低上界if mid &lt;= a thenappr ← mid;q ← comp;elsep ← comp;end ifend for//結束後q乘以b的積就是小於等於a的b的倍數中最大的，這說明q就是商；appr是最後一個小於等於a的平均值，所以它和a的差就是餘數r ← a - appr;return q, r;以上的演算法的複雜度在formula_106級別，當formula_91較大時，遠遠比原始的演算法快捷。推廣.多項式的帶餘除法.以域formula_108為係數的多項式構成的多項式整環formula_109中也可以定義帶餘除法。設有formula_110、formula_111兩個多項式，其中formula_111不是零多項式。則存在由formula_110和formula_111唯一確定的多項式formula_115和formula_116，使得：formula_117並且多項式formula_116是零多項式或者它的次數嚴格小於formula_111的次數，稱為多項式帶餘除法的餘元。:10歐幾里德整環.普通的整數或實數之間的帶餘除法可以良好定義。在更廣泛的代數結構中，能夠定義帶餘除法的代數結構被稱為歐幾里德整環。定義如下：設有整環formula_120和從formula_120到自然數的對映formula_122，使得：若formula_123而formula_124，則存在formula_125使得formula_126，而且要麼有formula_127，或者 formula_128。則稱formula_120為歐幾里德整環。:141歐幾里德整環中，使用一個額外的函式來比較兩個元素之間的“大小”關係，從而能夠定義帶餘除法。這個函式也稱為範數。歐幾里德整環必然是主理想整環因而也必然是唯一分解整環。:141:16-17