Indirekter Beweis ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:23 Fr 02.12.2011 | | Autor: | HannSG |
| Aufgabe | Beweisen Sie:
Für alle [mm] a_{1},..., a_{n} \in \IZ \{0} [/mm] und b [mm] \in \IZ [/mm] gilt:
ggT [mm] (a_{i},b)=1 [/mm] für alle i=1,...,n [mm] \gdw [/mm] ggT [mm] (a_{1}*....*a_{n},b)=1
[/mm]
Hinweis: Indirekter Beweis. |
aus ggT [mm] (a_{i},b)=1 [/mm] folgt doch, dass hier von Primzahlen die Rede ist, oder?
und mir ist bewusst dass durch die Multiplikation der ggT gleich 1 bleibt. Aber ich weiß nicht wie ich das formell richtig ausdrücken kann.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:57 Fr 02.12.2011 | | Autor: | leduart |
Hallo
ggT(36,49)=1 beides keine Primzahlen.
Warum nimmst du nicht an [mm] ggT(a1*a2*a3)=c\ne1 [/mm] mit [mm] ggT(a_i)=1
[/mm]
Wenn dus für 3 kannst weisst du wie es geht.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:19 Sa 03.12.2011 | | Autor: | Catman |
> Hallo
> ggT(36,49)=1 beides keine Primzahlen.
> Warum nimmst du nicht an [mm]ggT(a1*a2*a3)=c\ne1[/mm] mit
> [mm]ggT(a_i)=1[/mm]
> Wenn dus für 3 kannst weisst du wie es geht.
> Gruss leduart
Könntest du diese Idee genauer erläutern? a1*a2*a3 ist doch nur eine Zahl? Wie kann man davon den ggT nehmen?
|
|
|
| |
|
Ich nehme mal an er meinte es noch mit $b$ mit drinn.
Also [mm] ggT($a_1*a_2*a_3,b) [/mm] = c > 1$, aber [mm] ggT($a_i,b) [/mm] = 1$ für alle $i$.
Wenn du schon Primfaktorzerlegungen kennst und weißt, was es für die Primfaktorzerlegung bedeutet wenn zwei Zahlen teilerfremd sind könnte dir das sicher helfen, aber es geht sonst auch zu Fuß.
Also versuche einfach mal vier Zahlen [mm] $a_1,a_2,a_3,b$ [/mm] zu finden, die obere beiden Bedingungen erfüllen.
Da das ja nicht geht (es widerspricht dem was du zeigen sollst) wirst du dabei wahrscheinlich scheitern; aber wenn du es oft genug probierst wirst du irgendwann sehen warum du scheiterst; und das ist dann der Ansatz für deinen Beweis.
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:15 So 04.12.2011 | | Autor: | Catman |
> Ich nehme mal an er meinte es noch mit [mm]b[/mm] mit drinn.
> Also ggT([mm]a_1*a_2*a_3,b) = c > 1[/mm], aber ggT([mm]a_i,b) = 1[/mm] für
> alle [mm]i[/mm].
>
> Wenn du schon Primfaktorzerlegungen kennst und weißt, was
> es für die Primfaktorzerlegung bedeutet wenn zwei Zahlen
> teilerfremd sind könnte dir das sicher helfen, aber es
> geht sonst auch zu Fuß.
> Also versuche einfach mal vier Zahlen [mm]a_1,a_2,a_3,b[/mm] zu
> finden, die obere beiden Bedingungen erfüllen.
> Da das ja nicht geht (es widerspricht dem was du zeigen
> sollst) wirst du dabei wahrscheinlich scheitern; aber wenn
> du es oft genug probierst wirst du irgendwann sehen warum
> du scheiterst; und das ist dann der Ansatz für deinen
> Beweis.
>
>
> lg
>
> Schadow
Danke für die Antwort.
Also c kann ja nur größer 1 sein, wenn ein ai nicht teilerfremd von b ist. Das ist ja auch logisch. Aber ich weiß nicht, wie ich das jetzt mathematisch als Beweis ausdrücke.
Also aus [mm] ggT(a_{1},a_{2},...,a_{i},b)=1 [/mm] folgt doch, dass alle [mm] a_{1} [/mm] bis [mm] a_{i} [/mm] teilerfremd zu b sein müssen, was die rechte Seite der Gleichung ja ausdrückt, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:36 So 04.12.2011 | | Autor: | leduart |
Hallo
genau das sollst du doch beweisen: du weisst je 2 [mm] a_i [/mm] haben [mm] ggT(a_i,a_k)=1 [/mm] wenn [mm] k\ne [/mm] i
und [mm] ggT(a_i,b)=1
[/mm]
dir ist klar, dass dann auch [mm] ggT(a_1*a_2*...a_n,b)=1 [/mm] ist. sag erstmal in Worten warum du das denkst.
dann wie kommst du von [mm] ggT;a_1,b)=1 [/mm] und [mm] ggT(a_2,b)=1 [/mm] zu [mm] ggT(a_1*a_2,b)=1
[/mm]
wenn du das hast ists für n Faktoren eine Induktion.
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:40 Mo 05.12.2011 | | Autor: | Catman |
> Hallo
> genau das sollst du doch beweisen: du weisst je 2 [mm]a_i[/mm]
> haben [mm]ggT(a_i,a_k)=1[/mm] wenn [mm]k\ne[/mm] i
> und [mm]ggT(a_i,b)=1[/mm]
> dir ist klar, dass dann auch [mm]ggT(a_1*a_2*...a_n,b)=1[/mm] ist.
> sag erstmal in Worten warum du das denkst.
> dann wie kommst du von [mm]ggT;a_1,b)=1[/mm] und [mm]ggT(a_2,b)=1[/mm] zu
> [mm]ggT(a_1*a_2,b)=1[/mm]
> wenn du das hast ists für n Faktoren eine Induktion.
> gruss leduart
Ja, wenn der ggT(a1,b) und ggT(a2,b) =1 sind, dann haben weder a1 noch a2 einen gemeinsamen Primfaktor mit b in der Zerlegung. Also hat a1*a2 auch keinen gemeinsamen Primfaktor mit b. Also ggt=1. Stimmt das?
Aber ich weiß nicht wie ich das so Beweismäßig aufschreibe.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:13 Mi 07.12.2011 | | Autor: | leduart |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo
a) man macht den Beweis per induktion:
Vors: ggT(a_1,b)=1 ggT(a2,b)=1
Beh ggT(a1*a_2,b)=1
Beweis: nach vors haben b und a_1 und b und a_2 keinen gemeinsamen Primfaktor , dann hat auch a1*a2 wegen der Eindutigkeit der primfaktor zerlegung keinen gemeinsamen Primfaktor mit b
also ggT(a1'a2 ,b)=1
Ind vors ggT(a_1'a_2*...*a_n,b)=1
d.h. a_1'a_2*...*a_n und b hat keinen gemeinsamen primfaktot, Ind Beh. ggT(a_1*a_2...*a_n*a_{n+1},b)=1 wenn auch ggT{a_{n+1},b)=1
den Schritt solltet ihr können.
indirekter beweis
vors über die einzelnen ggT wie oben.
Beh: ggT(a_1'a_2*...*a_n,b)=c\ne1 c ist selbst prim, oder enthält mindestens einen Primfaktor p_1
P_1 muss b und a_1'a_2*...*a_n, teilen
wegen der Eindeutigkeit der Primzahlzerlegung muss dann wenigstens ein a_i den Faktor p_1 enthalten.
das widerspricht ggT(a_i,b)=1 also ist die annahme falsch.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 22:35 Mo 05.12.2011 | | Autor: | HannSG |
> Hallo
> genau das sollst du doch beweisen: du weisst je 2 [mm]a_i[/mm]
> haben [mm]ggT(a_i,a_k)=1[/mm] wenn [mm]k\ne[/mm] i
> und [mm]ggT(a_i,b)=1[/mm]
> dir ist klar, dass dann auch [mm]ggT(a_1*a_2*...a_n,b)=1[/mm] ist.
> sag erstmal in Worten warum du das denkst.
kann man vielleicht von [mm] b|a_{i} [/mm] ausgehen? und dann darf man ja auch links eine beliebige Zahl dazu multiplizieren.
> dann wie kommst du von [mm]ggT;a_1,b)=1[/mm] und [mm]ggT(a_2,b)=1[/mm] zu
> [mm]ggT(a_1*a_2,b)=1[/mm]
[mm] b|a_2 [/mm] und [mm] b|a_1 \Rightarrow b|a_2 [/mm] * [mm] a_1 \Rightarrow [/mm] ggT [mm] (a_1*a_2,b)=1
[/mm]
> wenn du das hast ists für n Faktoren eine Induktion.
wie soll ich jetzt eine Induktion machen? Und in der Aufgabe steht ja auch, dass ich das indirekt beweisen soll.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:21 Mi 07.12.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:24 Mi 07.12.2011 | | Autor: | HannSG |
Ich verstehe es leider immer noch nicht ganz. Kann mir das vieleicht jemand nochmal genauer erklären.
Danke.
Lg HannSG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:16 Mi 07.12.2011 | | Autor: | leduart |
Hallo
du schriebst :
$ [mm] b|a_2 [/mm] $ und $ [mm] b|a_1 \Rightarrow b|a_2 [/mm] $ * $ [mm] a_1 \Rightarrow [/mm] $ ggT $ [mm] (a_1\cdot{}a_2,b)=1 [/mm]
[mm] b|a_2 [/mm] und [mm] b|a_1 [/mm] heisst in Worten b teilt a-1 und [mm] a_2 [/mm] dann wäre [mm] ggT(a_1*a_2,b)=b [/mm] und nicht 1 ??
gruss leduart
|
|
|
|
