Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » echter Teiler

echter Teiler

Schüler Ausbildungsstätte,

Tags: Primteiler, Primzahl, Teiler

SoNyu

17:25 Uhr, 06.06.2013

Hi, ich hätte eine Frage zu folgender Aufgabe:

Alle vorkommenden Zahlen seien natürlich. Ein Teiler

t

von

n

heißt echter Teiler, wenn

t

von

1

und

n

verschieden ist.

p

wird Primzahl genannt, wenn

p \neq 1

ist und keine echten Teiler, also keine Teiler außer

1

und

p

besitzt. p heißt Primteiler von

n

, wenn

p

Primzahl und Teiler von

n

ist. Zeige:

a)

t ∣ n \Rightarrow t \leq n

; ist

t

ein echter Teiler, so gilt

t < n

.

b) Jedes

n > 1

besitzt mindestens einen Primteiler. Hinweis: Die Menge der Teiler

> 1

von

n

besitzt ein kleinstes Element.

c) Jede natürliche Zahl

> 1

ist ein Produkt aus Primzahlen (dabei sind auch "Produkte" zugelassen, die nur aus einem Faktor bestehen). Hinweis: Wohlordnungsprinzip.

Wäre nett, wenn mich jemand bei der Bearbeitung der drei Aufgaben begleitet.
Ich möchte die Aufgaben nacheinander bearbeiten.

Zur Aufgabe a):

Hier habe ich mir gedacht, dass aus

t ∣ n

folgt, dass ein

s

gibt, für das gilt

t \cdot s = n

t, n > 0

ist auch

s > 0

Ich hätte jetzt gedacht, dass ich hier so eine Art Widerspruchsbeweis führen kann.

Ich nehme an, dass

t > n

.
Dann ist auch

\frac{t}{s} > \frac{n}{s}

Und

\frac{n}{s}

ist ja

t

Daher

\frac{t}{s} > t

Und das wäre ein Widerspruch, weshalb ich die Annahme

t > n

verwerfen muss und

t \leq n

gilt. Dabei gilt die Gleichheit

t = n

dann wenn

s = 1

wäre und

t

somit kein echter Teiler wäre.

Nur leider habe ich keine Ahnung ob das richtig ist, oder ob das total daneben ist.

Vielen Dank im voraus.

:-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Teilbarkeit natürlicher Zahlen

SoNyu

10:51 Uhr, 07.06.2013

Über eine Rückmeldung würde ich mich sehr freuen.

:-)

Bummerang

14:38 Uhr, 07.06.2013

Hallo,

also der Ansatz

t \cdot s = n

ist schon richtig, aber der Rest klingt etwas unglücklich. Versuche es doch direkt:

t | n \Leftrightarrow \exists s \in ℕ, s \neq 0, s \cdot t = n

Das ist eine der üblichen Definitionenn für einen Teiler. Nun ist aber

s i ℕ

und

s \neq 0

das selbe wie

s \in ℕ

und

s \geq 1

. Diese Ungleichung nutzt man:

s \geq 1 | \cdot t

s \cdot t \geq 1 \cdot t = t;

nun ist ja

s

so gewählt, dass

s \cdot t = n

ist, also:

n = s \cdot t \geq t

n \geq t

Echte Teiler sind ja alle Teiler ausser 1 und

n

selbst, also sind alle echten Teiler kleiner oder gleich und weil sie nicht gleich sein können immer kleiner.

SoNyu

15:11 Uhr, 07.06.2013

Wo genau siehst du den die logische Lücke in meinem "Beweis"?

Ich finde nämlich, dass mein Beweis eigentlich deinem sehr ähnlich ist. Ich habe es halt nur über einen Widerspruch aufgezogen.

Wir definieren übrigens die natürlichen Zahlen so, dass die Null nicht zu ihnen gehört.

Bummerang

15:27 Uhr, 07.06.2013

Hallo,

"Wo genau siehst du den die logische Lücke in meinem 'Beweis'?"

Wer hat behuptet, dass es da eine gäbe? Das etwas unglücklich bezieht sich darauf, dass man sich mit

\frac{t}{s}

ausserhalb der natürlichen Zahlen begeben kann, was man bei Beweisen über natürliche Zahlen gerne vermeidet.

SoNyu

15:35 Uhr, 07.06.2013

Na ja, wenn er richtig ist, dann hättest du da ja auch einfach so schreiben können und mir deine alternative als etwas "direkteren" Weg anbieten können.

Die Argumentation, dass es unschön ist einen Ausdruck

\frac{t}{s}

zu haben, der keine natürliche Zahl sein muss, sehe ich ein. :-)

Vielen Dank.

Kannst du mir auch bei den anderen Aufgabenteilen helfen?

Zur b)

Ich weiß nicht genau, was mir der Hinweis bringt.
Kann ich daraus einfach schließen, dass wenn es ein kleinstes Element in der Menge der Teiler gibt, was ja sicher ist, dass dieses Element eine Primzahl sein muss.
Wäre es keine Primzahl, so könnte ich es als Produkt zweier Faktoren schreiben, die ungleich 1, oder der Zahl selbst sein müssten, was ich ja durchaus annehmen kann.
Das würde dann heißen, dass diese Zahl selbst sich wieder als Produkt darstellen ließe, wessen Teiler auch die ursprüngliche Zahl selbst teilt, denn aus wenn gilt:

