Will man alle Teiler einer Zahl bestimmen, so kann man dies sehr systematisch über die Primfaktorzerlegung der Zahl tun. Ist z.B. die Zahl 360=2³·3²·5 gegeben, so ergeben sich die Teiler: 2⁰·3⁰·5⁰; 2⁰·3⁰·5¹; 2⁰·3¹·5⁰; 2⁰·3¹·5¹; 2⁰·3²·5⁰; 2⁰·3²·5¹; 2¹·3⁰·5⁰ usw. (die Teiler sind dann allerdings nicht nach Größe geordnet)
Im Endeffekt muß an alle möglichen Exponentenkombinationen aufspüren. Im Beispiel ergeben sich 4·3·2=24 mögliche Teiler (einschließlich 1 und 360 - nicht geordnet).
Im allgemeinen Fall n= ergeben sich also
(a ₁+1)·(a₂+1)· ··(a_r+1) mögliche Teiler.

SATZ 1.6
Hat n die Primfaktorzerlegung n=, so gilt für die Anzahl der Teiler von n: t (n)= (a ₁+1)·(a₂+1)··· (a_r+1). (gelesen: Tau von n)

AUFGABE 1.16
a) Bestimme t(n) für n=32, 200, 9295
b) Ermittle alle Zahlen, die durch x teilbar sind und genau x Teiler haben, für a ) x=11    b ) x=6    g ) x=30
c) Ermittle alle Zahlen, die durch 30 teilbar sind und genau 70 Teiler haben.

Übungsprogramm zur Berechnung von Tau

AUFGABE 1.17
Achte bei den folgenden Aufgaben auf notwendige Fallunterscheidungen:
a) Bestimme alle z<20.000 mitt(z)=45.
b) Bestimme alle z<20.000 mit t(z)=50.
c) Eine Zahl z mit 10.000<z<20.000 ist durch 30 teilbar. Bestimme z, wenn noch t (z)=56 gegeben ist. (4 Lösungen)
d) Warum gibt es kein z mit t (z)=11 und z<1.000?

DEFINITION 1.5
Für n>1 heißt s (n):=t₁+t₂+...+t_r mit t_{i Î}T_n die "Teilersumme" von n. Dabei wird über alle Teiler von n summiert; also sind auch 1 und n unter den Summanden.

AUFGABE 1.18
a) Berechne s (n) für n=32, 200 und 9295.
b) Bestimme s (n) für alle Zahlen von 15 bis 32. Kannst Du eine Regel für Primzahlen erkennen?

AUFGABE 1.19
Beweise: a+aq+aq²+aq³+...+aq^n-1= (vergleiche Aufgabe 1.8)
Berechne nun (1) 6+18+54+...+118.098 und (2) 144+72+36+...+

AUFGABE 1.20
a) Zeige an den Beispielen n=8 ,n=16 und n=27:
n prim Þ s (n^k)=
Beweise diese Formel nun.

AUFGABE 1.21
Zeige an den Beispielen n=72 und n=2000 :
n=p^kq^l Ù p,q prim Þ s (n)=
Beweise diese Formel nun.

SATZ 1.7
Hat n die Primfaktorzerlegung n= , so gilt: :
s (n)=

Beweis: Nur kurz angedeutet: Man wendet i.P. mehrfach den Sachverhalt von Aufgabe 1.21 an.

Übungsprogramm zur Berechnung von Sigma

DEFINITION 1.6
s^*(n):=s (n)-n heißt "Summe der echten Teiler" von n (oder kurz "echte Teilersumme" von n)

AUFGABE 1.22
Berechne für die folgenden Zahlen n jeweils t(n), s (n) und s^*(n).
a) n=128 b) n=31.104 c) n=3087 d) n=3.836.437.605
e) n=1184 f) n=10.935.925 g) n=1.084.730.902.983 (Tip: 1007ïn)
h) n=3×10^k, kÎN

AUFGABE 1.23
a) Eine Zahl n hat genau 8 Teiler. Sie ist kleiner als 50 und durch 7 teilbar. Berechne n.
b) Die Zahl n=2^2× 3^x× 11² hat 36 Teiler. Bestimme n.
c) Die Zahl n=3^4× 5^x hat die Teilersumme s(n)=3751. Bestimme n.
d) Für eine Zahl n mit genau zwei Primfaktoren gelte t (n²)=81. Berechne t (n³). (zwei mögliche Lösungen)

