ggT, Beweis

03.04.2012, 12:18

Springpony

ggT, Beweis

Zeige: Wenn $\begin{eqnarray*} ggT(x,y_i)=1 \end{eqnarray*}$ dann ist $\begin{eqnarray*} ggT(x,y_1*..*y_k) = 1 \end{eqnarray*}$
$\begin{eqnarray*} 1 \leq i \leq k \end{eqnarray*}$ , alles ganze zahlen

Vorrausetzung: $\begin{eqnarray*} ggT(x,y_i)=1 \end{eqnarray*}$
Sei $\begin{eqnarray*} ggT(x,y_i ) \neq 1 \end{eqnarray*}$
$\begin{eqnarray*} => \exists d>1 \in \mathbb Z \end{eqnarray*}$ so dass $\begin{eqnarray*} d|x, d|y_i \end{eqnarray*}$

$\begin{eqnarray*} d|y_i =>d|(y_i*(y_1*y_{i-1}*y_{i+1}*...*y_k) => d|y_1*..*y_k \end{eqnarray*}$

da d|x
$\begin{eqnarray*} => ggT(x,y_1*..*y_k ) \end{eqnarray*}$ ist mindestens $\begin{eqnarray*} d \end{eqnarray*}$ und $\begin{eqnarray*} d>1 \end{eqnarray*}$

STimmt der Beweis oder darf man den nicht so angehen??

03.04.2012, 12:37

weisbrot

Auf diesen Beitrag antworten »

RE: ggT, Beweis
hallo! das ist die ganz falsche harangehensweise. wenn du einen widerspruchsbeweis machen willst, dann gehst du vom gegenteil des zu zeigenden aus und führst das ganze zu einem widerspruch (bzw. wenn du kontraposition machen willst gehst du vom gegenteil des zu zeigenden an und zeigst das gegenteil der annahme). lg

03.04.2012, 12:44

Springpony

Auf diesen Beitrag antworten »

Wäre das dann der richtige Beweis für die Richtung:
Wenn $\begin{eqnarray*} ggT(x,y_1*..*y_k) = 1 \end{eqnarray*}$ dann ist $\begin{eqnarray*} ggT(x,y_i)=1 \end{eqnarray*}$
?

> Zeige: Wenn $\begin{eqnarray*} ggT(x,y_i)=1 \end{eqnarray*}$ dann ist $\begin{eqnarray*} ggT(x,y_1*..*y_k) = 1 \end{eqnarray*}$
Welche Beweisart würdest du hier empfehlen, weil ich hab einiges probiert und kam nirgends weiter.

03.04.2012, 12:55

weisbrot

Auf diesen Beitrag antworten »

nein, das wäre die umkehrung, das ist auch nicht zu zeigen.
du kannst die behauptung z.b. zeigen mit: $\begin{eqnarray*} ggT(x,\prod y_i) \neq 1 \Rightarrow ggT(x,y_i)\neq 1 \forall i \end{eqnarray*}$
probiers doch mal so. lg

03.04.2012, 14:28

Springpony

Auf diesen Beitrag antworten »

$\begin{eqnarray*} ggT(x,\prod y_i) \neq 1 \end{eqnarray*}$
$\begin{eqnarray*} =>\exists d \in\mathbb Z , d > 1 \end{eqnarray*}$ so dass $\begin{eqnarray*} d|x, d|\prod y_i \end{eqnarray*}$

Da würde ich nicht weiterkommen.

03.04.2012, 14:41

weisbrot

Auf diesen Beitrag antworten »

oh, ähm, ich hab einen fehler gemacht:

Zitat:

$\begin{eqnarray*} ggT(x,\prod y_i) \neq 1 \Rightarrow ggT(x,y_i)\neq 1 \forall i \end{eqnarray*}$

es muss heißen: $\begin{eqnarray*} ggT(x,\prod y_i) \neq 1 \Rightarrow \exists i : ggT(x,y_i)\neq 1 \end{eqnarray*}$ , sry.
naja der anfang ist ja schonmal gut. insbesondere gibt es dann eine primzahl (p), die d, und somit x und das produkt teilt. dann kannst du zeigen dass p auch ein y_i teilt. lg

03.04.2012, 14:53

Springpony

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \exists p \end{eqnarray*}$ sodass $\begin{eqnarray*} p|d=>p|x,p|\prod y_i \end{eqnarray*}$

Ich versteh nicht ganz wie ich daraus folgere, dass p|y_i

Wenn du mir da nochmals kurz aushelfen könntest Augenzwinkern

)
LG

