目次 ／ 整数の性質 ／ 数学A

第1章　約数と倍数

—— 整数を素数の積に分けて、約数と倍数を見通しよく扱う ——

この章から「整数の性質」の分野に入ります。まず約数と倍数をかけ算の式で言い表し、数字の並びから倍数かどうかを見分ける判定法を学びます。次に、整数を素数だけのかけ算に分ける「素因数分解」を身につけます。素因数分解ができると、約数の個数や総和、最大公約数・最小公倍数が、書き出さなくても計算だけで求められるようになります。最後に、$n!$ が $2$ や $5$ で何回割り切れるかを数える方法を扱い、「$100!$ の末尾に $0$ はいくつ並ぶか」に答えます。

問題マップ記録を読み込み中…
基1基2基3基4基51234567891011121314151617181920
未回答 25× 0○ 01か月定着 0

約数と倍数

小学校では「1212 は 33 の倍数」「33 は 1212 の約数」と習いました。高校では、負の数や 00 も仲間に入れて、約数と倍数をかけ算の式で言い表します。この分野では、とくに断らないかぎり、文字は整数を表すものとします。

公式1：約数と倍数

2つの整数 aa，bb（bb≠0{}\neq 0）について

a\displaystyle a=bk\displaystyle {}= bk(k は整数)\displaystyle (k \ \text{は整数})

と表されるとき、bb を aa の約数、aa を bb の倍数という。「aa は bb で割り切れる」ともいう。

性質　aa，bb がともに mm の倍数ならば、aa+b{}+ b，aa−b{}- b，kaka（kk は整数）もすべて mm の倍数である。

−12-12=3×(−4){}= 3 \times (-4) なので −12-12 も 33 の倍数ですし、1212=(−3)×(−4){}= (-3) \times (-4) なので −3-3 は 1212 の約数です。約数は正と負がペアで現れるため、ふだんは正の約数だけを考えます。また 00=b×0{}= b \times 0 と書けるので、00 はどんな整数の倍数でもあります。

性質のほうは、式にすればすぐに分かります。aa=mk{}= mk，bb=ml{}= ml（kk，ll は整数）とおくと

a\displaystyle a+b\displaystyle {}+ b=m(k+l),\displaystyle {}= m(k + l),a\displaystyle a−b\displaystyle {}- b=m(k−l)\displaystyle {}= m(k - l)

で、kk+l{}+ l も kk−l{}- l も整数だからです。「mm の倍数であることを示す」問題では、目標の式を「m×(整数)m \times (\text{整数})」の形に変形する、というのが基本の方針になります。

5円玉しか入っていない財布を思い浮かべてください。中身の金額は、何枚入っていても必ず5の倍数の円です。こういう財布を2つ合わせても、片方からもう片方と同じ金額を抜き取っても、変わるのは5円玉の枚数だけなので、金額は5の倍数のままです。倍数どうしの和や差が倍数になるのは、これと同じ理屈です。

「aa が mm の倍数」とは「aa=m×(整数){}= m \times (\text{整数}) と書ける」ことで、mm の倍数どうしを足しても引いても mm の倍数のままだということです。

例題1：約数と倍数

(1) 7272 の正の約数をすべて求めなさい。

(2) 連続する3つの整数の和は 33 の倍数であることを示しなさい。

【解答】

(1) かけて 7272 になる2つの数の組を、小さいほうの数が 11，22，33，…… の順に探します（55 と 77 では割り切れません）。

72\displaystyle 72=1×72\displaystyle {}= 1 \times 72=2×36\displaystyle {}= 2 \times 36=3×24\displaystyle {}= 3 \times 24=4×18\displaystyle {}= 4 \times 18=6×12\displaystyle {}= 6 \times 12=8×9\displaystyle {}= 8 \times 9

よって、正の約数は

1,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}1,} 2,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 2,} 3,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 3,} 4,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 4,} 6,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 6,} 8,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 8,} 9,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 9,} 12,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 12,} 18,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 18,} 24,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 24,} 36,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 36,} 72‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 72}

の12個です。8×98 \times 9 の次は 9×89 \times 8 で左右が入れかわるだけなので、そこで探すのをやめられます。

(2) 連続する3つの整数は、真ん中の数を nn として nn−1{}- 1，nn，nn+1{}+ 1 と表せます。その和は

(n−1)\displaystyle (n - 1)+n\displaystyle {}+ n+(n+1)\displaystyle {}+ (n + 1)=3n\displaystyle {}= 3n

で、nn は整数なので 3n3n は 33 の倍数です。（証明終）

倍数の判定法

22 や 33 の倍数かどうかは、実際に割り算をしなくても、数字の並びを見るだけで判定できます。

公式2：倍数の判定法

自然数 NN について、次が成り立つ。

  • 22 の倍数   ⟺  \iff 一の位が偶数（00，22，44，66，88）
  • 55 の倍数   ⟺  \iff 一の位が 00 か 55
  • 44 の倍数   ⟺  \iff 下2けたが 44 の倍数（0000 も含む）
  • 88 の倍数   ⟺  \iff 下3けたが 88 の倍数（000000 も含む）
  • 33 の倍数   ⟺  \iff 各位の数字の和が 33 の倍数
  • 99 の倍数   ⟺  \iff 各位の数字の和が 99 の倍数

4けたの自然数で理由を確かめます。千の位、百の位、十の位、一の位の数字を aa，bb，cc，dd とすると

N\displaystyle N=1000a\displaystyle {}= 1000a+100b\displaystyle {}+ 100b+10c\displaystyle {}+ 10c+d\displaystyle {}+ d

です。1010 は 22 と 55 の倍数、100100 は 44 の倍数、10001000 は 88 の倍数なので、それぞれ上の位の部分は必ず割り切れ、残る下の位だけで判定が決まります（公式1の性質）。

33 と 99 の判定は、10001000=999{}= 999+1{}+ 1 のように分けると見えてきます。

N\displaystyle N=(999a+99b+9c)\displaystyle {}= (999a + 99b + 9c)+(a+b+c+d)\displaystyle {}+ (a + b + c + d)=9(111a+11b+c)\displaystyle {}= 9(111a + 11b + c)+(a+b+c+d)\displaystyle {}+ (a + b + c + d)

前半は 99 の倍数（したがって 33 の倍数）です。そのため、NN と各位の和 aa+b{}+ b+c{}+ c+d{}+ d は、一方が 99 の倍数なら他方も 99 の倍数になります（公式1の性質で、前半を足すか引くかすれば移り合います）。33 についても同じです。何けたの数でも、1010=9{}= 9+1{}+ 1，100100=99{}= 99+1{}+ 1，…… と分けられるので、同じ理屈が通ります。

なお、66 の倍数は「22 の倍数であり、33 の倍数でもある数」として判定できます。22 と 33 のように共通の素因数（公式3）をもたない2数の倍数は、その積の倍数になるからです（厳密定義 定理5）。

1個9円の駄菓子を10円玉で買うと、お釣りは1円です。100円玉なら11個買って1円、1000円札なら111個買って1円余ります。どのお金も、9円の買い物をしきったあとに「1枚につき1円」が残るのです。財布に1000円札が aa 枚、100円玉が bb 枚、10円玉が cc 枚、1円玉が dd 枚あるとき、合計 NN 円でちょうど駄菓子を買いきれるかどうかは、残りの合計 aa+b{}+ b+c{}+ c+d{}+ d 円が9の倍数かどうかで決まります。各位の数字は、お札や硬貨の枚数そのものです。

22・44・55・88 の倍数は下の位だけを、33・99 の倍数は各位の数字の和を見れば判定できるということです。

例題2：倍数の判定法

(1) 4けたの自然数 5□285\square 28 が 99 の倍数となるとき、□\square に入る数字を求めなさい。

(2) 4けたの自然数 4□724\square 72 が 66 の倍数となるとき、□\square に入る数字をすべて求めなさい。

【解答】

(1) 各位の数字の和は 55+□{}+ \square+2{}+ 2+8{}+ 8=15{}= 15+□{}+ \square です。□\square は 00 から 99 までの数字なので、1515+□{}+ \square は 1515 以上 2424 以下で、その中の 99 の倍数は 1818 だけです。よって 3‾\underline{3} です（53285328=9×592{}= 9 \times 592）。

(2) 66 の倍数は、22 の倍数かつ 33 の倍数です。一の位が 22 なので、22 の倍数の条件は □\square に関係なく満たされます。各位の数字の和 44+□{}+ \square+7{}+ 7+2{}+ 2=13{}= 13+□{}+ \square は 1313 以上 2222 以下で、これが 33 の倍数になるのは 1515，1818，2121 のときです。よって 2,‾\underline{\rule[-0.1944em]{0em}{0.8389em}2,} 5,‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 5,} 8‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 8} です。

素数と素因数分解

公式3：素数と素因数分解

22 以上の自然数で、正の約数が 11 とその数自身の2つだけであるものを素数という。22 以上の自然数で素数でないものを合成数という。11 は素数でも合成数でもない。

自然数を素数だけの積で表すことを素因数分解といい、その積に現れる素数を素因数という。

360\displaystyle 360=23⋅32⋅5\displaystyle {}= 2^3 \cdot 3^2 \cdot 5

22 以上の自然数の素因数分解は、かける順序の違いを除いてただ1通りである。

素数を小さい順に並べると 22，33，55，77，1111，1313，1717，1919，2323，2929，…… です。偶数の素数は 22 だけです。

素因数分解は、小さい素数から順に、割れるだけ割っていきます。割り算を縦に積み重ねる「はしご算」で書くと見通しがよくなります。

236021802903453155\begin{array}{r|l} 2 & 360 \\ \hline 2 & 180 \\ \hline 2 & 90 \\ \hline 3 & 45 \\ \hline 3 & 15 \\ \hline & 5 \end{array}

左に並んだ素数と、最後に残った 55 をかければ元の数にもどります。同じ素数は累乗でまとめて小さい順に並べ、かけ算の記号は「⋅\cdot」で書くのが、この分野での書き方です。

ある数が素数かどうかを調べるときは、N\sqrt{N} 以下の素数で割ってみれば十分です。NN=ab{}= ab（aa≦b{}\leqq b）と2つに分けられるなら a2a^2≦ab{}\leqq ab=N{}= N なので、小さいほうの aa は N\sqrt{N} 以下になるからです。たとえば 9797 は、97\sqrt{97}<10{}< 10 なので、22，33，55，77 で割り切れないことを確かめれば素数だと分かります。

11 を素数の仲間に入れないのには理由があります。もし 11 を素数とすると、66=2⋅3{}= 2 \cdot 3=1⋅2⋅3{}= 1 \cdot 2 \cdot 3=12⋅2⋅3{}= 1^2 \cdot 2 \cdot 3 のように素因数分解がいくらでも作れてしまい、「ただ1通り」という大切な性質が崩れるからです。この「ただ1通り」は当たり前に見えますが、きちんとした証明が必要です（厳密定義 定理3）。

