整数せいすうの性質せいしつ — 約数やくすう・倍数ばいすう・ユークリッドの互除法じょほう・n進しん法ほう

この章しょうで学まなぶこと

数かずAの整数せいすう分野ぶんやです。 約数やくすう・倍数ばいすうの性質せいしつから、 互除法じょほう・n進しん法ほうまでを扱あつかいます。

• 素因数分解そいんすうぶんかいと約数やくすうの個数こすう
• 最大公約数さいだいこうやくすう (GCD)・最小公倍数さいしょうこうばいすう (LCM)
• ユークリッドの互除法ゆーくりっどのごじょほう
• n進法エヌしんほう (2進しん法ほう・10進しん法ほうの変換へんかん)

ポイント: 素因数分解そいんすうぶんかいができれば、 約数やくすうの個数こすう・最大公約数さいだいこうやくすう・最小公倍数さいしょうこうばいすうがすべて求もとまります。 大おおきな数かずの最大公約数さいだいこうやくすうはユークリッドの互除法ゆーくりっどのごじょほうが速はやいです。

1. 素因数そいんすう分解ぶんかいと約数やくすうの個数こすう

自然しぜん数すう$N$ を素因数そいんすう分解ぶんかいして $N=p^a{q}^b{r}^c\cdots$ となるとき、 約数やくすうの個数こすうは

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

例題れいだい1: $72$ の正せいの約数やくすうの個数こすうを求もとめなさい。

解答かいとう: $72=2^3\times 3^2$。 約数やくすうの個数こすうは $(3+1)(2+1)=4\times 3=12$個。 検算けんざん: 約数やくすうを書かき出だすと $1,2,3,4,6,8,9,12,18,24,36,72$ で12個こ。 一致いっち。

2. 最大公約数さいだいこうやくすう・最小公倍数さいしょうこうばいすう

2数すうを素因数そいんすう分解ぶんかいし、 共通きょうつうの素因数そいんすうの 小ちいさいほうの指数しすう をかけると最大公約数さいだいこうやくすう、 大おおきいほうの指数しすう をかけると最小公倍数さいしょうこうばいすうになります。 また、

$\left(最大公約数\right)\times \left(最小公倍数\right)=\left(2数の積\right)$

例題れいだい2: $24$ と $36$ の最大公約数さいだいこうやくすうと最小公倍数さいしょうこうばいすうを求もとめなさい。

解答かいとう: $24=2^3\times 3$、 $36=2^2\times 3^2$。 最大公約数さいだいこうやくすう$=2^2\times 3=12$。 最小公倍数さいしょうこうばいすう$=2^3\times 3^2=72$。 検算けんざん: $12\times 72=864=24\times 36$。 一致いっち。

3. ユークリッドの互除法じょほう

2数$a,b$ ($a>b$) の最大公約数さいだいこうやくすうは、 $a$ を $b$ で割わった余あまりを $r$ とすると 「$b$ と $r$ の最大公約数さいだいこうやくすう」 に等ひとしくなります。 これを余あまりが $0$ になるまでくり返かえします。

例題れいだい3: $\gcd (252,105)$ を互除法じょほうで求もとめなさい。

解答かいとう: $252=105\times 2+42$ $105=42\times 2+21$ $42=21\times 2+0$ 余あまりが $0$ になる直前ちょくぜんの割われる数$21$ が最大公約数さいだいこうやくすう。 検算けんざん: $252=21\times 12$、 $105=21\times 5$ で $12$ と $5$ は互たがいに素もと。 よって $\gcd =21$ で一致いっち。

4. n進しん法ほう

ふだん使つかう数かずは10進法じっしんほうです。 コンピュータでは2進法にしんほうがよく使つかわれます。 2進しん法ほうは $0$ と $1$ だけで、 各位かくいは $2$ のべき乗じょうを表あらわします。

例題れいだい4: 2進しん法ほうの ${1101}_{\left(2\right)}$ を10進しん法ほうで表あらわしなさい。

解答かいとう: ${1101}_{\left(2\right)}=1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0=8+4+0+1=13$。

例題れいだい5: 10進しん法ほうの $25$ を2進しん法ほうで表あらわしなさい。

解答かいとう: $25$ をくり返かえし $2$ で割わり、 余あまりを下したから並ならべます。 $25÷2=12$余あまり $1$ / $12÷2=6$余あまり $0$ / $6÷2=3$余あまり $0$ / $3÷2=1$余あまり $1$ / $1÷2=0$余あまり $1$。 下したから並ならべて ${11001}_{\left(2\right)}$。 検算けんざん: ${11001}_{\left(2\right)}=16+8+0+0+1=25$。 一致いっち。

どう問とわれるか

