ggT charaktersisieren, < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:55 Fr 17.10.2014 | | Autor: | sissile |
| Aufgabe | Seien
m= [mm] \prod_{j=1}^M p_j^{k_j}
[/mm]
n= [mm] \prod_{i=1}^M p_i^{l_i}
[/mm]
Dabei haben wir die [mm] p_i [/mm] so gewählt, dass alle Primzahlen vorkommen die m oder n teilen, und wir haben gleiche Primzahlen zu Potenzen zusammengefasst; außerdem setzen wir [mm] k_j [/mm] =0 [mm] (l_j [/mm] =0), fall [mm] p_j [/mm] nicht m (n) teilt.
Es gilt dann ggT(m,n)= [mm] \prod_{i=1}^M p_i^{min(k_i, l_i)} [/mm]
Beweisen Sie die Formel für ggT von m und n. |
Hallo zusammen,
Sind m,n [mm] \in \IZ, [/mm] so ist ggT(m,n):= [mm] max\{a\in \IZ: a|m \wedge a|n\}
[/mm]
[mm] \prod_{i=1}^M p_i^{min(k_i, l_i)} [/mm] = d
1)ZZ.: d|m [mm] \wedge [/mm] d|n
Es sind also [mm] c_1 [/mm] und [mm] c_2 \in \IZ [/mm] zu finden, sodass
[mm] d*c_1=m [/mm]
[mm] d*c_2 [/mm] =n
Sei [mm] c_1= \prod_{o=1}^M p_o^{x_o} [/mm] mit p so gewählt wie in der Angabe
[mm] c_2= \prod_{o=1}^M p_o^{y_o}
[/mm]
und [mm] x_i, y_i [/mm] gewählt so dass:
[mm] min(k_i, l_i) [/mm] + [mm] x_i [/mm] = [mm] k_i [/mm]
[mm] min(k_i, l_i) [/mm] + [mm] y_i [/mm] = [mm] l_i
[/mm]
Dann folgt
[mm] \prod_{i=1}^M p_i^{min(k_i, l_i)} [/mm] * [mm] \prod_{o=1}^M p_o^{x_o} =\prod_{i=1}^M p_i^{min(k_i, l_i)+ x_i}= \prod_{j=1}^M p_j^{k_j}
[/mm]
bzw [mm] \prod_{i=1}^M p_i^{min(k_i, l_i)} [/mm] * [mm] \prod_{o=1}^M p_o^{y_0} =\prod_{i=1}^M p_i^{l_i}
[/mm]
2)
Sei also s [mm] \in \IZ [/mm] gewählt sodass s|m, s|n.
ZZ.: s [mm] \le [/mm] d
Die Primfaktorzerlegung von s besteht dann doch auch nur aus den [mm] p_i [/mm] mit i [mm] \in\{1,..M,\} [/mm] oder??
[mm] s=\prod_{o=1}^M p_o^{r_o}
[/mm]
s|m, d.h [mm] \exists [/mm] k [mm] \in \IZ [/mm] sodass [mm] (\prod_{o=1}^M p_o^{r_o}) [/mm] * k = [mm] \prod_{j=1}^M p_j^{k_j}
[/mm]
s|n, d.h [mm] \exists [/mm] h [mm] \in \IZ [/mm] sodass [mm] (\prod_{o=1}^M p_o^{r_o}) [/mm] * h = [mm] \prod_{i=1}^M p_j^{l_i}
[/mm]
Nun stecke ich...Habt ihr Tipps?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:17 Fr 17.10.2014 | | Autor: | leduart |
Hallo
mach dich den zweiten Teil mit einen Widerspruch, angenommen es gibt einen Teiler grßer dein d, wie muss der aussehen? er muss mindestens [mm] 1p_i [/mm] mehr haben, dann teilt er eines der beiden nicht mehr.
Gruß leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:38 Sa 18.10.2014 | | Autor: | sissile |
> Hallo
> mach dich den zweiten Teil mit einen Widerspruch,
> angenommen es gibt einen Teiler grßer dein d, wie muss der
> aussehen? er muss mindestens [mm]1p_i[/mm] mehr haben, dann teilt er
> eines der beiden nicht mehr.
> Gruß leduart
>
Hallo leduart,
> er muss mindestens [mm]1p_i[/mm] mehr haben
als d meinst du?
Das leuchtet mir noch nicht ganz ein.
Die [mm] p_i [/mm] sind doch nur die Primzahlen, die m oder n teilen.
LG,
sissi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:04 Sa 18.10.2014 | | Autor: | leduart |
Hallo
$ [mm] d=\prod_{i=1}^M p_i^{min(k_i, l_i)} [/mm] $
du hast schon d teilt m,n
angenommen ggt(m,n)>d dann kann der ggt nur Teiler von m oder n enthalten also mus ein wieteres [mm] p_i [/mm] dazukommen
du hättest dann [mm] ggt=d*p_i [/mm] für mindestens ein i. teilt das dann noch n und m?
Gruß leduart
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:26 So 19.10.2014 | | Autor: | sissile |
Hallo leduart
> Hallo
> [mm]d=\prod_{i=1}^M p_i^{min(k_i, l_i)}[/mm]
> du hast schon d teilt
> m,n
> angenommen ggt(m,n)>d dann kann der ggt nur Teiler von m
> oder n enthalten also mus ein wieteres [mm]p_i[/mm] dazukommen
> du hättest dann [mm]ggt=d*p_i[/mm] für mindestens ein i. teilt das
> dann noch n und m?
> Gruß leduart
Sei i=M
m = [mm] \prod_{j=1}^{M-1} p_j^{k_j} p_M^{k_M}
[/mm]
n =m = [mm] \prod_{i=1}^{M-1} p_i^{l_i} p_M^{l_M}
[/mm]
Sei [mm] k_M [/mm] > [mm] l_M
[/mm]
-> d= [mm] \prod_{i=1}^{M-1} p_i^{min(k_i , l_i)} p_M^{l_M}
[/mm]
-> s= [mm] \prod_{i=1}^{M-1} p_i^{min(k_i , l_i)} p_M^{l_M +1}
[/mm]
->s teilt nicht n
Eine Frage dazu: s teilt nicht n, kann ich das auch noch in einen Beweis umschreiben? Ich meine mir ist es klar, weil es von irgendeiner Primzahl eine Potenz höher ist als n.
Ich hab noch einen anderen Weg gefunden mit deiner Hilfe:
Sei s [mm] \in \IZ: [/mm] s|m [mm] \wedge [/mm] s|n und s>d
d.h. [mm] \exists [/mm] a,b: s*a=m, s*b=n
Wie du sagst, s kann nur Teiler von m oder n enthalten, hat also die Form:
s= [mm] \prod_{r=1}^{M} p_r^{w_r}
[/mm]
Aus s*a=m wird [mm] \prod_{r=1}^{M} p_r^{w_r}*a =\prod_{j=1}^{M} p_j^{k_j} [/mm] => a = [mm] \prod_{c=1}^{M} p_c^{x_c} [/mm] wobei [mm] x_c= k_c [/mm] - [mm] w_c \forall [/mm] c [mm] \in \{1,..,M\}
[/mm]
Aus s*b=n wird [mm] \prod_{r=1}^{M} p_r^{w_r}*n =\prod_{i=1}^{M} p_i^{l_i} [/mm] => b = [mm] \prod_{c=1}^{M} p_c^{y_c} [/mm] wobei [mm] y_c= l_c [/mm] - [mm] w_c\forall [/mm] c [mm] \in \{1,..,M\}
[/mm]
Daraus folgt
[mm] \forall [/mm] i [mm] \in \{0,..M\} [/mm] gilt [mm] w_i [/mm] < [mm] k_i, w_i
[mm] \underbrace{=>}_{\*} [/mm] s|d => s [mm] \le [/mm] d => Widerspruch zu s >d
[mm] {\*} [/mm] da [mm] \exists [/mm] h= [mm] \prod_{o=1}^M p_o^{g_o} [/mm] mit [mm] w_o [/mm] + [mm] g_o [/mm] = [mm] min(k_o, l_o) \forall [/mm] o [mm] \in \{1,..,M\} [/mm] und s*h=d
LG,
sissi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 21.10.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
