最大公約数さいだいこうやくすうgreatest common divisorと一次不定方程式いちじふていほうていしきlinear Diophantine equationを処理しょりする定石じょうせき

11. 使つかう場面ばめん

• 大おおきな二整数にせいすうの $gcd$gcd を計算けいさんする
• $ax+by=c$ax+by=c の整数解せいすうかいの存在判定そんざいはんてい・一解いっかい・全解ぜんかいを求もとめる
• $ax\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ax\equiv b\pmod n の逆元ぎゃくげんが必要ひつようになる

22. 見分みわけ方かた

「二整数にせいすうの共通尺度きょうつうしゃくど」は互除法ごじょほう、「整数係数せいすうけいすうの一次式いちじしきで $c$c を作つくる」は拡張互除法かくちょうごじょほうを選えらぶ。$ax+by=c$ax+by=c を通常つうじょうの二元一次方程式にげんいちじほうていしきのように一意いちいに解とこうとしてはいけない。まず $gcd(a,b)\mid c$gcd(a,b)\mid c を判定はんていする。

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

一解いっかい $(x_0,y_0)$(x_0,y_0) があるとき

適用前てきようまえに $(a,b)\ne (0,0)$(a,b)\ne(0,0) とする。一般解いっぱんかいでは $d>0$d>0 と定さだめる。

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

1. $a=0$a=0 または $b=0$b=0 なら、非零ひれいの係数けいすうの絶対値ぜったいちを $d$d とし、$d\mid c$d\mid c を判定はんていして直接ちょくせつ解とく。
2. $ab\ne 0$ab\ne0 なら $\left|a\right|,\left|b\right|$|a|,|b| を取とり、大おおきい方ほうを小ちいさい方ほうで割わって余あまりへ落おとす。
3. 余あまりが $0$0 になるまで反復はんぷくし、$0$0 になる直前ちょくぜんの除数じょすう $d$d を得える。
4. $d\nmid c$d\nmid c なら整数解せいすうかいなしと結論けつろんする。
5. 解かいが必要ひつようなら除法じょほうの列れつを逆代入ぎゃくだいにゅうし、$d=\left|a\right|u+\left|b\right|v$d=|a|u+|b|v を作つくる。$x_1=\mathrm{sgn}\left(a\right)u$x_1=\operatorname{sgn}(a)u、$y_1=\mathrm{sgn}\left(b\right)v$y_1=\operatorname{sgn}(b)v として、$d=a{x}_1+b{y}_1$d=ax_1+by_1 へ符号ふごうを戻もどす。
6. $c/d$c/d 倍ばいして一解いっかいを得えて、一般解いっぱんかいgeneral solutionへ拡張かくちょうする。
7. 一解いっかいの代入だいにゅうと、パラメータ部分ぶぶんが相殺そうさいすることを確認かくにんする。

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

$ax\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ax\equiv b\pmod n は $ax+ny=b$ax+ny=b と同おなじである。$gcd(a,n)=1$gcd(a,n)=1 なら逆元ぎゃくげんを用もちいて一ひとつの剰余類じょうよるいへ落おとせる。$gcd(a,n)>1$gcd(a,n)>1 でも、$gcd(a,n)\mid b$gcd(a,n)\mid b なら解かいは存在そんざいするため、「逆元ぎゃくげんなし」と「解かいなし」を混同こんどうしない。

66. 落おとし穴あな

• 可解条件かかいじょうけんを確認かくにんせず逆代入ぎゃくだいにゅうを始はじめる
• 一解いっかいだけを求もとめて全解ぜんかいとみなす
• 一般解いっぱんかいの二ふたつの符号ふごうを同符号どうふごうにし、代入時だいにゅうじに相殺そうさいしなくなる
• 合同式ごうどうしきで互たがいに素そでない係数けいすうをそのまま割わる

77. 関連かんれんリンク

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