整数解の問題の解答－整数方程式の解き方－

 

整数解の問題

整数の問題-合同式の利用で整数解の問題を提起いたしました。この問題は、直感では解けません。ユークリッドの互除法を使わないと、１つの整数解を求めることは、極めて難しいと思います。

問題

　１１７２６･ｘ－５８８３5･ｙ＝１２３･･･････（1)　の整数解をもとめてください。

（１）の１つの整数解さえ求まれば、（１）を解くのは容易です。１つの整数解を求めるのが難しいのです。では、どうすればいいのか。ユークリッドの互除法を用いれば、複雑な整数解の問題も解く事が出来ます。

問題の解答－ユークリッドの互除法の利用

まず(1)の１つの整数解を求めます｡直感では無理ですから、ユークリッドの互除法を使います。

係数１１７２６、５８８３５を互除法により次の式が得られます。

５８８３５＝１１７２６ｘ５＋２０５･････････(2)

１１７２６＝２０５ｘ５７＋４１　････････(3)

２０５＝４１ｘ５････････････(4)

（これから、５８８３５と１１７２６の最大公約数は４１です。）

(2)から、２０５＝５８８３５－１１７２６ｘ５となりますから、これを(3)に代入すると次式を得ます。

１１７２６＝（５８８３５－１１７２６ｘ５）ｘ５７＋４１

これを整理すると、１１７２６ｘ２８６－５８８３５ｘ５７＝４１･･･(5)

(5)式の両辺を３倍すると、

１１７２６ｘ８５８－５８８３５ｘ１７１＝１２３　となりますから、

(1)式の1つの整数解は（ｘ、ｙ）＝（８５８､１７１）であることが分かります。１つの解が解れば、後は簡単で､(1)式は

１１７２６（ｘ－８５８）－５８８３５（ｙ－１７１）＝０となりますから、１１７２６（ｘ－８５８）＝５８８３５（ｙ－１７１）････(6)です。

ここで、１１７２６と５８８３５の最大公約数は、４１ですから、(6)は

２８６（ｘ－８５８）＝１４３５（ｙ－１７１）となり、２８６と１４３５は互いに素ですから、

ｘ－８５８＝１４３５ｋ、ｙ－１７１＝２８６ｋ（ｋは整数）となります。

従って、(1)の整数解は

ｘ＝８５８＋１４３５ｋ

ｙ＝１７１+２８６ｋ　　　（ｋは整数）となります。

問題の背景

整数解、合同式については、下記の記事を参照してください。