整数の問題の基本

整数の問題

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

整数の基本

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

２数の最大公約数を求める手順です。
例えば、　$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$　は整数)　となります。