合同式ごうどうしきcongruenceで余あまりremainderを処理しょりする定石じょうせき

11. 使つかう場面ばめん

• 巨大きょだいな整数せいすうinteger・冪べきpowerの余あまりや末尾まつびを求もとめる
• $n\mid A$n\mid A を示しめす、または整数解せいすうかいinteger solutionが存在そんざいしないことを余あまりで示しめす
• 曜日ようびなど周期しゅうきperiodだけが重要じゅうような量りょうを扱あつかう
• 一次合同式いちじごうどうしきlinear congruence $ax\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ax\equiv b\pmod n を解とく

22. 見分みわけ方かた

求もとめるものが「$n$n で割わった余あまり」または「$n$n の倍数ばいすうか」なら、値あたい全体ぜんたいを計算けいさんせず、早はやい段階だんかいで法ほうmodulus $n$n による合同式ごうどうしきへ移うつす。末尾まつび一桁ひとけたなら法ほう $10$10、偶奇ぐうきparityなら法ほう $2$2、各桁かくけたの和わによる整除せいじょdivisibilityなら法ほう $3$3 または $9$9 を候補こうほにする。

33. 使つかう公式こうしき

加法かほう・減法げんぽう・乗法じょうほうと非負整数ひふせいすう乗じょうは合同ごうどうを保存ほぞんする。除法じょほうは一般いっぱんには合同ごうどうを保存ほぞんしない。$ca\equiv cb\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ca\equiv cb\pmod n から $a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a\equiv b\pmod n を得えるには、$gcd(c,n)=1$gcd(c,n)=1、つまり $c$c と $n$n が互たがいに素そcoprimeであることが十分条件じゅうぶんじょうけんである。

44. 解とき方かたの手順てじゅん

1. 問といから法ほう $n$n を決定けっていする。
2. 各数かくすうを計算けいさんしやすい代表元だいひょうげんrepresentativeへ置換ちかんする。$n-1\equiv -1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$n-1\equiv-1\pmod n も利用りようする。
3. 冪べきなら余あまりの反復はんぷくを列挙れっきょし、周期しゅうきの開始位置かいしいちを特定とくていする。底ていと法ほうが互たがいに素そなら、初項しょこうからの周期しゅうきを用もちいて指数しすうを縮約しゅくやくできる。互たがいに素そでなければ、前周期ぜんしゅうきpreperiodを周期部分しゅうきぶぶんから分離ぶんりする。
4. 一次合同式いちじごうどうしきなら $d=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)$d=\gcd(a,n) を計算けいさんし、$d\mid b$d\mid b を確認かくにんする。成立せいりつしなければ解かいはない。
5. $d\mid b$d\mid b なら $a^{\prime }=a/d$a'=a/d、$b^{\prime }=b/d$b'=b/d、$n^{\prime }=n/d$n'=n/d とし、$a^{\prime }$a' の法ほう $n^{\prime }$n' における逆元ぎゃくげんmultiplicative inverseを用もちいて $x\equiv (a^{\prime }{)}^{-1}{b}^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}{n}^{\prime }$x\equiv (a')^{-1}b'\pmod {n'} を得える。法ほう $n$n では $d$d 個この解かい $x_0+k{n}^{\prime }$x_0+kn'（$0\text{[PARSE ERROR: Undefined("Command("le")")]}k<d$0\le k<d）になる。
6. 最小非負剰余さいしょうひふじょうよleast nonnegative residueで答こたえ、元もとの式しきへ代入だいにゅうして検算けんざんする。

55. 判別はんべつと注意点ちゅういてん

複数ふくすうの法ほうの条件じょうけんを同時どうじに満みたす整数せいすうを求もとめる場合ばあいは、中国剰余定理ちゅうごくじょうよていりChinese remainder theoremへ進すすむ。法ほうが互たがいに素そでない場合ばあいは、法ほうどうしの最大公約数さいだいこうやくすうを法ほうとして余あまりが一致いっちするか、先さきに確認かくにんする。冪べきの周期しゅうきにフェルマーの小定理しょうていりFermat's little theoremを使つかうときは、底ていと法ほうが互たがいに素そであることを確認かくにんする。

66. 落おとし穴あな

• 合同記号ごうどうきごうを等号とうごうと同おなじものとして扱あつかう
• 法ほうを書かかず、途中とちゅうで異ことなる法ほうを混在こんざいさせる
• 係数けいすうと法ほうが互たがいに素そか確認かくにんせず、両辺りょうへんを割わる
• 負ふの代表元だいひょうげんを最小非負剰余さいしょうひふじょうよへ戻もどさず答こたえる

77. 関連かんれんリンク

88. 演習えんしゅうリンク