倍数、約数 | きょうさい対策ブログ

○約数・倍数

\( \displaystyle a,b (b \neq 0) \)を整数とする．
\( \displaystyle a=bc \)となる整数\( \displaystyle c \)が存在するとき，\( \displaystyle a \)は\( \displaystyle b \)の倍数，\( \displaystyle b \)は\( \displaystyle a \)の約数であるという.
※\( \displaystyle a \div b \)は\( \displaystyle a=bx \)となる\( \displaystyle x \)を表す．\( \displaystyle a=0 \cdot x \)となる\( \displaystyle x \)は1つには定まらないので，0で割ることは定義されない．

○素数・合成数・素因数分解

(1)\( \displaystyle 2 \)以上の自然数で，その数自身と\( \displaystyle 1 \)以外に正の約数をもたない数を素数という．
(2)\( \displaystyle 1 \)と異なる\( \displaystyle 2 \)つ以上の自然数の積で表される数を合成数といい，このとき，積を構成する1つ1つの自然数を因数という．
(3)因数のうち素数であるものを素因数といい，自然数を素数だけの積で表すことを素因数分解するという．

○約数の個数・総和

自然数\( \displaystyle n \)の素因数分解を\( \displaystyle n={p_1}^{a_1}{p_2}^{a_2} \cdots {p_t}^{a_t} \)とする.
(1)\( \displaystyle n \)の正の約数は，一般に
\( \displaystyle \ \ \ \ \ {p_1}^{k_1}{p_2}^{k_2} \cdots {p_t}^{k_t} \) (各番号\( \displaystyle i \)ごとに，\( \displaystyle k_i=0,1, \cdots ,a_i \))
という形をしている(素因数から何個かずつ取った積)．
→\( \displaystyle n \)の正の約数の個数は，\( \displaystyle (a_1+1)(a_2+1) \cdots (a_t+1) \)
(2)\( \displaystyle n \)の正の約数の総和は，
\( \displaystyle \ \ \ \ \ \sum_{k_1=0}^{a_1} {p_1}^{k_1} \sum_{k_2=0}^{a_2} {p_2}^{k_2} \cdots \sum_{k_t=0}^{a_t} {p_t}^{k_t} \)

(例) \( \displaystyle 2025 \)の正の約数の個数と正の約数の総和を求める．

説明例(クリックして下さい)

\( \displaystyle 2025=25 \cdot 81=3^4 \cdot 5^2 \)
\( \displaystyle 2025 \)の約数の個数は，\( \displaystyle (4+1) \times (2+1)=15 \)個 (答)
\( \displaystyle 2025 \)の約数の総和は，
\( \displaystyle \ \ \ \ \ (3^0+3^1+ \cdots +3^4)(5^0+5^1+5^2) \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ =\frac{3^5-1}{3-1} \cdot 31=121 \cdot 31=3751 \) (答)

○階乗数の素因数

\( \displaystyle n! \)が素数\( \displaystyle p \)で割り切れる回数は，\( \displaystyle \sum_{k=1}^{\infty} \left[ \frac{n}{p^k} \right] \)
※\( \displaystyle [x] \)はガウス記号で，\( \displaystyle x \)の整数部分を意味する．

(例)上の意味を，「\( \displaystyle 10! \)が\( \displaystyle 2 \)で割り切れる回数を求める」ことで具体的に考える．

説明例(クリックして下さい)

\( \displaystyle 1 \)から\( \displaystyle 10 \)までの数について，それぞれ\( \displaystyle 2, 2^2, 2^3, \cdots \)で割り切れるかどうかをまとめると次のようになる(◯＝割り切れる)．

上表の◯の総数は，\( \displaystyle 10! \)が\( \displaystyle 2 \)で割り切れる回数を意味している．それぞれの段ごとの◯の数を合計して，
\( \displaystyle \ \ \ \ \ \left[ \frac{10}{2} \right]+\left[ \frac{10}{2^2} \right]+\left[ \frac{10}{2^3} \right]=5+2+1=8 \)
よって，\( \displaystyle 10! \)は\( \displaystyle 2 \)で\( \displaystyle 8 \)回割り切れる．

