www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Gruppe, Ring, Körper" - ggT in \IZ
ggT in \IZ < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

ggT in \IZ: Idee und Korrektur
Status: (Frage) beantwortet Status 
Datum: 22:39 Mi 05.05.2010
Autor: vwxyz

Aufgabe
Für a;b [mm] \in \IN_{0} [/mm] sei [mm] ggT_{+}(a;b) \in \IN_{0} [/mm] der nichtnegative größte gemeinsame Teiler.
a) Für a := 223092870 und b := 143197215 bestimme man [mm] ggT_{+}(a;b) [/mm] und die zugehörigen Bézout-Koeffizienten.
b) Für k,m,n [mm] \in \IN_{0} [/mm] zeige man: Es gilt [mm] ggT_{+}(k^{m}-1;k^{n}-1) [/mm] = [mm] k^{ggT_{+}(m;n)}-1. [/mm]
c) Es sei [mm] [F_{n} \in \IN_{0},n \in \IN_{0}] [/mm] die durch [mm] F_{0} [/mm] := 0, [mm] F_{1} [/mm] := 1 und [mm] F_{n} [/mm] := [mm] F_{n}-1 +F_{n-2}, [/mm] für n [mm] \ge [/mm] 2, rekursiv definierte Folge der Fibonacci-Zahlen. Man zeige: Für m,n [mm] \in \IN_{0} [/mm] sind [mm] F_{n} [/mm] und [mm] F_{n-1} [/mm] teilerfremd, und es gilt [mm] ggT_{+}(F_{m},F_{n}) [/mm] =  [mm] F_{ggT_{+}(m,n)} [/mm]

Hi Leute
also a ist ja ganz simple da hab ich auch kein Problem mit.
bei der c) habe ich folgenden Ansatz:
Es gilt ja der Euklidische Algorithmuss für ggT(m,n) also:

[mm] m=q_{0}n+r_{1} [/mm] wobei [mm] r_{1} [mm] n=q_{1}r_{1}+r_{2} [/mm] wobei [mm] r_{2} [mm] r_{1}=q_{2}r_{2}+r_{3} [/mm] wobei [mm] r_{3} ...
[mm] r_{k-1}=q_{k}r_{k} [/mm]

Dann ist [mm] r_{k} [/mm] der ggT von m und n und es gilt
[mm] ggT(m,n)=ggt(n,r_{1})=ggT(r_{1},r_{2})=... [/mm]

Wende ich das nun auf [mm] F_{n} [/mm] und [mm] F_{n-1} [/mm] an so ist doch [mm] q_{i} [/mm] stets 1 und die [mm] r_{i} [/mm] durchlaufen die Fibonacci-Zahlen von oben nach unten denn [mm] F_{n} [/mm] und [mm] F_{n-1}sind [/mm] ja teilerfremd und [mm] F_{n} [/mm] und [mm] F_{kn-1} [/mm] sowieso

so und dann muss doch gelten [mm] ggT(F_{m},F_{n}) [/mm] = [mm] ggT(F_{q_{0}n+r_{1}},F_{n}) [/mm] = [mm] ggT(F_{q_{0}n-1}F_{r_{1}}+F_{q_{0}n}F_{r_{1}+1},F_{n}) [/mm] = [mm] ggT(F_{n},F_{q_{0}n-1}F_{r_{1}}) [/mm] = [mm] ggT(F_{n},F_{r_{1}}) [/mm]


Also weiter:
[mm] ggT(F_{m},F_{n})=ggT(F_{n},F_{r_{1}})=ggT(F_{r_{1}},F_{r_{2}})=... [/mm]

und das ist doch dann: [mm] ggT(F_{m}F_{n})=F_{r_k}=F_{ggT(m,n)} [/mm] oder?

Bei der b) hab ich ehrlich gesagt noch kaum einen Ansatz:

Hatte mir überlegt es gilt ja

ggt(m,n) = [mm] \pm \produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\beta_{i}\}} [/mm]

mit n = [mm] \produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\}} [/mm]

und m= [mm] \produkt_{i=1}^{k} p_{i}^{min\{\beta_{i}\}} [/mm]

