餘數定理

餘數定理係數論上面一條基本而重要嘅定理。喺證明好多數論問題都會用到佢。

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

舉個例，將13粒提子分畀5個人，每個人就會有2粒，餘3粒。呢個已經係用咗餘數定理嘅概念，用數學式去寫就係

$${\displaystyle 13\div 5=2\dots 3}$$

 

$${\displaystyle 13=5\times 2+3}$$

 

整數版本

假設任何兩個整數 a、b，${\displaystyle a,b\in \mathbb {Z} }$ 。對應呢兩個數，一定會有另外兩個數叫 q 同 r，${\displaystyle r,q\in \mathbb {Z} }$ ，通常會叫 q 做商（quotient），r 做餘數（remainder）。

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

${\displaystyle a=bq+r}$ 

而r會符合 ${\displaystyle 0\leq r$  呢個條件，同埋對應 a、b 嘅 r、q 係只得一個。

多項式版本

一般嚟講，呢個多項式喺係Q[x]入面，Q係指所有有理數，即係所有嘅分數。想知更多可以去睇多項式。

假設任何兩個多項式 f(x) 同 g(x)，一定會有另外兩個多項式叫 q(x) 同 r(x)，佢哋有以下關係：

${\displaystyle f(x)=g(x)q(x)+r(x)}$ 

而 r(x) 會符合 ${\displaystyle deg(r)$  呢個條件。

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

${\displaystyle \{a-zb\geq 0:z\in \mathbb {Z} \}}$ 

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

因為 ${\displaystyle a>0}$ ，將呢個集入數值最細嗰粒元素叫做 r，咁 ${\displaystyle r=a-qb}$ 。

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

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

假設有兩個唔同嘅 q 同 r，佢哋兩個符合餘數定理，即係 ${\displaystyle a=bq+r=bq'+r'}$ ，同埋 ${\displaystyle 0\geq r$ 。

因為佢哋都係兩條式都係等於a，所以可以寫成：${\displaystyle bq+r=bq'+r'}$ 。

下一步，${\displaystyle b(q-q')=r-r'}$ 。

根據可除性，b 係可以整除 ${\displaystyle (r-r')}$ 。由於兩個 r 都細過 b，所以 ${\displaystyle r-r'}$  都係細過 b。

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

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

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

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

中學版餘數定理

假設${\displaystyle f(x)}$ 係一個多項式，咁${\displaystyle f(a)}$ 嘅數值就會等於${\displaystyle f(x)\div (x-a)}$ 嘅餘數。

證明

假設將${\displaystyle f(x)\div (x-a)}$ 。

根據餘數定理，得出${\displaystyle f(x)=(x-a)q(x)+r(x)}$ 。

將a代入x，得到${\displaystyle f(a)=(a-a)q(a)+r(a)}$ ，再推一步，${\displaystyle f(a)=r(a)}$ 。

因為${\displaystyle r(a)}$ 就係${\displaystyle f(x)\div (x-a)}$ 嘅餘數。

例一

問題：搵${\displaystyle {\frac {x^{2}+2x+3}{x+2}}}$ 嘅餘數。

步驟：假設${\displaystyle f(x)=x^{2}+2x+3}$ ，${\displaystyle g(x)=x+2}$ 。

而家想整走${\displaystyle f(x)=(x-a)q(x)+r(x)}$ 入面，${\displaystyle (x-a)q(x)}$ 呢個項。所以將${\displaystyle x+2=0}$ 。

求${\displaystyle x}$ 後，得知將${\displaystyle a=-2}$ 代入${\displaystyle x}$ 。

求${\displaystyle f(a=-2)=a^{2}+2a+3}$ 。

${\displaystyle f(-2)=(-2)^{2}+(-2)*2+3=-4+4+3=3}$ 。

所以${\displaystyle {\frac {x^{2}+2x+3}{x+2}}}$ 嘅餘數係3。

因式定理

如果${\displaystyle (x-a)}$ 係多項式${\displaystyle f(x)}$ 嘅因數，咁一定係${\displaystyle f(a)=0}$ 。

證明

假設${\displaystyle g(x)=(x-a)}$ 。利用多項式版本嘅餘數定理，得到${\displaystyle f(x)=(x-a)q(x)+r(x)}$ 。

將a代入x，得到${\displaystyle f(a)=(a-a)q(a)+r(a)}$ ，再推一步，${\displaystyle f(a)=r(a)}$ 。

因為${\displaystyle (x-a)}$ 係${\displaystyle f(x)}$ 嘅一個因數，所以兩個除完係無餘數。因此${\displaystyle r(a)=0}$ 。

總括而言，${\displaystyle f(a)=0}$ 。

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

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

而佢都可以證明出以下幾個喺數論入面有用嘅定理。

• 所有嘅單數，都一定係，對應有啲整數${\displaystyle k\in \mathbb {Z} }$ ，${\displaystyle 4k+1}$ 或者${\displaystyle 4k+3}$ 呢兩個樣之一。
• 任何一個整數${\displaystyle a\in \mathbb {Z} }$ 嘅平方，都一定係，對應有啲整數${\displaystyle k\in \mathbb {Z} }$ ，${\displaystyle 3k}$ 或者${\displaystyle 3k+1}$ 呢兩個樣之一。
• 任何一個單數${\displaystyle a\in \mathbb {Z} }$ 嘅平方，都一定係，對應有啲整數${\displaystyle k\in \mathbb {Z} }$ ，${\displaystyle 8k+1}$ 呢個樣。
• 任何一個單數${\displaystyle a\in \mathbb {Z} }$ 嘅三次方，都一定係，對應有啲整數${\displaystyle k\in \mathbb {Z} }$ ，${\displaystyle 9k,9k+1}$ 或者${\displaystyle 9k+8}$ 呢幾個樣之一。

• 輾轉相除法
• 可除性