章末問題

まず、$180$ を素因数分解します。素因数分解とは、整数をこれ以上分解できない素数(1とその数自身以外に約数を持たない、2以上の整数)だけの積の形に表すことです。

$180 = 2 \times 90 = 2 \times 2 \times 45 = 2 \times 2 \times 3 \times 15 = 2 \times 2 \times 3 \times 3 \times 5$

これを指数を使って整理すると、次のようになります。

$180 = 2^2 \times 3^2 \times 5^1$

約数の個数を求める

一般に、整数 $N$ が $N = p^a \times q^b \times r^c$(ただし $p, q, r$ は異なる素数)と素因数分解できるとき、$N$ の正の約数の個数は次の式で求められます。

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

これは、$p$ を $0$ 個から $a$ 個までの $(a+1)$ 通り、$q$ を $0$ 個から $b$ 個までの $(b+1)$ 通り、$r$ を $0$ 個から $c$ 個までの $(c+1)$ 通り、それぞれ自由に選んで掛け合わせることで、すべての約数を重複なく作れるからです。

$180 = 2^2 \times 3^2 \times 5^1$ なので、指数はそれぞれ $2, 2, 1$ です。よって約数の個数は、

$(2+1)(2+1)(1+1) = 3 \times 3 \times 2 = 18$

答えは $18$ 個 です。

約数の総和を求める

約数の総和は、それぞれの素因数について「$0$ 乗から最大の指数乗までを足したもの」を作り、それらを掛け合わせることで求められます。これは、上で説明した「約数を1つずつ作る」という考え方を、掛け算ではなく足し算に置き換えたものです。

$2^2$ の部分については $2^0+2^1+2^2 = 1+2+4 = 7$

$3^2$ の部分については $3^0+3^1+3^2 = 1+3+9 = 13$

$5^1$ の部分については $5^0+5^1 = 1+5 = 6$

これらを掛け合わせます。

$7 \times 13 \times 6$

まず $7 \times 13$ を計算します。

$7 \times 13 = 91$

次に $91 \times 6$ を計算します。

$91 \times 6 = 546$

答えは $546$ です。

まず、$84$ と $126$ をそれぞれ素因数分解します。

$84 = 2 \times 42 = 2 \times 2 \times 21 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7$

$126 = 2 \times 63 = 2 \times 3 \times 21 = 2 \times 3 \times 3 \times 7 = 2 \times 3^2 \times 7$

最大公約数を求める

最大公約数は、両方の素因数分解に共通して現れる素因数を、それぞれ「指数が小さい方」の個数だけ取り出して掛け合わせることで求まります。

• $2$ について:$84$ では $2^2$、$126$ では $2^1$ なので、小さい方の $2^1$ を採用します。
• $3$ について:$84$ では $3^1$、$126$ では $3^2$ なので、小さい方の $3^1$ を採用します。
• $7$ について:どちらも $7^1$ なので、そのまま $7^1$ を採用します。

したがって、

$\text{最大公約数} = 2^1 \times 3^1 \times 7^1 = 2 \times 3 \times 7$

$2 \times 3 = 6$、さらに $6 \times 7 = 42$ なので、最大公約数は $42$ です。

最小公倍数を求める

最小公倍数は、両方の素因数分解に現れるすべての素因数を、それぞれ「指数が大きい方」の個数だけ取り出して掛け合わせることで求まります。

• $2$ について:大きい方の $2^2$ を採用します。
• $3$ について:大きい方の $3^2$ を採用します。
• $7$ について:$7^1$ を採用します。

したがって、

$\text{最小公倍数} = 2^2 \times 3^2 \times 7 = 4 \times 9 \times 7$

$4 \times 9 = 36$、さらに $36 \times 7 = 252$ なので、最小公倍数は $252$ です。

検算

2つの自然数 $a, b$ については、次の関係が必ず成り立ちます(最大公約数と最小公倍数の積は、もとの2数の積に等しい)。

$a \times b = (\text{最大公約数}) \times (\text{最小公倍数})$

実際に確かめてみましょう。左辺は $84 \times 126 = 10584$ です。右辺は $42 \times 252 = 10584$ です。両辺が一致するので、答えは正しいと確認できます。

ユークリッドの互除法は、「$2$ つの自然数 $a, b$($a > b$)について、$a$ を $b$ で割った余りを $r$ とすると、$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい」という性質を使って、割る数をどんどん小さくしていく方法です。余りが $0$ になったとき、そのときの割る数が最大公約数です。

ステップ1

$323$ を $221$ で割ります。

$323 = 221 \times 1 + 102$

