Primfaktorzerlegung-Rechner

Primfaktorzerlegung-Rechner - Zahlen zerlegen

🔢 Zerlegen Sie jede Zahl in ihre Primfaktoren. Sehen Sie Ergebnisse als Produkt, mit Exponenten, als Faktorbaum-Visualisierung und mit Schritt-für-Schritt-Divisionsprozess.

Was ist eine Primfaktorzerlegung?

Die Primfaktorzerlegung (oder Ganzzahlfaktorisierung) ist der Prozess, eine zusammengesetzte Zahl als Produkt von Primzahlen darzustellen. Jede zusammengesetzte Zahl hat eine eindeutige Primfaktorzerlegung.

Fundamentalsatz der Arithmetik

Jede ganze Zahl größer als 1 kann eindeutig als Produkt von Primzahlen dargestellt werden, bis auf die Reihenfolge der Faktoren. Dies ist einer der wichtigsten Sätze der Zahlentheorie.

Darstellungsformen

Produktform: 2 × 2 × 3 × 5

Exponentialform: 2² × 3 × 5

Indexform: 2² · 3¹ · 5¹

Beispiele

Beispiel 1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• Primfaktoren: 2, 3

Beispiel 2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• Primfaktoren: 2, 3, 5

Beispiel 3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• Primfaktoren: 2, 5

Methoden der Faktorisierung

1. Probeteilung:

• Teilen Sie durch die kleinsten Primzahlen (2, 3, 5, 7...)
• Fortsetzen, bis der Quotient 1 ist
• Einfach, aber bei großen Zahlen langsam

2. Faktorbaum:

• Zerlegen Sie die Zahl in zwei Faktoren
• Fahren Sie fort, bis alle Faktoren Primzahlen sind
• Anschaulich und leicht verständlich

3. Primzahldivision:

• Teilen Sie nur durch Primzahlen
• Effizienter als alle Zahlen zu testen
• Standardalgorithmus für Computer

Schritt-für-Schritt: 60 faktorisieren

60 ÷ 2 = 30   (2 ist prim)
30 ÷ 2 = 15   (2 ist prim)
15 ÷ 3 = 5    (3 ist prim)
5 ÷ 5 = 1     (5 ist prim)

Ergebnis: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

Alle Teiler finden

Sobald Sie die Primfaktorzerlegung haben, können Sie alle Teiler bestimmen:

Beispiel: 60 = 2² × 3¹ × 5¹

• Für jede Primzahl den Exponenten von 0 bis zum Maximum wählen
• 2⁰ oder 2¹ oder 2² → (1, 2, 4)
• 3⁰ oder 3¹ → (1, 3)
• 5⁰ oder 5¹ → (1, 5)
• Alle Möglichkeiten kombinieren
• Teiler: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Formel für die Anzahl der Teiler

Wenn n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Anzahl der Teiler = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

Beispiel: 60 = 2² × 3¹ × 5¹

• Anzahl der Teiler = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12 Teiler

Formel für die Summe der Teiler

Summe = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

Beispiel: 60 = 2² × 3 × 5

• Summe = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

Anwendungen der Primfaktorzerlegung

• Kryptographie: RSA beruht auf der Schwierigkeit, große Zahlen zu faktorisieren
• ggT/kgV: Größten gemeinsamen Teiler und kleinstes gemeinsames Vielfaches finden
• Brüche kürzen: Auf den einfachsten Term reduzieren
• Zahlentheorie: Eigenschaften ganzer Zahlen untersuchen
• Informatik: Hashfunktionen, Algorithmen

Spezielle Zahltypen

Vollkommene Zahlen:

• Gleich der Summe der echten Teiler
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

Überabundante Zahlen:

• Summe der echten Teiler > Zahl
• 12: Teilersumme = 1+2+3+4+6 = 16 > 12

Defiziente Zahlen:

• Summe der echten Teiler < Zahl
• 8: Teilersumme = 1+2+4 = 7 < 8

Potenzen von 2

Zahlen, die Potenzen von 2 sind, haben eine einfache Zerlegung:

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

Hochzusammengesetzte Zahlen

Zahlen mit mehr Teilern als jede kleinere positive ganze Zahl:

• 1 (1 Teiler)
• 2 (2 Teiler)
• 4 (3 Teiler)
• 6 (4 Teiler)
• 12 (6 Teiler)
• 24 (8 Teiler)
• 36 (9 Teiler)
• 60 (12 Teiler)

Schwierigkeit der Faktorisierung

• Kleine Zahlen: leicht von Hand zu faktorisieren
• Große Primzahlen: sehr schwer zu faktorisieren
• Semiprime: Produkt zweier Primzahlen, Grundlage von RSA
• 200+ Ziffern: derzeit klassisch praktisch unlösbar
• Quantencomputer: Shors Algorithmus kann effizient faktorisieren

Häufige Zerlegungen

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 Pro-Tipp: Um schnell zu prüfen, ob eine Zahl durch kleine Primzahlen teilbar ist, merken Sie sich: teilbar durch 2, wenn die letzte Ziffer gerade ist; durch 3, wenn die Quersumme durch 3 teilbar ist; durch 5, wenn die letzte Ziffer 0 oder 5 ist; durch 9, wenn die Quersumme durch 9 teilbar ist; durch 11, wenn die alternierende Quersumme durch 11 teilbar ist. Beispiel 4356: Quersumme = 4+3+5+6 = 18 (durch 9 teilbar), also ist 4356 durch 9 teilbar! Beginnen Sie mit diesen schnellen Checks, bevor Sie größere Primzahlen ausprobieren.