Hi
bei www.confine.com/disavowed/challenges gibt es einen Contest, bei dem man verschiedene Aufgaben zu lösen hat.
Im Medium Level ist unter „programming“ die höchste Zahl unter 100 Quintillionen gesucht, die ein Palindrom ist und durch alle Primzahlen von 10 bis 30 teilbar ist.
Nun hat man mir gesagt, dass „durch alle Primzahlen von 10 bis 30 teilbar“ gleichzeitig „durch das Produkt aller Primzahlen von 10 bis 30 teilbar“ bedeutet.
Das verstehe ich aber nicht, dass hiesse ja, dass das kgv dieser Primzahlen das Produkt dieser Primzahlen ist, oder?
Gibt es dafür irgendwo im Netz einen Beweis, oder kann ihn jemand hier posten?
Ich denke, daß die Tatsache, daß der kgv zweier Primzahlen das Produkt ist, relativ schnell einsehbar ist. Dazu muß man sich nur verdeutlichen, was kgv ist.
Der kgv zweier ganzer Zahlen a und b ist die kleinste Zahl, für die gilt
kgv/a ist ganze Zahl und kgv/b ist ganze Zahl
Die letzten beiden Aussagen bedeuten, daß a und b Teiler von kgv sein müssen.
Nun hat kgv eine Primfaktorzerlegung. Sind laut Voraussetzung a und b Primzahlen, dann müssen sie in dieser Primfaktorzerlegung vorkommen, um Teiler zu sein. Also gilt
kgv = a*b*c
wobei c irgendeine Zahl ist, die durch die übrigen Primfaktoren zustande kommt oder 1.
Die kleinste mögliche Zahl c, die alle Bedingungen erfüllt, ist c=1, also ist a*b der kleinste gemeinsame Vielfache.
Nun hat kgv eine Primfaktorzerlegung. Sind laut Voraussetzung
a und b Primzahlen, dann müssen sie in dieser
Primfaktorzerlegung vorkommen, um Teiler zu sein. Also gilt
kgv = a*b*c
wobei c irgendeine Zahl ist, die durch die übrigen
Primfaktoren zustande kommt oder 1.
Die kleinste mögliche Zahl c, die alle Bedingungen erfüllt,
ist c=1, also ist a*b der kleinste gemeinsame Vielfache.
Das versteh ich noch nicht ganz. Ich kenn mich mit Primfaktorzerlegung leider nicht aus.
Also warum müssen a und b in dieser Zerlegung vorkommen?
Also, es gibt einen sehr wichtigen Satz in der Theorie der Zahlen, daß sich jede ganze Zahl eindeutig als Produkt von Primzahlen schreiben lässt (wobei die 1 nicht zu den Primzahlen gehört), also z.B.
24 = 2*2*2*3
oder
42 = 2*3*7
Wichtig ist, daß diese Zerlegung eindeutig ist.
Sagt man nun, daß eine Primzahl ein Teiler von einer Zahl ist, dann bedeutet das ja, daß es eine ganze Zahl gibt, so daß die Primzahl mal dieser ganzen Zahl die erste Zahl ergibt, oder mit Formeln ausgedrückt:
p ist Teiler der Zahl a bedeutet, daß es eine Zahl b gibt, so daß
a = p*b
Setzt man nun die Primfaktorzerlegung von b in diese Formel ein, also b= p1*…*pn, dann bekommt man eine Primfaktorzerlegung von a, also
a = p*p1*…*pn
Da die Primfaktorzerlegung von a eindeutig ist, ist bewiesen, daß p darin vorkommen muß, wenn p ein Teiler von a ist.
Das verstehe ich aber nicht, dass hiesse ja, dass das kgv
dieser Primzahlen das Produkt dieser Primzahlen ist, oder?
Gibt es dafür irgendwo im Netz einen Beweis, oder kann ihn
jemand hier posten?
Das kgV mehrerer Zahlen kann nur dann kleiner als das Produkt dieser Zahlen sein, wenn sie gemeinsame Teiler haben (z.B. kgV(4,6) = 12