ホーム >> 整数 >> 約数,倍数,最大公約数,最小公倍数

約数,倍数,最大公約数,最小公倍数などの整数論の基本的な用語について解説します.



⇨予備知識


約数,倍数,最大公約数,最小公倍数の定義

$a,b$ を整数とします.ある整数 $q$ を用いて $$a=qb$$ とかけるとき,$a$ は $b$ で割り切れる (あるいは $b$ は $a$ を割り切る) といい,$a$ を $b$ の倍数,$b$ を $a$ の約数といいます. また,$a=qb$ のとき,$b,q$ をそれぞれ $a$ の因数といいます.


・$16$ は $8$ で割り切れる ($16=2\times 8$). したがって,$8$ は $16$ の約数,$16$ は $8$ の倍数.
・$-12$ は $3$ で割り切れる ($-12=(-4)\times 3$). したがって,$3$ は $-12$ の約数,$-12$ は $3$ の倍数.
・$-36$ は $-9$ で割り切れる ($-36=4\times (-9)$). したがって,$-9$ は $-36$ の約数,$-36$ は $-9$ の倍数.
・$6$ のすべての約数は $-6,-3,-2,-1,1,2,3,6$ です. $6$ のすべての倍数は $...,-24, -12,-6,6,12,18,24,...$ とつづきます (無限にあります).

$a,b,n,m$ を整数とします. $n$ が $a$ でも $b$ でも割り切れるとき,$n$ を $a$ と $b$ の公約数といいます. 公約数のうち,最大の整数を最大公約数といいます. $a$ と $b$ がともに $m$ で割り切れるとき,$m$ を $a$ と $b$ の公倍数といいます. 正の公倍数のうち,最小の整数を最小公倍数といいます.

最大公約数が $1$ となるような $2$ つの整数を互いに素といいます.


・$4,6$ の公約数は $-2,-1,1,2$
・$4,6$ の最大公約数は $2$
・$4,6$ の公倍数は $...,-48,-36,-24,-12,12,24,36,48,...$ とつづきます (無限にあります).
・$4,6$ の最小公倍数は $12$

・$12,-18$ の公約数は $-6,-3,-2,-1,1,2,3,6$
・$12,-18$ の最大公約数は $6$
・$12,-18$ の公倍数は $...,-72,-36,36,72,...$ とつづきます (無限にあります).
・$12,-18$ の最小公倍数は $36$

・$3,5$ の公約数は $-1,1$,最大公約数は $1$.したがって,$3$ と $5$ は互いに素.

注意

・約数や公約数といったときに正の数のみを対象とする流儀もあります.
・公約数や公倍数は一般には複数ありえますが,最大公約数や最小公倍数はただひとつに決まります.
・最大公約数,最小公倍数は必ず正の数です.

倍数関係の基本性質

倍数関係 ($a$ が $b$ で割り切れる,あるいは $b$ が $a$ を割り切るという関係) の基本的な性質を $2$ つ紹介します.いずれも,あらためて言われるまでもなく当たり前のことかもしれませんが,証明も含めてきちんと確認しておきましょう.

倍数関係と線形結合: $a_1,a_2,b,c_1,c_2$ を整数とする.$a_1,a_2$ が $b$ で割り切れるとき, $c_1a_1+c_2a_2$ も $b$ で割り切れる.

証明: 仮定より,ある整数 $q_1,q_2$ を用いて, $$a_1=bq_1,\ a_2=bq_2$$ とかける.したがって, $$c_1a_1+c_2a_2=c_1(bq_1)+c_2(bq_2)=b(c_1q_1+c_2q_2)$$ となり,$c_1q_1+c_2q_2$ は整数なので,$c_1a_1+c_2a_2$ は $b$ で割り切れる.

上の命題は 『$a_1,a_2,...,a_n$ が $b$ で割り切れるとき,$c_1a_1+c_2a_2+\cdots +c_na_n$ も $b$ で割り切れる』という主張に一般化することができます.

