ggT teilerfremder Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:46 Do 15.05.2008 | | Autor: | msg08 |
| Aufgabe | Durch das Prinzip des Euklidischen Algorithmus erhält man bei teilerfremden Zahlen immer 1.
Euklidischer Algorithmus für bel. natürliche Zahlen a und b:
Solange a [mm] \neq [/mm] b
Falls a > b: a = a-b
Falls a < b: b = b-a |
Hi,
in der Zahlentheorie gibt es glaub ich einen Satz. Mit dem soll genau das erklärt werden. Der ggT zweier teilerfremder Zahlen ist immer 1.
Kennt ihn jemand? Mich interessiert das sehr brennend. Habe mir den Euklidischen Algorithmus logisch soweit erschlossen, nur brauche ich jetzt noch eben das Verständnis zum ggT zweier teilerfremden Zahlen.
Freue mich über jeden logischen Ansatz zum Verständnis.
Wieso passiert das?
MfG
Martin
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:34 Do 15.05.2008 | | Autor: | msg08 |
Vielen Dank für die vielen Links!!!
Vielleicht würde mir das genauere Verständnis von Rest = 0 helfen.
Also die Definition für Teilerfremdheit ist glaub ich Verständnisvoraussetzung.
Wieso der Algorithmus aber selbst bei Teilerfremdheit die 1 ergibt, erklärt es nicht.
Mache mal deutlich, wie weit ich mich da jetzt rangetastet habe:
Gesucht ist der ggT von 12 und 44
Primfaktorzerlegung:
12 = 2*2*3
44 = 2*2*11
Derselbe Faktor wäre hier also 2*2 = 4.
Jetzt werden rein logisch die Zahlen in gleicherPrimfaktor-viele Summanden gelegt:
12 = 2*2*3 = 4*3 = (3) + (3) + (3) + (3)
44 = 2*2*11 = 4*11 = (11) + (11) + (11) + (11)
jetzt passiert eben die Eigenschaft des Euklidschen Algorithmuses für teilerfremde Zahlen.
In den Summanden der Zahlen hätte man immer teilerfremde Zahlen zueinander und die werden ja immer jeweils auf 1 gebracht!!!
Vielleicht hilft das Verständnis von Rest = 0 ja, steige aber leider nicht hinter.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:33 Do 15.05.2008 | | Autor: | andreas |
hi
> Vielleicht würde mir das genauere Verständnis von Rest = 0
> helfen.
ich muss zugeben, dass ich vorhin die definition des euklidischen algorithmus, wie du ihn verwenmdest zu schlampig gelesen habe: also vergiss rest null. es sollte heißen: sobald $a = b$ ist diese zahl genau der ggT der ursprünglichen zahlen.
> Also die Definition für Teilerfremdheit ist glaub ich
> Verständnisvoraussetzung.
>
> Wieso der Algorithmus aber selbst bei Teilerfremdheit die 1
> ergibt, erklärt es nicht.
rechen dazu am besten später mal ein beispiel, dann wird es vielleicht etwas klarer. zum beweis der eigenschaft genügt im prinzip (die recht einfach zu beweisende aussage) [mm] $\textrm{ggT}(a, [/mm] b) = [mm] \textrm{ggT}(a, [/mm] b-a) = [mm] \textrm{ggT}(a [/mm] - b, b)$ für $a [mm] \not= [/mm] b$.
> Mache mal deutlich, wie weit ich mich da jetzt rangetastet
> habe:
>
> Gesucht ist der ggT von 12 und 44
>
> Primfaktorzerlegung:
>
> 12 = 2*2*3
> 44 = 2*2*11
>
> Derselbe Faktor wäre hier also 2*2 = 4.
genau. folglich ist [mm] $\textrm{ggT}(12, [/mm] 44) = 4$. der rest ist hier nicht so hlifreich. mach dir besser klar, wie der algorithmus arbeitet. ich schreibe jetzt einfach mal die belegung der variablen in den einzelnen schritten bis zum abbruch auf.
Euklidischer Algoritmus für $m = 12$ und $n = 44$:
1. Schritt
$a = m = 12$
$b = n = 44$.
2. Schritt ($a < b$):
$a = 12$
$b = 44 - 12 = 32$
3. Schritt ($a < b$):
$a = 12$
$b = 32 - 12 = 20$
4. Schritt ($a < b$):
$a = 12$
$b = 20 - 12 = 8$
5. Schritt ($a > b$):
$a = 12 - 8 = 4$
$b = 8$
6. Schritt ($a < b$):
$a = 4$
$b = 8 - 4 = 4$
da nun $a = b = 4$ sollte dies auch der ggT von $m = 12$ und $n = 44$ sein und das stimmt ja auch mit dem überein, was du oben festgestellt hast.
rechnen nun doch mal mit dem algorithmus den ggT von $39$ und $32$ aus. was erhälst du?
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:56 Do 15.05.2008 | | Autor: | msg08 |
> rechen dazu am besten später mal ein beispiel, dann wird es
> vielleicht etwas klarer. zum beweis der eigenschaft genügt
> im prinzip (die recht einfach zu beweisende aussage)
> [mm]\textrm{ggT}(a, b) = \textrm{ggT}(a, b-a) = \textrm{ggT}(a - b, b)[/mm]
> für [mm]a \not= b[/mm].
Das kann ich nur an konkreten Werten gekoppelt zeigen. Mache ich gleich mal mit dem von dir gegebenen Beispiel. Allgemein fehlt mir leider der Weg.
> Euklidischer Algoritmus für [mm]m = 12[/mm] und [mm]n = 44[/mm]:
>
> 1. Schritt
> [mm]a = m = 12[/mm]
> [mm]b = n = 44[/mm].
>
> 2. Schritt ([mm]a < b[/mm]):
> [mm]a = 12[/mm]
> [mm]b = 44 - 12 = 32[/mm]
>
> 3. Schritt ([mm]a < b[/mm]):
> [mm]a = 12[/mm]
> [mm]b = 32 - 12 = 20[/mm]
>
> 4. Schritt ([mm]a < b[/mm]):
> [mm]a = 12[/mm]
> [mm]b = 20 - 12 = 8[/mm]
>
> 5. Schritt ([mm]a > b[/mm]):
> [mm]a = 12 - 8 = 4[/mm]
> [mm]b = 8[/mm]
>
> 6. Schritt ([mm]a < b[/mm]):
> [mm]a = 4[/mm]
> [mm]b = 8 - 4 = 4[/mm]
mir gefällt dein systematischer Aufbau des Durchspielens. Merk ich mir. Sehr sehr schön!!!
> rechnen nun doch mal mit dem algorithmus den ggT von [mm]39[/mm] und
> [mm]32[/mm] aus. was erhälst du?
Euklidischer Algoritmus für [mm]m = 39[/mm] und [mm]n = 32[/mm]:
1. Schritt
[mm]a = m = 39[/mm]
[mm]b = n = 32[/mm].
2. Schritt ([mm]a > b[/mm]): ggT(m=a-b, n=b)
[mm]a = 39-32 = 7[/mm]
[mm]b = 32[/mm]
3. Schritt ([mm]a < b[/mm]): ggT(m=a, n=b-a)
[mm]a = 7[/mm]
[mm]b = 32-7 = 25[/mm]
4. Schritt ([mm]a < b[/mm]):
[mm]a = 7[/mm]
[mm]b = 25 - 7 = 18[/mm]
5. Schritt ([mm]a < b[/mm]):
[mm]a = 7[/mm]
[mm]b = 18-7 = 11[/mm]
6. Schritt ([mm]a < b[/mm]):
[mm]a = 7[/mm]
[mm]b = 11-7 = 4[/mm]
7. Schritt ([mm]a > b[/mm]):
[mm]a = 7-4 = 3[/mm]
[mm]b = 4[/mm]
8. Schritt ([mm]a < b[/mm]):
[mm]a = 3[/mm]
[mm]b = 4-3 = 1[/mm]
9. Schritt ([mm]a > b[/mm]):
[mm]a = 3-1 = 2[/mm]
[mm]b = 1[/mm]
10. Schritt ([mm]a > b[/mm]):
[mm]a = 2 -1 = 1[/mm]
[mm]b = 1[/mm]
da a=b=1 sollte das auch der ggT von [mm] m=39 [/mm] und [mm] n=32 [/mm] sein, weiter noch von ggt[m=a,n=b], ggt[m=a-b,n=b], wenn m>n und ggt[m=a,n=b-a], wenn m<n.
> [mm]\textrm{ggT}(a, b) = \textrm{ggT}(a, b-a) = \textrm{ggT}(a - b, b)[/mm]
> für [mm]a \not= b[/mm].
Kann man mathematisch bestimmt raffinierter beweisen.
Bei meinen Überlegungen selber bin ich leider auch nicht weiter :(.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:31 Do 15.05.2008 | | Autor: | andreas |
hi
kannst du etwas konkretere fragen stellen? mir ist nicht ganz klar, was dir unklar ist beziehungsweise was du wissen willst.
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:32 Do 15.05.2008 | | Autor: | msg08 |
Also wenn man sich die natürlichen Zahlen als Strecken vorstellt, so kann man jede Strecke in gleichgroße Strecken aufteilen.
Die Möglichkeit der diskreten Aufteilungen gibt ja die Primfaktorzerlegung an.
Hat man also eine Primzahl als Strecke vorgegeben, so ist ihr kleinstes Teil die 1. Also kann die Strecke in Primzahl gleichgroße 1Stücke geteilt werden.
Wendet man den Euklidischen Algorithmus an, so zieht man ja in vorgegebener Weise voneinander Strecken 2er Zahlen ab, bis man beide Male eine gleichgroße Strecke hat. Das ist dann ja die größte gemeinsame Strecke, die Teil beider Gesamtstrecken ist.
Wenn man teilerfremde Zahlen bzw. Strecken hat, so ergibt sich immer 1 als ggT.
Wieso ist das aber so?
Also ich suche nicht nach Beweisen, dass es eben so ist, sondern nach einer logischen Erklärung wieso das so ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:36 Sa 17.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:22 So 18.05.2008 | | Autor: | msg08 |
Noch eine Verlängerung!!!
Eine Erklärung fänd ich nämlich schon sehr klasse!!!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:24 So 18.05.2008 | | Autor: | msg08 |
Vielleicht kriegt ja jetzt einer eine Idee zu diesem logischen Phänomen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:06 So 18.05.2008 | | Autor: | leduart |
Hallo
1. ist dir klar, was ggT von a und b bedeutet?
es ist die größte Zahl, durch die a und b beide teilbar sind.
bei kleinen Zahlen kann man jetzt schnell alle Teiler aufschreiben, wie bei etwa 36 und 42
36=2+2*3*3
42=2*3*7
man sieht sie haben 2 und 3 gemeinsam also sind beide durch 6 teilbar.
wenn du das mit 123456 und 87654 machen willst gehst du am Stock!
deshalb erstmal der Sinn des Algorithmus, man kommt schnell auf kleinere Zahlen, ohne mühsam zu dividieren!
jetz dein "logisches Phänomen:
Du stellst dir die Zahlen gern auf dem Zahlenstrahl vor. wenn eine Zahl durch 6 Teilbar ist, kannst du das Stück zu ihr in lauter 6er Strecken einteilen. genauso die zweite Zahl die durch 6 Teilbar ist.
Wenn du jetzt die kleinere abziehst, also von hinten abträgst, schneidest du ja nur 6er Strecken ab, d.h der Rest, die Differenz ist wieder durch 6 Teilbar.
dann hast du jetzt die Differenz und die kleinere der ursprünglichen Zahlen, mit denen machst du dasselbe, wieder landest du bei ner Zahl, die aus 6-er strecken besteht.
löst das dein Problem?
Ergebnis: haben 2 Zahlen einen gemeinsamen Teiler, dann hat den auch ihre Differenz (natürlich auch ihre Summe!
Wenn das deine Frage nicht wirklich beantwortet, musst du versuchen deine Schwierigkeit noch mal anders darzustellen.
gruss leduart
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:23 So 18.05.2008 | | Autor: | msg08 |
Sehr sehr sehr sehr sehr sehr schöne Schilderung soweit!!!
Vielen lieben Dank!!!
Ein Vorstellungsweg ganz nach meiner Natur!!!
Was ich mir dann nicht erklären kann ist noch Folgendes:
Wieso lande ich am Ende bei 2 gleichgroßen Stücken.
In dem Fall 2 6er-Strecken?
Nochmal zur Vorstellung, superschön!!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:42 So 18.05.2008 | | Autor: | leduart |
Hallo msg
Man landet nicht bei 2 sondern bei einer,
bei unserem Beispiel 42 und 36
42-36=6
36-6=30
30-6=24
usw
12-6=6
nirgends 2 6er
der bessere Algorithmus kürzt das ab:
42-36=6
36=6*6
oder
45,81
81-45=36
45-36=9
36=4*9
statt 4 mal hintereinander immer wieder 9 abzuziehen.
man kann auch gleich ein Vielfaches abziehen
220, 33
220-6*33=22
33-22=11
22-11=11
ggt (220,33)=11
Versuchs mal mit riesigen Zahlen, damit sichs auch lohnt!
Gruss leduart, kein Prof.!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:57 So 18.05.2008 | | Autor: | msg08 |
ggT(1000,312)
1000-312=688
688-312=376
376-312=64
312-64=248
248-64=184
184-64=120
120-64=56
64-56=8
56-8=48
48-8=40
40-8=32
32-8=24
24-8=16
16-8=8
8=8
verkürzt:
ggT(1000,312)
1000-3*312=64
312-4*64=56
64-56=8
56=7*8
Auch die Anwendung wird mir so viel klarer und geht besser von der hand.
Nur wieso lande ich am Ende immer bei dem gemeinsamen Teiler?
Kann ich mir leider nicht deutlich machen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:14 So 18.05.2008 | | Autor: | andreas |
hi
> Nur wieso lande ich am Ende immer bei dem gemeinsamen
> Teiler?
hm, das hat leduart ja im prinzip schon geschrieben: angenommen du hast zwei zahlen $m$ und $n$ und willst $c = [mm] \textrm{ggT}(m, [/mm] n)$ berechnen. da $c$ sowohl $m$ als auch $n$ teilt (es ist ja ein gemeinsamer teiler), kannst du beide in "stücke" der länge $c$ zerlegen. du nimmst bei dem algorithmus immer vielfache der länge $c$ weg und am ende kann dann natürlich auch nur ein vielfaches der länge $c$ übrigbleiben. da die restlichen faktoren in $m$ und $n$ aber teilerfremd sind, landet man dann am ende auch wirklich bei $c$ und nicht etwa bei $2c$, denn sonst müsste $2c$ ein teiler von sowohl $m$ als auch $n$ sein und das widerspricht der definition, dass $c$ der größte gemeinsame teiler von $m$ und $n$ ist.
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 16:12 So 18.05.2008 | | Autor: | msg08 |
> hi
>
> > Nur wieso lande ich am Ende immer bei dem gemeinsamen
> > Teiler?
>
> hm, das hat leduart ja im prinzip schon geschrieben:
> angenommen du hast zwei zahlen [mm]m[/mm] und [mm]n[/mm] und willst [mm]c = \textrm{ggT}(m, n)[/mm]
> berechnen. da [mm]c[/mm] sowohl [mm]m[/mm] als auch [mm]n[/mm] teilt (es ist ja ein
> gemeinsamer teiler), kannst du beide in "stücke" der länge
> [mm]c[/mm] zerlegen. du nimmst bei dem algorithmus immer vielfache
> der länge [mm]c[/mm] weg und am ende kann dann natürlich auch nur
> ein vielfaches der länge [mm]c[/mm] übrigbleiben.
Auch super erklärt!!! Bin soweit vollkommen mit einverstanden.
> da die restlichen
> faktoren in [mm]m[/mm] und [mm]n[/mm] aber teilerfremd sind, landet man dann
> am ende auch wirklich bei [mm]c[/mm] und nicht etwa bei [mm]2c[/mm], denn
> sonst müsste [mm]2c[/mm] ein teiler von sowohl [mm]m[/mm] als auch [mm]n[/mm] sein und
> das widerspricht der definition, dass [mm]c[/mm] der größte
> gemeinsame teiler von [mm]m[/mm] und [mm]n[/mm] ist.
den Teil krieg ich noch nicht rein
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:43 So 18.05.2008 | | Autor: | msg08 |
Habs!!!!!!!!!
Die Reste zueinander ergeben eine streng monoton abfallende Folge natürlicher Zahlen, an deren Ende eben Rest=0 rauskommen muß.
ggT(a,b) mit natürlichen Zahlen a,b oBdA a>b
a = [mm] n*b+r_{0}
[/mm]
b = [mm] n*r_{0}+r_{1}
[/mm]
...
[mm] r_{n-2} [/mm] = [mm] n*r_{n-1}+r_{n}
[/mm]
[mm] r_{0} [/mm] > [mm] r_{1} [/mm] > ... > [mm] r_{n}=0
[/mm]
wegen [mm] ggT(a,b) = (b,r_{0}) = ... = ggT(r_{n-2},r_{n-1}) = r_{n-1} [/mm]
[mm] r_{n-1} [/mm] wär das 6er-Stück, mit dessen Vielfachem [mm] r_{n-2} [/mm] aufginge.
Vielen vielen Dank andreas und leduart!!!!!!!!!!!!!!!!!!!
Bitte als beantwortet kennzeichnen.
|
|
|
|
![[]](/images/popup.gif){kind=small}
hier