水は H2O\mathrm{H_2O}、二酸化炭素は CO2\mathrm{CO_2} のように、物質は原子の組み合わせで書き表せます。整数の世界では、素数が原子、合成数が分子にあたります。360360=23⋅32⋅5{}= 2^3 \cdot 3^2 \cdot 5 は、「22 が3個、33 が2個、55 が1個でできた分子」を表す化学式のようなものです。

素数は整数をつくる「原子」で、2以上の自然数はどれも素数の積としてただ1通りに書けるということです。

例題3：素因数分解

(1) 504504 を素因数分解した式を求めなさい。

(2) 540n\sqrt{540n} が自然数となるような最小の自然数 nn を求めなさい。

【解答】

(1) 小さい素数から順に割っていきます。

2504225221263633217\begin{array}{r|l} 2 & 504 \\ \hline 2 & 252 \\ \hline 2 & 126 \\ \hline 3 & 63 \\ \hline 3 & 21 \\ \hline & 7 \end{array}

よって 504=23⋅32⋅7‾\underline{504 = 2^3 \cdot 3^2 \cdot 7} です。

(2) 540540=22⋅33⋅5{}= 2^2 \cdot 3^3 \cdot 5 です。540n\sqrt{540n} が自然数 mm になるのは、540n540n=m2{}= m^2 のときです。自然数の2乗を素因数分解すると、たとえば 90290^2=(2⋅32⋅5)2{}= (2 \cdot 3^2 \cdot 5)^2=22⋅34⋅52{}= 2^2 \cdot 3^4 \cdot 5^2 のように、どの素因数の指数も偶数になります。540540 の指数を見ると、22 は2個で偶数ですが、33 は3個、55 は1個で奇数です。どんな nn でも 33 と 55 を少なくとも1個ずつ補う必要があるので、最小のものは

n\displaystyle n=3⋅5\displaystyle {}= 3 \cdot 5=15‾\displaystyle {}= \underline{15}

です。このとき 540×15540 \times 15=8100{}= 8100=902{}= 90^2 で、8100\sqrt{8100}=90{}= 90 となります。

約数の個数と総和

例題1では、7272 の正の約数を12個書き出しました。素因数分解 7272=23⋅32{}= 2^3 \cdot 3^2 を使うと、書き出さなくても個数が分かります。

公式4：約数の個数と総和

自然数 NN が NN=paqbrc{}= p^a q^b r^c（pp，qq，rr は異なる素数）と素因数分解されるとき、NN の正の約数の

個数は\displaystyle \text{個数は}(a+1)(b+1)(c+1)\displaystyle (a + 1)(b + 1)(c + 1)総和は\displaystyle \text{総和は} \quad(1+p+p2+⋯+pa)\displaystyle (1 + p + p^2 + \cdots + p^a)×(1+q+q2+⋯+qb)\displaystyle \quad \times (1 + q + q^2 + \cdots + q^b)×(1+r+r2+⋯+rc)\displaystyle \quad \times (1 + r + r^2 + \cdots + r^c)

である。素因数が2種類や4種類以上のときも、同じようにかけ合わせる。

7272=23⋅32{}= 2^3 \cdot 3^2 の正の約数を素因数分解すると、22 と 33 以外の素因数は現れず、22 は3個まで、33 は2個までしか含みません。7272 に無い材料は使えないからです（厳密定義 定理4）。つまり約数は 2i⋅3j2^i \cdot 3^j（ii=0,{}= 0, 1,\ 1, 2,\ 2, 3\ 3，jj=0,{}= 0, 1,\ 1, 2\ 2）の形の数で、表に並べると次のようになります。

30=13^0 = 131=33^1 = 332=93^2 = 9
20=12^0 = 1113399
21=22^1 = 222661818
22=42^2 = 44412123636
23=82^3 = 88824247272

22 の指数の選び方が 00 から 33 の4通り、33 の指数の選び方が 00 から 22 の3通りで、表のマスは 4×34 \times 3=12{}= 12 個です。公式の「+1+1」は、指数 00、つまり「その素数を使わない」という選び方の分です。

総和は、表のマスを全部足したものです。(1+2+4+8)(1+3+9)(1 + 2 + 4 + 8)(1 + 3 + 9) を展開すると、左のかっこから1つ、右のかっこから1つ選んでかけた積がすべて現れ、それがちょうど表のマスの数になっています。

(1+2+4+8)(1+3+9)\displaystyle (1 + 2 + 4 + 8)(1 + 3 + 9)=15×13\displaystyle {}= 15 \times 13=195\displaystyle {}= 195

例題1の12個を実際に足しても 195195 になります。

ハンバーガーを注文するとき、パティを0〜3枚、チーズを0〜2枚から選べるとします。パティの選び方は4通り、チーズは3通りなので、組み合わせは 4×34 \times 3=12{}= 12 通りです。「パティなし」「チーズなし」も立派な1つの選び方として数えるのがポイントで、約数の個数の「指数 +1+1」は、この「なし」の分にあたります。

正の約数は、各素因数を何個使うか（0個も含む）の選び方で決まるので、個数は（指数 +1+1）の積、総和は (1+p+⋯+pa)(1 + p + \cdots + p^a) の積になるということです。

例題4：約数の個数と総和

(1) 360360 の正の約数の個数と、その総和を求めなさい。

(2) 正の約数の個数が 66 個である自然数のうち、最小のものを求めなさい。

【解答】

(1) 360360=23⋅32⋅5{}= 2^3 \cdot 3^2 \cdot 5 なので、正の約数の個数は

(3+1)(2+1)(1+1)\displaystyle (3 + 1)(2 + 1)(1 + 1)=24 個‾\displaystyle {}= \underline{24 \ \text{個}}

総和は

(1+2+4+8)(1+3+9)(1+5)\displaystyle (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5)=15×13×6\displaystyle {}= 15 \times 13 \times 6=1170‾\displaystyle {}= \underline{1170}

(2) 素因数分解したときの（指数 +1+1）の積が 66 になればよく、66=6{}= 6 または 66=3×2{}= 3 \times 2 です。

  • 素因数が1種類のとき：p5p^5 の形。最小は 252^5=32{}= 32
  • 素因数が2種類のとき：p2qp^2q の形。指数の大きいほうに小さい素数をあてて、最小は 22⋅32^2 \cdot 3=12{}= 12

よって最小のものは 12‾\underline{12} です（正の約数は 11，22，33，44，66，1212 の6個）。

最大公約数と最小公倍数

公式5：最大公約数・最小公倍数

2つ以上の整数に共通な約数を公約数といい、そのうち最大のものを最大公約数という。共通な倍数を公倍数といい、そのうち正で最小のものを最小公倍数という。

素因数分解を使うと、次のように求められる。

  • 最大公約数：共通な素因数に、指数の小さいほうをつけてかける
  • 最小公倍数：現れるすべての素因数に、指数の大きいほうをつけてかける

公約数はすべて最大公約数の約数であり、公倍数はすべて最小公倍数の倍数である。

また、最大公約数が 11 である2つの整数は互いに素であるという。

6060=22⋅3⋅5{}= 2^2 \cdot 3 \cdot 5 と 7272=23⋅32{}= 2^3 \cdot 3^2 で確かめます。共通でない素因数は指数 00（505^0=1{}= 1）と考えて、素因数ごとにそろえて並べます。

223355値
6060222^2313^1515^16060
7272232^3323^2505^07272
最大公約数（小さいほう）222^2313^1505^01212
最小公倍数（大きいほう）232^3323^2515^1360360

公約数は 6060 と 7272 の両方の約数なので、どの素因数も両方の個数を超えられず、「小さいほう」までしか含めません。逆に公倍数は、6060 と 7272 の材料をどちらも丸ごと含む必要があるので、「大きいほう」以上が要ります。6060 と 7272 の公約数 11，22，33，44，66，1212 が、すべて 1212 の約数になっていることも確かめられます。

互いに素かどうかは、共通の素因数があるかどうかで判定できます。たとえば 88=23{}= 2^3 と 1515=3⋅5{}= 3 \cdot 5 は共通の素因数がないので互いに素です。どちらも素数ではありませんが、互いに素であることに変わりはありません。

バラ60本とかすみ草72本で、どれも同じ中身の花束をつくり、1本も余らせないようにします。花束の数は60と72の両方を割り切る数でなければならず、いちばん多くつくれるのは最大公約数の12束です（1束にバラ5本・かすみ草6本）。一方、池のまわりを1周12分で走る人と18分で走る人が同時にスタートすると、2人がスタート地点で再び出会うのは、12と18の最小公倍数の36分後です。「等しく分ける」なら最大公約数、「そろうのを待つ」なら最小公倍数、と覚えておくと使い分けに迷いません。

素因数分解を素因数ごとに縦にそろえ、指数の小さいほうを取れば最大公約数、大きいほうを取れば最小公倍数になるということです。

例題5：最大公約数と最小公倍数

次の数の最大公約数と最小公倍数を求めなさい。

(1) 8484，120120　　(2) 1212，1818，3030

【解答】

(1) 8484=22⋅3⋅7{}= 2^2 \cdot 3 \cdot 7，120120=23⋅3⋅5{}= 2^3 \cdot 3 \cdot 5 です。

最大公約数\displaystyle \text{最大公約数}=22⋅3\displaystyle {}= 2^2 \cdot 3=12‾,\displaystyle {}= \underline{12},最小公倍数\displaystyle \text{最小公倍数}=23⋅3⋅5⋅7\displaystyle {}= 2^3 \cdot 3 \cdot 5 \cdot 7=840‾\displaystyle {}= \underline{840}

(2) 1212=22⋅3{}= 2^2 \cdot 3，1818=2⋅32{}= 2 \cdot 3^2，3030=2⋅3⋅5{}= 2 \cdot 3 \cdot 5 です。3つに共通な素因数は 22 と 33 で、指数の小さいほうはどちらも 11 です。

最大公約数\displaystyle \text{最大公約数}=2⋅3\displaystyle {}= 2 \cdot 3=6‾,\displaystyle {}= \underline{6},最小公倍数\displaystyle \text{最小公倍数}=22⋅32⋅5\displaystyle {}= 2^2 \cdot 3^2 \cdot 5=180‾\displaystyle {}= \underline{180}

3つ以上の数でも、「小さいほう」「大きいほう」を3つの中で選べば、同じ方法で求められます。

最大公約数と最小公倍数の関係

公式6：最大公約数と最小公倍数の関係

2つの自然数 aa，bb の最大公約数を gg、最小公倍数を ll とすると