• 約数やくすうの個数こすうは 素因数そいんすう分解ぶんかい → 指数しすう +1 の積せき がそのまま問とわれます。
• 最大公約数さいだいこうやくすう・最小公倍数さいしょうこうばいすうは素因数そいんすう分解ぶんかいか互除法じょほう。 大おおきな数かずは互除法じょほうが速はやい。
• n進しん法ほうは 「n進しん → 10進しん」 は各位かくいの重みおもみをかけて和わ、 「10進しん → n進しん」 はくり返かえし割わって余あまりを下したから並ならべる、 と方向ほうこうで手順てじゅんが違ちがいます。

よくまちがえるところ

整数せいすう分野ぶんやは手順てじゅんそのものは短みじかいのに、 数かぞえる向むき と 指数しすうの取とり方かた でまちがえます。

まちがい	例れい	直なおし方かた
約数やくすうの個数こすうで指数しすうをそのままかける	72 = 2³ × 3² で 3 × 2 = 6 個ことする	(3+1)(2+1) = 12 個こ
互除法じょほうで最後さいごの余あまり 0 を答えこたえにする	252 と 105 の最大公約数さいだいこうやくすうを 0 とする	余あまりが 0 になる直前ちょくぜんの割われる数かず 21
最小公倍数さいしょうこうばいすうで小ちいさいほうの指数しすうを取とる	24 = 2³ × 3、 36 = 2² × 3² で 2² × 3 = 12 とする	大おおきいほうの指数しすうで 2³ × 3² = 72
10進しん法ほうから n進しん法ほうで余あまりを上うえから並ならべる	25 を2進しん法ほうで 10011 とする	下したから並ならべて 11001

いちばん多おおいのは 約数やくすうの個数こすうで指数しすうに 1 をたし忘わすれること です。 72 = 2³ × 3² の約数やくすうは、 2 を 0 個こ・1 個こ・2 個こ・3 個このどれかと、 3 を 0 個こ・1 個こ・2 個このどれか組み合わせくみあわせてつくります。 2 の使つかい方かたが 4 通とおり、 3 の使つかい方かたが 3 通とおりなので 4 × 3 = 12 個こです。 「0 個こ使つかう」 場合ばあいがあるから 1 をたす、 と理由りゆうごと覚おぼえると忘わすれません。

n進しん法ほうの変換へんかん手順てじゅん

向むき	やること	例れい
n進しん法ほうから10進しん法ほうへ	各位かくいの数かずに位くらいの重みおもみをかけて全部ぜんぶたす	1101 (2進しん法ほう) = 8 + 4 + 0 + 1 = 13
10進しん法ほうから n進しん法ほうへ	商しょうが 0 になるまで n で割わり、 余あまりを下したから並ならべる	25 = 11001 (2進しん法ほう)

2進しん法ほうの位くらいの重みおもみは次つぎのとおりです。

位くらい	2⁴	2³	2²	2¹	2⁰
10進しん法ほうでの値あたい	16	8	4	2	1

25 を2進しん法ほうに直なおすときは、 次つぎのように割わり算ざんをならべます。

順番じゅんばん	計算けいさん	余あまり
1	25 ÷ 2 = 12	1
2	12 ÷ 2 = 6	0
3	6 ÷ 2 = 3	0
4	3 ÷ 2 = 1	1
5	1 ÷ 2 = 0	1

余あまりを下したから読よんで 11001。 検算けんざんは 16 + 8 + 1 = 25 で一致いっちします。

自分じぶんでチェック

• 約数やくすうの個数こすうが (各かく指数しすう + 1) の積せきになる理由りゆうを説明せつめいできる
• 最大公約数さいだいこうやくすうは小ちいさいほうの指数しすう、 最小公倍数さいしょうこうばいすうは大おおきいほうの指数しすうと言いえる
• 互除法じょほうで余あまりが 0 になる直前ちょくぜんの割われる数かずが答えこたえだと言いえる
• 10進しん法ほうから n進しん法ほうへは余あまりを下したから並ならべると言いえる
• n進しん法ほうから10進しん法ほうへは位くらいの重みおもみをかけてたすと言いえる

まとめ

• 約数やくすうの個数こすう = (各かく指数しすう +1) の積せき
• 最大公約数さいだいこうやくすう × 最小公倍数さいしょうこうばいすう = 2数すうの積せき
• ユークリッドの互除法ゆーくりっどのごじょほう: 余あまりが $0$ になる直前ちょくぜんの割われる数かずが GCD
• n進しん → 10進しんは重みおもみの和わ、 10進しん → n進しんはくり返かえし割わって余あまりを下したから

次じ章しょうでは、 データの分析ぶんせきと二に次じ (数理すうり技能ぎのう) 対策たいさく を学まなび、 仕上しあげをします。