数学A 第4章 整数の性質 — 整数の基本性質
この節の練習問題9問だけをまとめて見る・印刷する →
整数の除法
整数の割り算の復習
まず,小学校以来慣れ親しんできた,整数の除法(integer division)について復習する.
たとえば,次の図のような計算により,17を3で割ると,商は5で余りは2とわかる.この関係を式で表すと
17=3×5+2
となる.
このとき,17を割られる数,3を割る数と呼ぶので,一般的には次のような関係が成り立つ.
(割られる数)=(割る数)×(商)+(余り)
また,(割る数) > (余り) ≧0 の関係がある.
整数の除法とは何か,つまり整数 a を正の整数 b で割ったときの商と余りを求めるとはどういうことなのかを きちんと定義すると
a=b・ Q+r (0≦r<b)
を満たす整数 Q と r を求めることとなる.そして,この求まった値 Q と r をそれぞれ,商と余りと呼ぶのである.
約数と倍数
余りが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≠0 であるから 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) である.
証明
公倍数の1つを M ,最小公倍数を l とし, M を l で割って
M=lq+r (0≦r<l)
と表す. lq は公倍数の整数倍であるから公倍数であり, r=M-lq は公倍数どうしの差であるから,これも公倍数である.
ここで 0<r とすると, r<l より l が最小の正の公倍数であることに反する.よって r=0 となり, M は l の倍数である.
∎
§
定理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素因数分解の一意性
合成数の素因数分解は,積の順序を考えなければ1通りに定まる.
ある数の約数の個数については次のことが成り立つ.
§
定理14約数の個数
自然数 N の素因数分解が, N=p^a・ q^b・ r^c… であるとき, N の正の約数の個数は
(a+1)(b+1)(c+1)…
となる.
N の正の約数は, p を 0 個から a 個までの a+1 通り, q を b+1 通り, r を c+1 通り, … と選んでかけ合わせた形に限る.よって,約数の個数はそれぞれの選び方の個数の積となる.
たとえば 60=2²・3・5 の正の約数は, (2+1)(1+1)(1+1)=12 個である.
素数の個数
素数は無数にあることを示すことができる.
暗記3素数が無数にあることの証明
素数を小さい方から並べると
2,3,5,7,…
である.
- 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,…,pn しかないとする.ここで
N=p1p2…pn+1
とおくと, N はどの pi で割っても1余るので,どの pi でも割り切れない.
よって, N 自身が素数であるか,または p1,p2,…,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 ⇔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 ⇔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 の項をふくむ方程式は
(整数)(整数)(整数)(整数)×(整数)=(整数)
の形に変形して解く.
両辺に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-12
この節についてAIに質問する
この節に書かれている内容だけを根拠に答えます。個人情報は書かないでください。
この回答は役に立ちましたか?