a\displaystyle a=ga′,\displaystyle {}= ga',b\displaystyle b=gb′\displaystyle {}= gb'(a′, b′ は互いに素な自然数)\displaystyle (a',\ b' \ \text{は互いに素な自然数})

と表せて

l\displaystyle l=ga′b′,\displaystyle {}= ga'b',ab\displaystyle ab=gl\displaystyle {}= gl

が成り立つ。

aa，bb を最大公約数 gg で割った残りを a′a'，b′b' とします。もし a′a' と b′b' に共通の素因数 pp が残っていたら、gpgp も aa，bb の公約数になり、gg が最大であることに反します。だから a′a' と b′b' は互いに素です。公倍数は ga′ga' と gb′gb' の両方の材料を含む必要があり、a′a' と b′b' に共通の材料はないので、最小のものは ga′b′ga'b' です。すると

ab\displaystyle ab=ga′⋅gb′\displaystyle {}= ga' \cdot gb'=g⋅ga′b′\displaystyle {}= g \cdot ga'b'=gl\displaystyle {}= gl

となります。例題5(1) なら、8484=12⋅7{}= 12 \cdot 7，120120=12⋅10{}= 12 \cdot 10 で、77 と 1010 は互いに素、ll=12⋅7⋅10{}= 12 \cdot 7 \cdot 10=840{}= 840 です。確かに 84×12084 \times 120=10080{}= 10080=12×840{}= 12 \times 840 となっています。

Aさんの買い物メモとBさんの買い物メモに、どちらも「牛乳」と「卵」が書いてあったとします。2枚のメモを並べると、牛乳と卵は2回ずつ出てきます。2人分をまとめて1枚のリストにするなら、共通の品は1回書けば足ります。abab は2枚のメモを並べたもの、ll はまとめたリスト、gg はだぶっていた共通の品です。並べたメモは「まとめたリスト」と「もう1回分の共通の品」でできていて、数の世界では「並べる」がかけ算にあたるので、abab=l×g{}= l \times g となるわけです。

2数を最大公約数 gg でくくると残りの a′a'，b′b' は互いに素になり、そこから ll=ga′b′{}= ga'b' と abab=gl{}= gl が出てくるということです。

例題6：最大公約数と最小公倍数から2数を求める

2つの自然数 aa，bb（aa<b{}< b）の最大公約数が 1212、最小公倍数が 144144 であるとき、aa，bb の組をすべて求めなさい。

【解答】

最大公約数が 1212 なので、aa=12a′{}= 12a'，bb=12b′{}= 12b'（a′a'，b′b' は互いに素な自然数で a′a'<b′{}< b'）と表せます。最小公倍数について

12a′b′\displaystyle 12a'b'=144\displaystyle {}= 144より\displaystyle \text{より}a′b′\displaystyle a'b'=12\displaystyle {}= 12

積が 1212 になる組 (a′, b′)(a',\ b') は (1, 12)(1,\ 12)，(2, 6)(2,\ 6)，(3, 4)(3,\ 4) です。このうち (2, 6)(2,\ 6) は公約数 22 をもつので互いに素ではありません（この組だと最大公約数が 2424 になってしまいます）。残る2組から

(a, b)=(12, 144),‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}(a,\ b) = (12,\ 144),} (36, 48)‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ (36,\ 48)}

（確かめ）3636=22⋅32{}= 2^2 \cdot 3^2，4848=24⋅3{}= 2^4 \cdot 3 の最大公約数は 22⋅32^2 \cdot 3=12{}= 12、最小公倍数は 24⋅322^4 \cdot 3^2=144{}= 144 です。

階乗に含まれる素因数の個数

最後に、たくさんの数の積が、ある素数で何回割り切れるかを数えます。数と式 第7章で登場した n!n!=1×2×3×⋯×n{}= 1 \times 2 \times 3 \times \cdots \times n を使います。

公式7：n!n! に含まれる素因数 pp の個数

n!n! を素因数分解したときの素数 pp の指数（n!n! が pp で何回割り切れるか）は、次の和で求められる。

（nn 以下の pp の倍数の個数）＋（nn 以下の p2p^2 の倍数の個数）＋（nn 以下の p3p^3 の倍数の個数）＋ ……

pkp^k が nn を超えたら、その先はすべて 00 なので足すのをやめる。nn 以下の pp の倍数の個数は、n÷pn \div p の商である。

10!10! と pp=2{}= 2 で考えます。11 から 1010 までの数のうち、22 を1個以上含むのは 22 の倍数の 22，44，66，88，1010 の5個です。そのうち 22 を2個以上含むのは 44 の倍数の 44，88 の2個、3個以上含むのは 88 の倍数の 88 の1個です。88=23{}= 2^3 は、22 の倍数・44 の倍数・88 の倍数として3回数えられ、ちょうど3個分になります。合計すると

5\displaystyle 5+2\displaystyle {}+ 2+1\displaystyle {}+ 1=8\displaystyle {}= 8

で、実際に 10!10!=3628800{}= 3628800=28⋅34⋅52⋅7{}= 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 です。

「n!n! の末尾に 00 がいくつ並ぶか」も、この公式で分かります。末尾の 00 の個数は n!n! が 1010=2⋅5{}= 2 \cdot 5 で何回割り切れるか、つまり 22 と 55 のペアの数です。22 は 55 よりずっと多く含まれるので、ペアの数は 55 の個数で決まります。

スタンプカードにたとえてみます。11 から nn までの数それぞれに、「22 で割り切れる回数」だけスタンプを押すとします。1人ずつ回数を調べる代わりに、1回目は 22 の倍数全員に1個ずつ、2回目は 44 の倍数だけにもう1個ずつ、3回目は 88 の倍数だけにさらに1個ずつ、と押していけば、どの数にも正しい個数のスタンプがたまります。スタンプの総数は、各回に押した人数を足したものです。

n!n! に含まれる素因数 pp の個数は、pp の倍数・p2p^2 の倍数・p3p^3 の倍数……の個数を順に足して数えればよいということです。

例題7：n!n! に含まれる素因数の個数

(1) 30!30! が 22 で何回割り切れるか、その回数を求めなさい。

(2) 100!100! を計算すると末尾に 00 が何個続くか、その個数を求めなさい。

【解答】

(1) 3030 以下の、22 の倍数は 1515 個、44 の倍数は 77 個、88 の倍数は 33 個、1616 の倍数は 11 個です（3232>30{}> 30）。

15\displaystyle 15+7\displaystyle {}+ 7+3\displaystyle {}+ 3+1\displaystyle {}+ 1=26 回‾\displaystyle {}= \underline{26 \ \text{回}}

(2) 末尾の 00 の個数は、100!100! が 1010=2⋅5{}= 2 \cdot 5 で何回割り切れるかに等しくなります。100100 以下の、55 の倍数は 2020 個、2525 の倍数は 44 個です（125125>100{}> 100）。よって 55 の個数は 2020+4{}+ 4=24{}= 24 です。22 の個数は 5050+25{}+ 25+12{}+ 12+6{}+ 6+3{}+ 3+1{}+ 1=97{}= 97 で 55 より多いので、2⋅52 \cdot 5 のペアは 2424 組できます。答えは 24 個‾\underline{24 \ \text{個}} です。

この章では、素因数分解を道具にして、約数・倍数の問題を計算で解けるようにしました。ただ、何百けたもある数の素因数分解は、コンピュータでも簡単ではありません。次の第2章では、素因数分解をしなくても最大公約数が求められる「ユークリッドの互除法」を学びます。

基礎確認問題（全5問）

まずは公式をそのまま使う、ごく簡単な問題で確認しましょう。

問1

4848 の正の約数をすべて求めなさい。

つまずいたときは：
答えを見る
答え

1,1, 2,\ 2, 3,\ 3, 4,\ 4, 6,\ 6, 8,\ 8, 12,\ 12, 16,\ 16, 24,\ 24, 48\ 48（1×481 \times 48，2×242 \times 24，3×163 \times 16，4×124 \times 12，6×86 \times 8）

自己採点：
記録を読み込み中…

問2

12341234，35163516，70207020，99989998 のうち、44 の倍数であるものをすべて求めなさい。

つまずいたときは：
答えを見る
答え

35163516，70207020（下2けたの 1616，2020 が 44 の倍数）

自己採点：
記録を読み込み中…

問3

252252 を素因数分解した式を求めなさい。

つまずいたときは：
答えを見る
答え

22⋅32⋅72^2 \cdot 3^2 \cdot 7

自己採点：
記録を読み込み中…

問4

7272 の正の約数の個数と、その総和を求めなさい。

つまずいたときは：
答えを見る
答え

1212 個、総和 195195（7272=23⋅32{}= 2^3 \cdot 3^2 より (3+1)(2+1)(3 + 1)(2 + 1)，(1+2+4+8)(1+3+9)(1 + 2 + 4 + 8)(1 + 3 + 9)=15×13{}= 15 \times 13）

自己採点：
記録を読み込み中…

問5

3636 と 6060 の最大公約数と最小公倍数を求めなさい。

つまずいたときは：
答えを見る
答え

最大公約数 1212、最小公倍数 180180（3636=22⋅32{}= 2^2 \cdot 3^2，6060=22⋅3⋅5{}= 2^2 \cdot 3 \cdot 5）

自己採点：
記録を読み込み中…

実践問題（全20問）

難易度マークは ★＝基礎、★★＝標準、★★★＝入試レベルです。★から順に取り組みましょう。

問1　★

(1) 整数 aa，bb がともに 77 の倍数のとき、a2a^2−3b{}- 3b は 77 の倍数であることを示しなさい。

(2) 整数 aa が 66 の倍数、bb が 44 の倍数のとき、abab は 2424 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

解説を参照（(1) a2a^2−3b{}- 3b=7(7k2−3l){}= 7(7k^2 - 3l)　(2) abab=24kl{}= 24kl）

解説

「m×(整数)m \times (\text{整数})」の形に変形するのが方針です。

(1) aa=7k{}= 7k，bb=7l{}= 7l（kk，ll は整数）とおくと

a2\displaystyle a^2−3b\displaystyle {}- 3b=49k2\displaystyle {}= 49k^2−21l\displaystyle {}- 21l=7(7k2−3l)\displaystyle {}= 7(7k^2 - 3l)

7k27k^2−3l{}- 3l は整数なので、a2a^2−3b{}- 3b は 77 の倍数です。（証明終）

(2) aa=6k{}= 6k，bb=4l{}= 4l（kk，ll は整数）とおくと

ab\displaystyle ab=24kl\displaystyle {}= 24kl

klkl は整数なので、abab は 2424 の倍数です。（証明終）

なお、「aa が 66 の倍数であり、44 の倍数でもある」なら、いえるのは 2424 の倍数ではなく 1212 の倍数までです（たとえば aa=12{}= 12）。積と「かつ」を混同しないようにしましょう。

