倍数・約数・素数・合成数の定義
以下，$a,b\in \mathbb{Z}$とする．
- $a\neq 0$であるとき，$b=an$となるような$n\in\mathbb{Z}$があれば，$b$を$a$の倍数，$a$を$b$の約数という．
- $p\neq 1$が正の整数で，正の約数が$1$と$p$自身だけであるとき，$p$を素数という．
- $n$が正の整数で，正の約数を$1$と$n$以外に持つとき，$n$を合成数という．
また，約数と倍数に関連して，公約数と公倍数を次で定義する．
- $a,b$の共通の約数を$a,b$の公約数という．
- $a\neq 0$かつ$b\neq 0$であるとき，$a,b$の共通の倍数を$a,b$の公倍数という．
さらに，最大公約数と最小公倍数について次で定義する．
- $a\neq 0$または$b\neq 0$であるとき，$a,b$の正の公約数のなかで最大のものを最大公約数といい，$\gcd(a,b)$と書く．$\gcd(a,b)=1$ならば，$a,b$は互いに素であるという．
- $a,b\neq 0$なら，$a,b$の正の公倍数のなかで最小のものを最小公倍数といい，$\rm{lcm}(a,b)$と書く．
例1
- $2$の倍数は，$\dots, -4,-2,0,2,4,6,8,10\dots $．
- $5$の倍数は，$\dots, -10,-5,0,5,10,\dots $．
- $2$と$5$の最小公倍数は$10$，つまり$\rm{lcm}(2,5)=10$．
- $30$の約数は，$1,2,3,5,6,10,15,30$．
- $35$の約数は，$1,5,7,35$．
- $30$と$35$の最大公約数は5，つまり$\gcd(30,35)=5$．
- $7$の約数は，$1,7$のみ．約数に$1$と$7$自身しか持たないので，$7$は素数である．
- $7$と$30$の最大公約数は$1$，つまり$\gcd(7,30)=1$で，$7$と$30$は互いに素である．
練習問題1
- $0\leq n \leq 100$を満たす$n$のうち，$2$の倍数であるものはいくつあるか？
- $0\leq n \leq 100$を満たす$n$のうち，$3$の倍数であるものはいくつあるか？
- $0\leq n \leq 100$を満たす$n$のうち，$5$を約数にもつ$n$はいくつあるか？
- $0\leq n \leq 100$を満たす$n$のうち，$7$を約数にもつ$n$をすべて挙げよ．
- $0\leq n \leq 100$を満たす$n$のうち，$11$を約数にもつ$n$をすべて挙げよ．
- $0\leq n \leq 100$を満たす$n$のうち，素数をすべて挙げよ．
- $2$と$11$の公倍数を小さいものから3つ挙げよ．
- $121$と$129$の公約数をすべて挙げよ．また，互いに素であるかどうか答えよ．
- $65$と$85$の公約数をすべて挙げよ．
- $\gcd(90,99)=$?
練習問題1の解答
- $2,4,6,8,10,\dots,96,98,100$の50個．
- $3,6,9,12,15,\dots,93,96,99$の33個．
- $5,10,15,20,25,\dots,90,95,100$の20個．
- $7,14,21,28,35,42,49,56,63,70,77,84,91,98$．
- $11,22,33,44,55,66,77,88,99$．
- $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$
- $22,44,66$．
- $1$．$\gcd(121,129)=1$より互いに素である．
- $1,5$．
- $\gcd(90,99)=9$