AUFGABE 1.24
a) Das Quadrat der Zahl n=a^xb^yc^z (a,b,c prim; x,y,zÎN ) hat genau 455 Teiler. Bestimme t (n). Bestimme dieses n, wenn zusätzlich bekannt ist: 9000ïn Ù n<1.000.000.
b) Bestimme k und l, wenn von n=2^k× 11^l (k,l>1) bekannt ist: s (n)=45.384.

AUFGABE 1.25
a) Eine Zahl z mit 56 Teilern und drei verschiedenen Primfaktoren hat die Teilersumme 40.640. Bestimme z.
b) Eine Zahl z mit drei verschiedenen Primfaktoren und 30 Teilern hat die Teilersumme 52.514 und ist durch 36 teilbar. Berechne s ^*(z)!
c) Eine Zahl z mit 28 Teilern hat die Teilersumme 40.640 und ist durch 12 teilbar. Berechne z.
d) Eine Zahl z mit t (z)=25 ist durch 10 teilbar. Bestimme s(z).
e) Für z=2³× p× q (p,q prim) mit s (z)=540.960 gilt, daß q um 270 größer als p ist. Berechne z.

Übungsprogramm zur Berechnung von Sigma und Tau

DEFINITION 1.7
Eine Zahl n>1 mit s (n)<2n (bzw. s ^*(n)<n) heißt "defizient" .
Eine Zahl n>1 mit s (n)>2n (bzw. s ^*(n)>n) heißt "abundant".
Eine Zahl n>1 mit s (n)=2n (bzw. s ^*(n)=n) heißt vollkommen".

AUFGABE 1.26
Untersuche die Zahlen aus Aufgabe 1.22 auf Abundanz oder Defizienz.

AUFGABE 1.27
a) 12 ist abundant - untersuche 12k für k= 5, 14, 96
b) 10 ist defizient - untersuche 10k für k=2, 3, 4, 5, 6

AUFGABE 1.28
Suche zu jedem der folgenden Kriterien für Abundanz und Defizienz drei mindestens zweistellige Beispiele und verifizere damit:

SATZ 1.8
Im Folgenden seien p und q (wie immer) Primzahlen.
Eine Zahl n ist defizient, wenn

a) n eine Primzahlpotenz ist. (n=p^r)
b) n=p× q mit p, q³3 ist.
c) n=p^r× q^s mit p, q³ 3 uns r,s ³1 ist.
d) n ein Produkt von bis zu 6 Primzahlpotenzen mit p_i>3 ist.
e) n=3^k × 5×7 mit k<3 ist.
f) n=2^k× p mit p³ 3 und 2^k+1<p+1 ist.

SATZ 1.9
Eine Zahl n ist abundant, wenn

a) n ein Vielfaches einer vollkommenen Zahl ist.
b) n ein Vielfaches einer abundanten Zahl ist.
c) n=2^k× p mit p³ 3 und 2^k+1>p+1 ist.
d) n= ist und für mindestens ein p_i>3 gilt: 2^k+1>p_i+1
e) n=3^k× 5× 7 mit k³3 ist.
f) die Primfaktorzerlegung von n den Faktor: 3²× 5× 7×11 enthält.

AUFGABE 1.29
Untersuche die folgenden Zahlen mit Hilfe der Sätze 1.8 und 1.9 auf Abundanz und Defizienz. Berechne jeweils auch s
a) 2835 b) 243 c) 66 d) 391 e) 2184
f) 100 g) 186 h) 104 i) 107.653 j) 463.287.825

AUFGABE 1.30
Untersuche alle Zahlen von 5500 bis 5520 mit Hilfe der Sätze 1.8 und 1.9 auf Abundanz, Defizienz und Vollkommenheit.
(ebenso für die Zahlen von 15500 bis 15510)

AUFGABE 1.31
a) Die Zahl n=2^x× 11^y hat genau 21 Teiler und ist abundant.
Bestimme s(n).
b) Für die Zahl n=a^x× b^y× c^z (a,b,c prim; 1£ x£ y£ z) gelte: t (n³)=1729. Bestimme t (n) und t (n²).

AUFGABE 1.32
Beweise: n ist abundant, wenn n Produkt von mindestens drei aufeinanderfolgenden natürlichen Zahlen ist.

BEWEISE, BEWEISE, BEWEISE

Hier sollen die Beweise zu den Kriterien für Abundanz und Defizienz aus den Sätzen 1.8 und 1.9 nachgeholt werden.