dann gilt doch für [mm] k^{m} [/mm] und [mm] k^{n} [/mm] jeweils
[mm] k^{n}= (\produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\}})^{n} [/mm] bzw.
analog für m

und für [mm] ggt(k^{m},k^{n}) [/mm] = [mm] (\pm \produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\beta_{i}\}})^{nm} [/mm] Aber weiß nicht ob es bis dahin richtig ist und wie ich nun weiter komme

Vielen Dank im Vorraus.


        
Bezug
ggT in \IZ: Antwort
Status: (Antwort) fertig Status 
Datum: 22:59 Mi 05.05.2010
Autor: abakus


> Für a;b [mm]\in \IN_{0}[/mm] sei [mm]ggT_{+}(a;b) \in \IN_{0}[/mm] der
> nichtnegative größte gemeinsame Teiler.
>  a) Für a := 223092870 und b := 143197215 bestimme man
> [mm]ggT_{+}(a;b)[/mm] und die zugehörigen Bézout-Koeffizienten.
>  b) Für k,m,n [mm]\in \IN_{0}[/mm] zeige man: Es gilt
> [mm]ggT_{+}(k^{m}-1;k^{n}-1)[/mm] = [mm]k^{ggT_{+}(m;n)}-1.[/mm]
>  c) Es sei [mm][F_{n} \in \IN_{0},n \in \IN_{0}][/mm] die durch
> [mm]F_{0}[/mm] := 0, [mm]F_{1}[/mm] := 1 und [mm]F_{n}[/mm] := [mm]F_{n}-1 +F_{n-2},[/mm] für
> n [mm]\ge[/mm] 2, rekursiv definierte Folge der Fibonacci-Zahlen.
> Man zeige: Für m,n [mm]\in \IN_{0}[/mm] sind [mm]F_{n}[/mm] und [mm]F_{n-1}[/mm]
> teilerfremd, und es gilt [mm]ggT_{+}(F_{m},F_{n})[/mm] =  
> [mm]F_{ggT_{+}(m,n)}[/mm]
>  Hi Leute
>  also a ist ja ganz simple da hab ich auch kein Problem
> mit.
>  bei der c) habe ich folgenden Ansatz:
>  Es gilt ja der Euklidische Algorithmuss für ggT(m,n)
> also:
>  
> [mm]m=q_{0}n+r_{1}[/mm] wobei [mm]r_{1}
>  [mm]n=q_{1}r_{1}+r_{2}[/mm] wobei [mm]r_{2}
>  [mm]r_{1}=q_{2}r_{2}+r_{3}[/mm] wobei [mm]r_{3}
>  ...
>  [mm]r_{k-1}=q_{k}r_{k}[/mm]
>  
> Dann ist [mm]r_{k}[/mm] der ggT von m und n und es gilt
>  [mm]ggT(m,n)=ggt(n,r_{1})=ggT(r_{1},r_{2})=...[/mm]
>  
> Wende ich das nun auf [mm]F_{n}[/mm] und [mm]F_{n-1}[/mm] an so ist doch
> [mm]q_{i}[/mm] stets 1 und die [mm]r_{i}[/mm] durchlaufen die
> Fibonacci-Zahlen von oben nach unten denn [mm]F_{n}[/mm] und
> [mm]F_{n-1}sind[/mm] ja teilerfremd und [mm]F_{n}[/mm] und [mm]F_{kn-1}[/mm] sowieso
>  
> so und dann muss doch gelten [mm]ggT(F_{m},F_{n})[/mm] =
> [mm]ggT(F_{q_{0}n+r_{1}},F_{n})[/mm] =
> [mm]ggT(F_{q_{0}n-1}F_{r_{1}}+F_{q_{0}n}F_{r_{1}+1},F_{n})[/mm] =
> [mm]ggT(F_{n},F_{q_{0}n-1}F_{r_{1}})[/mm] = [mm]ggT(F_{n},F_{r_{1}})[/mm]
>
>
> Also weiter:
>  
> [mm]ggT(F_{m},F_{n})=ggT(F_{n},F_{r_{1}})=ggT(F_{r_{1}},F_{r_{2}})=...[/mm]
>  
> und das ist doch dann: [mm]ggT(F_{m}F_{n})=F_{r_k}=F_{ggT(m,n)}[/mm]
> oder?
>  
> Bei der b) hab ich ehrlich gesagt noch kaum einen Ansatz:
>  
> Hatte mir überlegt es gilt ja
>  
> ggt(m,n) = [mm]\pm \produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\beta_{i}\}}[/mm]
>  
> mit n = [mm]\produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\}}[/mm]
>  
> und m= [mm]\produkt_{i=1}^{k} p_{i}^{min\{\beta_{i}\}}[/mm]
>  
> dann gilt doch für [mm]k^{m}[/mm] und [mm]k^{n}[/mm] jeweils
> [mm]k^{n}= (\produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\}})^{n}[/mm]
> bzw.
> analog für m