自己採点：
記録を読み込み中…

問2　★

(1) 3□573\square 57 が 33 の倍数　(2) 81□681\square 6 が 44 の倍数　(3) 5□945\square 94 が 99 の倍数

上の (1)〜(3) のそれぞれについて、4けたの自然数の □\square に入る数字をすべて求めなさい。

つまずいたときは：
答えを見る
答え

(1) 0,0, 3,\ 3, 6,\ 6, 9\ 9　(2) 1,1, 3,\ 3, 5,\ 5, 7,\ 7, 9\ 9　(3) 0,0, 9\ 9

解説

(1) 各位の数字の和は 33+□{}+ \square+5{}+ 5+7{}+ 7=15{}= 15+□{}+ \square です。1515 は 33 の倍数なので、□\square 自身が 33 の倍数であればよく、0,‾\underline{\rule[-0.1944em]{0em}{0.8389em}0,} 3,‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 3,} 6,‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 6,} 9‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 9} です。

(2) 下2けたの「□6\square 6」が 44 の倍数であればよいです。1616，3636，5656，7676，9696 は 44 の倍数、0606，2626，4646，6666，8686 は 44 の倍数ではないので、1,‾\underline{\rule[-0.1944em]{0em}{0.8389em}1,} 3,‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 3,} 5,‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 5,} 7,‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 7,} 9‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 9} です。

(3) 各位の数字の和は 55+□{}+ \square+9{}+ 9+4{}+ 4=18{}= 18+□{}+ \square で、1818 以上 2727 以下です。このうち 99 の倍数は 1818 と 2727 なので、0,‾\underline{\rule[-0.1944em]{0em}{0.8389em}0,} 9‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 9} です（50945094=9×566{}= 9 \times 566，59945994=9×666{}= 9 \times 666）。

自己採点：
記録を読み込み中…

問3　★

(1) 12601260　(2) 30873087　(3) 10011001

上の (1)〜(3) を素因数分解した式を、それぞれ求めなさい。

つまずいたときは：
答えを見る
答え

(1) 22⋅32⋅5⋅72^2 \cdot 3^2 \cdot 5 \cdot 7　(2) 32⋅733^2 \cdot 7^3　(3) 7⋅11⋅137 \cdot 11 \cdot 13

解説

(1) 小さい素数から順に割ります。

212602630331531055357\begin{array}{r|l} 2 & 1260 \\ \hline 2 & 630 \\ \hline 3 & 315 \\ \hline 3 & 105 \\ \hline 5 & 35 \\ \hline & 7 \end{array}

よって 12601260=22⋅32⋅5⋅7‾{}= \underline{2^2 \cdot 3^2 \cdot 5 \cdot 7} です。

(2) 一の位が 77 なので 22 でも 55 でも割れません。各位の数字の和が 33+0{}+ 0+8{}+ 8+7{}+ 7=18{}= 18 なので 99 の倍数で、30873087=9×343{}= 9 \times 343 です。343343=7×49{}= 7 \times 49=73{}= 7^3 なので、30873087=32⋅73‾{}= \underline{3^2 \cdot 7^3} です。

(3) 10011001 は一の位が 11、各位の数字の和が 22 なので、22，33，55 では割れません。77 で割ると 10011001=7×143{}= 7 \times 143、さらに 143143=11×13{}= 11 \times 13 です。よって 10011001=7⋅11⋅13‾{}= \underline{7 \cdot 11 \cdot 13} です。

自己採点：
記録を読み込み中…

問4　★

(1) 252n\sqrt{252n} が自然数となるような最小の自然数 nn を求めなさい。

(2) 1350n1350n がある自然数の3乗となるような最小の自然数 nn を求めなさい。

つまずいたときは：
答えを見る
答え

(1) nn=7{}= 7　(2) nn=20{}= 20

解説

(1) 252252=22⋅32⋅7{}= 2^2 \cdot 3^2 \cdot 7 です。自然数の2乗は、素因数分解の指数がすべて偶数です。指数が奇数なのは 77 だけなので、nn=7‾{}= \underline{7} です。このとき 252×7252 \times 7=1764{}= 1764=422{}= 42^2 です。

(2) 13501350=2⋅33⋅52{}= 2 \cdot 3^3 \cdot 5^2 です。自然数の3乗は、素因数分解の指数がすべて 33 の倍数です。22 はあと2個、55 はあと1個で指数が 33 になるので

n\displaystyle n=22⋅5\displaystyle {}= 2^2 \cdot 5=20‾\displaystyle {}= \underline{20}

このとき 1350×201350 \times 20=27000{}= 27000=23⋅33⋅53{}= 2^3 \cdot 3^3 \cdot 5^3=303{}= 30^3 です。

自己採点：
記録を読み込み中…

問5　★

(1) 200200 の正の約数の個数と、その総和を求めなさい。

(2) 540540 の正の約数の個数を求めなさい。

つまずいたときは：
答えを見る
答え

(1) 1212 個、総和 465465　(2) 2424 個

解説

(1) 200200=23⋅52{}= 2^3 \cdot 5^2 なので、正の約数の個数は

(3+1)(2+1)\displaystyle (3 + 1)(2 + 1)=12 個‾\displaystyle {}= \underline{12 \ \text{個}}

総和は

(1+2+4+8)(1+5+25)\displaystyle (1 + 2 + 4 + 8)(1 + 5 + 25)=15×31\displaystyle {}= 15 \times 31=465‾\displaystyle {}= \underline{465}

(2) 540540=22⋅33⋅5{}= 2^2 \cdot 3^3 \cdot 5 なので

(2+1)(3+1)(1+1)\displaystyle (2 + 1)(3 + 1)(1 + 1)=24 個‾\displaystyle {}= \underline{24 \ \text{個}}
自己採点：
記録を読み込み中…

問6　★

(1) 9090，126126　(2) 2424，6060，8484

上の (1)(2) のそれぞれについて、最大公約数と最小公倍数を求めなさい。

つまずいたときは：
答えを見る
答え

(1) 最大公約数 1818、最小公倍数 630630　(2) 最大公約数 1212、最小公倍数 840840

解説

(1) 9090=2⋅32⋅5{}= 2 \cdot 3^2 \cdot 5，126126=2⋅32⋅7{}= 2 \cdot 3^2 \cdot 7 です。

最大公約数\displaystyle \text{最大公約数}=2⋅32\displaystyle {}= 2 \cdot 3^2=18‾,\displaystyle {}= \underline{18},最小公倍数\displaystyle \text{最小公倍数}=2⋅32⋅5⋅7\displaystyle {}= 2 \cdot 3^2 \cdot 5 \cdot 7=630‾\displaystyle {}= \underline{630}

(2) 2424=23⋅3{}= 2^3 \cdot 3，6060=22⋅3⋅5{}= 2^2 \cdot 3 \cdot 5，8484=22⋅3⋅7{}= 2^2 \cdot 3 \cdot 7 です。3つに共通な素因数は 22 と 33 で、指数の小さいほうは 22 が 22、33 が 11 です。

最大公約数\displaystyle \text{最大公約数}=22⋅3\displaystyle {}= 2^2 \cdot 3=12‾,\displaystyle {}= \underline{12},最小公倍数\displaystyle \text{最小公倍数}=23⋅3⋅5⋅7\displaystyle {}= 2^3 \cdot 3 \cdot 5 \cdot 7=840‾\displaystyle {}= \underline{840}
自己採点：
記録を読み込み中…

問7　★

縦 9696 cm、横 168168 cm の長方形の板を、すき間も余りもなく同じ大きさの正方形に切り分ける。正方形をできるだけ大きくするとき、正方形の1辺の長さと、できる正方形の枚数を求めなさい。

つまずいたときは：
答えを見る
答え

1辺 2424 cm、2828 枚

解説

1辺 xx cm の正方形で余りなく切り分けられるのは、xx が 9696 と 168168 の公約数のときです。いちばん大きい xx は最大公約数です。

96\displaystyle 96=25⋅3,\displaystyle {}= 2^5 \cdot 3,168\displaystyle 168=23⋅3⋅7\displaystyle {}= 2^3 \cdot 3 \cdot 7

より、最大公約数は 23⋅32^3 \cdot 3=24{}= 24 です。縦に 96÷2496 \div 24=4{}= 4 枚、横に 168÷24168 \div 24=7{}= 7 枚並ぶので、枚数は 4×74 \times 7=28{}= 28 枚です。

よって 1 辺 24 cm， 28 枚‾\underline{1 \ \text{辺} \ 24 \ \text{cm}，\ 28 \ \text{枚}} です。

自己採点：
記録を読み込み中…

問8　★

(1) 3535 と 6666　(2) 9191 と 143143　(3) 111111 と 185185　(4) 6464 と 8181

上の (1)〜(4) の2数の組のうち、互いに素であるものをすべて求めなさい。

つまずいたときは：
答えを見る
答え

(1)，(4)

解説

素因数分解して、共通の素因数があるかを調べます。

(1) 3535=5⋅7{}= 5 \cdot 7，6666=2⋅3⋅11{}= 2 \cdot 3 \cdot 11 で、共通の素因数はありません。互いに素です。

(2) 9191=7⋅13{}= 7 \cdot 13，143143=11⋅13{}= 11 \cdot 13 で、1313 が共通です。

(3) 111111=3⋅37{}= 3 \cdot 37，185185=5⋅37{}= 5 \cdot 37 で、3737 が共通です。

(4) 6464=26{}= 2^6，8181=34{}= 3^4 で、共通の素因数はありません。互いに素です。

よって (1)，(4)‾\underline{(1)，(4)} です。(4) のように、どちらも素数でなくても互いに素になることがあります。

自己採点：
記録を読み込み中…

問9　★★

4けたの自然数 NN は、千の位の数字が 77、十の位の数字が 22 である。NN が 44 の倍数であり、99 の倍数でもあるとき、NN をすべて求めなさい。

つまずいたときは：
答えを見る
答え

NN=7020,{}= 7020, 7128,\ 7128, 7524,\ 7524, 7920\ 7920

解説

百の位の数字を aa、一の位の数字を bb とします（aa，bb は 00 から 99 までの整数）。

4の倍数の条件　下2けた「2b2b」が 44 の倍数なので、2020，2424，2828 のいずれかで、bb=0,{}= 0, 4,\ 4, 8\ 8 です。

9の倍数の条件　各位の数字の和 77+a{}+ a+2{}+ 2+b{}+ b=9{}= 9+a{}+ a+b{}+ b が 99 の倍数なので、aa+b{}+ b は 00，99，1818 のいずれかです。