(例，京都府)
\( \displaystyle 28 \)の正の約数は\( \displaystyle 1 \)，\( \displaystyle 2 \)，\( \displaystyle 4 \)，\( \displaystyle 7 \)，\( \displaystyle 14 \)，\( \displaystyle 28 \)で，\( \displaystyle 28 \)自身を除く正の約数の総和は\( \displaystyle 28 \)である．このように，ある正の整数\( \displaystyle n \)が，「\( \displaystyle n \)自身を除く正の約数の総和が\( \displaystyle n \)に等しい」とき，\( \displaystyle n \)は完全数であるという．これについて，次の各問いに答えなさい．
(1)\( \displaystyle p \)を正の整数とする．\( \displaystyle 2^p-1 \)が素数ならば，\( \displaystyle 2^{p-1}(2^p-1) \)は完全数であることを証明しなさい．
(2)\( \displaystyle p \)を正の整数とする．\( \displaystyle 2^p-1 \)が素数ならば，\( \displaystyle p \)は素数であることを証明しなさい．
(3)完全数を\( \displaystyle 28 \)以外に\( \displaystyle 3 \)つ挙げなさい．（数値のみ答えなさい．）

説明例(クリックして下さい)

(1) \( \displaystyle n=2^{p-1}(2^p-1) \)とおく．
\( \displaystyle 2^p-1 \)が素数であるから，\( \displaystyle n=2^{p-1}(2^p-1) \)の正の約数の総和は，
\( \displaystyle \ \ \ \ \ \left(1+(2^p-1)\right) \times \left(1+2+2^2+ \cdots +2^{p-1}\right) \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ =2^p \times \frac{2^p-1}{2-1}=2^p(2^p-1)=2n \)
この総和\( \displaystyle 2n \)から\( \displaystyle n \)をひくと\( \displaystyle n \)に等しいから，\( \displaystyle n=2^{p-1}(2^p-1) \)は完全数である．■
(2)対偶「\( \displaystyle p \)が素数でないならば，\( \displaystyle 2^p-1 \)は素数でない」を示す．
\( \displaystyle p \)が素数でないのは，\( \displaystyle p=1 \)または\( \displaystyle p \)が合成数のときである．

\( \displaystyle p=1 \)のとき，\( \displaystyle 2^p-1=2-1=1 \)は素数ではない．

\( \displaystyle p \)が合成数のとき，\( \displaystyle 2 \)以上の整数\( \displaystyle a, b \)を用いて，\( \displaystyle p=ab \)と表せる．このとき，
\( \displaystyle \ \ \ \ \ 2^p-1=2^{ab}-1=(2^a)^b-1 \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ =(2^a-1)\left\{(2^a)^{b-1}+(2^a)^{b-2}+ \cdots +2^a+1\right\} \)
ここで，
\( \displaystyle \ \ \ \ \ 2^a-1 \geqq 2^2-1>1 \)
\( \displaystyle \ \ \ \ \ (2^a)^{b-1}+(2^a)^{b-2}+ \cdots +2^a+1 \geqq 2^2-1>1 \)
であるから，\( \displaystyle 2^p-1 \)は合成数で，素数でない．対偶が真であるから，元の命題「\( \displaystyle 2^p-1 \)が素数ならば，\( \displaystyle p \)は素数である」も真である．■
(3) (説明のため，過程も記述する)(1)(2)により，素数\( \displaystyle p \)の中から，\( \displaystyle 2^p-1 \)が素数になるようなものを探せばよいことがわかる．実際に試してみると，
\( \displaystyle p=2 \)のとき，\( \displaystyle 2^p-1=3 \)(素数)だから，\( \displaystyle 2^1 \cdot (2^2-1)=6 \)は完全数．
\( \displaystyle p=3 \)のとき，\( \displaystyle 2^p-1=7 \)(素数)だから，\( \displaystyle 2^2 \cdot (2^3-1)=28 \)は完全数(これが例として問題文にあるもの)．
\( \displaystyle p=5 \)のとき，\( \displaystyle 2^5-1=31 \)(素数)だから，\( \displaystyle 2^4 \cdot (2^5-1)=16 \cdot 31=496 \)は完全数．
\( \displaystyle p=7 \)のとき，\( \displaystyle 2^7-1=127 \)(素数)だから，\( \displaystyle 2^6 \cdot (2^7-1)=64 \cdot 127=8128 \)は完全数．
よって，完全数\( \displaystyle 28 \)以外に\( \displaystyle 3 \)つ挙げると，例えば，\( \displaystyle 6, 496, 8128 \) (答)

