数学A 第4章整数の性質 — 整数の基本性質

この節の練習問題9問だけをまとめて見る・印刷する →

整数の除法

整数の割り算の復習

まず、小学校以来慣れ親しんできた、整数の除法(integer division)について復習する。

たとえば、次の図のような計算により、17を3で割ると、商は5で余りは2とわかる。この関係を式で表すと $17=3\times5+2$

となる。

このとき、17を割られる数、3を割る数と呼ぶので、一般的には次のような関係が成り立つ。

$（割られる数）（割る数）（商）（余り）（割られる数）=（割る数）\times（商）+（余り）$

また、（割る数） $>$ （余り） $≧0$ の関係がある。

整数の除法とは何か、つまり整数 $a$ を正の整数 $b$ で割ったときの商と余りを求めるとはどういうことなのかをきちんと定義すると

$a=b・ Q+r (0≦r<b)$

を満たす整数 $Q$ と $r$ を求めることとなる.そして、この求まった値 $Q$ と $r$ をそれぞれ、商と余りと呼ぶのである。

「筆算したもの」の表記の下に、17を3で割る割り算の筆算がある。割られる数17の上に商の5が置かれ、17の下に15、線を挟んで最下部に余りの2が配置されている。

約数と倍数

余りが0になるような割り算を考える。例えば、12を3で割ると、商は4余りは0となる。このとき、3は12の約数であり、12は3の倍数であるという。

一般には次のように表すことができる。

定義1約数と倍数

2つの整数 $a,b$ が、ある整数 $k$ を用いて

$a=bk$

と表せる時、 $b$ は $a$ の約数であるといい、 $a$ は $b$ の倍数であるという。

文脈によっては約数のことを、因数と呼ぶこともある。例えば

$60=3・4・5$

なので、3や4や5は、60の約数であり因数である。

問題1倍数の和と積

整数 $a$ の倍数の和は $a$ の倍数であることを示せ。
整数 $a$ の倍数の積は $a$ の倍数であることを示せ。

解答を見る

整数 $a$ の倍数は、適当な整数 $m,n$ を用いて、 $am,an$ と表すことができる。

このとき、倍数の和は

$am+an =a(m+n)$

であり、 $m+n$ は整数であるから、 $a$ の倍数である。

また、倍数の積は

$am・ an =a・ amn$

であり、 $amn$ は整数であるから、 $a$ の倍数である。

定理2倍数の和と積

整数 $a$ の倍数どうしの和は、 $a$ の倍数である。

また、整数 $a$ の倍数どうしの積は、 $a$ の倍数である。

割り算の一意性

定理3割り算の一意性

整数 $a$ と正の整数 $b$ に対して

$a=b・ Q+r (0≦r<b)$

を満たす整数の組 $Q,r$ は、ただ1組だけ存在する。

証明を見る

証明

$Q,r$ が存在することは、実際に割り算をすればよい。ここでは、そのような組が1組しかないことを示す。

$a$ が

$a=bQ1+r1 (0≦r1<b) a=bQ2+r2 (0≦r2<b)$

と2通りに表せたとすると、辺々引いて

$b(Q1-Q2)=r2-r1$

となる。 $0≦r1<b$ 、 $0≦r2<b$ であるから、 $-b<r2-r1<b$ である。一方、 $r2-r1$ は $b$ の倍数であるから、 $r2-r1=0$ となるほかない。

よって $r1=r2$ であり、 $b\neq0$ であるから $Q1=Q2$ となる。すなわち、商と余りはただ1組に定まる。

∎

最大公約数と最小公倍数

最大公約数と最小公倍数とは何か

定義4最大公約数と最小公倍数

2つ以上の整数において、それらに共通する約数を公約数といい、公約数のうち最大のものを最大公約数という。

最大公約数が1であるとき、その2つ以上の整数は互いに素であるという。

また、2つ以上の整数において、それらに共通する倍数を公倍数といい、正の公倍数のうち最小のものを最小公倍数という。

2つの整数 $a$ と $b$ の最大公約数は、英語表記のgreatest common divisorの頭文字をとって $gcd(a,b)$ などと表す。また、最小公倍数（least common multiple）も同様に、 $lcm(a,b)$ などと表す。

最大公約数や最小公倍数を求めるには、素因数分解を使う。例えば、42と60をそれぞれ素因数分解すると

$42=2・3・7 60=2²・3・5$

となる。

これら2つの数に共通する素因数は2と3である。共通する素因数について、指数の小さいほうを選んでかけ合わせたものが最大公約数となるので、42と60の最大公約数は $2・3=6$ である。そして、公約数は最大公約数6の約数であるから

$1,2,3,6$

となる。

また、現れるすべての素因数について、指数の大きいほうを選んでかけ合わせたものが最小公倍数となるので、42と60の最小公倍数は $2²・3・5・7=420$ である。そして、公倍数は最小公倍数420の倍数である。