ステップ2

割る数だった $221$ を、今出た余り $102$ で割ります。

$221 = 102 \times 2 + 17$

($102 \times 2 = 204$ で、$221 - 204 = 17$ です。)

ステップ3

割る数だった $102$ を、今出た余り $17$ で割ります。

$102 = 17 \times 6 + 0$

($17 \times 6 = 102$ なので、余りはちょうど $0$ になります。)

余りが $0$ になったので、ここで計算は終わりです。最後に割る数として使った数、つまり $17$ が最大公約数です。

答えは $17$ です。

検算

$323 \div 17 = 19$ なので $323 = 17 \times 19$、また $221 \div 17 = 13$ なので $221 = 17 \times 13$ です。どちらも $17$ で割り切れており、$19$ と $13$ はこれ以上共通の約数を持たないので、たしかに $17$ が最大公約数だとわかります。

ステップ1:ユークリッドの互除法で最大公約数を確認する

$1$次不定方程式 $ax+by=c$($a,b,c$ は整数の定数、$x,y$ が整数解を求めたい未知数)が整数解を持つのは、$a$ と $b$ の最大公約数が $c$ を割り切るときです。まず $34$ と $21$ の最大公約数を確認します。

$34 = 21 \times 1 + 13$

$21 = 13 \times 1 + 8$

$13 = 8 \times 1 + 5$

$8 = 5 \times 1 + 3$

$5 = 3 \times 1 + 2$

$3 = 2 \times 1 + 1$

$2 = 1 \times 2 + 0$

余りが $0$ になったときの割る数は $1$ なので、$34$ と $21$ の最大公約数は $1$ です。$1$ はどんな整数も割り切るので、方程式 $34x+21y=1$ は整数解を持ちます。

ステップ2:割り算の式を逆にたどって、$1$ を $34$ と $21$ の組み合わせで表す

上で作った式を、下から順番に「$1=\cdots$」の形に変形しながら、$34$ と $21$ だけで表せるように代入していきます。これを逆代入(ぎゃくだいにゅう)と呼びます。

下から2番目の式 $3 = 2 \times 1 + 1$ を、$1=$ の形に直します。

$1 = 3 - 2 \times 1$

次に、$5 = 3\times1+2$ という式を $2 = 5 - 3\times1$ の形に直し、上の式の $2$ に代入します。

$1 = 3 - (5 - 3 \times 1) \times 1 = 3 - 5 + 3 = 2 \times 3 - 5$

次に、$8 = 5\times1+3$ という式を $3 = 8 - 5\times1$ の形に直し、上の式の $3$ に代入します。

$1 = 2 \times (8 - 5 \times 1) - 5 = 2 \times 8 - 2 \times 5 - 5 = 2 \times 8 - 3 \times 5$

次に、$13 = 8\times1+5$ という式を $5 = 13 - 8\times1$ の形に直し、上の式の $5$ に代入します。

$1 = 2 \times 8 - 3 \times (13 - 8 \times 1) = 2 \times 8 - 3 \times 13 + 3 \times 8 = 5 \times 8 - 3 \times 13$

次に、$21 = 13\times1+8$ という式を $8 = 21 - 13\times1$ の形に直し、上の式の $8$ に代入します。

$1 = 5 \times (21 - 13 \times 1) - 3 \times 13 = 5 \times 21 - 5 \times 13 - 3 \times 13 = 5 \times 21 - 8 \times 13$

最後に、$34 = 21\times1+13$ という式を $13 = 34 - 21\times1$ の形に直し、上の式の $13$ に代入します。

$1 = 5 \times 21 - 8 \times (34 - 21 \times 1) = 5 \times 21 - 8 \times 34 + 8 \times 21 = 13 \times 21 - 8 \times 34$

整理すると、

$1 = (-8) \times 34 + 13 \times 21$

これは $34x+21y=1$ の形と見比べると、$x=-8, y=13$ が1つの解になっていることを示しています。

検算:$34 \times (-8) + 21 \times 13 = -272 + 273 = 1$ となり、たしかに成り立ちます。

ステップ3:すべての整数解(一般解)を求める

$x=-8, y=13$ を1組の解(これを特殊解と呼びます)として、他のすべての整数解を表す式を作ります。

もとの方程式 $34x+21y=1$ と、特殊解が満たす式 $34\times(-8)+21\times13=1$ の両辺をそれぞれ引き算します。

$34x + 21y - \{34\times(-8) + 21\times13\} = 1 - 1$

$34\{x-(-8)\} + 21(y-13) = 0$

