Asal çarpanlara ayırma sonucunu anlamak
Aşağıdaki tablo, üslü gösterimin nasıl çalıştığını göstermek için birkaç bilindik sayının asal çarpanlara ayrılışını gösterir.
| Sayı | Asal çarpanlara ayırma | Bölen sayısı |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (asal bir sayı) | 17 (kendisi, üs 1) | 2 |
| 1.024 | 2¹⁰ | 11 |
- Bir asal sayının kendi çarpanlara ayrılışı, basitçe üssü 1 olan kendisidir ve her zaman tam olarak 2 bölene sahiptir: 1 ve kendisi. Bu, tam olarak bir asal sayının tanımlayıcı özelliğidir.
- 1 sayısı ne asal ne bileşiktir ve asal çarpanlara ayrılışı yoktur (boş çarpımdır); bu hesaplayıcı 2 veya daha büyük bir girdi gerektirir.
- Çok büyük sayılar için, deneme bölmesi hesaplama açısından yavaşlar çünkü sayının kareköküne kadar aday asal sayıları test etmesi gerekir — bu nedenle son derece büyük sayıları (yüzlerce basamak) çarpanlarına ayırmak hesaplama açısından zordur ve RSA şifrelemesinin güvenlik temelini oluşturur.
Asal çarpanlara ayırma nedir?
Asal çarpanlara ayırma, bir tam sayıyı, çarpıldığında onu veren asal sayılar kümesine ayırma işlemidir. Bir asal sayı, tam olarak iki pozitif bölene sahip olan, 1'den büyük bir tam sayıdır: 1 ve kendisi (2, 3, 5, 7, 11, 13, ... ilk birkaç asal sayıdır). Örneğin, 360, 2³ × 3² × 5 olarak çarpanlarına ayrılır, yani 360 = 2×2×2×3×3×5.
Sayı teorisinin temel taşı sonuçlarından biri olan aritmetiğin temel teoremi, 1'den büyük her tam sayının, çarpanların yazılma sırası dışında, tek ve yalnızca bir asal çarpanlara ayrılışı olduğunu garanti eder. Bu benzersizlik, asal çarpanlara ayırmayı, birbirine eşit derecede geçerli birkaç cevaptan biri değil, iyi tanımlanmış, güvenilir bir işlem yapan şeydir.
Asal çarpanlara ayırma, matematik ve bilgisayar biliminin temel alanlarının dayanağıdır: sayıların en büyük ortak bölenini ve en küçük ortak katını bulmak, bir sayının tüm bölenlerini belirlemek, kesirleri ve kökleri sadeleştirmek için kullanılır — ve çok büyük sayılar için, hesaplama zorluğu, büyük bir sayıyı çarpanlarına ayırmanın, çarpanlarını çarpmaktan çok daha zor olduğu gerçeğine dayanan RSA açık anahtarlı kriptografisinin matematiksel temelidir.
Bu asal çarpanlara ayırma hesaplama aracı nasıl kullanılır
- 2 veya daha büyük bir tam sayı girin (1 trilyona kadar).
- Hesaplayıcı, standart deneme bölmesi yöntemini izleyerek, yalnızca 1 kalana kadar mümkün olan en küçük asal çarpana tekrar tekrar böler.
- Asal çarpanlara ayırmayı üslü biçimde okuyun (örn. 2³ × 3² × 5), burada her üs, o asal sayının çarpımda kaç kez göründüğünü gösterir.
- Sayının sahip olduğu toplam pozitif bölen sayısını ve bu bölenlerin tümünün toplamını inceleyin — ikisi de doğrudan asal çarpanlara ayırmadan türetilir.
Asal çarpanlara ayırma, bölen sayısı ve bölen toplamı nasıl hesaplanır
Deneme bölmesi, 2'den başlayarak ardışık aday asal sayıları test ederek, sayıyı her asal sayıya tam olarak böldüğü kadar bölerek ve ardından bir sonraki adaya geçerek asal çarpanlara ayrılmayı bulur. Çözülmüş örnek: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45 (artık 2'ye bölünmüyor, dolayısıyla 2 sayısı 3 kez görünür); 45 ÷ 3 = 15, ÷3 = 5 (artık 3'e bölünmüyor, dolayısıyla 3 sayısı 2 kez görünür); 5 ÷ 5 = 1 (5 bir kez görünür). Sonuç: 360 = 2³ × 3² × 5.
n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ asal çarpanlara ayrılışı bilindiğinde, toplam pozitif bölen sayısı (1 ve n'nin kendisi dahil), her üsse 1 eklenip sonuçların çarpılmasıyla bulunur: (e₁+1) × (e₂+1) × ... × (eₖ+1). 360 = 2³ × 3² × 5¹ için çözülmüş örnek: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 bölen.
Tüm bölenlerin toplamı, çarpımsal bölen-toplamı formülü kullanılarak bulunur: çarpanlara ayırmadaki her p^e asal kuvveti için, katkısı (p^(e+1) − 1) ÷ (p − 1) — 1 + p + p² + ... + p^e geometrik dizisinin toplamı — ve bu katkılar tüm asal çarpanlar boyunca birbiriyle çarpılır. 360 için çözülmüş örnek: 2³ terimi (2⁴−1)/(2−1) = 15 katkısında bulunur, 3² terimi (3³−1)/(3−1) = 13 katkısında bulunur ve 5¹ terimi (5²−1)/(5−1) = 6 katkısında bulunur; 15 × 13 × 6 = 1.170 çarpımı, 360'ın 24 böleninin toplamıdır.
Sık yapılan hatalar
- 1'e ulaşmadan önce çarpanlara ayırmayı erken durdurmak — bulunan her çarpan, bir sonraki aday asal sayıya geçmeden önce (yalnızca bir kez değil) tamamen bölünerek çıkarılmalıdır.
- 1'i asal sayı olarak ele almak — modern matematiksel kurala göre, 1 ne asal ne bileşiktir ve onu bir çarpanlara ayırmaya dahil etmek, aritmetiğin temel teoreminin garanti ettiği benzersizliği ihlal eder.
- Bölenleri saymak için üssün (yalnızca taban asal sayının değil) önemli olduğunu unutmak — bölen sayısı formülü, farklı asal sayıların sayısını değil, her asal sayı için (üs + 1) değerini kullanır.
- Her büyük sayının küçük asal çarpanlara sahip olduğunu varsaymak — birçok büyük sayının (özellikle iki büyük asal sayının çarpımının) hiç küçük çarpanı yoktur, bu da onları kriptografik uygulamalar için kullanışlı yapan tam olarak bu özelliktir.
Sıkça Sorulan Sorular
Bir sayının asal çarpanlara ayrılışını nasıl bulursunuz?
Sayıyı, onu tam olarak bölen en küçük asal sayıya tekrar tekrar bölün, artık tam olarak bölmeyene kadar aynı asal sayıyla devam edin, ardından bir sonraki asal sayıya geçin ve kalan bölüm 1 olana kadar tekrarlayın. 360 için: 2'ye üç kez bölün (360→180→90→45), ardından 3'e iki kez (45→15→5), ardından 5'e bir kez (5→1), bu da 360 = 2³ × 3² × 5 verir.
Bir sayının kaç böleni vardır?
Asal çarpanlara ayırmadaki her üsse 1 ekleyin ve sonuçları birbiriyle çarpın. 360 = 2³ × 3² × 5¹ için, bölen sayısı (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24'tür. Bu, 1 ve sayının kendisi dahil tüm pozitif bölenleri sayar.
Aritmetiğin temel teoremi nedir?
Aritmetiğin temel teoremi, 1'den büyük her tam sayının, asal sayıların listelendiği sıra dışında, tam olarak bir şekilde asal sayıların çarpımı olarak yazılabileceğini belirtir. Bu benzersizlik, asal çarpanlara ayırmayı, birbirine eşit derecede geçerli birden çok cevaptan biri değil, iyi tanımlanmış bir işlem yapar ve sayı teorisinin büyük bölümünün temelini oluşturur.
1 bir asal sayı mıdır?
Hayır. Modern matematiksel kurala göre, 1 ne asal ne bileşiktir. Bir asal sayı, tam olarak iki farklı pozitif bölene (1 ve kendisi) sahip olarak tanımlanır; 1 sayısının ise yalnızca bir pozitif böleni (kendisi) vardır, dolayısıyla bu tanımı karşılamaz. 1'i asal sayılardan hariç tutmak, aritmetiğin temel teoreminin geçerli olması için de gereklidir, çünkü aksi halde bir sayı herhangi bir sayıda ekstra 1 çarpanıyla 'çarpanlarına ayrılabilir'.
Asal çarpanlara ayırma şifreleme için neden önemlidir?
Modern RSA açık anahtarlı kriptografisi, iki büyük asal sayıyı çarpmanın hesaplama açısından kolay olduğu, ancak büyük çarpımlarını orijinal asal sayılara geri çarpanlara ayırmanın, şu anda bilinen klasik algoritmalarla hesaplama açısından çok zor olduğu gerçeğine dayanır. Bu asimetri — çarpmak kolay, çarpanlara ayırmak zor — bir açık anahtarın (çarpım) açıkça paylaşılmasına izin verirken, özel anahtar (asal çarpanlar) gizli kalır ve yeterince büyük asal sayılar için pratik bir zaman diliminde etkin bir şekilde geri elde edilemez.
Bir sayının tüm bölenlerinin toplamını nasıl bulursunuz?
n = p₁^e₁ × p₂^e₂ × ... asal çarpanlara ayrılışını kullanarak, her asal çarpan için (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1) hesaplayın ve sonuçları çarpın. 360 = 2³ × 3² × 5 için: 2³ terimi (2⁴−1)/(2−1)=15 verir, 3² terimi (3³−1)/(3−1)=13 verir ve 5¹ terimi (5²−1)/(5−1)=6 verir; 15×13×6 = 1.170 çarpımı, 360'ın tüm bölenlerinin toplamıdır.
Kaynaklar
- 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.)