睇餘數定理嘅原碼

'''餘數定理'''（Division Theorem or Division Algorithm）係[[數論]]上面一條基本而重要嘅[[定理]]。喺證明好多數論問題都會用到佢。

餘數定理係講兩個數，一個除另一個嘅時候，會有一個商同一個餘數。呢個定理係喺唔同嘅域都有對應嘅版本，最常見嘅有多整數同多項式嘅版本。

== 概念 ==
餘數定理係一條常用嘅理論，一做除法就會用到。

舉個例，將13粒提子分畀5個人，每個人就會有2粒，餘3粒。呢個已經係用咗餘數定理嘅概念，用數學式去寫就係<math display="block">13\div5 = 2\dots3</math>換一個寫法就係<math display="block">13=5\times2+3</math>13係'''被除數'''，5係'''除數'''，2係'''商'''，3係'''餘數'''。

== 定理 ==

=== 整數版本 ===
假設任何兩個[[整數]] a、b，<math>a,b \in\Z</math>。對應呢兩個數，一定會有另外兩個數叫 q 同 r，<math>r,q \in \Z</math>，通常會叫 q 做[[商]]（quotient），r 做[[餘數]]（remainder）。

而以上四個數字會得出以下關係：

<math>a=bq+r</math>

而r會符合 <math>0\leq r <b </math> 呢個條件，同埋對應 a、b 嘅 r、q 係只得一個。

=== 多項式版本 ===
<blockquote>''一般嚟講，呢個多項式喺係Q[x]入面，Q係指所有有理數，即係所有嘅分數。想知更多可以去睇[[多項式]]。''</blockquote>假設任何兩個[[多項式]] f(x) 同 g(x)，一定會有另外兩個多項式叫 q(x) 同 r(x)，佢哋有以下關係：

<math>f(x)=g(x)q(x)+r(x)</math>

而 r(x) 會符合 <math>deg(r)< deg(g)</math> 呢個條件。

== 證明 ==
首先證明 q 同 r 係存在：假設 a 係大過[[零]]。我哋考慮以下呢個[[集]] (Set)。

<math>\{a-zb\geq0:z\in\Z\}</math>

咁其實上面呢個集係集合咗，所有a減走b嘅倍數嘅正整數。即係呢個集係 <math>\{a-bb,a-2b,a-3b,\dots\}</math>。

因為 <math>a>0</math>，將呢個集入數值最細嗰粒元素叫做 r，咁 <math>r=a-qb</math>。

再假設，如果 <math>r\geq b</math>，將 <math>r=a-qb</math> 代入去。結果，<math>a-(q+1)\geq0</math>。由於 <math>r=a-qb</math> 係最細個粒，所以
<math>a-(q+1)\geq0</math> 嘅情況係唔可能出現。因此，<math>0\leq r<b </math>。

之後，證明獨特性，呢個證明需要用到可除性嘅概念。

假設有兩個唔同嘅 q 同 r，佢哋兩個符合餘數定理，即係 <math>a=bq+r=bq'+r'</math>，同埋 <math>0\geq r<b,0\geq r'<b</math>。

因為佢哋都係兩條式都係等於a，所以可以寫成：<math>bq+r=bq'+r'</math>。

下一步，<math>b(q-q')=r-r'</math>。

根據可除性，b 係可以整除 <math>(r-r')</math>。由於兩個 r 都細過 b，所以 <math>r-r'</math> 都係細過 b。

根據上面兩個事實，b 只可以整除 b 嘅倍數，而 b又可以整除到 <math>r-r'</math>，而 <math>r-r'</math> 係大過等於零同細過 b。可以得出 <math>r-r'=0</math> 呢個事實。

因此兩個r係一樣。再根據呢個事實，就可以得知兩個 q 都係一樣。

上面證明任何兩個整數相除，佢哋對應嘅商同餘數都係獨一無二。

== 推理 ==
香港中學教嘅餘數定理（Remainder Theorem）同[[餘數定理|因式定理]]（Factor Theorem）都係餘數定理嘅推論（Corollary）。

=== 中學版[[餘數定理 (DSE)|餘數定理]] ===
假設<math>f(x)</math>係一個多項式，咁<math>f(a)</math>嘅數值就會等於<math>f(x)\div(x-a)</math>嘅餘數。

==== 證明 ====
假設將<math>f(x)\div(x-a)</math>。

根據餘數定理，得出<math>f(x)=(x-a)q(x)+r(x)</math>。

將a代入x，得到<math>f(a)=(a-a)q(a)+r(a)</math>，再推一步，<math>f(a)=r(a)</math>。

因為<math>r(a)</math>就係<math>f(x)\div(x-a)</math>嘅餘數。

===== 例一 =====
問題：搵<math>\frac{x^2+2x+3}{x+2}</math>嘅餘數。

步驟：假設<math>f(x)=x^2+2x+3</math>，<math>g(x)=x+2</math>。

而家想整走<math>f(x)=(x-a)q(x)+r(x)</math>入面，<math>(x-a)q(x)</math>呢個項。所以將<math>x-2=0</math>。

求<math>x</math>後，得知將<math>a=2</math>代入<math>x</math>。

求<math>f(a=2)=a^2+2a+3</math>。

<math>f(2)=2^2+2*2+3=4+4+3=11</math>。

所以<math>\frac{x^2+2x+3}{x+2}</math>嘅餘數係11。

=== 因式定理 ===
如果<math>(x-a)</math>係多項式<math>f(x)</math>嘅因數，咁一定係<math>f(a)=0</math>。

==== 證明 ====
假設<math>g(x)=(x-a)</math>。利用多項式版本嘅餘數定理，得到<math>f(x)=(x-a)q(x)+r(x)</math>。

將a代入x，得到<math>f(a)=(a-a)q(a)+r(a)</math>，再推一步，<math>f(a)=r(a)</math>。

因為<math>(x-a)</math>係<math>f(x)</math>嘅一個因數，所以兩個除完係無餘數。因此<math>r(a)=0</math>。

總括而言，<math>f(a)=0</math>。

因式定理可以用嚟測定(x-a)係唔係一個因數，同埋可以用嚟幫手進行因式分解。

== 應用 ==
餘數定理重有好多唔同嘅應用。佢可以用嚟證明[[輾轉相除法]]，從而可以搵到[[最大公因數]]。

而佢都可以證明出以下幾個喺數論入面有用嘅定理。
* 所有嘅單數，都一定係，對應有啲整數<math>k\in\Z</math>，<math>4k+1</math>或者<math>4k+3</math>呢兩個樣之一。
* 任何一個整數<math>a\in\Z</math>嘅平方，都一定係，對應有啲整數<math>k\in\Z</math>，<math>3k</math>或者<math>3k+1</math>呢兩個樣之一。
* 任何一個單數<math>a\in\Z</math>嘅平方，都一定係，對應有啲整數<math>k\in\Z</math>，<math>8k+1</math>呢個樣。
* 任何一個單數<math>a\in\Z</math>嘅三次方，都一定係，對應有啲整數<math>k\in\Z</math>，<math>9k,9k+1</math>或者<math>9k+8</math>呢幾個樣之一。

== 睇埋 ==
* [[輾轉相除法]]
* [[可除性]]

{{現代數學基礎}}
{{數論}}
[[Category:數學]]
[[Category:數論]]