倍数と約数
任意の整数a,b(b≠0)が整数qによってa=bqとなるとき
aはbの倍数、bはaの約数とよび、b|aと書くことにしましょう。
整除関係
倍数であるかどうかという関係を整除関係とよぶことにしましょう。
同伴
整数a,bについてa|bかつb|aとはどういう状態かといえば、
b=±aということです。
aとbは同伴である、という言い方をして、a≃bと書くことにしましょう。
もちろん、a≃bと、a=±bは同じ意味です。
素数と合成数
正の約数が1と自分自身しかない2以上の整数を素数とよぶことにして、
素数以外の2以上の整数を合成数とよびましょう。
公約数
0でない整数dが、整数a,bについて
d|aかつd|bとなっていれば、dをa,bの公約数とよびましょう。
整数aの正の約数の集合をD(a)と表記しましょう。
整数a,bの公約数の集合D(a)∩D(b)={dabn}を考えたとき、最大のものを
最大公約数とよびましょう。
また、a,bの最大公約数を、gcd（a,b）と表記することにしましょう。
互いに素
gcd（a,b）=1のとき、aとbは互いに素である、と表現しましょう。
素と素数とは意味が違います。
例えば、4と9は互いに素ですが、4も9も素数ではありません。
ユークリッドの互除法
ユークリッドの互除法とは、
整数a,bの最大公約数dを求める以下の手順です。
手順1：b=0ならd=|a|として、最大公約数dは求まりました。
手順2：aをbで割った余りをrとする。（なお、除法の原理から、a=bq+rかつ、0≦r<|b|です。）
手順3：aの値にbを代入する。bの値にはrを代入する。手順1に戻る。
やってみましょう。a=9、b=12として、dは3ですが、本当にそうなるのか実証します。
手順1：b=0ではありません。
手順2：9を12で割った余りは、もちろん9です。
手順3：aに12を代入、bに9を代入。
手順1：b=0ではありません。
手順2：12を9で割った余りは、商が1、余り3です。
手順3：aに9を代入、bに3を代入。
手順1：b=0ではありません。
手順2：9を3で割った余りは、商が3、余り0です。
手順3：aに3を代入、bに0を代入。
手順1：b=0です。d=|a|=3となって終了。見事にあっています。