bb ごとに aa を決めます。

  • bb=0{}= 0 のとき：aa=0{}= 0 または aa=9{}= 9 で、NN=7020,{}= 7020, 7920\ 7920
  • bb=4{}= 4 のとき：aa+b{}+ b=9{}= 9 より aa=5{}= 5（aa+b{}+ b=18{}= 18 だと aa=14{}= 14 で不適）で、NN=7524{}= 7524
  • bb=8{}= 8 のとき：aa+b{}+ b=9{}= 9 より aa=1{}= 1（aa+b{}+ b=18{}= 18 だと aa=10{}= 10 で不適）で、NN=7128{}= 7128

よって N=7020,‾\underline{\rule[-0.1944em]{0em}{0.8777em}N = 7020,} 7128,‾\underline{\rule[-0.1944em]{0em}{0.8777em}\ 7128,} 7524,‾\underline{\rule[-0.1944em]{0em}{0.8777em}\ 7524,} 7920‾\underline{\rule[-0.1944em]{0em}{0.8777em}\ 7920} です。

自己採点：
記録を読み込み中…

問10　★★

4けたの自然数 NN の千の位、百の位、十の位、一の位の数字を、順に aa，bb，cc，dd とする。(b+d)(b + d)−(a+c){}- (a + c) が 1111 の倍数ならば、NN は 1111 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

解説を参照（NN=11(91a+9b+c){}= 11(91a + 9b + c)+{(b+d)−(a+c)}{}+ \{(b + d) - (a + c)\}）

解説

NN=1000a{}= 1000a+100b{}+ 100b+10c{}+ 10c+d{}+ d です。10001000=1001{}= 1001−1{}- 1，100100=99{}= 99+1{}+ 1，1010=11{}= 11−1{}- 1 と分けると

N\displaystyle N=1001a\displaystyle {}= 1001a−a\displaystyle {}- a+99b\displaystyle {}+ 99b+b\displaystyle {}+ b+11c\displaystyle {}+ 11c−c\displaystyle {}- c+d\displaystyle {}+ d=(1001a+99b+11c)\displaystyle {}= (1001a + 99b + 11c)+(−a+b−c+d)\displaystyle {}+ (-a + b - c + d)=11(91a+9b+c)\displaystyle {}= 11(91a + 9b + c)+{(b+d)−(a+c)}\displaystyle {}+ \{(b + d) - (a + c)\}

となります（10011001=11×91{}= 11 \times 91，9999=11×9{}= 11 \times 9）。91a91a+9b{}+ 9b+c{}+ c は整数なので、第1項は 1111 の倍数です。仮定より第2項も 1111 の倍数なので、その和 NN も 1111 の倍数です。（証明終）

たとえば 72827282 は (2+2)(2 + 2)−(7+8){}- (7 + 8)=−11{}= -11 なので 1111 の倍数で、実際 72827282=11×662{}= 11 \times 662 です。本文の 33・99 の判定法が 1010=9{}= 9+1{}+ 1 を使ったのに対し、ここでは 1010=11{}= 11−1{}- 1 を使ったので、足し算が「交互の足し引き」に変わりました。

自己採点：
記録を読み込み中…

問11　★★

(1) 正の約数の個数が 1010 個である自然数のうち、最小のものを求めなさい。

(2) 自然数 NN=2a⋅3b{}= 2^a \cdot 3^b（aa，bb は自然数）の正の約数は 1212 個あり、その総和は 280280 である。NN を求めなさい。

つまずいたときは：
答えを見る
答え

(1) 4848　(2) NN=108{}= 108

解説

(1) （指数 +1+1）の積が 1010 になればよく、1010=10{}= 10 または 1010=5×2{}= 5 \times 2 です。

  • 素因数が1種類：p9p^9 の形で、最小は 292^9=512{}= 512
  • 素因数が2種類：p4qp^4q の形で、指数の大きいほうに小さい素数をあてて、最小は 24⋅32^4 \cdot 3=48{}= 48

よって最小のものは 48‾\underline{48} です。

(2) 約数の個数から (a+1)(b+1)(a + 1)(b + 1)=12{}= 12 で、aa≧1{}\geqq 1，bb≧1{}\geqq 1 なので

(a, b)\displaystyle (a,\ b)=(1, 5),\displaystyle {}= (1,\ 5), (2, 3),\displaystyle \ (2,\ 3), (3, 2),\displaystyle \ (3,\ 2), (5, 1)\displaystyle \ (5,\ 1)

のいずれかです。総和は 11+2{}+ 2+⋯{}+ \cdots+2a{}+ 2^a と 11+3{}+ 3+⋯{}+ \cdots+3b{}+ 3^b の積なので、それぞれ計算します。

  • (1, 5)(1,\ 5)：3×3643 \times 364=1092{}= 1092
  • (2, 3)(2,\ 3)：7×407 \times 40=280{}= 280
  • (3, 2)(3,\ 2)：15×1315 \times 13=195{}= 195
  • (5, 1)(5,\ 1)：63×463 \times 4=252{}= 252

総和が 280280 になるのは (a, b)(a,\ b)=(2, 3){}= (2,\ 3) のときなので、NN=22⋅33{}= 2^2 \cdot 3^3=108‾{}= \underline{108} です。

自己採点：
記録を読み込み中…

問12　★★

720720 の正の約数のうち、奇数であるものの個数と総和を求めなさい。また、偶数であるものの総和を求めなさい。

つまずいたときは：
答えを見る
答え

奇数の約数は 66 個で総和 7878、偶数の約数の総和は 23402340

解説

720720=24⋅32⋅5{}= 2^4 \cdot 3^2 \cdot 5 です。

奇数の約数　奇数の約数は素因数 22 を含まないので、3j⋅5k3^j \cdot 5^k（jj=0,{}= 0, 1,\ 1, 2\ 2，kk=0,{}= 0, 1\ 1）の形です。個数は 3×23 \times 2=6{}= 6 個、総和は

(1+3+9)(1+5)\displaystyle (1 + 3 + 9)(1 + 5)=13×6\displaystyle {}= 13 \times 6=78\displaystyle {}= 78

偶数の約数　偶数の約数は 22 を1個以上含むので、22 のかっこから 11 を除いて

(2+4+8+16)\displaystyle (2 + 4 + 8 + 16)×(1+3+9)(1+5)\displaystyle \qquad \times (1 + 3 + 9)(1 + 5)=30×78\displaystyle {}= 30 \times 78=2340\displaystyle {}= 2340

よって、奇数の約数は 6 個‾\underline{6 \text{ 個}} で総和 78‾\underline{78}、偶数の約数の総和は 2340‾\underline{2340} です。

（確かめ）約数全体の総和は (1+2+4+8+16)×78(1 + 2 + 4 + 8 + 16) \times 78=31×78{}= 31 \times 78=2418{}= 2418 で、7878+2340{}+ 2340=2418{}= 2418 と一致します。

自己採点：
記録を読み込み中…

問13　★★

2つの自然数 aa，bb（aa<b{}< b）の最大公約数が 88、最小公倍数が 240240 であるとき、aa，bb の組をすべて求めなさい。

つまずいたときは：
答えを見る
答え

(a, b)(a,\ b)=(8, 240),{}= (8,\ 240), (16, 120),\ (16,\ 120), (24, 80),\ (24,\ 80), (40, 48)\ (40,\ 48)

解説

aa=8a′{}= 8a'，bb=8b′{}= 8b'（a′a'，b′b' は互いに素な自然数で a′a'<b′{}< b'）とおきます。最小公倍数は 8a′b′8a'b' なので

8a′b′\displaystyle 8a'b'=240\displaystyle {}= 240より\displaystyle \text{より}a′b′\displaystyle a'b'=30\displaystyle {}= 30

3030=2⋅3⋅5{}= 2 \cdot 3 \cdot 5 は同じ素因数を2個以上含まないので、どう2つに分けても互いに素になります。積が 3030 で a′a'<b′{}< b' となる組は

(a′, b′)\displaystyle (a',\ b')=(1, 30),\displaystyle {}= (1,\ 30), (2, 15),\displaystyle \ (2,\ 15), (3, 10),\displaystyle \ (3,\ 10), (5, 6)\displaystyle \ (5,\ 6)

の4組で、すべて条件を満たします。よって

(a, b)=(8, 240),‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}(a,\ b) = (8,\ 240),} (16, 120),‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ (16,\ 120),} (24, 80),‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ (24,\ 80),} (40, 48)‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ (40,\ 48)}
自己採点：
記録を読み込み中…

問14　★★

2つの自然数 aa，bb（aa<b{}< b）の和が 6060、最大公約数が 66 であるとき、aa，bb の組をすべて求めなさい。

つまずいたときは：
答えを見る
答え

(a, b)(a,\ b)=(6, 54),{}= (6,\ 54), (18, 42)\ (18,\ 42)

解説

aa=6a′{}= 6a'，bb=6b′{}= 6b'（a′a'，b′b' は互いに素な自然数で a′a'<b′{}< b'）とおきます。和の条件から

6a′\displaystyle 6a'+6b′\displaystyle {}+ 6b'=60\displaystyle {}= 60より\displaystyle \text{より}a′\displaystyle a'+b′\displaystyle {}+ b'=10\displaystyle {}= 10

a′a'<b′{}< b' となる組は (1, 9)(1,\ 9)，(2, 8)(2,\ 8)，(3, 7)(3,\ 7)，(4, 6)(4,\ 6) です。(2, 8)(2,\ 8) と (4, 6)(4,\ 6) は公約数 22 をもつので除きます（この組では最大公約数が 1212 になってしまいます）。残る2組から

(a, b)=(6, 54),‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}(a,\ b) = (6,\ 54),} (18, 42)‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ (18,\ 42)}

「互いに素」の条件を確かめ忘れると、(12, 48)(12,\ 48) や (24, 36)(24,\ 36) まで答えに入れてしまうので注意しましょう。

自己採点：
記録を読み込み中…

問15　★★

(1) 50!50! が 33 で何回割り切れるか、その回数を求めなさい。

(2) 50!50! を計算すると末尾に 00 が何個続くか、その個数を求めなさい。

つまずいたときは：
答えを見る
答え

(1) 2222 回　(2) 1212 個

解説

(1) 5050 以下の、33 の倍数は 1616 個（50÷350 \div 3=16{}= 16 余り 22）、99 の倍数は 55 個、2727 の倍数は 11 個です（8181>50{}> 50）。

16\displaystyle 16+5\displaystyle {}+ 5+1\displaystyle {}+ 1=22 回‾\displaystyle {}= \underline{22 \ \text{回}}

(2) 末尾の 00 の個数は、2⋅52 \cdot 5 のペアの数です。5050 以下の、55 の倍数は 1010 個、2525 の倍数は 22 個なので（125125>50{}> 50）、55 の個数は 1010+2{}+ 2=12{}= 12 です。22 の個数は 2525+12{}+ 12+6{}+ 6+3{}+ 3+1{}+ 1=47{}= 47 で十分に多いので、ペアは 1212 組です。