多項式についても、共通な因数のうち次数の最も高いものを最大公約数、共通な倍式のうち次数の最も低いものを最小公倍数という。ただし、定数倍の違いは考えない。

問題2最大公約数と最小公倍数

次の各組の多項式の最大公約数と最小公倍数を求めよ。ただし、答えの式は展開しなくてもよい。

$x²-1,x+1$
$x²-4x+4,x²-4$
$x²+2x-3,x²+x-6$
$x³-27,x²-2x-3$

解答を見る

$x²-1=(x+1)(x-1)$ なので、最大公約数は $x+1$ 、最小公倍数は $(x+1)(x-1)$ である。
$x²-4x+4=(x-2)²$ 、 $x²-4=(x-2)(x+2)$ なので、最大公約数は $x-2$ 、最小公倍数は $(x-2)²(x+2)$ である。
$x²+2x-3=(x-1)(x+3)$ 、 $x²+x-6=(x+3)(x-2)$ なので、最大公約数は $x+3$ 、最小公倍数は $(x-1)(x+3)(x-2)$ である。
$x³-27=(x-3)(x²+3x+9)$ 、 $x²-2x-3=(x-3)(x+1)$ なので、最大公約数は $x-3$ 、最小公倍数は $(x-3)(x²+3x+9)(x+1)$ である。

定理5公倍数は最小公倍数の倍数

2つ以上の整数の公倍数は最小公倍数の倍数である。

証明を見る

証明

公倍数の1つを $M$ 、最小公倍数を $l$ とし、 $M$ を $l$ で割って

$M=lq+r (0≦r<l)$

と表す。 $lq$ は公倍数の整数倍であるから公倍数であり、 $r=M-lq$ は公倍数どうしの差であるから、これも公倍数である。

ここで $0<r$ とすると、 $r<l$ より $l$ が最小の正の公倍数であることに反する。よって $r=0$ となり、 $M$ は $l$ の倍数である。

∎

定理6公約数は最大公約数の約数

2つ以上の整数の公約数は最大公約数の約数である。

定理7最大公約数と最小公倍数の積

正の整数 $a,b$ の最大公約数を $g$ 、最小公倍数を $l$ とすると

$ab = gl$

が成り立つ。

互いに素な数の性質

互いに素な数については、次のような性質がある。

定理8互いに素な数の性質

$a,b$ が互いに素であるとき、

$bc$ が $a$ で割り切れるならば、 $c$ が $a$ で割り切れる。

が成り立つ。ただし、 $c$ は整数である。

証明を見る

証明

$a$ と $b$ は互いに素であるから、最大公約数と最小公倍数の積より、 $a$ と $b$ の最小公倍数は $ab$ である。

$bc$ は $b$ の倍数であり、仮定より $a$ の倍数でもあるから、 $a$ と $b$ の公倍数である。

公倍数は最小公倍数の倍数より、 $bc$ は $ab$ の倍数である。すなわち、適当な整数 $m$ を使って

$bc = abm$

と表せる。この両辺を $b$ で割って、 $c=am$ 、すなわち $c$ は $a$ で割り切れる。

∎

ユークリッドの互除法

最大公約数を求めるには素因数分解を行えばよいが、 $1961$ のように大きな数を素因数分解するのは難しい（ $1961=37・53$ ）。

素因数分解しにくい大きな数の最大公約数を求めるには、次の定理を使うと良い。

定理9ユークリッドの互除法

2つの自然数 $a,b$ において、 $a$ を $b$ で割った余りを $r$ とすると、

$a$ と $b$ の最大公約数は、 $b$ と $r$ の最大公約数と等しい

すなわち

$gcd(a,b)=gcd(b,r)$

が成り立つ。

暗記1ユークリッドの互除法

ユークリッドの互除法を証明せよ。

解答を見る

$a$ を $b$ で割った商を $q$ とすると

$a=bq+r$

である。

$a$ と $b$ の公約数を $d$ とすると、 $a$ も $bq$ も $d$ の倍数であるから、倍数の和と積より、その差 $r=a-bq$ も $d$ の倍数である。よって、 $d$ は $b$ と $r$ の公約数でもある。

逆に、 $b$ と $r$ の公約数を $d'$ とすると、 $bq$ も $r$ も $d'$ の倍数であるから、その和 $a=bq+r$ も $d'$ の倍数である。よって、 $d'$ は $a$ と $b$ の公約数でもある。

すなわち、 $a$ と $b$ の公約数と、 $b$ と $r$ の公約数はすべて一致する。したがって、そのうち最大のものも等しく

$gcd(a,b)=gcd(b,r)$

が成り立つ。

例として1071と1029の最大公約数を求めてみよう。

