整数の問題－合同式の利用－

整数の問題の項目の学習

新課程から、整数の問題が数学に導入されました。整数論でよく使われる合同式も学びます。整数の問題を合同式を使うと簡単に問題が解けることが良くあります。

合同式とは何か

合同式は、ある整数　ａ、ｂの差が正整数ｃで割り切れるときに、ａ≡ｂ(modｃ）と書きます。つまり、ａ－ｂ＝ｋｃ（ｋは整数）のときに、ａとｂはｃを法として合同といいます。合同式は、これまた、あのガウスが発明したもので、これを使うと整数の問題が楽に解けるときが良くあります。

合同式を使う例

例えば、ａ，ｂ，ｃがピタゴラス数である時、つまり　\(ａ^2＋ｂ^2\)＝\(ｃ^2\)が成り立つ時に、ａ，ｂ，ｃの少なくとも1つは３の倍数である事を証明する問題の場合、通常はａ，ｂ，ｃを３で割った余りで分類し、どうなるかを調べていくのが通常です。つまり、ａ＝３ｎ、３ｎ＋１、３ｎ＋２などと分けて計算し、与えられた式がどうなるかを調べていきます。

これを合同式を考え、３を法として合同式を使うと、ａ≡０，１，２となります。それぞれの場合、\(ａ^2\)≡０，１、４≡1（mod3）となります。これは、ｂについても同様で、\(ｂ^2\)≡０，１(mod3)となります。

従って、ａ，ｂ，ｃが３の倍数で無いとすれば、\(ａ^2+ｂ^2\)≡２（mod3)　となります。一方\(ｃ^2\)≡１ですからこれは、不合理です。従って、ａ，ｂ，ｃのうち少なくとも１つは３の倍数です。合同式は使いこなせば、とても便利です。

大きな数字をある自然数で割った余り

これも合同式を使うと割合容易に求まります。\(２９^{100}\) を７で割った余りはいくらでしょうか。まず、２９≡１(mod７)となります。従って、

\(２９^{100}≡1（mod７）\)となります。答えは、余り１となります。これは、簡単な例ですが、もう少し複雑な問題も同様な考え方で、余りを求めることが出来ます。

１次整数方程式の問題１

整数解の問題は、数字が大きくなると、相当難しくなります。例えば

ｘ，ｙを整数として、４ｘ－5ｙ＝２　を解きなさい、と言う問題は楽に解けます。１つの解が、（ｘ、ｙ）＝（３，２）ですから、４･３－５･２＝２となります。この２式の引き算をすれば、４（ｘ－３）－５（ｙ-２）＝０となります。従って、４（ｘ－3）＝５（ｙ－２）です。ここで、4と５は互いに素ですから、ｘ－３＝５ｋ、ｙ－２＝４ｋ（ｋは整数）となります。よって、ｘ＝３+５ｋ、ｙ＝２＋4ｋ（ｋは整数）が答えです。

１次整数方程式の問題２

これが、次のような問題であればどうでしょうか。この問題でも、１つの解を求めればいいのですが、それが難しいのです。

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

どうやって１つの解を求めるのかが問題になります。

整数の個数の問題

１２個の約数を持つ自然数のうち、最小のものを求めてください。ただし自然数ｎの約数には、１とｎを含むものとします。（私立医学部入試問題）