※合同式を用いると，\( \displaystyle 2^p=(2^a)^b \equiv 1 \ (\text{mod} \ 2^a-1) \)から，\( \displaystyle 2^p-1 \)が\( \displaystyle 2^a-1 \)を約数にもつことがすぐにわかり，(2)の\( \displaystyle (2^a)^b-1=(2^a-1)\left\{(2^a)^{b-2}+ \cdots +2^a+1\right\} \)という因数分解は不要になる．
※\( \displaystyle 2^p-1 \)は素数にならない場合もある．例えば，\( \displaystyle 2^{11}-1=2047=23 \cdot 89 \)．
※\( \displaystyle 2^p-1 \)が素数になるとき，この\( \displaystyle 2^p-1 \)をメルセンヌ素数という(無限に存在するかどうかは2026年時点で未解決)．

○最大公約数・最小公倍数

\( \displaystyle a,b \)を整数とする．
(1)\( \displaystyle a,b \)に共通な約数を公約数といい，そのうち最大のものを最大公約数という．\( \displaystyle a \)と\( \displaystyle b \)の最大公約数を\( \displaystyle \gcd(a,b) \)で表す.
(2)\( \displaystyle a,b \)に共通な倍数を公倍数といい，そのうち正で最小のものを最小公倍数という．\( \displaystyle a \)と\( \displaystyle b \)の最小公倍数を\( \displaystyle \text{lcm}(a,b) \)で表す．

(3)\( \displaystyle \gcd(a,b)=1 \)のとき，\( \displaystyle a \)と\( \displaystyle b \)は互いに素であるという．
(4)\( \displaystyle a,b \)は自然数とする．\( \displaystyle a=a’ \cdot \gcd(a,b), b=b’ \cdot \gcd(a,b) \)のとき，
・\( \displaystyle \gcd(a’,b’)=1 \)
・\( \displaystyle \text{lcm}(a,b)=a’b’ \cdot \gcd(a,b) \)
・\( \displaystyle ab=\text{lcm}(a,b) \cdot \gcd(a,b) \)

(例，島根県)
最大公約数が\( \displaystyle 48 \)，最小公倍数が\( \displaystyle 1152 \)であるような\( \displaystyle 2 \)つの正の整数の組をすべて求めよ．

説明例(クリックして下さい)

求める\( \displaystyle 2 \)つの正の整数を\( \displaystyle a,b \ (a \leqq b) \)とおく．
最大公約数が\( \displaystyle 48 \)であるから，
\( \displaystyle \ \ \ \ \ a=48a’, b=48b’ \ (\gcd(a’,b’)=1, a’ \leqq b’) \)
と表される．また，最小公倍数は\( \displaystyle 48a’b’ \)と表せるから，
\( \displaystyle \ \ \ \ \ 48a’b’=1152 \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \therefore a’b’=24 \)
\( \displaystyle \gcd(a’,b’)=1, a’ \leqq b’ \)を満たす自然数\( \displaystyle a’, b’ \)の組は
\( \displaystyle \ \ \ \ \ (a’,b’)=(1,24), (3,8) \)
したがって，求める\( \displaystyle 2 \)数\( \displaystyle (a,b) \)は
\( \displaystyle \ \ \ \ \ (a,b)=(48,1152), (144,384) \) (答)

○最大公約数の性質

\( \displaystyle a,b,c \)を整数，\( \displaystyle n \)を自然数とする.
(1)\( \displaystyle \gcd(1,a)=1 \)
(2)\( \displaystyle \gcd(a,b)=\gcd(b,a-bc) \) [ユークリッドの互除法]
(3)\( \displaystyle \gcd(na,nb)=n \cdot \gcd(a,b) \)
(4)\( \displaystyle \gcd(a,b)=1 \)のとき，\( \displaystyle \gcd(a,bc)=\gcd(a,c) \)

