# Solve Modular Arithmetic

> 合同算術の問題を系統的に解く。線形合同式、中国剰余定理（CRT）、フェルマーの 小定理、オイラーの定理、べき乗剰余、および離散対数問題を含む。暗号学（RSA、 ディフィー・ヘルマン）への応用も扱う。

- Skill: `pjt222/solve-modular-arithmetic-3` (Agent Skill)
- Install (CLI): `npx get-skill add pjt222/solve-modular-arithmetic-3`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pjt222/solve-modular-arithmetic-3/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- License: MIT
- Author: pjt222 (https://skillmd.com/u/pjt222)
- Updated: 2026-09-21
- Page: https://skillmd.com/skills/pjt222/solve-modular-arithmetic-3

---


# 合同算術の解法

合同算術の問題を系統的に解く。合同式の基本操作、線形合同式の解法、中国剰余定理の適用、オイラーの定理とフェルマーの小定理の活用、べき乗剰余の高速計算、および暗号学的応用を含む。

## 使用タイミング

- 線形合同式 ax ≡ b (mod m) を解く場合
- 中国剰余定理を適用して連立合同式を解く場合
- フェルマーの小定理やオイラーの定理を使用してべき乗剰余を計算する場合
- モジュラ逆元を計算する場合
- RSAの暗号化・復号化の計算を行う場合
- ハッシュ関数や擬似乱数生成器の合同算術的基盤を理解する場合

## 入力

- **必須**: 合同式または連立合同式
- **必須**: 法（modulus）
- **任意**: 使用する定理の指定
- **任意**: 計算の精度要件

## 手順

### ステップ1: 問題の分類と前処理

合同算術の問題を分類し、適切な手法を選択する：

1. **線形合同式**: ax ≡ b (mod m) — 拡張ユークリッド互除法で解く
2. **連立合同式**: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ... — 中国剰余定理
3. **べき乗剰余**: a^n mod m — 繰り返し二乗法
4. **離散対数**: a^x ≡ b (mod p) — ベビーステップ・ジャイアントステップ法
5. **モジュラ逆元**: a^(-1) mod m — 拡張ユークリッド互除法

**期待結果：** 問題タイプが特定され、適切な解法が選択される。

**失敗時：** 問題が標準形に当てはまらない場合は、変数変換や合同式の変形で既知の形に帰着させる。

### ステップ2: 基本定理の適用

適切な定理を適用して問題を解く：

1. **フェルマーの小定理**: pが素数でgcd(a, p) = 1ならば a^(p-1) ≡ 1 (mod p)
2. **オイラーの定理**: gcd(a, m) = 1ならば a^φ(m) ≡ 1 (mod m)
3. **中国剰余定理**: m₁, m₂, ..., mₖが互いに素ならば、連立合同式は法M = m₁m₂...mₖに対して一意解を持つ
4. **ウィルソンの定理**: pが素数であることの必要十分条件は (p-1)! ≡ -1 (mod p)
5. **二次剰余の相互法則**: ルジャンドル記号の計算に使用

**期待結果：** 定理が正しく適用され、合同式が解かれる。

**失敗時：** 定理の適用条件（互いに素、素数法など）が満たされていない場合は、条件を確認してから適用する。

### ステップ3: 計算の実行

具体的な計算を実行する：

1. **拡張ユークリッド互除法**: gcd(a, m) = ax + myを満たすx, yを求める。xがモジュラ逆元。
2. **繰り返し二乗法**: a^n mod mを O(log n) の乗算で計算する。nを二進展開し、各ビットに対して二乗と必要に応じた乗算を行う。
3. **CRTの計算**: M = m₁m₂...mₖ、Mᵢ = M/mᵢ、yᵢ = Mᵢ^(-1) mod mᵢを計算し、x = Σ aᵢMᵢyᵢ (mod M)。
4. **中間結果の確認**: 各ステップの中間結果を記録し、計算ミスを早期に発見する。

**期待結果：** 計算が正確に完了し、解が求められる。

**失敗時：** 数が大きすぎて手計算が困難な場合は、コンピュータ代数システムを使用する。計算過程を文書化すること。

### ステップ4: 解の検証と解釈

得られた解を検証する：

1. **代入検証**: 解を元の合同式に代入して等式が成立することを確認する。
2. **解の範囲**: 解は法mを法として一意（0 ≤ x < m）。一般解はx + km（kは整数）。
3. **解の存在条件**: ax ≡ b (mod m)が解を持つのはgcd(a, m) | bの場合のみ。解が存在する場合、gcd(a, m)個の解がある。
4. **暗号学的文脈**: RSAではe×d ≡ 1 (mod φ(n))を解いて秘密鍵dを求める。

**期待結果：** すべての解が検証され、解の完全性（すべての解が求められている）が確認される。

**失敗時：** 解が存在しない場合は、その理由（gcd(a, m)がbを割り切らない）を明示する。

## バリデーション

- [ ] 定理の適用条件（互いに素、素数法など）が確認されている
- [ ] 拡張ユークリッド互除法の計算が正しい
- [ ] CRTの法が互いに素であることが確認されている
- [ ] 解が元の合同式に代入して検証されている
- [ ] 解の個数が正しい（gcd(a, m)個）
- [ ] 解の範囲が正しく記述されている

## よくある落とし穴

- **gcdの確認忘れ**: ax ≡ b (mod m)を解く前にgcd(a, m)がbを割り切るか確認すること。割り切らなければ解は存在しない。
- **CRTの適用条件**: 法が互いに素でない場合、標準的なCRTは適用できない。一般化されたCRTを使用する。
- **べき乗剰余での桁溢れ**: 中間結果が非常に大きくなる。各乗算後に剰余を取ることで管理可能なサイズに保つ。
- **負の剰余**: 多くのプログラミング言語では負の数の剰余が負になる。正の剰余に変換する（m + (a mod m)) mod m）。
- **オイラーの定理の適用条件**: a と m が互いに素でなければ a^φ(m) ≡ 1 (mod m) は成立しない。

## 関連スキル

- `analyze-prime-numbers` -- 合同算術の基盤となる素数の分析
- `explore-diophantine-equations` -- 合同式と密接に関連する整数方程式

