Loading AI tools
定理 来自维基百科,自由的百科全书
歐幾里得除法(英語:Euclidean division),也稱為帶餘除法(英語:division with remainder),是數學中的一種基本算術計算方式。給定一個被除數和一個除數,帶餘除法給出一個整數商和一個介於一定範圍的餘數,使得下面等式成立:
一般所稱「歐幾里得除法」,限定餘數的範圍為:
還有叫做「居中除法」(英語:centered division)的變體,限定餘數為,這種餘數稱為「居中餘數」。這樣的限定都是為了使得滿足等式的有且僅有一個。這時候的稱為帶餘除法的商。
最常見的帶餘除法是整數與整數的帶餘除法(被除數和除數都是整數),但實數與整數乃至實數與實數的帶餘除法也有應用。對一般的抽象代數系統,能夠進行帶餘除法的都是具有歐幾里得性質的系統。如果餘數為零,則稱整除。一般約定除數不能為。
帶餘除法可表示為:
表達為:「除以等於,餘」。
帶餘除法的計算有長久的歷史,有各種計算工具和計算方法。最常用的是長除法(豎式除法)。帶餘除法在數論中有不少用途,比如說輾轉相除法的基本步驟就是帶餘除法。術語「歐幾里得除法」是在二十世紀期間作為「歐幾里得環的除法」的簡稱而介入的。
以下是整數帶餘除法的例子:依照公曆,一年中的四月份有30天。每星期有7天,從四月的第一天開始,可以數出有四個星期,此外還有2天。如果要數出5個星期,則還差了5天。帶餘除法表示,就是:
裡面的30是被除數,7是除數,4是帶餘除法得到的商,2是帶餘除法得到的餘數。日常生活中說:「四月份有四個多星期」,是帶餘除法的結果。
另一個例子是分配問題。假設有30個蘋果要分給7個人,每人分的要一樣多,那麼可以使用帶餘除法:
這說明每人可以分到4個,還剩餘2個。如果每人分5個,則是不夠的。每人如果只分3個,則還剩餘9個,可以繼續分。帶餘除法說明了在人人分到的要一樣多的條件下,每人可以分到的最多蘋果數目。
最基本的帶餘除法是整數與整數的帶餘除法,這時商和餘數都是整數。實數與整數的帶餘除法,或實數與實數的帶餘除法,餘數是實數,但不一定是整數。比如說討論使用正弦函數構造的數列時,就需要使用除數為的帶餘除法,來討論每一項具體的取值。
帶餘除法限定了餘數的範圍,使得商唯一存在。整數與整數的帶餘除法中,餘數的範圍通常是這樣的個元素的集合。被除數為實數的帶餘除法中,常常會使用介於0和除數之間(大於等於0,嚴格小於)的半開閉區間作為餘數的範圍;另一種常見的範圍是大於等於,嚴格小於。帶餘除法的基本定理說明:整數與整數的帶餘除法中,只要餘數的範圍是個整數,並且任何兩個數之差都不是b的倍數,那麼帶餘除法的商唯一存在;被除數為實數的除法中,只要餘數的範圍是一個如同長度為的半開半閉區間,那麼帶餘除法的商唯一存在。[1]:25
最常見的帶餘除法中用到的是整數除以整數的一個版本:
對任何給定的整數和非零整數,都存在唯一的整數以及屬於集合的整數,使得
定理的證明是將整數集合或實數軸分割成長度為|b|的區間段。證明由兩部分組成 - 首先證明和的存在性,其次證明和的唯一性。
假設餘數的範圍是,那麼將實數軸分割為:
這個分割方式構成了實數的一個分劃,每個實數都唯一地屬於其中的某一個區間段,所以被除數也必然唯一地屬於其中的某一個區間段。假設屬於區間段:,則說明
所以帶餘除法的商唯一確定,就是。
計算帶餘除法和計算除法的手段基本相同。手工計算時常常使用長除法,與除法不同之處是到個位即停止,剩餘的即是餘數。計算機運算中使用的帶餘除法一般耗費的時間比相同位數的乘法更久,所以編程時為了減少機器運算量,常常會盡力避免除法運算。一般的程式語言和數學、統計軟體中,帶餘除法運算符(指令)和取模運算符(指令)可能是分開的,也可能是合併的。如在進行帶餘除法時儘管默認返回的是商,但實際上餘數也儲存在運算結果中。除數是2的冪次的時候,可以使用右移的位移運算代替帶餘除法。這是因為計算機儲存數據使用的是二進制,取一個長度為的二進制數的前位,實際上就是它除以2的次冪後的商,而後位則是其餘數。
原始的帶餘除法算法可以視為是重複使用減法的過程。設要計算除以,則在裡面不斷地扣除,直到不能繼續扣除(滿足餘數範圍)為止。以、都是正整數,餘數範圍為的除法為例,偽代碼如下:
function Division(a, b)
q ← 0; r ← a;
while r >= b do
r ← r - b;
q ← q + 1;
end while
return q, r;
更為優化的算法是使用二進制以及二分法的結合。算法大致分為兩個部分:首先用不斷倍增的方式找出一個所屬的區間,然後用二分法不斷收窄區間,直到將限制在一個長度為的區間為止。舉例來說,要計算237除以9,可以首先列出如下表格:
0 | 1 | 2 | 3 | 4 | 5 |
1 | 2 | 4 | 8 | 16 | 32 |
9 | 18 | 36 | 72 | 144 | 288 |
也就是從小到大逐個列出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 <= a do
counter ← counter + 1;
power ← power * 2 ;
end while
p ← power; q ← power / 2;
//p和q乘以b以後分别是a的上界和下界,以下用二分法不断收窄上下界,直到上下界之差等于b(即p与q之差等于1)为止
for k from 1 to counter - 1 do
//计算上下界的平均值
comp ← (p + q) / 2;
mid ← comp * b;
//如果平均值小于等于a,则调高下界,同时记录平均值,否则调低上界
if mid <= a then
appr ← mid;
q ← comp;
else
p ← comp;
end if
end for
//结束后q乘以b的积就是小于等于a的b的倍数中最大的,这说明q就是商;appr是最後一个小于等于a的平均值,所以它和a的差就是余数
r ← a - appr;
return q, r;
以上的算法的複雜度在級別,當較大時,遠遠比原始的算法快捷。[3]
以域為係數的多項式構成的多項式整環中也可以定義帶餘除法。設有、兩個多項式,其中不是零多項式。則存在由和唯一確定的多項式和,使得:
並且多項式是零多項式或者它的次數嚴格小於的次數,稱為多項式帶餘除法的餘元。[4]:10
普通的整數或實數之間的帶餘除法可以良好定義。在更廣泛的代數結構中,能夠定義帶餘除法的代數結構被稱為歐幾里得整環。定義如下:
歐幾里得整環中,使用一個額外的函數來比較兩個元素之間的「大小」關係,從而能夠定義帶餘除法。這個函數也稱為範數。歐幾里得整環必然是主理想整環因而也必然是唯一分解整環。[1]:141[4]:16-17
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.