Hallo,
in Aufgabe b wurde ich d=ggT(m,n) ansetzen, dann gilt m=a*d und n=b*d mit teilerfremden a und b.
Aus [mm] k^m-1 [/mm] wird dann [mm] (k^d)^a-1 [/mm] und aus [mm] k^n-1 [/mm] wird [mm] (k^d)^b-1, [/mm] woraus sich jeweils (Summenformel geometrische Reihe!) [mm] (k^d-1) [/mm] ausklammern lässt.
Gruß Abakus

>  
> und für [mm]ggt(k^{m},k^{n})[/mm] = [mm](\pm \produkt_{i=1}^{k} p_{i}^{min\{\alpha_{i}\beta_{i}\}})^{nm}[/mm]
> Aber weiß nicht ob es bis dahin richtig ist und wie ich
> nun weiter komme
>  
> Vielen Dank im Vorraus.
>  


Bezug
                
Bezug
ggT in \IZ: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:50 Do 06.05.2010
Autor: vwxyz

Ok also habe das soweit umgeformt und weiß auch wie ich dann zu der Behauptung wieder komme habe aber noch ein Problem mit der geometrischen Reihe.

Wenn ich stehen haben

[mm] k^{m}-1= (k^{d})^{a}-1 [/mm] und [mm] k^{n}-1= (k^{d})^{b} [/mm] und nach der Summenformel gilt ja:

[mm] \summe_{i=1}^{a} [/mm] = [mm] \bruch{k^{d}*(k^{d})^{a}}{k^{d}-1} [/mm] - [mm] \bruch{a*(k^{d}-1)+k^{d}}{k^{d}-1} [/mm]
und ich weiß das es sich um Natürlichenzahlen handelt da k eie ist und die Summer von natürlichen Zahlen auch eine sein muss also muss auch :
[mm] \bruch{k^{d}*(k^{d})^{a}}{k^{d}-1} [/mm] - [mm] \bruch{a*(k^{d}-1)+k^{d}}{k^{d}-1} \in \IN [/mm] sein. Nur wie zeige ich das:

[mm] \bruch{k^{d}*(k^{d})^{a}}{k^{d}-1} [/mm] - [mm] \bruch{a*(k^{d}-1)+k^{d}}{k^{d}-1} [/mm] oder [mm] k^{d}*(k^{d}^{a})-a*(k^{d}-1)+k^{d} [/mm] = [mm] (k^{d})^{a}-1 [/mm] ist

Bezug
                        
Bezug
ggT in \IZ: Antwort
Status: (Antwort) fertig Status 
Datum: 23:01 Do 06.05.2010
Autor: abakus


> Ok also habe das soweit umgeformt und weiß auch wie ich
> dann zu der Behauptung wieder komme habe aber noch ein
> Problem mit der geometrischen Reihe.
>  
> Wenn ich stehen haben
>  
> [mm]k^{m}-1= (k^{d})^{a}-1[/mm] und [mm]k^{n}-1= (k^{d})^{b}[/mm] und nach
> der Summenformel gilt ja:
>  
> [mm]\summe_{i=1}^{a}[/mm] = [mm]\bruch{k^{d}*(k^{d})^{a}}{k^{d}-1}[/mm] -
> [mm]\bruch{a*(k^{d}-1)+k^{d}}{k^{d}-1}[/mm]

