取模運算和取餘運算（轉自百度，加入部分自己的了解）

轉載自：https://baike.baidu.com/item/%E5%8F%96%E6%A8%A1%E8%BF%90%E7%AE%97/10739384?fr=aladdin

取模運算

取模運算（“Module Operation”）和取餘運算（“Complementation ”）兩個概念有重疊的部分但又不完全一緻。主要的差別在于對負整數進行除法運算時操作不同。取模主要是用于計算機術語中。取餘則更多是數學概念。

模運算在數論和程式設計中都有着廣泛的應用，從奇偶數的判别到素數的判别，從模幂運算到最大公約數的求法，從孫子問題到凱撒密碼問題，無不充斥着模運算的身影。雖然很多數論教材上對模運算都有一定的介紹，但多數都是以純理論為主，對于模運算在程式設計中的應用涉及不多。

中文名取模運算

公式n = kp + r

求整數商 c = a/b

計算模 r = a - cb

目錄

1 取餘運算差別

2 概念

▪ 定義

▪ 基本性質

▪ 運算規則

▪ 重要定理

3 應用

▪ 判别奇偶數

▪ 判别素數

▪ 求最大公約數

▪ 水仙花數

▪ 模幂運算

▪ 《孫子問題(中國剩餘定理)》

▪ 凱撒密碼

取餘運算差別

對于整型數a，b來說，取模運算或者求餘運算的方法都是：

1.求 整數商： c = a/b;

2.計算模或者餘數： r = a - cb.

求模運算和求餘運算在第一步不同: 取餘運算在取c的值時，向0 方向舍入(fix()函數)；而取模運算在計算c的值時，向負無窮方向舍入(floor()函數)。

例如計算：-7 Mod 4

那麼：a = -7；b = 4；

第一步：求整數商c，如進行求模運算c = -2（向負無窮方向舍入），求餘c = -1（向0方向舍入）；

第二步：計算模和餘數的公式相同，但因c的值不同，求模時r = 1，求餘時r = -3。

歸納：當a和b符号一緻時，求模運算和求餘運算所得的c的值一緻，是以結果一緻。

當符号不一緻時，結果不一樣。求模運算結果的符号和b一緻，求餘運算結果的符号和a一緻。

另外各個環境下%運算符的含義不同，比如c/c++，java 為取餘，而python則為取模。

補充：

7 mod 4 = 3（商 = 1 或 2，1<2，取商=1）

-7 mod 4 = 1（商 = -1 或 -2，-2<-1，取商=-2）

7 mod -4 = -1（商 = -1或-2，-2<-1，取商=-2）

-7 mod -4 = -3（商 = 1或2，1<2，取商=1）

這裡模是4，取模其實全稱應該是取模數的餘數，或取模餘。

增加補充内容（以上五行）後，被修改商值，但是括号内容不變，出現奇怪沖突。

在python下 % 運算符代表取模，如要修改，請先用python做

-7 % 4

運算，或其它語言做取模運算驗證，了解後再動手。

概念

定義

給定一個正整數p，任意一個整數n，一定存在等式 ：

n = kp + r ；

其中 k、r 是整數，且 0 ≤ r < p，則稱 k 為 n 除以 p 的商，r 為 n 除以 p 的餘數。

對于正整數 p 和整數 a,b，定義如下運算：

取模運算：a % p（或a mod p），表示a除以p的餘數。

模p加法：(a + b) % p ，其結果是a+b算術和除以p的餘數。

模p減法： (a - b) % p ，其結果是a-b算術差除以p的餘數。

模p乘法：(a *b) % p ，其結果是 a * b算術乘法除以p的餘數。

說明：

1. 同餘式：正整數a，b對p取模，它們的餘數相同，記做 或者a ≡ b (mod p)。
2. n % p 得到結果的正負由被除數n決定,與p無關。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

基本性質

若p|(a-b)，則a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)

(a % p)=(b % p)意味a≡b (% p)

對稱性：a≡b (% p)等價于b≡a (% p)

傳遞性：若a≡b (% p)且b≡c (% p) ，則a≡c (% p)

運算規則

模運算與基本四則運算有些相似，但是除法例外。其規則如下：

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p ) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

a b % p = ( (a % p)b ) % p （4）

結合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

((ab) % p * c)% p = (a * (bc) % p) % p （6）

交換律：

(a + b) % p = (b+a) % p （7）

(a * b) % p = (b * a) % p （8）

配置設定律：

(a+b) % p = ( a % p + b % p ) % p （9）

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （10）

重要定理

若a≡b (% p)，則對于任意的c，都有(a + c) ≡ (b + c) (%p)；（11）

若a≡b (% p)，則對于任意的c，都有(a * c) ≡ (b * c) (%p)；（12）

若a≡b (% p)，c≡d (% p)，則 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a * c) ≡ (b * d) (%p)； （13）