ユークリッドの互除法ごじょほうEuclidean algorithmと一次不定方程式いちじふていほうていしきlinear Diophantine equation-基本演習きほんえんしゅう

3.1解答例かいとうれい

最後さいごの非零ひれい余あまりは $18$18 なので、$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(252,198)=18$\gcd(252,198)=18 である。

3.2診断しんだん

商しょうではなく、最後さいごの非零ひれい余あまりを読よむ。

4.1解答例かいとうれい

かつ $54=252-198$54=252-198 だから、

したがって $(x,y)=(4,-5)$(x,y)=(4,-5) が一組ひとくみの係数けいすうである。

4.2診断しんだん

逆代入後ぎゃくだいにゅうのちに元もとの式しきへ代入だいにゅうし、符号ふごうを検算けんざんする。

5.1解答例かいとうれい

を逆代入ぎゃくだいにゅうすると

よって $-5·17\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}43$-5\cdot17\equiv1\pmod{43} であり、逆元ぎゃくげんは $-5\equiv 38\text{[PARSE ERROR: Undefined("Command("pmod")")]}43$-5\equiv38\pmod{43} である。

5.2診断しんだん

逆元ぎゃくげんを探索たんさくする前まえに $\text{[PARSE ERROR: Undefined("Command("gcd")")]}(17,43)=1$\gcd(17,43)=1 を確認かくにんする。

6.1解答例かいとうれい

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(84,30)=6$\gcd(84,30)=6 だが $6\nmid 7$6\nmid7 である。したがって整数解せいすうかいは存在そんざいしない。

6.2診断しんだん

探索たんさくを始はじめる前まえに $\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)\mid c$\gcd(a,b)\mid c を確認かくにんする。

7.1解答例かいとうれい

互除法ごじょほうの逆代入ぎゃくだいにゅうから $6=-84+3·30$6=-84+3\cdot30 なので、$18=-3·84+9·30$18=-3\cdot84+9\cdot30 である。一ひとつの解かいは $(x_0,y_0)=(-3,9)$(x_0,y_0)=(-3,9) である。$d=6$d=6 より一般解いっぱんかいは

7.2診断しんだん

係数けいすう $b/d$b/d と $-a/d$-a/d が元もとの左辺さへんを変かえないことを代入だいにゅうして確認かくにんする。