よって 12 個‾\underline{12 \ \text{個}} です。

自己採点：
記録を読み込み中…

問16　★★

1212 との最小公倍数が 6060 となる自然数 nn をすべて求めなさい。

つまずいたときは：
答えを見る
答え

nn=5,{}= 5, 10,\ 10, 15,\ 15, 20,\ 20, 30,\ 30, 60\ 60

解説

6060 は nn の倍数なので、nn は 6060=22⋅3⋅5{}= 2^2 \cdot 3 \cdot 5 の約数です。そこで、00≦x{}\leqq x≦2{}\leqq 2，00≦y{}\leqq y≦1{}\leqq 1，00≦z{}\leqq z≦1{}\leqq 1 を満たす整数 xx，yy，zz を使って

n\displaystyle n=2x⋅3y⋅5z\displaystyle {}= 2^x \cdot 3^y \cdot 5^z

とおきます。1212=22⋅3{}= 2^2 \cdot 3 との最小公倍数は、素因数ごとに指数の大きいほうをとったものです。

  • 22 の指数：22 と xx の大きいほうは、xx≦2{}\leqq 2 なのでいつも 22
  • 33 の指数：11 と yy の大きいほうは、yy≦1{}\leqq 1 なのでいつも 11
  • 55 の指数：00 と zz の大きいほうが 11 になるのは、zz=1{}= 1 のとき

よって nn=5×2x⋅3y{}= 5 \times 2^x \cdot 3^y で、2x⋅3y2^x \cdot 3^y は 1212 の正の約数 11，22，33，44，66，1212 です。

n=5,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}n = 5,} 10,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 10,} 15,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 15,} 20,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 20,} 30,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 30,} 60‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 60}
自己採点：
記録を読み込み中…

問17　★★★

自然数 NN について、「NN の正の約数の個数が奇数である」ことと「NN がある自然数の2乗である」ことは同値である。このことを示しなさい。

つまずいたときは：
答えを見る
答え

解説を参照（約数の個数 (e1+1)(e2+1)⋯(ek+1)(e_1 + 1)(e_2 + 1)\cdots(e_k + 1) が奇数   ⟺  \iff 指数 eie_i がすべて偶数   ⟺  \iff NN は平方数）

解説

NN=1{}= 1 のときは、正の約数は 11 の1個（奇数）で、11=12{}= 1^2 なので成り立ちます。

NN≧2{}\geqq 2 のとき、NN=p1e1p2e2⋯pkek{}= p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}（pip_i は異なる素数、eie_i≧1{}\geqq 1）と素因数分解すると、正の約数の個数は

(e1+1)(e2+1)⋯(ek+1)(e_1 + 1)(e_2 + 1)\cdots(e_k + 1)

です。整数の積が奇数になるのは、かけた数がすべて奇数のときに限ります。よって

個数が奇数\displaystyle \text{個数が奇数}  ⟺  すべての ei\displaystyle {}\iff \text{すべての} \ e_i+1 が奇数\displaystyle {}+ 1 \ \text{が奇数}  ⟺  すべての ei が偶数\displaystyle {}\iff \text{すべての} \ e_i \ \text{が偶数}

すべての eie_i が偶数なら、NN=(p1e1/2p2e2/2⋯pkek/2)2{}= \left(p_1^{e_1/2}p_2^{e_2/2}\cdots p_k^{e_k/2}\right)^2 で、NN は自然数の2乗です。

逆に NN=m2{}= m^2 なら、mm の素因数分解を2回並べたものが NN の素因数分解になります。素因数分解はただ1通りなので、NN の指数 eie_i はすべて偶数です。（証明終）

別の見方　約数 dd と Nd\dfrac{N}{d} をペアにすると、約数は2個ずつ組になります。相手が自分自身になる（dd=Nd{}= \dfrac{N}{d}、つまり d2d^2=N{}= N）ときだけ1個余るので、個数が奇数になるのは NN が平方数のときです。たとえば 3636 の約数は 11 と 3636，22 と 1818，33 と 1212，44 と 99 がペアで、66 だけが1人で余ります。

自己採点：
記録を読み込み中…

問18　★★★

12k12^k が 1000!1000! を割り切るような最大の自然数 kk を求めなさい。

つまずいたときは：
答えを見る
答え

kk=497{}= 497

解説

12k12^k=22k⋅3k{}= 2^{2k} \cdot 3^k なので、1000!1000! に含まれる 22 と 33 の個数を数えます。

2の個数　22，44，88，……，512512 の倍数の個数を足して

500\displaystyle 500+250\displaystyle {}+ 250+125\displaystyle {}+ 125+62\displaystyle {}+ 62+31\displaystyle {}+ 31+15\displaystyle {}+ 15+7\displaystyle {}+ 7+3\displaystyle {}+ 3+1\displaystyle {}+ 1=994\displaystyle {}= 994

3の個数　33，99，2727，8181，243243，729729 の倍数の個数を足して

333\displaystyle 333+111\displaystyle {}+ 111+37\displaystyle {}+ 37+12\displaystyle {}+ 12+4\displaystyle {}+ 4+1\displaystyle {}+ 1=498\displaystyle {}= 498

12k12^k が割り切るには、2k2k≦994{}\leqq 994 かつ kk≦498{}\leqq 498 が必要十分です。2k2k≦994{}\leqq 994 より kk≦497{}\leqq 497 なので、最大の kk は 497‾\underline{497} です。

33 の個数 498498 のほうが少ないので「kk=498{}= 498」と答えたくなりますが、1212 は 22 を2個ずつ使うので、先に足りなくなるのは 22 のほうです。

自己採点：
記録を読み込み中…

問19　★★★

nn を自然数とする。

(1) 3n3n+2{}+ 2 と 2n2n+1{}+ 1 は互いに素であることを示しなさい。

(2) n2n^2+1{}+ 1 と nn+1{}+ 1 の最大公約数としてありうる値を、すべて求めなさい。

つまずいたときは：
答えを見る
答え

(1) 解説を参照（公約数 dd は 2(3n+2)2(3n + 2)−3(2n+1){}- 3(2n + 1)=1{}= 1 を割り切る）　(2) 1,1, 2\ 2（nn が偶数のとき 11、奇数のとき 22）

解説

公約数は、2数を何倍かして足したり引いたりした数も割り切ります（公式1の性質）。これを使って、数を小さくしていきます。

(1) 3n3n+2{}+ 2 と 2n2n+1{}+ 1 の正の公約数を dd とすると、dd は

2(3n+2)\displaystyle 2(3n + 2)−3(2n+1)\displaystyle {}- 3(2n + 1)=1\displaystyle {}= 1

も割り切ります。11 の正の約数は 11 だけなので dd=1{}= 1 です。正の公約数が 11 だけなので、最大公約数は 11 で、2数は互いに素です。（証明終）

(2) 最大公約数を gg とします。gg は nn+1{}+ 1 を割り切るので、(n+1)(n−1)(n + 1)(n - 1)=n2{}= n^2−1{}- 1 も割り切ります。gg は n2n^2+1{}+ 1 も割り切るので、その差

(n2+1)\displaystyle (n^2 + 1)−(n2−1)\displaystyle {}- (n^2 - 1)=2\displaystyle {}= 2

を割り切ります。よって gg=1{}= 1 または gg=2{}= 2 です。

  • nn が偶数のとき：nn+1{}+ 1 は奇数なので 22 で割り切れず、gg=1{}= 1（例：nn=2{}= 2 で 55 と 33）
  • nn が奇数のとき：nn+1{}+ 1 も n2n^2+1{}+ 1 も偶数なので、gg=2{}= 2（例：nn=3{}= 3 で 1010 と 44）

どちらも実際に起こるので、ありうる値は 1,‾\underline{\rule[-0.1944em]{0em}{0.8389em}1,} 2‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 2} です。

「最大公約数を変えずに数を小さくする」この考え方は、第2章のユークリッドの互除法につながります。

自己採点：
記録を読み込み中…

問20　★★★

nn を 22 以上の自然数とし、pp=2n{}= 2^n−1{}- 1 が素数であるとする。NN=2n−1p{}= 2^{n-1}p の正の約数の総和は 2N2N であることを示しなさい。

つまずいたときは：
答えを見る
答え

解説を参照（総和 =(1+2+⋯+2n−1)(1+p)= (1 + 2 + \cdots + 2^{n-1})(1 + p)=(2n−1)⋅2n{}= (2^n - 1) \cdot 2^n=2N{}= 2N）

解説

nn≧2{}\geqq 2 より pp=2n{}= 2^n−1{}- 1≧3{}\geqq 3 で、pp は奇数の素数なので 22 とは異なります。よって NN=2n−1⋅p{}= 2^{n-1} \cdot p が NN の素因数分解で、正の約数の総和は

(1+2+22+⋯+2n−1)(1+p)(1 + 2 + 2^2 + \cdots + 2^{n-1})(1 + p)

です。ここで SS=1{}= 1+2{}+ 2+22{}+ 2^2+⋯{}+ \cdots+2n−1{}+ 2^{n-1} とおくと

2S\displaystyle 2S−S\displaystyle {}- S=(2+22+⋯+2n)\displaystyle {}= (2 + 2^2 + \cdots + 2^n)−(1+2+⋯+2n−1)\displaystyle {}- (1 + 2 + \cdots + 2^{n-1})=2n\displaystyle {}= 2^n−1\displaystyle {}- 1

なので SS=2n{}= 2^n−1{}- 1=p{}= p です。また 11+p{}+ p=2n{}= 2^n なので、総和は

p⋅2n\displaystyle p \cdot 2^n=2⋅2n−1p\displaystyle {}= 2 \cdot 2^{n-1}p=2N\displaystyle {}= 2N

となります。（証明終）

総和 2N2N から NN 自身を除くと、「自分以外の約数の和が NN」になります。nn=2{}= 2 なら NN=6{}= 6（11+2{}+ 2+3{}+ 3=6{}= 6）、nn=3{}= 3 なら NN=28{}= 28（11+2{}+ 2+4{}+ 4+7{}+ 7+14{}+ 14=28{}= 28）です。このような数を完全数といいます（小話）。

自己採点：
記録を読み込み中…

数学小話コーナー

13年ゼミと17年ゼミ——素数の周期で現れるセミ

北アメリカの東部には、13年または17年に一度だけ、同じ地域で一斉に地上に現れるセミがいます。周期ゼミと呼ばれるなかまです。幼虫は長い年月を土の中で木の根の汁を吸って過ごし、決まった年の春から初夏にかけて、ときには1つの地域で何十億匹も羽化します。