1071を1029で割ると、商は1余りは42、すなわち

$1071=1029・1+42$

となるので、1071と1029の最大公約数は、1029と42の最大公約数と等しい。ここで得られた、1029と42に関して、再び割り算を行うと

$1029=42・24+21$

となるので、1029と42の最大公約数は、42と21の最大公約数と等しい。同様にして

$42=21・2+0$

となるので、42と21の最大公約数は21であることがわかる。すなわち、1071と1029の最大公約数は21である。

問題3ユークリッドの互除法の利用

1073と1517の最大公約数を、ユークリッドの互除法を使って求めよ。

解答を見る

大きいほうを小さいほうで割ることをくり返すと

$1517=1073・1+444 1073=444・2+185 444=185・2+74 185=74・2+37 74=37・2+0$

となる。

よって、1073と1517の最大公約数は $37$ である。

素数

素数とは何か

定義10素数

2以上の自然数で、正の約数が1とその数自体のみである数を、素数という。

例えば、次のような数はみな素数である。

$2,3,5,7,11,13,17$

定義11合成数

2以上の自然数で素数でないものを、合成数という。

例えば、14や60は

$14=2・7 60=3・4・5$

なので、合成数である。

素数の性質

定理12素数の性質

$a,b$ を整数、 $p$ を素数とする時

$ab$ が $p$ で割り切れるならば、 $a$ または $b$ が $p$ で割り切れる

暗記2素数の性質

素数の性質を証明せよ。

解答を見る

$a$ と $p$ の最大公約数は $p$ の約数であるから、 $1$ または $p$ である。

もし、最大公約数が $p$ ならば、 $a$ は $p$ で割り切れる。

もし、最大公約数が $1$ ならば、互いに素な数の性質より、 $b$ が $p$ で割り切れる。

よって、 $a,b$ のうち、少なくとも1つは $p$ で割り切れる。

素因数分解

素数である因数を素因数といい、自然数を素数だけの積の形で表すことを素因数分解するという。

例えば、60は

$60=2²・3・5$

と因数分解できる。

問題4素因数分解

次の数を素因数分解せよ。

$252$
$1001$
$2310$

解答を見る

小さい素数から順に割っていくと $252=2²・3²・7$
同様にして $1001=7・11・13$
同様にして $2310=2・3・5・7・11$

上の例題から経験的に次のことがわかる。

定理13素因数分解の一意性

合成数の素因数分解は、積の順序を考えなければ１通りに定まる。

ある数の約数の個数については次のことが成り立つ。

定理14約数の個数

自然数 $N$ の素因数分解が、 $N=p^a・ q^b・ r^c\dots$ であるとき、 $N$ の正の約数の個数は

$(a+1)(b+1)(c+1)\dots$

となる。

$N$ の正の約数は、 $p$ を $0$ 個から $a$ 個までの $a+1$ 通り、 $q$ を $b+1$ 通り、 $r$ を $c+1$ 通り、 $\dots$ と選んでかけ合わせた形に限る。よって、約数の個数はそれぞれの選び方の個数の積となる。

たとえば $60=2²・3・5$ の正の約数は、 $(2+1)(1+1)(1+1)=12$ 個である。

素数の個数

素数は無数にあることを示すことができる。

暗記3素数が無数にあることの証明

素数を小さい方から並べると

$2,3,5,7,\dots$

である。

$2・3+1,2・3・5+1,2・3・5・7+1$ が素数であることを確認せよ。
素数が無数にあることを示せ。

解答を見る

それぞれ計算すると

$2・3+1=7, 2・3・5+1=31, 2・3・5・7+1=211$

であり、どれも1とその数自体以外に正の約数をもたないので、素数である。
素数が有限個 $p1,p2,\dots,pn$ しかないとする。ここで

$N=p1p2\dotspn+1$

とおくと、 $N$ はどの $pi$ で割っても1余るので、どの $pi$ でも割り切れない。

よって、 $N$ 自身が素数であるか、または $p1,p2,\dots,pn$ 以外の素因数をもつことになり、いずれにしても素数が $n$ 個しかないことに反する。

したがって、素数は無数にある。

不定方程式の整数解

$ax+by=0$ の整数解

$2x+3y=0$ の整数解を求めてみよう。

$x,y$ を整数解とすると

$2x=-3y$

が成り立つ。 $3y$ は3の倍数であるから、 $2x$ も3の倍数である。

2と3は互いに素であるから、互いに素な数の性質より、 $x$ は3の倍数であり、適当な整数 $k$ を用いて、 $x=3k$ と表される。これを、 $2x=-3y$ に代入すると

$2・3k=-3y \Leftrightarrow y=-2k$

となるから、方程式の解は $x=3k,y=-2k$ と表される。

逆に、この形で表される整数 $x,y$ の組みは、方程式の解となる。