$34(x+8) = -21(y-13)$

ここで、$34$ と $21$ の最大公約数は $1$(問題文の準備で確認済み)なので、$34$ と $21$ は互いに素(共通の約数が $1$ しかない)です。$34(x+8)$ が $21$ の倍数になるためには、$34$ と $21$ が互いに素である以上、$(x+8)$ 自身が $21$ の倍数でなければなりません。そこで、整数 $k$ を使って、

$x+8 = 21k$

と表せます。これを $34(x+8) = -21(y-13)$ に代入すると、

$34 \times 21k = -21(y-13)$

両辺を $21$ で割ると、

$34k = -(y-13)$

$y = 13 - 34k$

以上をまとめると、すべての整数解は、

$x = -8+21k, \quad y = 13-34k \quad (k \text{ は任意の整数})$

と表せます。

検算($k=1$ の場合):$x=-8+21=13$、$y=13-34=-21$ です。$34\times13+21\times(-21) = 442-441=1$ となり、たしかに成り立ちます。

前半:$100$ を3進法で表す

n進法(nしんほう)とは、数を表すときに「$n$ 個集まったら位が1つ繰り上がる」というルールで表す方法です。ふだん私たちが使っている10進法は $n=10$ の場合にあたります。10進法の数を3進法(3個集まったら繰り上がる)で表すには、その数を3で割り続け、出てきた余りを下から順に並べます。

$100 \div 3 = 33 \; \text{余り} \; 1$

$33 \div 3 = 11 \; \text{余り} \; 0$

$11 \div 3 = 3 \; \text{余り} \; 2$

$3 \div 3 = 1 \; \text{余り} \; 0$

$1 \div 3 = 0 \; \text{余り} \; 1$

商が $0$ になったら計算をやめます。出てきた余りを、下(最後に出たもの)から上(最初に出たもの)へ順番に並べると、$1, 0, 2, 0, 1$ となります。

したがって、

$100 = 10201_{(3)}$

検算:3進法の各位は、右から $3^0, 3^1, 3^2, 3^3, 3^4$ の位を表します。$10201_{(3)}$ を10進法に戻すと、

$1\times3^4 + 0\times3^3 + 2\times3^2 + 0\times3^1 + 1\times3^0$

$= 1\times81 + 0\times27 + 2\times9 + 0\times3 + 1\times1$

$= 81+0+18+0+1 = 100$

もとの数と一致するので、正しく変換できています。

後半:$2102_{(3)}$ を10進法で表す

3進法の数を10進法に直すには、各位の数字に、その位が表す $3$ のべき乗を掛けて、すべて足し合わせます。$2102_{(3)}$ は右から順に $2, 0, 1, 2$ という数字が並んでいるので、

$2102_{(3)} = 2\times3^3 + 1\times3^2 + 0\times3^1 + 2\times3^0$

それぞれ計算すると、

$2\times3^3 = 2\times27 = 54$

$1\times3^2 = 1\times9 = 9$

$0\times3^1 = 0$

$2\times3^0 = 2\times1 = 2$

これらをすべて足します。

$54+9+0+2 = 65$

答えは $65$ です。

方針を立てる

$a$ と $b$ の最大公約数が $6$ であるということは、$a$ と $b$ はどちらも $6$ の倍数であり、しかも $6$ より大きい共通の約数を持たない、ということです。そこで、整数 $p, q$ を使って、

$a = 6p, \quad b = 6q$

と表すことにします。ここで、$p$ と $q$ は互いに素(最大公約数が $1$)である必要があります。もし $p$ と $q$ に $1$ より大きい共通の約数があると、$a$ と $b$ の最大公約数が $6$ より大きくなってしまい、条件に合わなくなるからです。

最小公倍数の条件を使う

問題2で確認したとおり、2つの自然数については「最大公約数 $\times$ 最小公倍数 $=$ 2数の積」という関係が成り立ちます。これを使うと、

$6 \times 180 = a \times b = 6p \times 6q = 36pq$

左辺を計算すると $6\times180=1080$ なので、

$1080 = 36pq$

両辺を $36$ で割ると、

$pq = 30$

条件を満たす $(p, q)$ を探す

$p$ と $q$ は、積が $30$ になる自然数の組で、かつ互いに素、さらに $a

$30 = 1\times30 = 2\times15 = 3\times10 = 5\times6$

これら4組について、それぞれ互いに素かどうかを確認します。$30=2\times3\times5$ であり、これは同じ素数を2つ以上持たない数(平方因子を持たない数)なので、$30$ をどのように2つの自然数の積に分けても、その2数は必ず互いに素になります。実際に確認すると、

