mod

mod 是取餘數的函式，要求得m / n 的餘數則寫成mod(m, n)。其中，m 稱為「被除數」，n 稱為「除數」。

]mod(7, 4) = 3

在mod 函式裡，除數與被除數皆可為負數。mod 定義餘數的方式為: 被除數減去小於被除數的最大除數倍數。

]Define.. mod(被除數, 除數)

]Instead.. 被除數 = m

]Instead.. 除數 = n

]If.. f(x) = xn , x ∈ Integer

]f(x) <= m

]mod(m, n) = m - f_max

由上面定義，我們可以知道被除數為負的情況下，mod 應該等同於除數對被除數為正的情況下的mod 的差。

]rule.. mod(m, n) = n - mod(-m, n)

]

]mod(7, 4) = 3

]mod(-7, 4) = -7 - (- 8) = 1

]mod(-7, 4) = 4 - mod(7, 4) = 4 - 3 = 1

在mod 的定義裡有一個x，這個x 是一個整數，但不限正負，因此除數的正負號是可以忽視的。

]rule.. mod(m, n) = mod(m, -n)

]

]mod(7, 4) = 3

]mod(7, -4) = 3

在國小有學過，除法算式裡，被除數與除數共同提出一個公因數時，該公因數不影響商，但影響餘數。因此，mod 函式裡被除數與除數可以同時提出一個正數到mod 外面相乘。

]rule.. a > 0 , mod(am, an) = a * mod(m, n)

]

]mod(14, 8) = 14 - 8 = 6

]mod(14, 8) = mod(7 * 2, 4 * 2) = 2 * mod(7, 4) = 2 * 3 = 6

一個mod 函式可以拆成兩個除數相同的mod 之和，且拆出兩個mod 的被除數和等於該原mod 函式的被除數，之後再把兩mod 之和當作被除數代入另一個除數相同的mod 即為解。

]rule.. mod(a + b, n) = mod(mod(a, n) + mod(b, n), n)

]

]mod(40, 9) = 4

]mod(40, 9) = mod(35 + 5, 9) = mod(mod(35, 9) + mod(5, 9), 9) = mod((35 - 27) + 5, 9) = mod(13, 9) = 4