以上より、方程式の整数解は $x=3k,y=-2k$ となる。

一般に次のことが成立する。

定理15 $ax+by=0$ の整数解

$a,b$ を互いに素な整数とするとき、 $ax+by=0$ を満たす整数解は

$（は整数） x=bk,y=-ak（kは整数）$

である。

$ax+by=1$ の整数解

次に、方程式 $2x+3y=1$ を満たす整数解を求めてみよう。

この場合、方程式 $2x+3y=1$ を満たす整数解を1つ見つけてしまえば、あとは $ax+by=0$ の整数解の問題に帰着できる。

暗記4 $ax+by=1$ の整数解

方程式 $2x+3y=1$ を満たす整数解を求めよ。

解答を見る

$2x+3y=1 ①$

を満たす整数解として、 $x=-1,y=1$ がある。つまり

$2・(-1)+3・1=1 ②$

$①-②$ より

$2{x-(-1)}+3{y-1}=0 \Leftrightarrow 2(x+1)+3(y-1)=0 ③$

2と3は互いに素であるから、 $ax+by=0$ の整数解より $③$ のすべての整数解は

$（は整数） x+1=3k,y-1=-2k（kは整数）$ と表せる。

よって、 $①$ のすべての整数解は

$（は整数） x=3k-1,y=-2k+1（kは整数）$

となる。

問題51次不定方程式の整数解

次の方程式の整数解をすべて求めよ。

$5x+3y=1$
$7x+11y=1$

解答を見る

$x=2,y=-3$ は $5・2+3・(-3)=1$ を満たすので、整数解の1つである。もとの方程式から辺々引くと

$5(x-2)+3(y+3)=0$

となり、5と3は互いに素であるから、 $ax+by=0$ の整数解より $x-2=3k,y+3=-5k$ と表せる。

よって、求める整数解は $x=3k+2,y=-5k-3$ （ $k$ は整数）である。
$x=-3,y=2$ は $7・(-3)+11・2=1$ を満たすので、整数解の1つである。もとの方程式から辺々引くと

$7(x+3)+11(y-2)=0$

となり、7と11は互いに素であるから、 $ax+by=0$ の整数解より $x+3=11k,y-2=-7k$ と表せる。

よって、求める整数解は $x=11k-3,y=-7k+2$ （ $k$ は整数）である。

積の形の不定方程式

$xy-2x-3y=0$ を満たす整数解を求めてみよう。

このように $xy$ の項をふくむ方程式は

$（整数）（整数）（整数）（整数）\times（整数）=（整数）$

の形に変形して解く。

両辺に6を足すと

$xy-2x-3y+6=6$

となり、左辺を因数分解して

$(x-3)(y-2)=6$

となる。 $x,y$ が整数ならば $x-3,y-2$ も整数であるから、6を2つの整数の積に分ける場合をすべて調べればよい。

$(x-3,y-2)$ の組は

$(1,6),(2,3),(3,2),(6,1),(-1,-6),(-2,-3),(-3,-2),(-6,-1)$

の8通りであるから、求める整数解は

$(x,y)=(4,8),(5,5),(6,4),(9,3),(2,-4),(1,-1),(0,0),(-3,1)$

となる。

最終更新: 2026-08-20

この節についてAIに質問する

この節に書かれている内容だけを根拠に答えます。個人情報は書かないでください。

質問の内容

数学A 第4章 整数の性質 — 整数の基本性質

整数の除法

整数の割り算の復習

約数と倍数

定義1約数と倍数

問題1倍数の和と積

定理2倍数の和と積

割り算の一意性

定理3割り算の一意性

最大公約数と最小公倍数

最大公約数と最小公倍数とは何か

定義4最大公約数と最小公倍数

問題2最大公約数と最小公倍数

定理5公倍数は最小公倍数の倍数

定理6公約数は最大公約数の約数

定理7最大公約数と最小公倍数の積

互いに素な数の性質

定理8互いに素な数の性質

ユークリッドの互除法

定理9ユークリッドの互除法

暗記1ユークリッドの互除法

問題3ユークリッドの互除法の利用

素数

素数とは何か

定義10素数

定義11合成数

素数の性質

定理12素数の性質

暗記2素数の性質

素因数分解

問題4素因数分解

定理13素因数分解の一意性

定理14約数の個数

素数の個数

暗記3素数が無数にあることの証明

不定方程式の整数解

ax+by=0 の整数解

定理15 ax+by=0 の整数解

ax+by=1 の整数解

暗記4 ax+by=1 の整数解

問題51次不定方程式の整数解

積の形の不定方程式

この節についてAIに質問する

数学A 第4章整数の性質 — 整数の基本性質

$ax+by=0$ の整数解

定理15 $ax+by=0$ の整数解

$ax+by=1$ の整数解

暗記4 $ax+by=1$ の整数解