モジュラ方程式 A mod X = B の解の個数を求める C/C++ プログラム

モジュラ方程式とは

数学におけるモジュラ方程式（modular equation）とは、モジュライ問題の意味での「モジュライ（moduli）」が満たす代数方程式のことです。つまり、モジュライ空間上に定義された複数の関数が与えられたとき、それらの間で成り立つ方程式、言い換えればモジュライに関する恒等式を指します。

この用語は、特に楕円曲線のモジュライ問題との関連で使われることが最も多いです。この場合、モジュライ空間自体の次元は1であるため、モジュラー曲線の関数体に属する任意の2つの有理関数 F と G は、複素数体上の2変数非零多項式 P によるモジュラ方程式 P(F, G) = 0 を必ず満たします。さらに、適切な非退化な F と G を選べば、方程式 P(X, Y) = 0 は実際にそのモジュラー曲線を定義することになります。

合同式の基本

次のような形の数学的表現を見たことがあるでしょう。

B ≡ (A mod X)

これは「B は A mod X と合同である」ことを意味します。具体例を挙げましょう。

21 ≡ 5 (mod 4)

記号「≡」は「合同（equivalence）」を表します。上の式では 21 と 5 が合同です。これは 21 mod 4 = 1 と 5 mod 4 = 1 が等しいためです。別の例として、51 ≡ 16 (mod 7) も同様に成り立ちます。

問題の定義

この問題では、2つの整数 A と B が与えられ、モジュラ方程式 (A mod X) = B を満たす X の取り得る値の個数を求める必要があります。

例：

入力: A = 26, B = 2
出力: X は 6 個の値を取れる

解説

X は {3, 4, 6, 8, 12, 24} のいずれかの値を取ることができます。これらのどの値で割っても余りが 2 になるからです。つまり、(26 mod 3) = (26 mod 4) = (26 mod 6) = (26 mod 8) = … = 2 となります。

解法のアプローチ

方程式は A mod X = B です。まず、A と B の大小関係によって場合分けを行います。

• A = B の場合： A より大きい任意の X に対して A mod X = A = B が成り立つため、解は無限に存在します。
• A < B の場合： 剰余が被除数より大きくなることはないため、条件を満たす X は1つも存在しません。
• A > B の場合： これが本題のケースです。

A > B の場合は、割り算の基本関係式を利用します。

被除数 = 除数 × 商 + 剰余

ここで、A が被除数、X が除数、B が剰余に対応します。したがって、

A = X × 商 + B

商を Y とおくと、

∴ A = X × Y + B
A − B = X × Y

Y が整数値を持つためには、X が (A − B) の約数である必要があります。

つまり、(A − B) の約数をすべて求めることが核心的な課題であり、その約数の個数こそが X の取り得る値の個数になります。

さらに、A mod X の剰余は必ず 0 以上 X − 1 以下の範囲に収まるため、X > B を満たす約数だけを数える必要があります。

以上のことから、「(A − B) の約数のうち B より大きいものの個数」が、A mod X = B を満たす X の取り得る値の総数であると結論できます。

C++ 実装例

#include <iostream>
#include <math.h>
using namespace std;
int Divisors(int A, int B) {
    int N = (A - B);
    int D = 0;
    for (int i = 1; i <= sqrt(N); i++) {
        if ((N % i) == 0) {
            if (i > B)
                D++;
            if ((N / i) != i && (N / i) > B)
                D++;
        }
    }
    return D;
}
int PossibleWaysUtil(int A, int B) {
    if (A == B)
        return -1;
    if (A < B)
        return 0;
    int D = 0;
    D = Divisors(A, B);
    return D;
}
int main() {
    int A = 26, B = 2;
    int Sol = PossibleWaysUtil(A, B);
    if (Sol == -1) {
        cout << " X can take Infinitely many values greater than " << A << "\n";
    } else {
        cout << " X can take " << Sol << " values\n";
        return 0;
    }
}

コードのポイント

関数 Divisors では、1 から √N まで順に試し割りを行うことで約数を効率的に列挙しています。i が N の約数であれば、ペアとなる約数 N/i も同時にチェックすることで、計算量を O(√N) に抑えています。また、A = B の場合は -1 を返して「無限個の解が存在する」ことを、A < B の場合は 0 を返して「解なし」を呼び出し元に伝える設計になっています。

このプログラムを実行すると、次の出力が得られます。

 X can take 6 values

このように、モジュラ方程式の解の個数問題は「差の約数を数える」というシンプルな約数計算の問題へと帰着できるのがポイントです。