一次合同・CRTで解の類を統合する

概要

一次合同・CRT

一次合同のgcd可解性を判定し、互いに素でない法も含めて複数の剰余類を一つへ統合する。

考え方

合同式で条件を整理するときは、解の整数を一つだけ求めるのではなく、どの間隔で解が現れるかまで持つ。例えば x≡4(mod5)x\equiv 4\pmod 5 は、整数 tt を使って x=4+5tx=4+5t と書ける整数全体を表す。このように同じ余りを持つ整数の集合を剰余類と呼ぶ。

まず一次合同を一つの剰余類へ直す。その後、複数の条件を二つずつ統合するのが中国剰余定理(CRT)の使い方である。法が互いに素でなくても、条件が両立すれば一つの剰余類にまとめられる。

一次合同を解いてから二類を統合する

例えば 6x≡4(mod10)6x\equiv 4\pmod {10} を解きたい。これは 6x−46x-4 が 1010 の倍数という条件なので、両辺だけでなく法も 22 で割り、3x≡2(mod5)3x\equiv 2\pmod 5 と同値に変形できる。法 55 では 3⋅2≡13\cdot 2\equiv 1 より 33 の逆元は 22 だから、次を得る。

6x≡4(mod10)  ⟺  3x≡2(mod5)  ⟺  x≡4(mod5)\begin{aligned} &6x\equiv 4\pmod {10}\\ &\iff 3x\equiv 2\pmod 5\\ &\iff x\equiv 4\pmod 5 \end{aligned}

元の法 1010 で 00 以上 1010 未満の代表を並べると、解は 4,94,9 の二つである。実際、6⋅4=246\cdot 4=24 も 6⋅9=546\cdot 9=54 も 1010 で割った余りが 44 になる。この二つを別々に管理する代わりに、…,−1,4,9,14,…\ldots,-1,4,9,14,\ldots をまとめて x≡4(mod5)x\equiv 4\pmod 5 と持てばよい。法を縮めることで、元の法で複数あった解の代表を一つの類で表せる。

一般に、整数 a,ba,b と正の法 mm に対して ax≡b(modm)ax\equiv b\pmod m を考える。g=gcd⁡(a,m)g=\gcd(a,m) とすると、axax も mm の倍数も gg の倍数なので、bb が gg の倍数でなければ解はない。例えば 6x≡3(mod10)6x\equiv 3\pmod {10} は偶数と奇数が一致しないため解なしとなる。

gg が bb を割るときは、a′=a/g, b′=b/g, m′=m/ga'=a/g,\ b'=b/g,\ m'=m/g と置く。mm が ax−bax-b を割る条件は、m′m' が a′x−b′a'x-b' を割る条件と同値である。さらに gcd⁡(a′,m′)=1\gcd(a',m')=1 なので、m′>1m'>1 なら逆元を使える。

