Euklidischer Algorithmus < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:03 Di 30.04.2013 | | Autor: | nbt |
| Aufgabe | | Seien [mm]m,n\in\IN_{>0}[/mm]. Zeigen Sie mit Hilfe des euklidischen Algorithmus, dass in [mm]K[X][/mm] gilt: [mm]ggT(X^n-1,X^m-1)=X^{ggT(m,n)}-1[/mm] |
Hi,
ich habs bei der Aufgabe zuerst mit Induktion versucht:
Induktion über m:
I.A.: $m=1$:
Induktion über n:
I.A.: $n=1$: RS: [mm] $X^{ggT(1,1)}-1=X-1$
[/mm]
LS: $ggT(X-1,X-1)=X-1$ Passt.
I.S.: [mm] $n\to [/mm] n+1$: [mm] ggT(X^{n+1}-1,X-1)=X-1 [/mm] ist klar.
I.V.: [mm] $ggT(X^n-1,X^m-1)=X^{ggT(m,n)}-1$
[/mm]
I.S.: [mm] $m\to [/mm] m+1$
Induktion über n:
I.A.: $n=1$: [mm] $ggT(X-1,X^{m+1}-1)=X^{ggT(1,m+1)}-1$
[/mm]
I.V.: [mm] $ggT(X^n-1,X^{m+1}-1)=X^{n,m+1}-1$
[/mm]
I.S.: [mm] $n\to [/mm] n+1$
Z.Z.: [mm] $ggT(X^{n+1}-1,X^{m+1}-1)=X^{ggT(n+1,m+1)}-1$
[/mm]
Aber genau da wiederholt sich ja alles! Ich hab mir auch schonmal die ersten paar Iterationen vom euklidischen Algorithmus hingeschrieben und ein Schema in der Entwicklung des Grades vom Restpolynom und vom Koeffizientenpolynom gesehn, aber ich bin dann trotzdem ned auf einen grünen Zweig gekommen.
Wär super, wenn mir jemand einen Hinweis geben könnte.
Vielen Dank,
nBt
|
|
| |
|
Hallo nbt,
ich würde Dir eine andere Vorgehensweise vorschlagen und gehe daher nicht auf Deinen Induktionsversuch ein. Nebenbei klappt Induktion bei ggT-Aufgaben meistens schlecht, wenn überhaupt. 
Sei [mm] g:=\ggT{(m,n)}.
[/mm]
Dann kannst Du explizit angeben (Polynomdivision!), was [mm] (x^m-1)/(x^g-1) [/mm] bzw. [mm] (x^n-1)/(x^g-1) [/mm] ist.
Zeige dann mittels des euklidischen Algorithmus, dass diese beiden Polynome teilerfremd sind. Das geht in einem Schritt.
Viel Erfolg dabei!
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:35 Mi 01.05.2013 | | Autor: | nbt |
Ah danke reverend, ich versteh dein Idee, denn es gilt:
[mm] $ggT(\frac{X^n-1}{X^g-1},\frac{X^m-1}{X^g-1})=\frac{1}{X^g-1}ggT(X^n-1,X^m-1)$. [/mm] Teilerfremdheit bedeutet, der ggT ist gleich Eins und damit würde die Behauptung folgen.
Aber bei der Ausführung haperts: Zunächst: Sei [mm] $q\in\IN$, [/mm] sodass $m-qg=0$ und [mm] $p\in\IN$, [/mm] sodass $n-pg=0$. Außerdem sei $n>m$.
[mm] $(X^m-1)/(X^g-1)=X^{m-g}+X^{m-2g}+...+1$
[/mm]
[mm] $(X^n-1)/(X^g-1)=X^{n-g}+X^{n-2g}+...+1$
[/mm]
[mm] $(X^{n-g}+X^{n-2g}+...+1)=X^{n-m}(X^{m-g}+X^{m-2g}+...+1)-X^{n-qg}+1$.
[/mm]
Ich glaub nicht, dass man so irgendwann auf nen Nullrest kommt.
Danke für die Geduld ;)
Grüße,
nBt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:44 Mi 01.05.2013 | | Autor: | hippias |
Statt Polynomdivision: Du kennst die Gleichung fuer die geometrische Reihe: [mm] $\sum_{i=0}^{n-1} Y^{i}= \frac{Y^{n}-1}{Y-1}$ ($Y\neq [/mm] 1$). Wende dies an auf $Y:= [mm] X^{g}$. [/mm]
|
|
|
|