13と17は、どちらも素数です。これは偶然なのでしょうか。よく知られた説明の1つは、「素数の周期だと、ほかの周期のものと出会いにくい」というものです。たとえば、4年ごとに数が増える天敵がいたとします。周期12年のセミは、12が4の倍数なので、地上に出るたびに毎回その天敵と出くわします。周期13年なら、出会うのは13と4の最小公倍数の52年に1度で済みます。

日本の生物学者の吉村仁さんは、別の角度から素数の意味を説明しました。氷河期の寒さで幼虫の成長が遅くなり、長い周期のセミが生まれたこと。そして、周期の違う集団どうしが同じ年に出てきて交雑すると、子の周期が乱れて数を減らしてしまうこと。素数の周期はほかの周期と重なる年が少ないので交雑を避けやすく、最後まで生き残ったのではないか、という考えです。どの説明が正しいのかは、まだ決着していません（※諸説あり）。

2024年には、ある13年ゼミの集団と、ある17年ゼミの集団が同じ年にアメリカで現れ、大きな話題になりました。この2つの集団がそろって現れたのは1803年以来、13×1713 \times 17=221{}= 221 年ぶりのことでした。

豆知識

周期が12年と18年なら、最小公倍数は36年です。ところが13年と17年は互いに素なので、最小公倍数は積の221年になります。公式6で gg=1{}= 1 とすると ll=ab{}= ab になるのと同じことです。

約数を足すと自分にもどる数——完全数

66 の、自分自身を除いた正の約数を足すと、11+2{}+ 2+3{}+ 3=6{}= 6 で元の数にもどります。2828 も 11+2{}+ 2+4{}+ 4+7{}+ 7+14{}+ 14=28{}= 28 です。このような数は、古代ギリシャの時代から完全数と呼ばれてきました。小さいほうから 66，2828，496496，81288128 と続きますが、その先は一気に大きくなり、5番目は 3355033633550336 です。

紀元前300年ごろに書かれたユークリッドの『原論』には、完全数をつくる方法が載っています。「2n2^n−1{}- 1 が素数ならば、2n−1(2n−1)2^{n-1}(2^n - 1) は完全数である」というもので、実践問題 j20 で証明するのがこの事実です（自分以外の約数の和が NN なら、約数の総和は 2N2N です）。nn=2{}= 2 なら 2⋅32 \cdot 3=6{}= 6、nn=3{}= 3 なら 4⋅74 \cdot 7=28{}= 28 が出てきます。

それから約2000年後の18世紀、オイラーが逆向きを証明しました。「偶数の完全数は、必ずユークリッドの形をしている」のです。では、奇数の完全数はあるのでしょうか。これは今も分かっていません。1つも見つかっていない一方で、存在しないという証明もない、数学で最も古い未解決問題の1つです。

2n2^n−1{}- 1 の形の素数は、17世紀フランスの修道士の名をとってメルセンヌ素数と呼ばれます。偶数の完全数を見つけることは、メルセンヌ素数を見つけることと同じです。1996年からは、世界中のボランティアのコンピュータで探す取り組みが続いていて、2024年には4100万けたを超える 21362798412^{136279841}−1{}- 1 が素数だと確かめられました。

豆知識

220220 の自分以外の約数を足すと 284284 に、284284 の自分以外の約数を足すと 220220 になります。このような2つの数を友愛数といいます。古代ギリシャのピタゴラスは、「友とは何か」と問われて「220と284のように、もう1人の自分であるものだ」と答えたと伝えられています（※諸説あり）。

1001 = 7 × 11 × 13——3けたの数を2回並べる手品

友だちに、好きな3けたの数を1つ思い浮かべてもらいます。ここでは 385385 とします。それを2回続けて書いて、6けたの数 385385385385 をつくってもらいます。

「その数を 77 で割ってみて。割り切れるはずだよ。」385385÷7385385 \div 7=55055{}= 55055 です。

「次は 1111 で割って。」55055÷1155055 \div 11=5005{}= 5005 です。

「最後に 1313 で割って。」5005÷135005 \div 13=385{}= 385 です。

どれも割り切れるうえに、最後には最初に思い浮かべた数がもどってきます。どんな3けたの数を選んでも、必ずこうなります。

種明かしは素因数分解です。3けたの数を xx とすると、それを2回並べた数は 1000x1000x+x{}+ x=1001x{}= 1001x です。そして 10011001 を素因数分解すると 7⋅11⋅137 \cdot 11 \cdot 13 です（実践問題 j03）。つまり 385385385385=385×7×11×13{}= 385 \times 7 \times 11 \times 13 なので、77，1111，1313 で順に割ると 385385 だけが残るのです。

豆知識

10001000=1001{}= 1001−1{}- 1 で、10011001 は 77 でも 1111 でも 1313 でも割り切れます。このことから、大きな数が 77（あるいは 1111，1313）の倍数かどうかを調べる方法が作れます。下から3けたずつ区切り、区切った数を交互に足し引きするのです。たとえば 12345691234569 なら、11，234234，569569 の3つに区切って 569569−234{}- 234+1{}+ 1=336{}= 336=7×48{}= 7 \times 48 となるので、12345691234569 は 77 の倍数です（実際 12345691234569=7×176367{}= 7 \times 176367）。実践問題 j10 の 1111 の判定法と同じく、「10001000 や 1010 を、割る数の倍数と ±1\pm 1 に分ける」という発想です。

厳密定義（発展）

※ここは発展ページです。本文では「素因数分解はただ1通り」を当たり前のこととして使い、そこから約数の個数や最大公約数の求め方を導きました。ここでは、その「ただ1通り」をきちんと証明し、本文の公式がどこから来るのかを確かめます。数と式の分野（第12章の厳密定義）で予告した性質も、ここで証明します。

このページでは、とくに断らないかぎり文字は整数を表します。また、次の自然数の性質を使います。

自然数の最小性　ある条件を満たす自然数が1つでもあれば、その中に最小のものがある。

11，22，33，…… と小さい順に調べていけば、いつかは条件を満たす最初の数に行き当たる、ということです。数列の分野で学ぶ数学的帰納法と、中身は同じ性質です。

割り切れるということ

定義1：整除

整数 aa，bb（bb≠0{}\neq 0）について、aa=bk{}= bk を満たす整数 kk が存在するとき、bb は aa を割り切るといい、b∣ab \mid a と書く。このとき、bb を aa の約数、aa を bb の倍数という。

b∣ab \mid a の縦棒は、分数 ab\dfrac{a}{b} のように数を表すのではなく、「割り切る」という関係を表す記号です。3∣123 \mid 12 は正しく、5∣125 \mid 12 は正しくありません。割る数を左に書くことにも注意しましょう。

定理1：整除の基本性質

(1) c∣bc \mid b かつ b∣ab \mid a ならば、c∣ac \mid a である。

(2) m∣am \mid a かつ m∣bm \mid b ならば、どんな整数 xx，yy についても m∣axm \mid ax+by{}+ by である。

(3) aa，bb が自然数で b∣ab \mid a ならば、bb≦a{}\leqq a である。

証明　(1) bb=ck{}= ck，aa=bl{}= bl となる整数 kk，ll があるので、aa=c(kl){}= c(kl) で、klkl は整数である。

(2) aa=mk{}= mk，bb=ml{}= ml とすると、axax+by{}+ by=m(kx+ly){}= m(kx + ly) で、kxkx+ly{}+ ly は整数である。

(3) aa=bk{}= bk とすると、aa>0{}> 0，bb>0{}> 0 より kk は正の整数なので kk≧1{}\geqq 1 であり、aa=bk{}= bk≧b{}\geqq b となる。（証明終）

本文の公式1の性質（倍数の和・差は倍数）は、(2) で xx=1{}= 1，yy=±1{}= \pm 1 とした場合です。実践問題 j19 で使った 2(3n+2)2(3n + 2)−3(2n+1){}- 3(2n + 1) も、(2) の形をしています。

素因数分解の存在と一意性

定義2：素数と合成数

22 以上の整数 pp で、正の約数が 11 と pp だけであるものを素数という。22 以上の整数で素数でないものを合成数という。

定理2：素因数分解の存在

22 以上の整数は、有限個の素数の積で表せる（素数そのものは、素数1個の積とみなす）。

証明　素数の積で表せない 22 以上の整数があったとして、そのうち最小のものを nn とする。nn は素数ではないので合成数であり、11 と nn 以外の正の約数 aa をもつ。nn=ab{}= ab とおく。定理1(3) と aa≠n{}\neq n より aa<n{}< n であり、aa≧2{}\geqq 2 より bb<n{}< n、aa≠n{}\neq n より bb≠1{}\neq 1 である。つまり aa，bb はどちらも 22 以上 nn 未満の整数で、nn の最小性から素数の積で表せる。すると nn=ab{}= ab も素数の積で表せることになり、矛盾する。（証明終）

定理3：素因数分解の一意性

22 以上の整数の素因数分解は、素数を並べる順序の違いを除いて、ただ1通りである。

証明　2通り以上に素因数分解できる 22 以上の整数があったとして、そのうち最小のものを nn とする。

n\displaystyle n=p1p2⋯pr\displaystyle {}= p_1p_2\cdots p_r=q1q2⋯qs\displaystyle {}= q_1q_2\cdots q_s

を、異なる2つの素因数分解とする。ただし、素数は小さい順に p1p_1≦p2{}\leqq p_2≦⋯{}\leqq \cdots≦pr{}\leqq p_r，q1q_1≦q2{}\leqq q_2≦⋯{}\leqq \cdots≦qs{}\leqq q_s と並べておく。

(i) 左右に共通の素数はない。 もし pip_i=qj{}= q_j となるものがあれば、両辺をこの素数で割った n′n'=npi{}= \dfrac{n}{p_i} について、残りの素数の並びが2つできる。元の2つの並びは異なるので、残りの並びも異なる。一方の並びが空（積が 11）で他方が空でない、ということは起こらない（素数の積は 22 以上）。両方が空なら、元の並びは同じだったことになる。よって n′n' は 22 以上 nn 未満の整数で、2通りに素因数分解でき、nn の最小性に反する。

(ii) rr≧2{}\geqq 2 かつ ss≧2{}\geqq 2 である。 もし ss=1{}= 1 なら nn=q1{}= q_1 は素数で、その 22 以上の約数 p1p_1 は q1q_1 に等しくなり、(i) に反する。rr=1{}= 1 のときも同様である。

(iii) 矛盾を導く。 (i) より p1p_1≠q1{}\neq q_1 なので、必要なら左右を入れかえて p1p_1<q1{}< q_1 とする。

m\displaystyle m=n\displaystyle {}= n−p1q2⋯qs\displaystyle {}- p_1q_2\cdots q_s

とおくと、mm は次の2通りに書ける。

m\displaystyle m=(q1−p1) q2⋯qs,\displaystyle {}= (q_1 - p_1)\,q_2\cdots q_s,m\displaystyle m=p1 (p2⋯pr−q2⋯qs)\displaystyle {}= p_1\,(p_2\cdots p_r - q_2\cdots q_s)