a|b und b|c, so ist a|c

Das könnte ich unter umständen so lange weiter machen, bis dies eben nicht mehr ginge, wir also ein Produkt aus Primzahlen haben, wovon dann natürlich das kleinste Element eine Primzahl sein müsste.

Geht das in die richtige Richtung?

Bummerang

16:37 Uhr, 07.06.2013

Hallo,

b)

"Kann ich daraus einfach schließen, dass wenn es ein kleinstes Element in der Menge der Teiler gibt, was ja sicher ist, dass dieses Element eine Primzahl sein muss."

Das ist der Aufhänger! Es ist sichergestellt, dass diese Menge ein kleinstes Element

t_{0}

enthält und Du behauptest, dass es eine Primzahl ist. Wäre es keine Primzahl (indirekter beweis also), dann hat dieser kleinste Teiler selbst einen echten Teiler

t_{1}

mit

1 < t_{1} < t_{0}

. Ausserdem gibt es zu

n

und

t_{0}

ein

s_{0},

so dass

n = t_{0} \cdot s_{0}

und zu

t_{0}

und

t_{1}

gibt es ein

s_{1},

so dass

t_{0} = t_{1} \cdot s_{1}

Also ist:

n = (t_{1} \cdot s_{1}) \cdot s_{0} = t_{1} \cdot (s_{1} \cdot s_{0})

Damit ist

t_{1}

ein Teiler von

n

und wegen

1 < t_{1} < t_{0}

ist

t_{1}

auch Element der Menge aller Teiler, die größer als 1 sind, aber wegen

t_{1} < t_{0}

ist

t_{0}

nicht mehr der kleinste Teiler aus dieser Menge. Das ist der Widerspruch, der die Annahme, dass

t_{0}

keine Primzahl ist, widerlegt.

Bei

c)

nutzt Du das Ergebnis aus

b)

für einen konstruktiven Beweis:

Wenn

n

eine Primzahl ist, dann ist

n

gemäß dem Zusatz zur Aufgabe ein solches Produkt. Wenn

n

keine Primzahl ist, dann folgt:

n = t_{0} \cdot s_{0}

mit

t_{0}

ist das kleinste Element aus der Menge der Teiler, die größer als 1 sind und

s_{0} > 1

. Was klar ist, ist, dass natürlich

s_{0} < n

gilt, das braucht man später noch mal.

Ist

s_{0}

selbst eine Primzahl, ist die Aufgabe beendet, ist

s_{0}

keine Primzahl, dann betrachtet man die Menge aller Teiler von

s_{0},

die größer als 1 sind. Dort entnimmt man wieder das kleinste Element

t_{1}

und erhält:

s_{0} = t_{1} \cdot s_{1}

mit

t_{1}

ist das kleinste Element aus der Menge der Teiler von

s_{0},

die größer als 1 sind und

s_{1} > 1

. Was klar ist, ist, dass natürlich

s_{1} < s_{0}

gilt, das braucht man später noch mal.

Setzt man das in

n = t_{0} \cdot s_{0}

ein, erhält man:

n = t_{0} \cdot (t_{1} \cdot s_{1}) = (t_{0} \cdot t_{1}) \cdot s_{1} = \prod_{k = 0}^{1} (t_{k}) \cdot s_{1}

Das ist der Induktionsanfang.

Es gilt also für ein

m = 1 : n = \prod_{k = 0}^{m} (t_{k}) \cdot s_{m}

und

s_{m} < s_{m - 1}

Ist

s_{m}

eine Primzahl, dann erfüllt

\prod_{k = 0}^{m + 1} (t_{k})

mit

t_{m + 1} = s_{m}

die geforderte Eigenschaft. Ist

s_{m}

keine Primzahl, dann betrachtet man die Menge der Teiler von

s_{m},

die größer als 1 sind, diese Menge hat ein kleinstes Element

t_{m + 1},

dass nach

b)

eine Primzahl ist und es gilt:

s_{m} = t_{m + 1} \cdot s_{m + 1}

mit

1 < s_{m + 1} < s_{m}

n = \prod_{k = 0}^{m} (t_{k}) \cdot s_{m} = \prod_{k = 0}^{m} (t_{k}) \cdot (t_{m + 1} \cdot s_{m + 1}) = (\prod_{k = 0}^{m} (t_{k}) \cdot t_{m + 1}) \cdot s_{m + 1} = \prod_{k = 0}^{m + 1} (t_{k}) \cdot s_{m + 1}

und das Produkt besteht nur aus Primzahlen. Das einzige, das uns jetzt noch hindern könnte: Der Algorithmus endet nie! Aber da für alle

k

gilt:

s_{k + 1} < s_{k},

wird die zu betrachtende Zahl immer kleiner. Da die Menge der natürlichen Zahlen, die kleiner als

s_{0}

sind endlich ist, ist auch nach endlich vielen Schritten der Algorithmus beendet.

SoNyu

16:41 Uhr, 07.06.2013

Zur Erinnerung:

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Ich habe nicht nach einer Komplettlösung gefragt....
Ich möchte ja auch noch selber nachdenken müssen. Deine Komplettlösung bringt mir gar nichts.

1099856

1099723

	Status: nicht eingeloggt	Noch nicht registriert?