(例，山梨県)
\( \displaystyle 5n+6 \)と\( \displaystyle 3n+1 \)の最大公約数が\( \displaystyle 13 \)になるような\( \displaystyle 50 \)以下の自然数\( \displaystyle n \)をすべて求めよ．

説明例(クリックして下さい)

ユークリッドの互除法より，
\( \displaystyle \gcd(5n+6,3n+1)=\gcd(3n+1,2n+5) \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\gcd(2n+5,n-4) \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\gcd(n-4,13) \)
ここで，
\( \displaystyle \ \ \ \ \ \gcd(n-4,13)=13 \)
\( \displaystyle \ \ \ \ \ \iff n-4 \)が\( \displaystyle 13 \)の倍数
\( \displaystyle \ \ \ \ \ \iff n-4=0,13,26,39 \ (\because 1-4 \leqq n-4 \leqq 50-4) \)
\( \displaystyle \ \ \ \ \ \iff n=4,17,30,43 \)
したがって，求める自然数\( \displaystyle n \)は
\( \displaystyle \ \ \ \ \ n=4,17,30,43 \) (答)

○\( \displaystyle n \)進法

\( \displaystyle n \)を自然数とする．\( \displaystyle n \)ずつで位が\( \displaystyle 1 \)つ繰り上がるように数を表す方法を\( \displaystyle n \)進法という．

きょうさい対策ブログ(skyosai.com)

1 / 6

(例1)十進法で表された数\( \displaystyle 12345 \)を，七進法で表す．

説明例(クリックして下さい)

\( \displaystyle 12345=a_0 \cdot 7^0+a_1 \cdot 7^1+a_2 \cdot 7^2 \cdots \)
と表したときの，\( \displaystyle a_0,a_1, \cdots \)を求めればよい．
\( \displaystyle 12345=7 \cdot 1763+4 \ \ \ \ \ \therefore a_0=4 \)
\( \displaystyle \ \ \ \ 1763=7 \cdot 251+6 \ \ \ \ \ \therefore a_1=6 \)
\( \displaystyle \ \ \ \ \ \ \ \ 251=7 \cdot 35+6 \ \ \ \ \ \therefore a_2=6 \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \ \ 35=7 \cdot 5+0 \ \ \ \ \ \therefore a_3=0 \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ 5=7 \cdot 0+5 \ \ \ \ \ \therefore a_4=\textcolor{red}{5} \)
よって，
\( \displaystyle 12345_{(10)}=4 \cdot 7^0+6 \cdot 7^1+6 \cdot 7^2+0 \cdot 7^3+\textcolor{red}{5} \cdot 7^4 \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ =\textcolor{red}{5}0664_{(7)} \) (答)

↑「7でわってあまりを取り出す」
を繰り返すことで\( \displaystyle a_0,a_1 \cdots \)を確定させていく

(例2)十進法で表された数\( \displaystyle 0.816 \)を，五進法で表す．

説明例(クリックして下さい)

\( \displaystyle 0.816=\frac{a_{-1}}{5}+\frac{a_{-2}}{5^2}+\frac{a_{-3}}{5^3}+ \cdots \)
と表したときの，\( \displaystyle a_{-1}, a_{-2}, \cdots \)を求めればよい．
\( \displaystyle 0.816 \times 5=4.08 \ \ \ \ \ \therefore a_{-1}=4 \)
\( \displaystyle \ \ \ \ \ 0.08 \times 5=0.4 \ \ \ \ \ \therefore a_{-2}=0 \)
\( \displaystyle \ \ \ \ \ \ \ \ \ 0.4 \times 5=2 \ \ \ \ \ \therefore a_{-3}=\textcolor{red}{2} \)
よって，
\( \displaystyle 0.816_{(10)}=4 \cdot 5^{-1}+0 \cdot 5^{-2}+\textcolor{red}{2} \cdot 5^{-3} \)
\( \displaystyle \ \ \ \ \ \ \ \ \ \ \ \ \ =0.40\textcolor{red}{2}_{(5)} \) (答)

↑「5倍して整数部分を取り出す」
を繰り返すことで\( \displaystyle a_{-1},a_{-2} \cdots \)を確定させていく

この記事は役に立ちましたか？

間違い/不具合かな？
と思ったらこちらへ