Den ggT (größten gemeinsamen Teiler) vergleichen ohne zu berechnen?
Hallöchen,
Wie findet man heraus ob die folgende Aussage stimmt, ohne dabei den ggT auszurechnen: "ggT(10101, 74787) = ggT(10101, 64686)"
Ich darf also weder den euklidischen Algorithmus, noch die Primfaktorzerlegung verwenden, aber was kann ich denn sonst machen?
Es ist eine Aufgabe an der Uni, für die ich zwar nur "wahr oder falsch mot Begründung" abgeben muss, aber ich komme auf keine Idee
Ich hoffe jemand kann mit helfen :)
3 Antworten
Ich würde so herangehen:
Es fällt auf, dass die erste, die dritte und die fünfte Ziffer bei allen drei zahlen gleich sind, zerlegen wir die beiden großen Zahlen doch einmal:
74787=70707+4080
64680=60606+4080
10101
Alle hier vorkommenden Zahlen sind durch 3 teilbar, was leicht an deren Quersummen erkennbar ist. Also teilen wir durch 3.
24929=23569+1360
21562=20202+1360
3367
24929, 21562 und 3367 müssen wir jetzt auf gemeinsame Teiler untersuchen.
Jetzt müssen wir "nur" noch die 3367 auf mögliche Teiler untersuchen. Die 7 ist dabei, aber durch die sind die anderen beiden Zahlen nicht teilbar.
Ok, der Beweis, dass die beiden ggTs gleich sind, haben hier zwei Leute schon geschrieben. Und sie haben mich dabei noch mal an die Aufgabenstellung erinnert. Die war nicht, den ggT zu finden, sondern zu beweisen, dass die ggTs gleich sind. Muss beim nächsten Mal etwas genauer lesen ...
Die Aussage stimmt.
Wegen...
(bzw. 64686 = 74787 - 10101)
... ist ggT(10101, 74787) = ggT(10101, 64686) den gleichen größten gemeinsamen Teiler.
Siehe auch: Bemerkung am Ende meiner Antwort. [Das habt ihr bestimmt auch so oder so ähnlich für den Beweis des euklidischen Algorithmus gezeigt.]
ggT(a, b) = ggT(a, b - a)
============
------ Bemerkung 1 ------
Seien a, b, c ∈ ℤ mit c = b - a. Dann ist eine Zahl d ∈ ℤ genau dann ein gemeinsamer Teiler von a und b, wenn d auch ein gemeinsamer Teiler von a und c ist.
------ Beweis zu Bemerkung 1 ------
1. Richtung:
Sei d ein gemeinsamer Teiler von a und b. Dann gibt es q₁, q₂ ∈ ℤ mit a = q₁ ⋅ d und b = q₂ ⋅ d. Dann ist...
Dementsprechend ist d dann auch ein Teiler von c. Und damit ist d dann auch ein gemeinsamer Teiler von a und c.
2. Richtung:
Sei d ein gemeinsamer Teiler von a und c. Dann gibt es q₁, q₂ ∈ ℤ mit a = q₁ ⋅ d und c = q₂ ⋅ d. Dann ist...
Dementsprechend ist d dann auch ein Teiler von b. Und damit ist d dann auch ein gemeinsamer Teiler von a und b.
------ Bemerkung 2 ------
Aus Bemerkung 1 ergibt sich offensichtlich für a, b, c ∈ ℤ mit c = b - a, dass dann ggT(a, b) = ggT(a, c) gilt.
Dies kann man auch folgendermaßen formulieren...
Für alle a, b ∈ ℤ gilt:
wenn ich mich recht erinnere, arbeitet ersie oft mit Word ( was anscheinend gut geht )
Und das kann man dann einfach hier einfügen?
Ok, das muss ich dann mal mit LibreOffice, Softmaker Office und Pages probieren. Word habe ich nicht, und MS Office kommt nicht auf meinen Mac, habe damit zu schlechte Erfahrungen gemacht.
Der eingebaute Formeleditor von GF gibt das leider nicht her.
Oh, doch. Mit dem Formeleditor von gutefrage.net arbeite ich hier meistens bei meinen Antworten (auch bei meiner Antwort hier bei dieser Frage).
Man kann auch in den Einstellungen...
https://www.gutefrage.net/einstellungen/darstellung
... die Option „Vereinfachten Formeleditor deaktivieren und Formeln direkt als LaTeX eingeben“ aktivieren. Das ist für mich angenehmer. Und dann hat man auch etwas mehr Möglichkeiten.
------------
Ansonsten, verwende ich in manchen Fälle auch manchmal immer noch (wie auch von Halbrecht angesprochen) MS Word zum aufschreiben der Formeln, und füge dann in die Antowrt einen Bildschirmausschnitt als Bild ein. [Das mache ich in letzter Zeit aber meist nur noch, wenn ich besondere Gestaltungsmöglichkeiten brauche. Beispielsweise wenn ich gewisse Teile farbig hervorheben möchte.]
Danke.
Schon lange her, dass ich mich mit LaTeX beschäftigt habe, muss ich wohl erstmal wieder auffrischen.
ggT( a, b ) = ggT( a, b-a )
Nur eine Frage: Wie schafffst Du es, die Formeln hier so darzustellen? Der eingebaute Formeleditor von GF gibt das leider nicht her.