1つ目の式から 00<m{}< m<n{}< n である。2つ目の式の右のかっこは、mm>0{}> 0，p1p_1>0{}> 0 より正の整数なので、mm≧p1{}\geqq p_1≧2{}\geqq 2 である。mm は nn 未満なので、その素因数分解はただ1通りである。

2つ目の式の右のかっこを素因数分解して（かっこが 11 なら何もしない）p1p_1 を付け加えると、p1p_1 を含む mm の素因数分解が得られる。一方、1つ目の式で q1q_1−p1{}- p_1 を素因数分解して（11 なら何もしない）q2q_2，……，qsq_s と並べても、mm の素因数分解が得られる。分解はただ1通りなので、p1p_1 はこちらの並びにも現れる。(i) より p1p_1 は q2q_2，……，qsq_s のどれとも異なるから、p1p_1 は q1q_1−p1{}- p_1 の素因数である。

すると q1q_1−p1{}- p_1=p1k{}= p_1k（kk は自然数）と書けて、q1q_1=p1(k+1){}= p_1(k + 1) となる。22≦p1{}\leqq p_1<q1{}< q_1 なので、これは素数 q1q_1 が 11 でも自分自身でもない約数 p1p_1 をもつことを意味し、矛盾する。（証明終）

この証明は、第2章で学ぶ互除法を使わずに、「最小の反例」だけで一意性を示すものです。教科書でよく見かける証明は、互除法（または第3章の一次不定方程式）から次の定理5(1) を先に示し、それを使って一意性を導きます。道すじは違っても、たどり着く結論は同じです。

11 を素数に入れないのは、この定理を守るためでした。11 を素数とすると 66=2⋅3{}= 2 \cdot 3=1⋅2⋅3{}= 1 \cdot 2 \cdot 3 となり、ただ1通りでなくなります。

約数の形

定理4：約数の形と個数・総和

NN=p1e1p2e2⋯pkek{}= p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}（p1p_1，……，pkp_k は異なる素数、eie_i≧1{}\geqq 1）とする。

(1) 自然数 dd が NN の約数であることと、dd=p1f1p2f2⋯pkfk{}= p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}（00≦fi{}\leqq f_i≦ei{}\leqq e_i）と表せることは同値である。

(2) NN の正の約数の個数は (e1+1)(e2+1)⋯(ek+1)(e_1 + 1)(e_2 + 1)\cdots(e_k + 1) であり、総和は

(1+p1+⋯+p1e1)\displaystyle (1 + p_1 + \cdots + p_1^{e_1})×(1+p2+⋯+p2e2)\displaystyle \qquad \times (1 + p_2 + \cdots + p_2^{e_2})×⋯×(1+pk+⋯+pkek)\displaystyle \qquad \times \cdots \times (1 + p_k + \cdots + p_k^{e_k})

である。

証明　(1)（⟸\Longleftarrow）NN=d⋅p1e1−f1⋯pkek−fk{}= d \cdot p_1^{e_1 - f_1}\cdots p_k^{e_k - f_k} で、右の積は自然数である。

（⟹\Longrightarrow）NN=dc{}= dc（cc は自然数）とする。dd と cc をそれぞれ素因数分解して並べると（11 なら何も並べない）、NN の素因数分解が1つ得られる。定理3 より、これは p1e1⋯pkekp_1^{e_1}\cdots p_k^{e_k} と同じ並びである。したがって dd の素因数は p1p_1，……，pkp_k のいずれかで、dd に含まれる pip_i の個数 fif_i は eie_i 以下である。

(2) (1) より、正の約数は指数の組 (f1, …, fk)(f_1,\ \ldots,\ f_k) で表され、定理3 より異なる組は異なる数を表す。fif_i の選び方は 00 から eie_i までの eie_i+1{}+ 1 通りずつなので、個数はその積である。総和の式を展開すると、各かっこから1つずつ選んだ積 p1f1⋯pkfkp_1^{f_1}\cdots p_k^{f_k} が、すべての組についてちょうど1回ずつ現れる。（証明終）

本文の例題3(2) で使った「自然数の2乗は、素因数分解の指数がすべて偶数」も、定理3 からしたがいます。m2m^2 の素因数分解は mm の素因数分解を2回並べたものなので、どの素数も偶数個ずつ現れるからです。

素数・互いに素な数と積

ここからは、自然数 xx と素数 pp について、xx の素因数分解に現れる pp の個数を vp(x)v_p(x) と書きます（pp が現れないときや xx=1{}= 1 のときは 00）。定理3 より vp(x)v_p(x) はただ1つに決まり、次の2つが成り立ちます。

定理5：素数・互いに素な数と積

aa，bb，cc を自然数とする。

(1) 素数 pp が abab を割り切るならば、pp は aa または bb を割り切る。

(2) aa と bb が互いに素で、a∣bca \mid bc ならば、a∣ca \mid c である。

(3) aa と bb が互いに素で、a∣ca \mid c かつ b∣cb \mid c ならば、ab∣cab \mid c である。

証明　(1) p∣abp \mid ab より vp(ab)v_p(ab)≧1{}\geqq 1、つまり vp(a)v_p(a)+vp(b){}+ v_p(b)≧1{}\geqq 1 なので、vp(a)v_p(a)，vp(b)v_p(b) の少なくとも一方は 11 以上である。

(2) aa の素因数 pp を1つとる。pp が bb も割り切ると pp が aa，bb の公約数になり、互いに素であることに反するので、vp(b)v_p(b)=0{}= 0 である。a∣bca \mid bc より

vp(a)\displaystyle v_p(a)≦vp(bc)\displaystyle {}\leqq v_p(bc)=vp(b)\displaystyle {}= v_p(b)+vp(c)\displaystyle {}+ v_p(c)=vp(c)\displaystyle {}= v_p(c)

aa の素因数でない素数 pp については vp(a)v_p(a)=0{}= 0≦vp(c){}\leqq v_p(c) である。すべての素数で vp(a)v_p(a)≦vp(c){}\leqq v_p(c) なので、a∣ca \mid c である。

(3) cc=ak{}= ak（kk は自然数）とおくと、b∣akb \mid ak で、bb と aa は互いに素なので、(2) より b∣kb \mid k である。kk=bl{}= bl とすると cc=abl{}= abl となり、ab∣cab \mid c である。（証明終）

(1) は『原論』第7巻にも載っている古い定理で、ユークリッドの補題と呼ばれます。(3) は、本文の公式2で使った「22 の倍数かつ 33 の倍数なら 66 の倍数」の根拠です（aa=2{}= 2，bb=3{}= 3）。44 と 66 のように互いに素でない場合は成り立たず、1212 は 44 の倍数かつ 66 の倍数ですが、2424 の倍数ではありません。

数と式 第12章の厳密定義 定理3（有理数の解の候補）の証明では、「pp と qq が互いに素で、pp が a0qna_0q^n を割り切るならば、pp は a0a_0 を割り切る」ことを使いました。符号は割り切れるかどうかに関係しないので、絶対値をとって自然数で考えます。qnq^n の素因数は qq の素因数だけなので、pp と qnq^n も互いに素です。そこで (2) を aa=∣p∣{}= |p|，bb=qn{}= q^n，cc=∣a0∣{}= |a_0| として使えば、∣p∣∣∣a0∣|p| \mid |a_0| が得られます。これで、あのときの約束が果たせました。

最大公約数と最小公倍数

定理6：最大公約数・最小公倍数と積

自然数 aa，bb の最大公約数を gg、最小公倍数を ll とすると、すべての素数 pp について

vp(g)\displaystyle v_p(g)=min⁡{vp(a), vp(b)},\displaystyle {}= \min\{v_p(a),\ v_p(b)\},vp(l)\displaystyle v_p(l)=max⁡{vp(a), vp(b)}\displaystyle {}= \max\{v_p(a),\ v_p(b)\}

である。ここで min⁡{x, y}\min\{x,\ y\} は xx，yy の小さいほう、max⁡{x, y}\max\{x,\ y\} は大きいほうを表す。さらに、aa，bb の正の公約数はすべて gg の約数、正の公倍数はすべて ll の倍数であり

ab\displaystyle ab=gl\displaystyle {}= gl

が成り立つ。

証明　すべての素数 pp について vp(G)v_p(G)=min⁡{vp(a), vp(b)}{}= \min\{v_p(a),\ v_p(b)\} となる自然数を GG とする（aa，bb の素因数以外では右辺が 00 なので、GG は有限個の素数の積として定まる）。定理4(1) より、自然数 dd が aa，bb の公約数であることは、すべての pp で vp(d)v_p(d)≦vp(a){}\leqq v_p(a) かつ vp(d)v_p(d)≦vp(b){}\leqq v_p(b)、つまり vp(d)v_p(d)≦vp(G){}\leqq v_p(G) であることと同値で、これは d∣Gd \mid G と同値である。とくに GG 自身は公約数であり、どの正の公約数 dd も d∣Gd \mid G を満たすので、定理1(3) より dd≦G{}\leqq G である。よって gg=G{}= G で、正の公約数はすべて gg の約数である。

同様に、vp(L)v_p(L)=max⁡{vp(a), vp(b)}{}= \max\{v_p(a),\ v_p(b)\} となる自然数 LL をとると、自然数 mm が aa，bb の公倍数であることは L∣mL \mid m と同値である。LL 自身は公倍数で、どの正の公倍数 mm についても LL≦m{}\leqq m なので、ll=L{}= L であり、正の公倍数はすべて ll の倍数である。

最後に、2つの数 xx，yy について min⁡{x, y}\min\{x,\ y\}+max⁡{x, y}{}+ \max\{x,\ y\}=x{}= x+y{}+ y なので、すべての素数 pp で

vp(gl)\displaystyle v_p(gl)=vp(g)\displaystyle {}= v_p(g)+vp(l)\displaystyle {}+ v_p(l)=vp(a)\displaystyle {}= v_p(a)+vp(b)\displaystyle {}+ v_p(b)=vp(ab)\displaystyle {}= v_p(ab)

となる。素因数分解がまったく同じ2つの自然数は等しいので、abab=gl{}= gl である。（証明終）

本文の公式5（指数の小さいほう・大きいほう）と公式6（abab=gl{}= gl）は、この定理をことばで言いかえたものです。

この章の証明は、すべて定理3（素因数分解の一意性）の上に立っています。ただ、この方法には弱点があります。数と式 第2章の小話で見たように、大きな数の素因数分解はコンピュータでも非常に難しいのです。第2章では、素因数分解をしないで最大公約数を求める「ユークリッドの互除法」を学び、第3章では、それを使って一次不定方程式を解きます。

この章の学習が終わったら

学習完了テストを受ける