Charakterisierung des ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:43 Do 18.09.2014 | | Autor: | Marcel |
| Aufgabe | In dem Buch "Einführung in die Kryptographie" von J. Buchmann wird, sofern
ich das richtig verstanden habe, der ggT von Zahlen [mm] $a_1, \ldots, a_k$ [/mm] aus [mm] $\IZ \setminus \{0\}$
[/mm]
wie folgt definiert:
[mm] $\gcd(a_1,\ldots,a_k)=\max\{n \in \IN:\;\; n | a_j \text{ für }j=1, \ldots, n\}\,.$
[/mm]
(gcd=greatest common divisor).
Nun ist in einer Aufgabe zu zeigen:
Es ist [mm] $\gcd(a_1,\ldots,a_k)$ [/mm] der eindeutig bestimmte nicht negative gemeinsame
Teiler von [mm] $a_1, \ldots, a_k,$ [/mm] der von allen gemeinsamen Teilern von [mm] $a_1, \ldots, a_k$ [/mm] geteilt wird. |
Hallo,
bzgl. der obigen Aufgabe habe ich folgendes gemacht:
[mm] $T:=\{t \in \IN:\;\; t | a_j \text{ für }j=1,\ldots,k\}\,.$
[/mm]
Klar ist dann
[mm] $d:=\gcd(a_1,\ldots,a_k)=\max T\,.$
[/mm]
Wir setzen
[mm] $T\,':=T \setminus \{d\}\,.$
[/mm]
Zu zeigen ist noch: Für alle $t [mm] \in T\,'$ [/mm] folgt
[mm] $t|d\,.$
[/mm]
Mir stellt sich jetzt die Frage: Kann man dies auch rein per Definitionem
zeigen? Ich komme da irgendwie auf keinen grünen Zweig.
Eine Idee, was man hier machen könnte, wäre für mich die folgende:
Jedes $t [mm] \in [/mm] T$ kann man eindeutig mit seiner Primfaktorzerlegung darstellen.
Jeder dieser Primfaktoren bzw. jeder Primfaktor inklusive seiner Vielfachheit
(ich bin jetzt gerade zu faul, nachzuschlagen; passt dieser Begriff? Gemeint
ist der zu dem Primfaktor *gehörende* Exponent [mm] $\ge [/mm] 1$) muss dann aber
auch zu [mm] $T\,'$ [/mm] gehören. Und mit einer Primfaktorzerlegung von [mm] $d\,$ [/mm] kommt man
dann wohl zu der gewünschten Aussage.
Aber, wie gesagt: Neben der Tatsache, dass obiges nur eine Beweisskizze
ist, die noch zu vervollständigen wäre:
Kann man hier auch "elementarer" argumentieren? Am Liebsten wäre es
mir, wenn man auf Primfaktorzerlegungen gänzlich verzichten würde. Sofern
das denn möglich ist...
Gruß,
Marcel
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:53 Do 18.09.2014 | | Autor: | reverend |
Hallo Marcel,
da ist was faul.
Sei [mm] a_1=30, a_2=42, a_3=70. [/mm] Dann ist [mm] \gcd{(a_1,a_2,a_3)}=2.
[/mm]
Was heißt jetzt
> [...] der eindeutig bestimmte nicht
> negative gemeinsame
> Teiler von [mm]a_1, \ldots, a_k,[/mm] der von allen Teilern von
> [mm]a_1, \ldots, a_k[/mm] geteilt wird.
??? ![[haee]](/images/smileys/haee.gif "[haee]")
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:58 Do 18.09.2014 | | Autor: | Marcel |
Hallo reverend,
> Hallo Marcel,
>
> da ist was faul.
>
> Sei [mm]a_1=30, a_2=42, a_3=70.[/mm] Dann ist
> [mm]\gcd{(a_1,a_2,a_3)}=2.[/mm]
>
> Was heißt jetzt
> > [...] der eindeutig bestimmte nicht
> > negative gemeinsame
> > Teiler von [mm]a_1, \ldots, a_k,[/mm] der von allen Teilern von
> > [mm]a_1, \ldots, a_k[/mm] geteilt wird.
>
> ???
naja, es ist dann doch
[mm] $T=\{1,2\}\,.$
[/mm]
Und es gilt
[mm] $1|2\,$ [/mm] (und [mm] $2|2\,$).
[/mm]
Aber ich sehe das Problem, es muss lauten:
"... der von allen GEMEINSAMEN Teilern von [mm] $a_1,...,a_k$ [/mm] geteilt wird."
Ich korrigiere das mal (im Buch steht's richtig).
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:12 Sa 20.09.2014 | | Autor: | felixf |
Moin Marcel!
> In dem Buch "Einführung in die Kryptographie" von J.
> Buchmann wird, sofern
> ich das richtig verstanden habe, der ggT von Zahlen [mm]a_1, \ldots, a_k[/mm]
> aus [mm]\IZ \setminus \{0\}[/mm]
> wie folgt definiert:
>
> [mm]\gcd(a_1,\ldots,a_k)=\max\{n \in \IN:\;\; n | a_j \text{ für }j=1, \ldots, n\}\,.[/mm]
>
> (gcd=greatest common divisor).
>
> Nun ist in einer Aufgabe zu zeigen:
> Es ist [mm]\gcd(a_1,\ldots,a_k)[/mm] der eindeutig bestimmte nicht
> negative gemeinsame
> Teiler von [mm]a_1, \ldots, a_k,[/mm] der von allen gemeinsamen
> Teilern von [mm]a_1, \ldots, a_k[/mm] geteilt wird.
>
> Hallo,
>
> bzgl. der obigen Aufgabe habe ich folgendes gemacht:
>
> [mm]T:=\{t \in \IN:\;\; t | a_j \text{ für }j=1,\ldots,k\}\,.[/mm]
>
> Klar ist dann
>
> [mm]d:=\gcd(a_1,\ldots,a_k)=\max T\,.[/mm]
>
> Wir setzen
>
> [mm]T\,':=T \setminus \{d\}\,.[/mm]
>
> Zu zeigen ist noch: Für alle [mm]t \in T\,'[/mm] folgt
>
> [mm]t|d\,.[/mm]
>
> Mir stellt sich jetzt die Frage: Kann man dies auch rein
> per Definitionem
> zeigen? Ich komme da irgendwie auf keinen grünen Zweig.
>
> Eine Idee, was man hier machen könnte, wäre für mich die
> folgende:
> Jedes [mm]t \in T[/mm] kann man eindeutig mit seiner
> Primfaktorzerlegung darstellen.
> Jeder dieser Primfaktoren bzw. jeder Primfaktor inklusive
> seiner Vielfachheit
> (ich bin jetzt gerade zu faul, nachzuschlagen; passt
> dieser Begriff? Gemeint
> ist der zu dem Primfaktor *gehörende* Exponent [mm]\ge 1[/mm])
> muss dann aber
> auch zu [mm]T\,'[/mm] gehören. Und mit einer Primfaktorzerlegung
> von [mm]d\,[/mm] kommt man
> dann wohl zu der gewünschten Aussage.
>
> Aber, wie gesagt: Neben der Tatsache, dass obiges nur eine
> Beweisskizze
> ist, die noch zu vervollständigen wäre:
> Kann man hier auch "elementarer" argumentieren? Am
> Liebsten wäre es
> mir, wenn man auf Primfaktorzerlegungen gänzlich
> verzichten würde. Sofern
> das denn möglich ist...
Ist [mm] $d_1 \in [/mm] T$, so schreibe $d = q [mm] d_1 [/mm] + r$ mit $0 [mm] \le [/mm] r < [mm] d_1$. [/mm] Sei [mm] $a_i [/mm] = d [mm] b_i$ [/mm] und [mm] $a_i [/mm] = [mm] d_1 c_i$ [/mm] fuer alle $i$; dann hast du [mm] $a_i [/mm] = d [mm] b_i [/mm] = q [mm] d_1 b_i [/mm] + r [mm] b_i$ [/mm] und [mm] $a_i [/mm] = [mm] d_1 c_i$, [/mm] also [mm] $(c_i [/mm] - q [mm] b_i) d_1 [/mm] = r [mm] b_i$. [/mm] Wegen $0 [mm] \le [/mm] r < [mm] d_1$ [/mm] ist also $0 [mm] \le c_i [/mm] - q [mm] b_i$ [/mm] und [mm] $c_i [/mm] - q [mm] b_i [/mm] < [mm] b_i$, [/mm] also [mm] $c_i [/mm] = q [mm] b_i [/mm] + r'_i$ mit $0 [mm] \le [/mm] r'_i < [mm] b_i$. [/mm] Damit ist [mm] $a_i [/mm] = [mm] d_1 c_i [/mm] = [mm] d_1 [/mm] (q [mm] b_i [/mm] + r'_i) = [mm] d_1 b_i [/mm] q + r'_i [mm] d_1 [/mm] = (d - r) [mm] b_i [/mm] + r'_i = [mm] a_i [/mm] - r [mm] b_i [/mm] + r'_i$, also $r'_i = r [mm] b_i$. [/mm] Wegen $0 [mm] \le [/mm] r'_i < [mm] b_i$ [/mm] muss dann aber $r'_i = 0$ sein, woraus auch $r = 0$ folgt.
Ich hoffe mal, dass ich mich jetzt nicht verrechnet hab  Ansonsten: hab noch ein paarmal verwendet, dass etwas nicht 0 ist, das musst du natuerlich genauer ausfuehren.
Und wenn das nicht geht, das ganze laesst sich auch noch mit den folgenden zwei Aussagen beweisen:
(i) sind $a$ und $b$ Teiler von $c$, dann ist auch $kgV(a, b)$ ein Teiler von $c$;
(ii) ist $kgV(a, b) = b$, so muss $a$ ein Teiler von $b$ sein.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:03 So 21.09.2014 | | Autor: | Marcel |
Hallo Felix,
> Moin Marcel!
>
> > In dem Buch "Einführung in die Kryptographie" von J.
> > Buchmann wird, sofern
> > ich das richtig verstanden habe, der ggT von Zahlen
> [mm]a_1, \ldots, a_k[/mm]
> > aus [mm]\IZ \setminus \{0\}[/mm]
> > wie folgt definiert:
> >
> > [mm]\gcd(a_1,\ldots,a_k)=\max\{n \in \IN:\;\; n | a_j \text{ für }j=1, \ldots, n\}\,.[/mm]
>
> >
> > (gcd=greatest common divisor).
> >
> > Nun ist in einer Aufgabe zu zeigen:
> > Es ist [mm]\gcd(a_1,\ldots,a_k)[/mm] der eindeutig bestimmte nicht
> > negative gemeinsame
> > Teiler von [mm]a_1, \ldots, a_k,[/mm] der von allen gemeinsamen
> > Teilern von [mm]a_1, \ldots, a_k[/mm] geteilt wird.
> >
> > Hallo,
> >
> > bzgl. der obigen Aufgabe habe ich folgendes gemacht:
> >
> > [mm]T:=\{t \in \IN:\;\; t | a_j \text{ für }j=1,\ldots,k\}\,.[/mm]
>
> >
> > Klar ist dann
> >
> > [mm]d:=\gcd(a_1,\ldots,a_k)=\max T\,.[/mm]
> >
> > Wir setzen
> >
> > [mm]T\,':=T \setminus \{d\}\,.[/mm]
> >
> > Zu zeigen ist noch: Für alle [mm]t \in T\,'[/mm] folgt
> >
> > [mm]t|d\,.[/mm]
> >
> > Mir stellt sich jetzt die Frage: Kann man dies auch rein
> > per Definitionem
> > zeigen? Ich komme da irgendwie auf keinen grünen Zweig.
> >
> > Eine Idee, was man hier machen könnte, wäre für mich die
> > folgende:
> > Jedes [mm]t \in T[/mm] kann man eindeutig mit seiner
> > Primfaktorzerlegung darstellen.
> > Jeder dieser Primfaktoren bzw. jeder Primfaktor
> inklusive
> > seiner Vielfachheit
> > (ich bin jetzt gerade zu faul, nachzuschlagen; passt
> > dieser Begriff? Gemeint
> > ist der zu dem Primfaktor *gehörende* Exponent [mm]\ge 1[/mm])
> > muss dann aber
> > auch zu [mm]T\,'[/mm] gehören. Und mit einer Primfaktorzerlegung
> > von [mm]d\,[/mm] kommt man
> > dann wohl zu der gewünschten Aussage.
> >
> > Aber, wie gesagt: Neben der Tatsache, dass obiges nur eine
> > Beweisskizze
> > ist, die noch zu vervollständigen wäre:
> > Kann man hier auch "elementarer" argumentieren? Am
> > Liebsten wäre es
> > mir, wenn man auf Primfaktorzerlegungen gänzlich
> > verzichten würde. Sofern
> > das denn möglich ist...
>
> Ist [mm]d_1 \in T[/mm], so schreibe [mm]d = q d_1 + r[/mm] mit [mm]0 \le r < d_1[/mm].
> Sei [mm]a_i = d b_i[/mm] und [mm]a_i = d_1 c_i[/mm] fuer alle [mm]i[/mm]; dann hast du
> [mm]a_i = d b_i = q d_1 b_i + r b_i[/mm] und [mm]a_i = d_1 c_i[/mm], also
> [mm](c_i - q b_i) d_1 = r b_i[/mm]. Wegen [mm]0 \le r < d_1[/mm] ist also [mm]0 \le c_i - q b_i[/mm]
> und [mm]c_i - q b_i < b_i[/mm], also [mm]c_i = q b_i + r'_i[/mm] mit [mm]0 \le r'_i < b_i[/mm].
> Damit ist [mm]a_i = d_1 c_i = d_1 (q b_i + r'_i) = d_1 b_i q + r'_i d_1 = (d - r) b_i + r'_i [/mm]
fehlt da nicht ein multiplikatives [mm] $d_1$?
[/mm]
[mm] $...=(d-r)b_i+r_i\,' \red{d_1}$?
[/mm]
Ich rechne mal damit weiter und schau', ob das die restl. Argumentation
beeinflusst!
> [mm]= a_i - r b_i + r'_i[/mm],
> also [mm]r'_i = r b_i[/mm]. Wegen [mm]0 \le r'_i < b_i[/mm] muss dann aber
> [mm]r'_i = 0[/mm] sein, woraus auch [mm]r = 0[/mm] folgt.
>
> Ich hoffe mal, dass ich mich jetzt nicht verrechnet hab
> Ansonsten: hab noch ein paarmal verwendet, dass etwas nicht
> 0 ist, das musst du natuerlich genauer ausfuehren.
Ich sehe jetzt nur, dass Du einmal quasi die Annahme $r [mm] \not=0$ [/mm] treffen musstest,
und somit ist das Ganze eigentlich ein Widerspruchsbeweis. Am Ende brauchst
Du auch eigentlich nur, dass ein [mm] $b_i [/mm] > 0$ ist, oder? Das ist klar. Mir ist noch
nicht so klar, wie die Folgerung am Ende geht, wenn da
[mm] $r_i\,'d_1$
[/mm]
am Ende steht. Es ist ein wenig schwer, den Überblick über all die Bezeichnungen
zu behalten.
Edit: Dann hätte man doch analog zu oben aus
[mm] $r_i\,'d_1=0$
[/mm]
ebenfalls, dass alle [mm] $r_i\,'=0$ [/mm] sein müssen (dass das für eins gilt, würde wohl
auch reichen - [mm] $d_1 \not=0$ [/mm] ist ja klar).
Und der Rest geht analog zu oben. Sehe ich das richtig?
Mhm, ne, da war noch ein Denkfehler von mir drinne. Es ist ja gar nicht klar,
dass [mm] $\lfloor\frac{r_i\,'d_1}{b_i}\rfloor=0$ [/mm] ist; oder doch?
> Und wenn das nicht geht, das ganze laesst sich auch noch
> mit den folgenden zwei Aussagen beweisen:
> (i) sind [mm]a[/mm] und [mm]b[/mm] Teiler von [mm]c[/mm], dann ist auch [mm]kgV(a, b)[/mm]
> ein Teiler von [mm]c[/mm];
> (ii) ist [mm]kgV(a, b) = b[/mm], so muss [mm]a[/mm] ein Teiler von [mm]b[/mm] sein.
>
> LG Felix
Danke erstmal. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:29 Di 14.10.2014 | | Autor: | felixf |
Moin Marcel,
> > > [mm]T:=\{t \in \IN:\;\; t | a_j \text{ für }j=1,\ldots,k\}\,.[/mm]
> > >
> > > Klar ist dann
> > >
> > > [mm]d:=\gcd(a_1,\ldots,a_k)=\max T\,.[/mm]
> > >
> > > Wir setzen
> > >
> > > [mm]T\,':=T \setminus \{d\}\,.[/mm]
> >
> > Ist [mm]d_1 \in T[/mm], so schreibe [mm]d = q d_1 + r[/mm] mit [mm]0 \le r < d_1[/mm].
> > Sei [mm]a_i = d b_i[/mm] und [mm]a_i = d_1 c_i[/mm] fuer alle [mm]i[/mm]; dann hast du
> > [mm]a_i = d b_i = q d_1 b_i + r b_i[/mm] und [mm]a_i = d_1 c_i[/mm], also
> > [mm](c_i - q b_i) d_1 = r b_i[/mm]. Wegen [mm]0 \le r < d_1[/mm] ist also [mm]0 \le c_i - q b_i[/mm]
> > und [mm]c_i - q b_i < b_i[/mm], also [mm]c_i = q b_i + r'_i[/mm] mit [mm]0 \le r'_i < b_i[/mm].
> > Damit ist [mm]a_i = d_1 c_i = d_1 (q b_i + r'_i) = d_1 b_i q + r'_i d_1 = (d - r) b_i + r'_i[/mm]
>
> fehlt da nicht ein multiplikatives [mm]d_1[/mm]?
>
> [mm]...=(d-r)b_i+r_i\,' \red{d_1}[/mm]?
Äh, ja. Sorry, hab's wohl verschlampt
> Ich rechne mal damit weiter und schau', ob das die restl.
> Argumentation
> beeinflusst!
>
> > [mm]= a_i - r b_i + r'_i[/mm],
> > also [mm]r'_i = r b_i[/mm].
Das ist jetzt $r'_i [mm] d_1 [/mm] = r [mm] b_i$.
[/mm]
> > Wegen [mm]0 \le r'_i < b_i[/mm] muss dann aber
> > [mm]r'_i = 0[/mm] sein, woraus auch [mm]r = 0[/mm] folgt.
> >
> > Ich hoffe mal, dass ich mich jetzt nicht verrechnet hab
> > Ansonsten: hab noch ein paarmal verwendet, dass etwas nicht
> > 0 ist, das musst du natuerlich genauer ausfuehren.
>
> Ich sehe jetzt nur, dass Du einmal quasi die Annahme [mm]r \not=0[/mm]
> treffen musstest,
> und somit ist das Ganze eigentlich ein Widerspruchsbeweis.
> Am Ende brauchst
> Du auch eigentlich nur, dass ein [mm]b_i > 0[/mm] ist, oder? Das
> ist klar.
Genau.
> Mir ist noch nicht so klar, wie die Folgerung am Ende geht, wenn da
>
> [mm]r_i\,'d_1[/mm]
>
> am Ende steht. Es ist ein wenig schwer, den Überblick
> über all die Bezeichnungen
> zu behalten.
Tja, das ist mir auch nicht so klar. Möglicherweise geht es gar nicht...
> Edit: Dann hätte man doch analog zu oben aus
>
> [mm]r_i\,'d_1=0[/mm]
>
> ebenfalls, dass alle [mm]r_i\,'=0[/mm] sein müssen (dass das für
> eins gilt, würde wohl
> auch reichen - [mm]d_1 \not=0[/mm] ist ja klar).
> Und der Rest geht analog zu oben. Sehe ich das richtig?
>
> Mhm, ne, da war noch ein Denkfehler von mir drinne. Es ist
> ja gar nicht klar,
> dass [mm]\lfloor\frac{r_i\,'d_1}{b_i}\rfloor=0[/mm] ist; oder
> doch?
Wegen $r'_i [mm] d_1 [/mm] = r [mm] b_i$ [/mm] ist [mm] $\frac{r_i' d_1}{b_i} [/mm] = r$. Es gibt also erstmal keinen Grund, warum das $< 1$ (und damit gleich 0) sein sollte. Leider :)
Ich vermute, du musst hiermit vorlieb nehmen:
> > Und wenn das nicht geht, das ganze laesst sich auch noch
> > mit den folgenden zwei Aussagen beweisen:
> > (i) sind [mm]a[/mm] und [mm]b[/mm] Teiler von [mm]c[/mm], dann ist auch [mm]kgV(a, b)[/mm]
> > ein Teiler von [mm]c[/mm];
> > (ii) ist [mm]kgV(a, b) = b[/mm], so muss [mm]a[/mm] ein Teiler von [mm]b[/mm]
> sein.
LG Felix
|
|
|
|
