整数の問題の基本

整数の問題

整数の問題は、きっかけを思いつけば解けるのに、きっかけを掴めないと解けないような問題もあります。専門的な数学の分野には、解析学、代数学、幾何学、などがありますが、整数を扱う整数論は難解な理論が多くあります。
整数論は、代数的整数論、解析的整数論などがあります。ここでは、入試で重要な整数に関する基本的な定理などをみてみましょう。

整数の基本

（１）ユークリッドの互除法

２数の最大公約数を求める手順です。
例えば、　\(851、1219\)　の最大公約数を求めてみましょう。簡単には素因数がみつからないと思います。こういう時に役に立つのが互除法です。
1219÷851＝1････368、　851÷368＝2････115、368÷115＝3･･････23、115÷23＝5　　従って、最大公約数は　23　という手順です。
不定方程式の整数解を求める場合に、特殊解を求めるのが難しいときによく使います。

（２）整数解の基本定理

整数　\(a,b\)　の最大公約数を　\(g\)　とするとき
\(ax+by=g\)
を満たす整数　\(x,y\)　が存在する。

（１）の互除法を実行すると、自然に証明できます。
\(a>b\)　とします。互除法で　\(a\)　を\(b\)　で割った商と余りを求めます。
さらに互除法の手順で、商を余りで割っていくと、有限回で余りは、\(0\)　になります。

\(a\)　を　\(b\)　で割った商を　\(q_1\)　余りを　\(r_1\)
\(b\)　を　\(q_1\)　で割った商を　\(q_2\)　余りを　\(r_2\)

とします。ここで。\(r_{n-1}＝0\)　になるとすると
\(a=bq_1+r_1\)
\(ｂ＝q_1q_2+r_2\)
などが成り立ちます。

（3）整数解の基本定理の系

\(a,b\)　を互いに素な整数とします。

このとき、\(ax+by=1\)

を満たす整数　\(x,y\)　の組が存在します。

例えば、\(5x+7y＝1\)　を満たす整数　\(x,y\)　が存在します。

合同式を使ってもいいですし、\((x,y)＝(3,-2)\)　ですから、
\(5・3+7(-2)=1\)　から、
\(5(x-3)+7(y+2)=0\)
よって、\(x=－7k+3、y=5k-2\)　(\(k\)　は整数)　となります。