合同式（mod）
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
整数問題で『割った余り』を持ち出す理由は、無限個の整数を有限個のグループに潰せるからにほかならない。mod m で考えるとは、整数全体を m 個の箱に分けて、箱の名前だけで計算することを指す。積と和が箱のまま計算できる（合同式が積・和で保たれる）ことが唯一にして最大の武器で、逆に割り算だけは自由にできない、という一点さえ押さえれば道具として完成する。
こんなときに使う
- 『〜で割った余り』『〜の倍数であることを示せ』→ 即 mod
- 末尾の数字 → mod 10（下2桁なら mod 100）
- 平方数が絡む → mod 3, mod 4, mod 8 を試す（平方数は mod 3 で 0,1 / mod 4 で 0,1 / mod 8 で 0,1,4 しか取らない）
- 3乗が絡む → mod 9（立方数は mod 9 で 0, 1, 8 のみ）
- n^k の余りの周期を聞かれている → 小さいkで実際に計算し周期を見つける
- 解が存在しないことを示せ → mod で矛盾を出す（存在しないことの証明はほぼこれか無限降下）
手順
- 1. 何で割るか（mod をいくつに取るか）を決める。これが8割
- 2. 決め方：問題に出てくる数の素因数、平方数なら 3・4・8、周期性なら実験して決める
- 3. 各文字を mod m での余りで場合分けする（m個の場合、対称性で減ることもある）
- 4. 合同式のまま計算し、両辺の取りうる値を比較して矛盾を出す／条件を絞る
- 5. 割り算をした箇所がないか点検する（gcd(a,m)=1 のときしか a で割れない）
例題
x, y, z を自然数とするとき、x² + y² = 3z² を満たすものは存在しないことを示せ。
解答
- 平方数を3で割った余りを調べる。整数 n は n ≡ 0, 1, 2 (mod 3) のいずれかで、
- n ≡ 0 なら n² ≡ 0、n ≡ ±1 なら n² ≡ 1 (mod 3)。よって平方数は mod 3 で 0 か 1 のみ。
- x² + y² ≡ 0 (mod 3) が必要（右辺が3の倍数だから）。
- 0 と 1 の2つの和で 0 (mod 3) になるのは 0 + 0 のときだけ。
- よって x ≡ 0 かつ y ≡ 0 (mod 3)、すなわち x = 3a, y = 3b と書ける。
- 代入して 9a² + 9b² = 3z² より 3(a² + b²) = z²。よって z² は3の倍数、3は素数だから z も3の倍数で z = 3c。
- 3(a² + b²) = 9c² より a² + b² = 3c²。
- これは元と同じ形で、a < x, b < y, c < z。同じ操作を繰り返せば自然数が無限に減り続けることになり矛盾（無限降下法）。
- ∴ 自然数解は存在しない。
別解・ほかの見方
- mod を使わず因数分解で積の形に持ち込む（(x+y)(x-y)=n 型）。有限個に閉じ込めたいときはこちら
- 不等式で範囲を絞る（大小関係を仮定して有限化）。3つの手段のうちどれが効くかは、問題の形で決まる
- 『存在しない』の証明は mod での矛盾か無限降下。『存在する』の証明は構成するだけでよい
- フェルマーの小定理は高校範囲外だが、周期性の実験で同じ結論に辿り着ける
落とし穴
- 合同式で両辺を割ってしまう（法と互いに素でなければ不可）
- mod をいくつに取るかを試行錯誤せず、最初の1つで諦める
- 『x²が3の倍数 ⇒ xが3の倍数』に3が素数であることの言及がない（東大はここを見る）
- 具体例で確認して満足し、一般の証明を書かない
- 無限降下で『最小の解を取る』と宣言せずに議論を進める
- mod を何で取るかを問題から読み取れない（末尾→mod 10、平方数→mod 3,4,8）
なぜ大事か
整数論証の共通言語。周期性・剰余での分類は東大整数の主戦場
東大での出方
東大の整数は合同式・因数分解・評価の3手段のどれを選ぶかを問う形で出る。単独の大問になる年が多く、誘導が薄いのが特徴。(1)で小さい場合を実験させ、(2)で一般の証明という構成が多い。
確認問題
- 2ⁿ を 7 で割った余りを n について調べ、周期を求めよ
- n が 3 の倍数でないとき n² - 1 が 3 の倍数であることを示せ
- x² + y² = z² で x, y の少なくとも一方は 3 の倍数であることを示せ
発展
mod の複数取り（mod 4 と mod 9 を同時に見て絞る）。中国剰余定理の考え方は範囲外だが、2つの条件を並べて絞るだけなら高校範囲で書ける。
前提になるノード
このノードを前提にするノード
「整数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。