ggT in \IZ < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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.
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
|
