一切由整除開始

每當我們研習數論，書本的第一章總是由整除 (Divisible) 開始，這也是初等數論 (Elementary Number Theory) 的基本。其實這初等並無貶意，這不過是為了和「堆疊數論」 (Additive Number Theory) 、「代數數論」 (Algebraic Number Theory) 等區分而已。

　

所謂 a 整除 b ，簡記為 a | b，即存在一整數 k 使 b = ak 。這樣我們稱 a 為 b 的因子 (Divisor 或 Factor) 或稱因數、約數。我們又可以說 b 為 a 的倍數 (Multiple) 。為便於諸位閱讀，本網沿用文字表述「整除」而不用符號。

　

對整除而言，我們有若干性質：

a 整除 b 則有 a 整除 kb 對任何整數 k；

a 整除 b 及 b 整除 a 則有 a = +b 或 -b；

a 整除 b 及 b 整除 c 則有 a 整除 c；

a 整除 b 及 a 整除 c 則有 a 整除 (sb + tc) 對任何整數 s, t；

對任何非零整數  k ， a 整除 b 當且僅當 ka 整除 kb。

　

我們可以看看一些證明整除性的例子：

　

證明若 3 整除 a 及 11 整除 a ，則 33 整除 a。

答：若 3 整除 a ，即令 a = 3k，其中 k 為某整數。而 11整除 a，即 11整除 3k。另一方面，11必然整除 11k。故得 11 整除 ( 2 * 11k - 7 * 3k) = k，得令 k = 11m。所以 a = 3*11m = 33m ，故 33 整除 a。

同理，只要 a、b 互素 (Coprime) ，而 a 整除 x 及 b 整除 x ，則有 ab 整除 x 了。關於互素這東西，可再參看另文《互素的學問》，進一步認識更多。

　

至於素數 (Prime Number) 又稱質數，即一不少於 2 的整數除了 1 和 自己以外，沒有別的因子，如 2, 3, 5, 7, 11, 13, ...... 若有別的因子，我們稱之為合數 (Composite Number) 或合成數，如 4, 6, 8, 9, 10, 12, 14, ...... 而 1 則視作單位 (Unit)，既非素數，也非合數。

在有了整除以後，我們再加上除法算法 (Division Algorithm)，即對任何整數 a, b (a 須為正)，必然存在惟一 的整數 q 和 r 使 b = qa + r，其中 r 為一小於 a 的非負整數。在小學裡，我們也學過這個 q 是商 (Quotient)，而 r 則是餘數 (Remainder)。初等數論便是這樣的建構起來。當然我們的素數理論也是這樣而來。