高校数学マスター演習

1. 素因数分解

整数を素数のかけ算で表すこと。整数問題の基本中の基本！

🔑 やり方

小さい素数（2, 3, 5, 7, ...）で順番に割っていくだけ！

💡 素数とは？ 1より大きい整数で、1とその数自身でしか割れない数。
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... ← これらが素数！

素因数分解すれば、最大公約数（GCD）と最小公倍数（LCM）は簡単に求まる！

🔑 求め方

📝 例: 12 = 2²×3, 18 = 2×3²
GCD: 2¹×3¹ = 6（小さい方をとる）
LCM: 2²×3² = 36（大きい方をとる）

🔑 便利な関係式

\gcd(a,b) \times \text{lcm}(a,b) = a \times b

GCD × LCM = 元の2つの数の積

大きい数のGCDを素因数分解なしで求める方法。
「割り算の余りでどんどん置き換えていく」だけ！

🔑 原理

a = bq + r \Rightarrow \gcd(a,b) = \gcd(b,r)

余りが0になったら、そのときの割る数がGCD！

📝 例: GCD(78, 30) を求める

78 = 30 \times 2 + 18

30 = 18 \times 1 + 12

18 = 12 \times 1 + 6

12 = 6 \times 2 + 0

余りが0になった → GCD = 6

素因数分解さえできれば、約数の個数は一瞬で出せる！

🔑 約数の個数の公式

素因数分解の各指数に1を足してかけるだけ：

(e_1+1)(e_2+1) \cdots (e_k+1)

📝 例: $360 = 2^3 \times 3^2 \times 5^1$ の約数の個数
→ $(3+1)(2+1)(1+1) = 24$ 個

🔑 1次不定方程式

ax + by = \gcd(a,b)

整数解が存在する条件: gcd(a,b) が右辺を割り切ること。
1つ解を見つけたら、一般解は簡単に出せる！

🔑 n進法

普段使ってるのは10進法。コンピュータは2進法を使ってる。
各桁をn^k倍して足せば10進法に変換できる！

101_{(2)} = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 5

Q1.36と48の最大公約数は？

Q2.12と18の最小公倍数は？

Q3.91を素因数分解せよ。

Q4.ユークリッドの互除法で GCD(78, 30) を求めよ。

Q5.17は何数？

Q6.整数aを5で割ると余りは0, 1, 2, 3, 4のどれか。a² を5で割った余りとしてあり得ないのは？

Q7.1次不定方程式 3x + 5y = 1 の整数解の1つは？

Q8.360の正の約数の個数は？

360 = 2^3 \times 3^2 \times 5

Q9.n進法の「101(2)」を10進法で表すと？

Q10.互いに素とは？