由 LeetCode 1922 數學題，推導乘法同餘性質

最近在看到了 LeetCode 1922. Count Good Numbers 的題目後，發現幾乎是一題純數學的題目，需要理解 Modular Exponentiation（模冪運算）這個技巧才能夠順利解題。

想當初在學習非對稱式加密的核心技術 RSA 時，所接觸到的 Euler’s Theorem（歐拉定理）就大量用到模（Mod，取餘數）運算。

這次的題目正巧也需要對於模運算性質有所理解，才能得出有效率的解法。在理解完題意之後，結論是需要透過程式來計算以下算式：

(5^x \cdot 4^y) \bmod (10^9 + 7)

其中題目限制 $x, y \leq 10^{15}$ ，這也就意味 $5^x \cdot 4^y$ 的數值可能相當大，遠大於絕大部分的程式語言中單一變數能儲存的數字上限。

那要如何計算出結果呢？既然最終要取模 $\bmod (10^9 + 7)$ ，這個模數（ $10^9 + 7$ ）也在變數的可儲存範圍內，那我們只要確保每次的中間計算結果都不會超出變數上限即可，因此解法的關鍵就在於「拆」。

怎麼拆呢？可以像是 $4^{30} = 4^{15} \cdot 4^{15}$ 將較大的數字拆成兩個較小的數字相乘，然後分別取模。

(x^a \cdot x^b) \bmod m = ((x^a \bmod m) \cdot (x^b \bmod m)) \bmod m\tag*{(★)}

上述公式便是將大數拆小再分別取模的等式，但在寫出此等式的當下我其實不太確定是否能成立，不過只要能證明它，我們就有理論支持，能透過一般程式語言來得出計算結果。

乘法同餘、餘數定理

上述要證明的式子，可以將其簡化成：

(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m \tag*{(1)}

式子 (1) 稱作乘法同餘性質（Multiplicative Congruence），舉例來說， $(14 \cdot 6) \mod 5 = 4$ ，也等同於分別取模相乘後，再將結果取模：

((14 \bmod 5) \cdot (6 \bmod 5)) \bmod 5\\ = (4 \cdot 1) \bmod 5 = 4

但這是否就能說我們想證明的等式成立了呢？也不然，這僅僅是舉一個例子而已。

要適當嚴謹的得出結論，我們需要先了解**餘數定理（Division Theorem）**這個概念：

任意整數 $x$ 與正整數 $m$ 必定存在唯一整數對 $(q, r)$ 使得

x = q \cdot m + r,\ 0 \leq r < m

舉例來說， $14 = 2 \cdot 5 + 4$ ，其中被除數 $x = 14$ ，商數 $q = 2$ 、除數 $m = 5$ ，餘數 $r = 4$ ，而餘數 $r$ 便是 $x$ 對 $m$ 取模的結果，記為 $r = x \bmod m$ 。

接著，我們可以根據餘數定理，來定義 $(a \cdot b) \bmod m$ 中的 $a = q_1 \cdot m + r_1,\ b = q_2 \cdot m + r_2$ ，並把 $a, b$ 在式子 (1) 的左式 $(a \cdot b) \bmod m$ 展開：

(a \cdot b) \bmod m = ((q_1 m + r_1) \cdot (q_2 m + r_2)) \bmod m

= (q_1 q_2 m^2 + q_1 r_2 m + q_2 r_1 m + r_1 r_2) \bmod m

= ((q_1 q_2 m + q_1 r_2 + q_2 r_1)m + r_1 r_2) \bmod m

由於 $q_1, q_2, r_1, r_2, m$ 都是整數，因此他們的乘積及加總的組合也會是整數，將其簡化成 $K = q_1 q_2 m + q_1 r_2 + q_2 r_1$ ， $K$ 會是一個整數，所以將 $a, b$ 帶入式子 (1) 的左式結果能再簡化成下面式子 (2)

(a \cdot b) \bmod m = (Km + r_1 r_2) \bmod m \tag*{(2)}

根據剛剛從餘數定理出發來定義的 $a, b$ ，我們能得出式子 (1) 右式的 $a \bmod m$ 和 $b \bmod m$ 就等同 $r_1$ 及 $r_2$ 這兩個餘數，因此式子 (1) 右式就能推導出下述式子 (3)。

((a \bmod m) \cdot (b \bmod m)) \bmod m = (r_1 r_2) \bmod m \tag*{(3)}

只要能證明 (2) 和 (3) 兩個式子的右式等價，整個乘法同餘的證明就大功告成，我們繼續拆解下去：

(Km + r_1 r_2) \bmod m = (r_1 r_2) \bmod m \tag*{(4)}

再另外定義一個整數 $c = k \cdot m$ （ $c$ 為除數 $m$ 的倍數， $k$ 是個整數），然後令 $x = r_1 r_2$ ，想證明的式子 (4) 就等價於下面式子 (5)

(x + c) \bmod m = x \bmod m \tag*{(5)}

根據餘數定理令 $x = q \cdot m + r$ 及 $c = k \cdot m$ 展開帶入式子 (5) 的左式：

(x + c) \bmod m \tag*{(5 Left)}

= (q \cdot m + r + c) \bmod m

= (q \cdot m + r + k \cdot m) \bmod m

= ((q + k) \cdot m + r) \bmod m

其中 $(q + k) \cdot m + r$ 剛好就符合餘數定理的架構，當此式對 $m$ 取餘，答案就為 $r$ ，所以得出

(x + c) \bmod m \tag*{(5 Left)}

= r

= x \bmod m \tag*{(5 Right)}

如此便得證，將 (5) 式的左式和右式之間的等號連接起來。