Hallo,
ich wollte darauf hinaus, dass [mm] \bruch{q^n-1}{q-1}=q^{n-1}+q^{n-2}+...+q^2+q+1 [/mm] gilt, woraus [mm] q^n-1=(q-1)(q^{n-1}+q^{n-2}+...+q^2+q^1+1) [/mm] folgt.

>  und ich weiß das es sich um Natürlichenzahlen handelt da
> k eie ist und die Summer von natürlichen Zahlen auch eine
> sein muss also muss auch :
>   [mm]\bruch{k^{d}*(k^{d})^{a}}{k^{d}-1}[/mm] -
> [mm]\bruch{a*(k^{d}-1)+k^{d}}{k^{d}-1} \in \IN[/mm] sein. Nur wie
> zeige ich das:
>
> [mm]\bruch{k^{d}*(k^{d})^{a}}{k^{d}-1}[/mm] -
> [mm]\bruch{a*(k^{d}-1)+k^{d}}{k^{d}-1}[/mm] oder
> [mm]k^{d}*(k^{d}^{a})-a*(k^{d}-1)+k^{d}[/mm] = [mm](k^{d})^{a}-1[/mm] ist


Bezug
                                
Bezug
ggT in \IZ: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:19 Do 06.05.2010
Autor: vwxyz

ok das heißt also wenn ich q:= [mm] k^{d} [/mm] folgt daraus dass [mm] k^{d}-1 [/mm] ist ein Teiler von beiden Werten. Wie kann ich das aber nachweisen,dass das der größte Teiler ist. Oder reicht es zu argumentieren da d /in ggt(m,n) ist und somit der Terme [mm] (q-1)(q^{n-1}+q^{n-2}+...+q^2+q^1+1) [/mm] ein Vielfaches von d ist somit auch Element der Menge der ggt(m,n) ist?

Bezug
                                        
Bezug
ggT in \IZ: Antwort
Status: (Antwort) fertig Status 
Datum: 06:53 Fr 07.05.2010
Autor: felixf

Moin

> ok das heißt also wenn ich q:= [mm]k^{d}[/mm] folgt daraus dass
> [mm]k^{d}-1[/mm] ist ein Teiler von beiden Werten. Wie kann ich das
> aber nachweisen,dass das der größte Teiler ist. Oder
> reicht es zu argumentieren da d /in ggt(m,n) ist und somit
> der Terme [mm](q-1)(q^{n-1}+q^{n-2}+...+q^2+q^1+1)[/mm] ein
> Vielfaches von d ist somit auch Element der Menge der
> ggt(m,n) ist?

Nein, das reicht nicht aus.

Es gibt zwei Moeglichkeiten:
a) du zeigst, dass $1 + q + [mm] q^2 [/mm] + [mm] \dots [/mm] + [mm] q^{a-1}$ [/mm] und $1 + q + [mm] \dots [/mm] + [mm] q^{b-1}$ [/mm] teilerfremd sind;
b) du verfolgst den Euklidischen Algorithmus nach (mit der Methode aus meiner Antwort auf deine urspruengliche Frage) und bekommst $q - 1$ als ggT heraus.

Um a) zu loesen kann man ebenfalls wie in b) vorgehen; zeige dass $ggT(1 + q + [mm] \dots [/mm] + [mm] q^{n - 1}, [/mm] 1 + q + [mm] \dots [/mm] + [mm] q^{m - 1}) [/mm] = 1 + q + [mm] \dots [/mm] + [mm] q^{ggT(n, m) - 1}$. [/mm] Dann beachte, dass $a$ und $b$ teilerfremd sind.

LG Felix



Bezug
        
Bezug
ggT in \IZ: Antwort
Status: (Antwort) fertig Status 
Datum: 06:33 Fr 07.05.2010
Autor: felixf

Hallo!

