ggt < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:05 Fr 04.02.2011 | | Autor: | katrin10 |
| Aufgabe | Zeigen Sie, dass für alle q, m, n [mm] \in \IN_{>0} [/mm] mit q [mm] \not= [/mm] 1 gilt:
[mm] ggt(q^m-1, q^n-1)=q^{ggt(m,n)}-1 [/mm] |
Hallo,
ich habe angenommen, dass m [mm] \ge [/mm] n gilt und habe dann in einem Vorbeweis gezeigt, dass die Gleichung gilt, falls ggt(m,n)=n.
Sei [mm] x:=q^{ggt(m,n)}-1
[/mm]
Sei y:=ggt(m,n), d. h. es existiert ein c [mm] \in \IN, [/mm] sodass gilt cy=m-n
Angenommen es existierten m,n [mm] \in \IN, [/mm] sodass [mm] ggt(q^m-1, q^n-1)
[mm] \Rightarrow [/mm] Für alle a, b [mm] \in \IN [/mm] gilt: [mm] q^m-1 \not= [/mm] ag oder [mm] q^n-1 \not= [/mm] bg
[mm] \Rightarrow q^m-q^n=q^n*(q^{m-n}-1)=q^n*(q^{cy}-1)\not=(a-b)*(q^y-1)
[/mm]
Da cy ein Vielfaches von y ist, ist [mm] q^{cy}-1 [/mm] ein Vielfaches von [mm] q^{y}-1, [/mm] d.h. [mm] d*(q^{y}-1)=q^{cy}-1 [/mm] und damit gibt es a und b, sodass [mm] q^n*d=a-b [/mm] gilt
Kann ich daraus folgern, dass [mm] ggt(q^m-1, q^n-1)=q^{ggt(m,n)}-1 [/mm] gilt?
Ist meine Vorgehensweise so schlüssig und richtig?
Vielen Dank.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:30 Fr 04.02.2011 | | Autor: | leduart |
Hallo
ich verstehe dein vorgehen nicht. was z. Bsp ist g?
ich denke der einfache Tiel ist zu zeigen dass $ [mm] x:=q^{ggt(m,n)}-1 [/mm] $ wirklich Teiler der beiden ist. das geht am einfasten wenn du [mm] q^m=(q^{x})^m'
[/mm]
[mm] q^n=(q^{x})^n' [/mm] schreibst.
dann ist nur noch zu beweisen dass [mm] q^x-1 [/mm] der größte Teiler ist, d.h. wemm ggT(m'n')=1 folgt mit [mm] q^x=Q [/mm]
Q-1 ist der einzige Teiler von [mm] Q^{m'}-1 [/mm] und [mm] Q^{n'}-1
[/mm]
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:18 Sa 05.02.2011 | | Autor: | katrin10 |
Hallo,
vielen Dank für die schnelle Antwort. Die Vorgehensweise erscheint mir logisch. Wenn x ein Teiler der beiden ist, muss x | [mm] q^m-1 [/mm] und x | [mm] q^n-1 [/mm] gelten. Doch wie kommt man auf den Ansatz $ [mm] q^m=(q^{x})^m' [/mm] $ und
$ [mm] q^n=(q^{x})^n' [/mm] $?
Katrin
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:31 Sa 05.02.2011 | | Autor: | leduart |
Hallo
der ggt der 2 Zahlen ist doch Faktor von beiden, und x war doch der ggt.
also m=ggt(m,n)*m' n=ggt(m,n)*n' wenn dich m', n' stört nenn sie M,N
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:50 Sa 05.02.2011 | | Autor: | katrin10 |
Hallo,
um zu zeigen, dass g ein größter gemeinsamer Teiler von a und b ist, muss man zeigen
a) g | a und g | b
b) ist d ein gemeinsamer Teiler von a und b, so gilt $ d [mm] \mid [/mm] g $.
Gibt es für b) eine Möglichkeit, wie man immer vorgehen kann oder ist das von der Aufgabe abhängig? Ich wäre nämlich nicht darauf gekommen, ggT(m', n')=1 in meiner Aufgabe zu zeigen.
Katrin
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:04 Sa 05.02.2011 | | Autor: | leduart |
Hallo
Du hast doch jetzt [mm] q^x-1 [/mm] ist Teiler, also a) ist erledigt.
jetzt musst du noch zeigen dass es keinen Teiler d gibt, der größer x ist.
du kannst [mm] q^n-1 [/mm] schreiben (geometrische Reihe) als [mm] (q^n-1)/(q-1)=[/mm] [mm]\summe_{i=0}^{n-1} q^i[/mm]
oder [mm] (q^n-1)=(q-1)$\summe_{i=0}^{n-1} q^i$
[/mm]
wende das auf dein m',n' mit ggT=1 an.
und versuch zu zeigen, dass [mm] $\summe_{i=0}^{n'-1} q^i$ [/mm] und [mm] $\summe_{i=0}^{M'-1} q^i$ [/mm] keinen gemeinsamen Teiler>1 haben wenn ggT(n',m')=1
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:01 Sa 05.02.2011 | | Autor: | katrin10 |
Hallo,
dass ggt(m',n')=1 gelten muss, ist mir klar, und dass 1 ein Teiler der beiden Reihen ist, stimmt auch. Jetzt fehlt also noch, dass 1 der größte gemeinsame Teiler ist. Ang. m' [mm] \ge [/mm] n'. Dann gilt für ein d [mm] \in \IN:
[/mm]
d|$ [mm] \summe_{i=0}^{n'-1} q^i [/mm] $ und d|$ [mm] \summe_{i=0}^{m'-1} q^i [/mm] $, d. h. d|$ [mm] \summe_{i=n'}^{m'-1} q^i [/mm] $
Allerdings verstehe ich nicht, wie ich jetzt weitermachen kann.
Vielen Dank für die Hilfe.
Katrin
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:40 Sa 05.02.2011 | | Autor: | leduart |
Hallo
ich zeigs dir an einem Beispiel, Beh [mm] ggT((q^4-1),(q^7-1))=q-1
[/mm]
weil ggT(4,7)=1
[mm] q^4-1=(q-1)*(1+q+q^2+q^3)
[/mm]
[mm] q^7-1=(q-1)*(1+q+.....+q^6)
[/mm]
[mm] Beh.ggt((1+q+q^2+q^3),(1+q+.....+q^6))=1
[/mm]
[mm] q^k [/mm] ist nicht Teiler von einem der beiden!
deshalb kann ich auch ggt [mm] ((1+q+.....+q^6), (1+q+.....+q^6)-q^3*(1+q+q^2+q^3) [/mm] betrachten. das ist [mm] ggT((1+q+.....+q^6),(1+q+q^2))
[/mm]
jetzt [mm] ggt((1+q+q^2+q^3),q*(1+q+q^2)=ggT((1+q+q^2+q^3),1=1
[/mm]
ich benutze immer wieder dass wenn d Teiler von a und b ist, dann auch Teiler von a-b, und a-r*b wenn r nicht Teiler von a
das ist der euklidsche algorithmus, um den ggT zu finden.
wenns kein Bsp ist, musst dus mit... schreiben, zeigen, dass du immer mindesten eine ordnung runterkommst und des halb bei 1 landest.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:29 Sa 05.02.2011 | | Autor: | katrin10 |
Hallo,
vielen Dank für das Beispiel und die ganzen Tipps.
Das Beispiel verstehe ich und ich habe jetzt ziemlich lange versucht, selbst mit Variablen zu rechnen. Ich habe jetzt angenommen, dass m' [mm] \ge [/mm] n'. Dann gilt:
[mm] ggt(\summe_{i=0}^{m'-1}q^{i},\summe_{i=0}^{n'-1}q^{i}) [/mm] = [mm] ggt(\summe_{i=0}^{m'-1}q^{i},\summe_{i=n'}^{m'-1}q^{i}) [/mm] =
[mm] ggt(\summe_{i=0}^{m'-1}q^{i},q^n'*\summe_{i=0}^{m'-n'-1}q^{i})=
[/mm]
[mm] ggt(\summe_{i=0}^{n'-1}q^{i},\summe_{i=0}^{m'-n'-1}q^{i})=
[/mm]
[mm] ggt(\summe_{i=0}^{n'-1}q^{i},q^{2n'-m}\summe_{i=0}^{m'-n'-1}q^{i})
[/mm]
Ab hier drehe ich mich allerdings immer im Kreis, da ich z. B. nicht weiß, ob n'-1 oder 2n'-m' größer ist.
Katrin
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:05 So 06.02.2011 | | Autor: | felixf |
Moin Katrin
> vielen Dank für das Beispiel und die ganzen Tipps.
>
> Das Beispiel verstehe ich und ich habe jetzt ziemlich lange
> versucht, selbst mit Variablen zu rechnen. Ich habe jetzt
> angenommen, dass m' [mm]\ge[/mm] n'. Dann gilt:
> [mm]ggt(\summe_{i=0}^{m'-1}q^{i},\summe_{i=0}^{n'-1}q^{i})[/mm] =
> [mm]ggt(\summe_{i=0}^{m'-1}q^{i},\summe_{i=n'}^{m'-1}q^{i})[/mm] =
>
> [mm]ggt(\summe_{i=0}^{m'-1}q^{i},q^n'*\summe_{i=0}^{m'-n'-1}q^{i})=[/mm]
>
> [mm]ggt(\summe_{i=0}^{n'-1}q^{i},\summe_{i=0}^{m'-n'-1}q^{i})=[/mm]
Das ist doch schonmal schoen. Das kannst du jetzt passend oft wiederholen, um zu zeigen dass dieser ggT gleich
> [mm]ggt(\summe_{i=0}^{n'-1}q^{i},\summe_{i=0}^{(m' \text{ mod} n')-1}q^{i})[/mm]
ist. Dann vertauscht du beide Seiten und wiederholst das Argument (also wieder Modulo in den Exponenten). Faellt dir eine Aehnlichkeit zum Euklidischen Algorithmus auf?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:14 Sa 13.09.2014 | | Autor: | kony |
Hallo Felix,
Könntest du bitte die einzelnen Schritte ausführlicher erklären, Ich habe alles verstanden bis wie ich die Summen m' n' den ggt ausrechne. Meine Analysis Vorlesungen sind ca. 10 Jahre her und jetzt mache ich den Master. Danke im vorraus!
Vg,
Kony
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:36 Sa 13.09.2014 | | Autor: | abakus |
> Hallo Felix,
>
> Könntest du bitte die einzelnen Schritte ausführlicher
> erklären, Ich habe alles verstanden bis wie ich die Summen
> m' n' den ggt ausrechne. Meine Analysis Vorlesungen sind
> ca. 10 Jahre her und jetzt mache ich den Master. Danke im
> vorraus!
>
> Vg,
> Kony
Hallo Kony,
der zitierte Thread ist knapp 4 Jahre alt. Felix ist zwar immer noch sehr aktiv hier, aber ob er nun gerade in diesen Tagen reinschaut und deine Frage findet ist nicht unbedingt sicher.
Ich möchte dir wenigstens anhand von Beispielen einen Impuls zu eigenen Überlegungen geben.
Nach der dritten binomischen Formel gilt z.B.
[mm] $x^8-1=(x^4+1)(x^4-1)$.
[/mm]
Nun lässt sich [mm] $x^4-1$ [/mm] wiederum zerlegen in [mm] $(x^2+1)(x^2-1)$, [/mm] und der letzte dieser beiden Faktoren ist (x+1)(x-1).
Es gilt also [mm] §x^8-1=(x^4+1)(x^2+1)(x+1)(x-1)$.
[/mm]
Betrachten wir nun mal [mm] $x^6-1$. [/mm] Es gilt [mm] $x^6-1=(x^3+1)(x^3-1)$. [/mm] Das lässt sich zerlegen in
[mm] $(x^3+1)(x^3-1)=(x^3+1)(x^2+x+1)(x-1)$.
[/mm]
Jetzt suche mal nach gemeinsamen Teilern von [mm] $x^8-1$ [/mm] und [mm] $x^6-1$.
[/mm]
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:30 So 06.02.2011 | | Autor: | katrin10 |
Vielen Dank für die Hilfe.
|
|
|
|