倍数関係と推移律: $a,b,c$ を整数とする.$a$ が $b$ で割り切れ,$b$ が $c$ で割り切れるとき,$a$ は $c$ で割り切れる.

証明: 仮定より,ある整数 $q_1,q_2$ を用いて, $$a=bq_1,\ b=cq_2$$ とかける.したがって, $$a=bq_1=(cq_2)q_1=c(q_1q_2)$$ となり,$q_1q_2$ は整数なので,$a$ は $c$ で割り切れる.

最大公約数,最小公倍数の基本性質

最大公約数と最小公倍数に関するいくつかの基本的な性質について紹介します.
下の命題は,『公倍数は最小公倍数で割り切れる』ということを述べています.

最小公倍数と公倍数: $a,b$ を整数とする.$m$ を $a,b$ の任意の公倍数,$l$ を $a,b$ の最小公倍数とする.このとき,$m$ は $l$ で割り切れる.

証明: $l>0$ であるから,除法の原理より, $$m=lq+r\ \ (0\le r < l)$$ を満たす整数 $q,r$ が存在する. したがって,$r=m-lq$ とかける.ここで仮定より,$m,l$ は $a,b$ で割り切れるので,前節の命題 (倍数関係と線形結合) を用いると,$r$ も $a,b$ で割り切れる.つまり,$r$ も $a,b$ の公倍数となる.ここで,$0< r < l$ とすると,$l$ の最小性に矛盾する.よって,$r=0$ であり,$m=lq$ となるので,$m$ は $l$ で割り切れる.

下の命題は,『最大公約数は公約数で割り切れる』ということを述べています.

最大公約数と公約数: $a,b$ を整数とする.$d$ を $a,b$ の任意の公約数,$g$ を $a,b$ の最大公約数とする.このとき,$g$ は $d$ で割り切れる.

証明: $d$ と $g$ の最小公倍数を $l$ とおく.仮定より,$a$ は $d,g$ の公倍数である.したがって,上の命題 (最小公倍数と公倍数) より,$a$ は $l$ で割り切れる.同様にして,$b$ も $l$ で割り切れる.したがって,$l$ は $a,b$ の公約数なので, $l\le g$ となる.
一方,$l$ は $d$ と $g$ の最小公倍数なので,特に $g\le l$ となる.
よって,$l=g$ となる.したがって,$d$ と $g$ の最小公倍数は $g$ である.特に $g$ は $d$ の倍数なので,$g$ は $d$ で割り切れる.

下の命題は,『$2$ つの正の整数の積は,その最大公約数と最小公倍数の積に等しい』ということを述べています.

最大公約数と最小公倍数の積: $a,b$ を正の整数とする.$g$ を $a,b$ の最大公約数,$l$ を $a,b$ の最小公倍数とする.このとき, $$\large ab=gl$$ が成り立つ.

証明: $g$ は $a,b$ の最大公約数なので,互いの素な整数 $a',b'$ を用いて $$a=ga',\ b=gb'$$ とかける.ここで,$m=ga'b'$ とおくと,$m=ab'=a'b$ であるから,$m$ は $a$ と $b$ の公倍数なので,$m$ は $l$ で割り切れる.したがって,ある整数 $n$ を用いて, $$m=ln$$ とかける.このとき,$ln=ab'=a'b$ である.一方,$l$ は $a$ と $b$ の最小公倍数なので,ある整数 $a'',b''$ を用いて $$l=aa''=bb''$$ とかける.したがって, $$aa''n=ab',\ bb''n=a'b$$ すなわち $$a''n=b',\ b''n=a'$$ を得る.つまり,$n$ は $a'$ と $b'$ の公約数である.ところが,$a'$ と $b'$ は互いに素だったので,$n=1$ でなければならない.よって,$m=l$ が成り立つので, $$ab=gga'b'=gl$$ となる.