由 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) 式的左式和右式之間的等號連接起來。