整数の問題の基本
整数の問題
整数の問題は、きっかけを思いつけば解けるのに、きっかけを掴めないと解けないような問題もあります。専門的な数学の分野には、解析学、代数学、幾何学、などがありますが、整数を扱う整数論は難解な理論が多くあります。
整数論は、代数的整数論、解析的整数論などがあります。ここでは、入試で重要な整数に関する基本的な定理などをみてみましょう。
整数の基本
(1)ユークリッドの互除法
2数の最大公約数を求める手順です。
例えば、 \(851、1219\) の最大公約数を求めてみましょう。簡単には素因数がみつからないと思います。こういう時に役に立つのが互除法です。
1219÷851=1・・・・368、 851÷368=2・・・・115、368÷115=3・・・・・・23、115÷23=5 従って、最大公約数は 23 という手順です。
不定方程式の整数解を求める場合に、特殊解を求めるのが難しいときによく使います。
(2)整数解の基本定理
整数 \(a,b\) の最大公約数を \(g\) とするとき
\(ax+by=g\)
を満たす整数 \(x,y\) が存在する。
(1)の互除法を実行すると、自然に証明できます。
\(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\)
\(b=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\) は整数) となります。