素因数分解の結果を理解する
以下の表は、よく知られたいくつかの数の素因数分解を示し、指数表記の仕組みを説明しています。
| 数 | 素因数分解 | 約数の個数 |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17（素数） | 17（それ自身、指数1） | 2 |
| 1024 | 2¹⁰ | 11 |
- 素数自身の素因数分解は、単にその数自身に指数1が付いたものであり、約数は常にちょうど2つ、1とその数自身です。これはまさに素数の定義そのものです。
- 1は素数でも合成数でもなく、素因数分解を持ちません（空積とみなされます）。この計算機は2以上の入力を必要とします。
- 非常に大きな数の場合、試し割り法はその数の平方根までの候補素数を試す必要があるため、計算上遅くなります——これが、極めて大きな数（数百桁）の因数分解が計算上困難であり、RSA暗号のセキュリティの基盤になっている理由です。
素因数分解とは？
素因数分解とは、整数を、掛け合わせるとその数になる素数の組に分解する操作です。素数とは、1より大きく、正の約数がちょうど2つ（1とその数自身）である整数のことです（2, 3, 5, 7, 11, 13, ...が最初のいくつかの素数です）。たとえば360は2³ × 3² × 5に分解され、これは360 = 2×2×2×3×3×5を意味します。
数論の基礎となる結果の一つである算術の基本定理は、1より大きいすべての整数が、因数を書く順序を除いて、ただ一通りの素因数分解しか持たないことを保証します。この一意性こそが、素因数分解を、複数ある等しく妥当な答えの一つではなく、明確で信頼できる演算にしているのです。
素因数分解は数学とコンピューターサイエンスの中核的な分野を支えています。数の最大公約数や最小公倍数を求めたり、ある数のすべての約数を特定したり、分数や根号を簡約したりするために使われます。そして非常に大きな数については、その計算上の困難さが、RSA公開鍵暗号の数学的基盤になっています。RSA暗号は、大きな数を因数分解することが、その因数同士を掛け合わせることよりもはるかに難しいという事実に依存しています。
この素因数分解計算機の使い方
- 2以上の整数を入力します（1兆まで対応）。
- 計算機は標準的な試し割り法に従い、1になるまで最小の素因数で繰り返し割っていきます。
- 指数表記（例：2³ × 3² × 5）で素因数分解を確認します。各指数は、その素数が積の中に何回現れるかを示します。
- その数が持つ正の約数の総数と、それらすべての約数の和を確認します——どちらも素因数分解から直接導かれます。
素因数分解、約数の個数、約数の和の求め方
試し割り法は、2から始めて候補となる素数を順に試し、その数を各素数で割り切れる回数だけ割り、次の候補に進むことで素因数分解を求めます。計算例：360 ÷ 2 = 180、÷2 = 90、÷2 = 45（もう2では割り切れないため、2は3回現れます）。45 ÷ 3 = 15、÷3 = 5（もう3では割り切れないため、3は2回現れます）。5 ÷ 5 = 1（5は1回現れます）。結果：360 = 2³ × 3² × 5。
素因数分解n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖがわかれば、正の約数の総数（1とn自身を含む）は各指数に1を足し、それらを掛け合わせることで求められます：(e₁+1) × (e₂+1) × ... × (eₖ+1)。360 = 2³ × 3² × 5¹の場合の計算例：(3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24個の約数。
すべての約数の和は、乗法的な約数和の公式を使って求められます。素因数分解に含まれる各素数の累乗p^eについて、その寄与は(p^(e+1) − 1) ÷ (p − 1)——等比数列1 + p + p² + ... + p^eの和——であり、これらの寄与をすべての素因数にわたって掛け合わせます。360の場合の計算例：2³の項は(2⁴−1)/(2−1) = 15、3²の項は(3³−1)/(3−1) = 13、5¹の項は(5²−1)/(5−1) = 6を寄与し、15 × 13 × 6 = 1170を掛け合わせると、360のすべての24個の約数の和になります。
よくある間違い
- 1に達する前に分解を早く止めてしまう——見つかった各因数は、次の候補素数に進む前に（1回だけでなく）完全に割り切るまで割る必要があります。
- 1を素数として扱う——現代の数学的な慣例では、1は素数でも合成数でもなく、これを因数分解に含めると、算術の基本定理が保証する一意性に反することになります。
- 約数の個数を数える際に、（素数の底だけでなく）指数が重要であることを忘れる——約数の個数の公式は、異なる素数の個数だけでなく、各素数について（指数 + 1）を使います。
- すべての大きな数が小さな素因数を持つと思い込む——多くの大きな数（特に2つの大きな素数の積）はまったく小さな因数を持たず、これはまさに、それらを暗号応用に有用にしている性質です。
よくある質問
数の素因数分解はどうやって求めますか？
その数を割り切れる最小の素数で繰り返し割り、それ以上割り切れなくなるまで同じ素数を使い続け、次の素数に進みます。これを商が1になるまで繰り返します。360の場合：2で3回割り（360→180→90→45）、次に3で2回割り（45→15→5）、次に5で1回割り（5→1）、360 = 2³ × 3² × 5が得られます。
ある数の約数はいくつありますか？
素因数分解の各指数に1を足し、それらを掛け合わせます。360 = 2³ × 3² × 5¹の場合、約数の個数は(3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24です。これは1とその数自身を含むすべての正の約数を数えたものです。
算術の基本定理とは何ですか？
算術の基本定理とは、1より大きいすべての整数が、素数を列挙する順序を除いて、ただ一通りの方法で素数の積として表せるという定理です。この一意性こそが、素因数分解を、複数ある等しく妥当な答えの一つではなく、明確な演算にしており、数論の多くの基礎になっています。
1は素数ですか？
いいえ。現代の数学的な慣例では、1は素数でも合成数でもありません。素数とは、正の約数がちょうど2つ（1とその数自身）であるものと定義されますが、1の正の約数は1つ（それ自身）しかないため、この定義を満たしません。1を素数から除外することは、算術の基本定理が成り立つためにも必要です。そうでなければ、ある数は1という因数をいくつでも余分に加えて「分解」できてしまうことになります。
素因数分解はなぜ暗号にとって重要なのですか？
現代のRSA公開鍵暗号は、2つの大きな素数を掛け合わせることは計算上簡単である一方、その大きな積を元の素数に戻すように因数分解することは、現在知られている古典的アルゴリズムでは計算上非常に困難であるという事実に依存しています。この非対称性——掛けるのは簡単、因数分解するのは難しい——により、公開鍵（積）は公然と共有できる一方、秘密鍵（素因数）は秘密のままとなり、十分に大きな素数であれば実用的な時間内では事実上復元不可能になります。
ある数のすべての約数の和はどうやって求めますか？
素因数分解n = p₁^e₁ × p₂^e₂ × ...を使い、各素因数について(pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1)を計算し、結果を掛け合わせます。360 = 2³ × 3² × 5の場合：2³の項は(2⁴−1)/(2−1)=15、3²の項は(3³−1)/(3−1)=13、5¹の項は(5²−1)/(5−1)=6を与え、15×13×6 = 1170を掛け合わせると、360のすべての約数の和になります。
参考文献
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)