>  b) Für k,m,n [mm]\in \IN_{0}[/mm] zeige man: Es gilt
> [mm]ggT_{+}(k^{m}-1;k^{n}-1)[/mm] = [mm]k^{ggT_{+}(m;n)}-1.[/mm]
>  c) Es sei [mm][F_{n} \in \IN_{0},n \in \IN_{0}][/mm] die durch
> [mm]F_{0}[/mm] := 0, [mm]F_{1}[/mm] := 1 und [mm]F_{n}[/mm] := [mm]F_{n}-1 +F_{n-2},[/mm] für
> n [mm]\ge[/mm] 2, rekursiv definierte Folge der Fibonacci-Zahlen.
> Man zeige: Für m,n [mm]\in \IN_{0}[/mm] sind [mm]F_{n}[/mm] und [mm]F_{n-1}[/mm]
> teilerfremd, und es gilt [mm]ggT_{+}(F_{m},F_{n})[/mm] =  
> [mm]F_{ggT_{+}(m,n)}[/mm]
>
>  bei der c) habe ich folgenden Ansatz:
>  Es gilt ja der Euklidische Algorithmuss für ggT(m,n)
> also:
>  
> [mm]m=q_{0}n+r_{1}[/mm] wobei [mm]r_{1}
>  [mm]n=q_{1}r_{1}+r_{2}[/mm] wobei [mm]r_{2}
>  [mm]r_{1}=q_{2}r_{2}+r_{3}[/mm] wobei [mm]r_{3}
>  ...
>  [mm]r_{k-1}=q_{k}r_{k}[/mm]
>  
> Dann ist [mm]r_{k}[/mm] der ggT von m und n und es gilt
>  [mm]ggT(m,n)=ggt(n,r_{1})=ggT(r_{1},r_{2})=...[/mm]
>  
> Wende ich das nun auf [mm]F_{n}[/mm] und [mm]F_{n-1}[/mm] an so ist doch
> [mm]q_{i}[/mm] stets 1 und die [mm]r_{i}[/mm] durchlaufen die
> Fibonacci-Zahlen von oben nach unten denn [mm]F_{n}[/mm] und
> [mm]F_{n-1}sind[/mm] ja teilerfremd und [mm]F_{n}[/mm] und [mm]F_{kn-1}[/mm] sowieso
>  
> so und dann muss doch gelten [mm]ggT(F_{m},F_{n})[/mm] =
> [mm]ggT(F_{q_{0}n+r_{1}},F_{n})[/mm] =
> [mm]ggT(F_{q_{0}n-1}F_{r_{1}}+F_{q_{0}n}F_{r_{1}+1},F_{n})[/mm] =
> [mm]ggT(F_{n},F_{q_{0}n-1}F_{r_{1}})[/mm] = [mm]ggT(F_{n},F_{r_{1}})[/mm]
>
>
> Also weiter:
>  
> [mm]ggT(F_{m},F_{n})=ggT(F_{n},F_{r_{1}})=ggT(F_{r_{1}},F_{r_{2}})=...[/mm]
>  
> und das ist doch dann: [mm]ggT(F_{m}F_{n})=F_{r_k}=F_{ggT(m,n)}[/mm]
> oder?
>  
> Bei der b) hab ich ehrlich gesagt noch kaum einen Ansatz:

Versuch doch mal bei b) genauso wie bei c) vorzugehen. Schau dir dazu an, wie man [mm] $k^a [/mm] - 1$ modulo [mm] $k^b [/mm] - 1$ ausrechnen kann. Schreibe $a = q b + r$ mit $0 [mm] \le [/mm] r < b$ und $q, r [mm] \in \IN$. [/mm] Dann ist [mm] $k^a [/mm] - 1 = [mm] k^{q b + r} [/mm] - 1 = [mm] (k^b)^q k^r [/mm] - 1$. Jetzt willst du modulo [mm] $k^b [/mm] - 1$ arbeiten, womit [mm] $k^b [/mm] = 1$ gilt: also ist [mm] $k^a [/mm] - 1 = 1 [mm] \cdot k^r [/mm] - 1 = [mm] k^r [/mm] - 1$ modulo [mm] $k^b [/mm] - 1$.

LG Felix


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de