03.04.2012, 15:21

weisbrot

Auf diesen Beitrag antworten »

na p ist also in der primfaktorzerlegung des produkts, also in der primfaktorzerlegung von mindestens einem der faktoren (also das ist einfach klar, denke ich; oder?). und der rest folgt dann ziemlich direkt. lg

03.04.2012, 15:49

Springpony

Auf diesen Beitrag antworten »

1)Zeige: Wenn $\begin{eqnarray*} ggT(x,y_i)=1 \end{eqnarray*}$ dann ist $\begin{eqnarray*} ggT(x,y_1*..*y_k) = 1 \end{eqnarray*}$
Mittels Kontraposition:
ZuZeigen: $\begin{eqnarray*} ggT(x,\prod y_i) \neq 1 \Rightarrow \exists i : ggT(x,y_i)\neq 1 \end{eqnarray*}$

$\begin{eqnarray*} ggT(x,\prod y_i) \neq 1 \end{eqnarray*}$
$\begin{eqnarray*} =>\exists d \in\mathbb Z , d > 1 \end{eqnarray*}$ so dass $\begin{eqnarray*} d|x, d|\prod y_i \end{eqnarray*}$

$\begin{eqnarray*} \exists p \end{eqnarray*}$ =Primzahl sodass $\begin{eqnarray*} p|d=>p|x,p|\prod y_i \end{eqnarray*}$
->p ist in der primfaktorzerlegung des produkts, also in der primfaktorzerlegung von mindestens einem der faktoren.
$\begin{eqnarray*} \exists i: p|y_i \end{eqnarray*}$
$\begin{eqnarray*} =>ggT(x,y_i) \neq 1 \end{eqnarray*}$ da dieser mindestens p sein muss und p> 1.

2) Zeige:Wenn $\begin{eqnarray*} ggT(x,y_1*..*y_k) = 1 \end{eqnarray*}$ dann ist $\begin{eqnarray*} ggT(x,y_i)=1 \end{eqnarray*}$
Mittels Kontraposition:
ZuZeigen: $\begin{eqnarray*} \exists i : ggT(x,y_i)\neq 1 \Rightarrow ggT(x,\prod y_i) \neq 1 \end{eqnarray*}$

$\begin{eqnarray*} ggT(x,y_i) \neq 1 \end{eqnarray*}$
$\begin{eqnarray*} =>\exists d \in\mathbb Z , d > 1 \end{eqnarray*}$ so dass $\begin{eqnarray*} d|x, d|y_i \end{eqnarray*}$

$\begin{eqnarray*} d|y_i \end{eqnarray*}$ => $\begin{eqnarray*} d|(y_1*..*y_k) \end{eqnarray*}$

$\begin{eqnarray*} ggT(x,y_1*..*y_k) \neq 1 \end{eqnarray*}$ da er mindestend d groß ist und d>1
Passt es so?

03.04.2012, 15:55

weisbrot

Auf diesen Beitrag antworten »

die rückrichtung solltest du also auch noch zeigen (ist ja auch ziemlich offensichtlich), ok. passt alles. lg

03.04.2012, 16:06

Springpony

Auf diesen Beitrag antworten »

danke <3
Retter in Not Augenzwinkern

Liebe grüße

Neue Frage »

Antworten »

ggT, Beweis

Verwandte Themen