• $(p,q)=(1,30)$:最大公約数は $1$
• $(p,q)=(2,15)$:最大公約数は $1$
• $(p,q)=(3,10)$:最大公約数は $1$
• $(p,q)=(5,6)$:最大公約数は $1$

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

$(a, b)$ に戻す

$a=6p, b=6q$ に、それぞれの $(p,q)$ を代入します。

$(p,q)=(1,30) \; \Rightarrow \; (a,b)=(6, 180)$

$(p,q)=(2,15) \; \Rightarrow \; (a,b)=(12, 90)$

$(p,q)=(3,10) \; \Rightarrow \; (a,b)=(18, 60)$

$(p,q)=(5,6) \; \Rightarrow \; (a,b)=(30, 36)$

答えは $(a,b)=(6,180),\ (12,90),\ (18,60),\ (30,36)$ の4組 です。

検算(例として $(18,60)$):$18=2\times3^2$、$60=2^2\times3\times5$ なので、最大公約数は $2\times3=6$、最小公倍数は $2^2\times3^2\times5=180$ です。たしかに条件どおりになっています。

方針を立てる

$x^2+y^2=25$ を満たす整数 $x, y$ を探します。$x^2 \geq 0$ かつ $y^2 \geq 0$ なので、$x^2 \leq 25$ でなければなりません。整数 $x$ でこれを満たすのは、

$x = -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5$

の11通りです。それぞれの $x$ について、$y^2=25-x^2$ を計算し、その値が(整数の2乗である)平方数になっているかどうかを調べます。

各 $x$ について調べる

$x=0$ のとき:$y^2=25-0=25=5^2$ なので、$y=\pm5$(平方数なので整数解あり)。

$x=\pm1$ のとき:$y^2=25-1=24$。$24$ は $4^2=16$ と $5^2=25$ の間にあり、どの整数の2乗にもならないので、整数解なし。

$x=\pm2$ のとき:$y^2=25-4=21$。$21$ も同様に平方数ではないので、整数解なし。

$x=\pm3$ のとき:$y^2=25-9=16=4^2$ なので、$y=\pm4$(整数解あり)。

$x=\pm4$ のとき:$y^2=25-16=9=3^2$ なので、$y=\pm3$(整数解あり)。

$x=\pm5$ のとき:$y^2=25-25=0=0^2$ なので、$y=0$(整数解あり)。

すべての格子点をまとめる

以上をすべて書き出すと、次の12個の点が条件を満たします。

$(5,0),\ (-5,0),\ (0,5),\ (0,-5)$

$(3,4),\ (3,-4),\ (-3,4),\ (-3,-4)$

$(4,3),\ (4,-3),\ (-4,3),\ (-4,-3)$

答えは 上記の12個の点 です。

検算(例として $(4,-3)$):$4^2+(-3)^2=16+9=25$ となり、たしかに円の方程式を満たしています。

因数分解する

$n^2-1$ は、2乗の差の形をしているので、次のように因数分解できます。

$n^2-1=(n-1)(n+1)$

素数になるための条件を考える

素数とは、正の約数がちょうど2個(1と自分自身)しかない整数のことです。つまり、素数を2つの正の整数の積として表す方法は、「$1\times(\text{その素数自身})$」の1通りしかありません。

$(n-1)(n+1)$ がこの形で素数になるためには、2つの因数 $(n-1)$ と $(n+1)$ のうち、一方が $1$ でなければなりません。

$n$ は自然数($n=1,2,3,\dots$)なので、$n+1 \geq 2$ が常に成り立ちます。つまり $(n+1)$ が $1$ になることはありません。したがって、$1$ になり得るのは $(n-1)$ の方だけです。

$n-1=1$

これを解くと、

$n=2$

$n=2$ 以外の場合を確認する

• $n=1$ のとき:$n-1=0$ なので、$(n-1)(n+1)=0\times2=0$ です。$0$ は素数ではありません(素数は2以上の整数と定義されているため)。
• $n \geq 3$ のとき:$n-1 \geq 2$ かつ $n+1 \geq 4$ となり、両方の因数が $2$ 以上になります。$2$ 以上の整数どうしの積は、その2つの数自身を約数として持つため、必ず合成数(素数でない2以上の整数)になり、素数にはなりません。

したがって、条件を満たすのは $n=2$ だけです。

答えを確認する

$n=2$ のとき、$n^2-1=2^2-1=4-1=3$ です。$3$ はたしかに素数です。

答えは $n=2$(このとき $n^2-1=3$)です。