ad 8a
Wir haben zu zeigen s (p^r)<2× p^r. Wir formen diese Aussage zunächst äquivalent um: s (p^r)= ï ×(p-1)
Û p^r+1-1<2p^r+1-2p^r
Û 2p^r-1<p^r+1 (*)
Um die Aussage zu beweisen, reicht es also, die umgeformte Aussage (*) aus einer allgemeingültigen Aussage abzuleiten. Einen Hinweis für eine geeignete Aussage liefert (*) nach Division durch p^r: . ist unbedeutend klein - daher versuchen wir es mit der für alle akzeptablen Aussage:
2£p (p prim!)
Þ 2p^r£p^r+1
Þ 2p^r-1<p^r+1 - und das ist Aussage (*).
Damit ist der Beweis vollständig. Man beachte den "Trick" in der letzten Zeile: die "kleiner-Seite" einer Ungleichung kann man getrost noch kleiner machen, ohne etwas am Wahrheitsgehalt der Ungleichung zu verändern (natürlich kann man ebenso die "größer-Seite" vergrößern).

ad 8b
Wir beginnen mit einer in Mathematikerkreisen beliebten Floskel: oBdA (d.h. ohne Beschränkung der Allgemeinheit (des Beweises)) gelte 2<p<q. Wir haben zu zeigen s (pq)<2pq. Leicht stellt man fest, dass pq nur die Teiler 1,p,q und pq hat. Wir formen also um:
s(pq)<2pq
Û 1+p+q+pq<2pq
Û 1+p+q<pq (*)
Da p>2 ist, können wir ersetzen: p=2+n mit n³ 1. Damit gilt:
pq=(2+n)× q=2q+nq=q+q+nq>p+q+nq>p+q+1 - das ist (*)!
Dabei gilt das erste ">" wegen q>p und das zweite wegen nq>1.

In diesem und auch im nächsten Beweis benötigen wir zwei Hilfssätze, die vorweg bewiesen werden sollen.

HS1
Beweis: Der linke Teil der Ungleichung läßt sich mit der Summenformel zur geometrischen Reihe (A 1.8) zusammenfassen:

Man beachte, daß der Zähler im ersten Bruch nach dem zweiten "="-Zeichen kleiner ist als der Nenner und damit der Bruch kleiner als 1 ist.

HS2
a_n:= ist streng monoton fallend (d.h. die Glieder der Folge werden mit größer werdenden n immer kleiner).
Beweis: . Mit zunehmendem n wird n-1 größer und der Summand, der zu 1 addiert wird, deshalb immer kleiner.

ad 8c
Nach Aufgabe 1.21 wissen wir : s(p^r× q^s)=s (p^r)× s (q^s). Dann gilt:
s (p^r× q^s)<2× (p^r× q^s)
Û s (p^r)× s (q^s)< 2× (p^r× q^s)
Û (*)
Wir beweisen nun wieder die äquivalente Ungleichung (*):


Würde man bei der letzten Abschätzung mit p=2 beginnen, so wäre das Produkt nicht mehr kleiner als 2. Dies erklärt die Bedingung p,q ³3 in Satz 8c.

ad 8d
Der Beweis von Satz 8d läuft analog zu dem von 8c:

(HS1)

Am letzten Produkt erhellt sich, warum ausgerechnet 6 Faktoren zulässig sind: für einen weiteren Faktor müßte man mit multiplizieren, was aber einen Wert von ca. 2,04 > 2 erzeugen würde.
Natürlich ist man bei der Abschätzung teilweise etwas grob: der Satz 8d besagt nicht etwa, dass ein Produkt von mehr als 6 Primfaktoren größer als drei nicht defizient sein könnte, wie man z.B. am Beispiel der Zahl n=11× 13× 17× 19× 23× 29× 31 sieht, die 7 Primfaktoren zum Trotz defizient ist. Satz 8d sagt lediglich, dass im Fall von sechs oder weniger Primfaktoren größer 3 die Zahl immer defizient ist.

ad 8e
s(3^k × 5× 7)=(3^k+1-1) ×24
Þs(n)- 2n=24(3^k+1-1)- 2× 3^k×5 × 7=24× 3^k+1 - 24- 70× 3^k=72× 3^k- 70× 3^k- 24
Þs (n)- 2n=2× 3^k- 24
Wir haben damit zugleich 1.9e bewiesen!

