第七周讲义-建中首页.PDFVIP

建國中學 2009 資訊科校內培訓講義 Chapter Chapter 77 數學方法數學方法 （Math（Math）） ChapterChapter 77 數學方法數學方法 （（MathMath ）） ●Section1 數論基礎 （Basic Number Theory） 數學是科學的皇后 ，數論是數學的皇后。 ——高斯 §1-1 整除,質數,互質及因式分解 為了定義除法 ，有除法原理 ：若a,b 為整數 ，則存在唯一的一組整數q,r ，使得a bq+r ， 且 0≤r |b| ，稱a 除以 b 的商為 q ，餘數為r 。而對於整數a,b 定義 b 整除 a 若且唯若存在整數 t 使 a=bt ，記為b|a ，此時亦稱b 為 a 的因數 ，a 為 b 的倍數 。 定義質數為一大於一之正整數p ，滿足除了1 與p 以外沒有其他因數 。則有算術基本定 r r r 理 ：對每一個大於1 的整數 n ，一定存在相異質數p ,p ,…,p ，使得n= p 1 p 2 ...p k ，這個表 1 2 k 1 2 k 示法 ，在不考慮順序下是唯一的，而此種表示法即 n 之因式分解 。 若 a,b,c 為整數 ，而a|b 且 a|c ，則稱a 為 b,c 之公因數 ，而b,c 公因數中最大的的一個為 其最大公因數 ，記為(b,c)。而若 b|a 且 c|a ，則稱a 為 b,c 之公倍數 ，而b,c 正公倍數中最小的 一個稱為 b,c 之最小公倍數 ，記為[b,c]。又若(b,c) =1 ，則稱b,c 互質 。 對於正整數 n ，定義歐拉函數 φ(n)為小於或等於 n 的正整數中與 n 互質的數的數目，則  1 有ϕ (n) = n ⋅ ∏ 1 -  。   p n ,p 質數  p  §1-2 模運算 在數論中 ，常常我們處理的許多問題都必須考慮數字除以某數字的餘數。為了便利討論 的進行 ，我們定義同餘符號”≡”如下 ：a≡b(mod m)代表 a–b 是 m 的倍數 ，稱為a 與 b 對模 m 同餘 ，也可寫作a≡ b 。模運算有以下幾個性質： m (1) 若 a≡b(mod m)，c≡d(mod m)，則 a+c≡b+d(mod m) (2) 若 a≡b(mod m)，c≡d(mod m)，則 a–c≡b–d(mod m) (3) 若 a≡b(mod m)，c≡d(mod m)，則 ac≡bd(mod m) (4) 若 ac≡bc(mod m)，則 a ≡b(mod m/(c,m))，若(c,m) =1 則 a≡b(mod m). (5) 若(a,m) 1 ，則存在唯一c 使 ac≡1(mod m)，其中 c 被稱作 a 對模 m 的逆 a- 1 在資訊競賽中 ，模運算通常對我們的幫助是在某些要求輸出答案除m 的餘數的題目中 ， 我們可以由這些性質知道如果計算過程只牽涉到加減乘 ，則可以直接全部在模m 下操作 。而 如果牽涉到除