整数せいすうの性質せいしつ — 約数やくすう・倍数ばいすう・ユークリッドの互除法じょほう・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進すすむ」 はくり返かえし割わって余あまりを下したから並ならべる、 と方向ほうこうで手順てじゅんが違ちがいます。

まとめ

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

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