ad 8f
s(n)=s (2^k× p)=(2^k+1-1)(p+1)
Þs(n)-2n=2^k+1× p+2^k+1- p-1-2× 2^k× p=2^k+1-p-1
Þs(n)- 2n
Die letzte Zeile liefert noch ein später benötigtes interessantes Ergebnis: n=2^k× p ist vollkommen genau dann, wenn p=2^k+1-1 und prim ist.

ad 9a
Es sei n vollkommen, also s (n)=2n, mit T_n={1,t₂,t₃,...,t_r}. Dann hat ein echtes Vielfaches k× n von n mindestens die Teiler k, kt₂ ,kt₃,...,kt_r. (Beispiel: T₆={1,2,3,6} - T_{3× 6}={3,6,9,18,..}).Von diesen Teilern ist aber sicher keiner gleich 1. Damit ergibt sich:
s (kn)³ 1+k+kt₂+...+kt_r=1+k(1+t₂+...+t_r)=1+k× s (n)>k× s (n)=k× 2n=2× kn

ad 9b: kann von 1.9a beinahe direkt übernommen werden
ad 9c: siehe Beweis 1.8f
ad 9d: folgt aus 1.9b und 1.9c
ad 9e: siehe 1.8e
ad 9f: folgt unten

Die Sätze 9a und 9b besagen, dass man aus jeder abundanten bzw. vollkommenen Zahl durch Vielfachenbildung unendlich viele abundante Zahlen konstruieren kann. Umgekehrt gibt es zu jeder abundanten Zahl n eine kleinste abundante oder eine vollkommenen Zahl, deren Vielfaches n ist. Wir wollen eine solche Zahl A-Wurzel von n nennen.

DEFINITION 1.8
n heißt "A-Wurzel", wenn n vollkommen ist oder wenn n abundant ist und keinen abundanten oder vollkommenen Teiler besitzt.

Die kleinste A-Wurzel ist die Zahl 6, die nächste 20, die folgenden sind 28, 70, 88, 104...
Jede dieser Zahlen ist also der Quell einer unendlichen Menge von abundanten Zahlen, die durch die Wurzel in der Primfaktorzerlegung ihren Stempel aufgeprägt bekommen. Nehmen wir die ersten 6 dieser A-Wurzeln, so können wir formulieren:
n ist abundant, wenn die Primfaktorzerlegung von n die Faktoren 2 × 3 oder 2^2× 5 oder 2^2× 7 oder 2× 5× 7 oder 2^3× 11 oder 2^3× 13 enthält .
Alle diese Kriterien könnte man auch mit 1.9d herleiten. So ergibt sich als nächste A-Wurzel z=2^4× 17=272, danach Z=2^4× 19=304 usw...
Nun stellt sich die Frage nach ungeraden A-Wurzeln. Ein erstes Kriterium liefert 1.9e: z=3^3× 5× 7=945 ist die erste ungerade abundante Zahl. Die nächsten sind 1575, 2205 ,2835, 3465,...
Alle diese Zahlen sind Vielfache von 315, was eine intensivere Beschäftigung mit dieser Zahl sinnvoll erscheinen läßt:
945=3× 315 1575=5× 315 2205=7× 315

Sind alle Primvielfachen von 315 abundant und damit A-Wurzeln?

Es sei also p>s (315× p)=s (315)× s (p) =624× (p+1)>2× 315× p
Û 624p+624>630p Û 624>6p Û 104>p

Also sind nicht alle Primvielfachen von 315 A-Wurzeln, jedoch alle bis p=103:
3³·5·7 ; 3²·5²·7 ; 3²·5·7² ; 3²·5·7·11 ; 3²·5·7·13 ;.....; 3²·5·7·103 sind A-Wurzeln.

Damit ist auch 9 f bewiesen.

Mit dem eben vorgeführten Ansatz kann man übrigens weitere ungerade A-Wurzeln suchen. Ist aber 3 nicht mehr in der Primfaktorzerlegung enthalten, so sind nach 8d mindestens 7 verschiedene Primfaktoren nötig.

AUFGABE 1.33
Suche A-Wurzeln unter den Primvielfachen von 36465.

Zusätzliche Aufgaben zu Kapitel 1
1) Ermittle eine Zahl n so, daß sowohl n als auch n-24 als auch n+24 eine Quadratzahl ist.
2) Ermittle alle Primzahlen p, für die 3p+4 eine Quadratzahl ist.

Download Kap 1(40 KB)

Copyright © Michael Dorner, Okt. 2000.