1. 模反元素

2021-06-12 22:21:04 +0800 CST Tags: m.m.i, number-theory

問題：給定兩個正整數 a 和 n，請找出最小的正整數 b 使得 ab $\equiv$ 1 (mod n)，若不存在則輸出 No Inverse。

解法：這個問題的經典作法是使用 extended Euclidean algorithm，只要我們能找到最小的正整數 x 以及另一個整數 y 滿足 ax + ny = 1，那麼 x 就是我們要的，反之答案就不存在。這個演算法的主要精神在於我們只要把被除數和除數都表示成 a 和 n 的線性組合，那麼餘數也必定能表示成 a 和 n 的線性組合，等到下一次迭代的時候除數變成被除數，餘數變成除數時，仍然滿足我們要的前提，最後等到餘數為 1 (也就是餘數為 0 的前一組餘數) 時，它的線性組合就幾乎滿足我們的需求了。為什麼說是「幾乎」呢？因為這個演算法只保證過程中的 |x| $\le$ n 而且 |y| $\le$ a，所以至少要先替 x 加一輪 n 再取除以 n 的餘數，才能保證它是最小正整數。最後來討論無解的情況，很明顯當 a 和 n 的最大公因數 d 大於 1 時 ax + ny 也必須是 d 的倍數所以不可能滿足等式，另外 d = 1 時 ax 必定能表達成 1 - ny，那麼對等號兩邊 mod n 之後只有在 n = 1 時會讓餘數為 0，其他情況餘數都會是 1。

證明 (非必要)：這題令人玩味的地方在於為什麼過程中永遠有 |x| $\le$ n 而且 |y| $\le$ a，可是不知道這個事實其實也沒關係，因為這裡會告訴我們怎麼調整一個任意整數到最小同餘非負整數。為了推導方便，讓我們重新定義一下符號，我們現在想找到滿足 $ax_i+by_i=1$ 的整數解 ($x_i$, $y_i$)。注意到這個演算法當 $ax_i+by_i < ax_{i+1}+by_{i+1}$ 時除一次之後就會反過來變 $ax_{i+1}+by_{i+1}$$> ax_{i+2}+by_{i+2}$，而且這個大小關係會維持到最後，所以不失一般性我可以直接假設 ($x_1$, $y_1$) 為 (1,0) 或 (0,1) 讓 $ax_1+by_1$ 比較大的那一組賦值。附註的定理整理得非常漂亮，如果我們遞迴地定義 $ax_1+by_1=(ax_2+by_2)\cdot q_1+(ax_3+by_3)$ 而 $ax_2+by_2=(ax_3+by_3)\cdot q_2+(ax_4+by_4)$ 依此類推到最後停下來的 $ax_{k-1}+by_{k-1}=(ax_k+by_k)\cdot q_{k-1}+(ax_{k+1}+by_{k+1})$，那麼附註的引理 1、2 所說的 $|x_i|\le|x_{i+1}|$ 而且 $|y_i|\le|y_{i+1}|$ 都是顯而易見，引理 3 所說的 $|x_{i+1}y_i − x_iy_{i+1}|=1$ 也可以很容易地從數學歸納法推得，它亦能直接推到 gcd ($x_i$, $y_i$) = gcd ($x_{i+1}$, $y_{i+1}$) = 1 的結論，再搭配 $ax_{k+1}+by_{k+1}=0$ 就能知道 |$x_{k+1}$| = b / gcd(a, b) $\le$ b，同時 |$y_{k+1}$| = a / gcd(a, b) $\le$ a 得證！

附註：
[1] https://www.staff.uni-mainz.de/pommeren/MathMisc/Euclid.pdf#page=3

例題：zerojudge a289。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void modular_multiplicative_inverse(int a, int n) {
    int x1=1, y1=0, x2=0, y2=1;
    do {
        int q = (a*x1 + n*y1) / (a*x2 + n*y2);
        int x3 = x1 - q*x2;
        int y3 = y1 - q*y2;
        x1 = x2; y1 = y2; x2 = x3; y2 = y3;
    } while (a*x2 + n*y2);
    if (a*x1+n*y1 > 1) cout << "No Inverse\n";
    else if (n == 1) cout << "No Inverse\n";
    else cout << (x1 + n) % n << '\n';
}