ax≡b(modm)  ⟺  a′x≡b′(modm′)  ⟺  x≡b′(a′)−1(modm′)\begin{aligned} &ax\equiv b\pmod m\\ &\iff a'x\equiv b'\pmod {m'}\\ &\iff x\equiv b'(a')^{-1}\pmod {m'} \end{aligned}

この解の代表を 0≤x0<m′0\leq x_0<m' に取ると、全解は x=x0+m′tx=x_0+m't(tt は任意の整数)である。元の法 m=gm′m=gm' での代表は x0,x0+m′,…,x0+(g−1)m′x_0,x_0+m',\ldots,x_0+(g-1)m' のちょうど gg 個となる。これで可解条件が十分でもあることと、解を漏らしていないことが分かる。

m′=1m'=1 の場合は、割った後の条件が法 11 の合同式となるため全整数が解である。逆元は計算せず、x≡0(mod1)x\equiv 0\pmod 1 を返す。元の法が 11 の場合や、a=0a=0 かつ mm が bb を割る場合もここに含まれる。

互いに素でない二つの条件を統合する

次に、x≡1(mod6)x\equiv 1\pmod 6 と x≡3(mod10)x\equiv 3\pmod {10} を同時に満たす整数を求めよう。一つ目を満たす整数は x=1+6kx=1+6k(kk は整数)なので、これを二つ目へ代入する。

1+6k≡3(mod10)6k≡2(mod10)3k≡1(mod5)k≡2(mod5)\begin{aligned} 1+6k&\equiv 3\pmod {10}\\ 6k&\equiv 2\pmod {10}\\ 3k&\equiv 1\pmod 5\\ k&\equiv 2\pmod 5 \end{aligned}

ここで使ったのは、先ほどの一次合同の解き方そのものである。k=2+5tk=2+5t を戻すと x=1+6(2+5t)=13+30tx=1+6(2+5t)=13+30t だから、統合結果は x≡13(mod30)x\equiv 13\pmod {30}。1313 が両条件を満たすだけでなく、3030 間隔の全解を表している。法は 6⋅10=606\cdot 10=60 ではなく、最小公倍数 lcm⁡(6,10)=30\operatorname{lcm}(6,10)=30 になる。

二つ目を x≡2(mod10)x\equiv 2\pmod {10} に替えると、代入後は 6k≡1(mod10)6k\equiv 1\pmod {10} となる。gcd⁡(6,10)=2\gcd(6,10)=2 は右辺の 11 を割らないので解はない。元の条件でも、一つ目は奇数、二つ目は偶数を要求しており両立しないと確認できる。

一般の二条件 x≡a(modm)x\equiv a\pmod m、x≡b(modn)x\equiv b\pmod n(m,n>0m,n>0)でも、x=a+mkx=a+mk と置けば mk≡b−a(modn)mk\equiv b-a\pmod n となる。したがって g=gcd⁡(m,n)g=\gcd(m,n) が差 b−ab-a を割ることが両立の必要十分条件である。これは a≡b(modg)a\equiv b\pmod g と同じで、二つの条件が共通の約数に関して矛盾しないかを調べている。

両立するとき、n′=n/g>1n'=n/g>1 なら、法 n′n' で m/gm/g の逆元を使って kk を求める。

k≡b−ag(mg)−1(modn′)k\equiv \frac{b-a}{g}\left(\frac{m}{g}\right)^{-1}\pmod {n'}

この右辺を 0≤k0<n′0\leq k_0<n' に正規化する。全解 k=k0+n′tk=k_0+n't を戻すと、x=a+mk0+mn′tx=a+mk_0+mn' t となる。そこで L=mn′=lcm⁡(m,n)L=mn'=\operatorname{lcm}(m,n) とし、a+mk0a+mk_0 を法 LL で正規化した代表を rr とすれば、統合結果は x≡r(modL)x\equiv r\pmod L である。逆にこの形の整数は両条件を満たすので、解全体がこの一類に一致する。二解の差が m,nm,n 双方の倍数、つまり LL の倍数になることからも一意性を確認できる。

n′=1n'=1 なら nn が mm を割る。両立を確認済みなら、一つ目を満たすすべての整数が二つ目も満たすので、逆元を取らず既存の類 x≡a(modm)x\equiv a\pmod m を正規化して返す。例えば x≡13(mod30)x\equiv 13\pmod {30} に x≡3(mod10)x\equiv 3\pmod {10} を加えても類は変わらない。同じ法同士の統合もこの場合に含まれ、代表が合同ならその類を返し、合同でなければ両立判定で解なしとなる。

複数条件では全整数の類から始める

初期状態を x≡0(mod1)x\equiv 0\pmod 1 とすれば、まだ条件のない全整数を表せる。条件を一つ加えるたびに、現在の類と新しい類を上の手順で統合する。「現在の類は、これまでの全条件を満たす整数全体」という意味を保てるため、途中で両立しなければ全体も解なしとなる。

ABC286 F の公式解説では、巡回の移動量から得た複数の余りを CRT で統合する。ABC423 G の公式解説では、桁列の連結から生じる一次合同を、最大公約数による可解判定と法の縮約で解く。問題へ進む際は、まず得られる条件が一次合同なのか、既に余りを指定した類なのかを見分ける。上の数値例と一般 CRT の導出は、本単元で補った説明である。

成立条件と計算量

法は正とし、逆元を取る前に必ず最大公約数による可解判定を行う。一次合同では m′=1m'=1、CRT では n′=1n'=1 を先に分岐させる。逆元を取れるのは、縮約した係数と法が互いに素で、法が 11 より大きい場合である。

負の代表も同じ類を表す。例えば x≡−1(mod5)x\equiv -1\pmod 5 は x≡4(mod5)x\equiv 4\pmod 5 と同じである。各段階の代表は、法を M>0M>0 として 00 以上 MM 未満へ正規化する。負数の % が負になり得る言語では、剰余を求めて負なら MM を加える。CRT の差 b−ab-a が負になる場合も、この正規化を省かない。

最小公倍数は L=m(n/g)L=m(n/g) として、積より先に割り算を行う。ただし、それだけでオーバーフローを防げるわけではない。LL、代表を作る a+mk0a+mk_0、k0k_0 を求める逆元との積まで収まる整数幅を確認する。最終的な代表が小さくても、途中の積や統合後の法は大きくなり得る。収まらない場合は、より広い整数型・多倍長整数・積を直接作らない剰余乗算などを、必要な箇所に使う。

扱う整数の絶対値と法を上から抑える値を U≥2U\geq 2 とする。整数の四則演算を定数時間と数える範囲では、最大公約数と逆元を拡張ユークリッドの互除法で求め、一次合同一つ、または二類の統合一回につき時間 O(log⁡U)O(\log U)。qq 個の条件の逐次統合は全体で O(qlog⁡U)O(q\log U) となる。UU には入力の法だけでなく、統合で成長する法や途中の整数も含める。反復版の互除法を使い、条件を順に読み込めば、追加空間は O(1)O(1) 個の整数で済む。多倍長整数を使う場合は、これに桁数に応じた演算時間・記憶量がかかる。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。一次合同の可解条件を確認し、非互いに素な法も含めてCRTで統合する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-modular-congruence

習得する技能

  • 合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: gcdと整数解の成立条件、法上の四則演算・高速累乗・逆元。

このUnitを直接前提とする単元: なし。

法上の演算とBézout等式を使えることを前提に、一次合同の可解性を判定して複数条件をCRTで統合する。

このUnitでは扱わないもの

  • 可解性判定を要しない通常の法上加減乗除・高速累乗、および剰余周期だけの利用。

根拠