ggT Beweis

29.07.2017, 16:16

gandalf24

ggT Beweis

Hallo zusammen, ich habe mit folgendem Beweis meine Schwierigkeiten:

Seien $\begin{eqnarray*} a,b, c \in \mathbb Z \end{eqnarray*}$ teilerfremd und $\begin{eqnarray*} c \neq 0 \end{eqnarray*}$ . Zeigen Sie, dass dann ein $\begin{eqnarray*} x \in \mathbb Z \end{eqnarray*}$ existiert, sodass:

$\begin{eqnarray*} ggt(a+bx, c) = 1 \end{eqnarray*}$

Ich weiß nicht so recht, wie ich darangehe.
Folgendes weiß ich:
$\begin{eqnarray*} ggt(a,b,c) = 1 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} \exists u, v, w: ua + vb + wc = 1 \end{eqnarray*}$ .

Nun soll ich, aber nicht zeigen, dass der ggT(a+bx, c) = 1 für alle x ist, sondern das mindestens eins existiert. Hat da jemand einen Tipp?

Vielen Dank!

01.08.2017, 12:03

Elvis

Auf diesen Beitrag antworten »

Danke, das hat mich ein paar Tage lang beschäftigt. Wir müssen vielleicht triviale Fälle gesondert betrachten.
Für den Fall ggT(a,b)=1 führe ich den Dirichletschen Primzahlsatz ins Feld, der liefert unendlich viele Primzahlen in der arithmetischen Folge a+bx, fast alle diese Primzahlen teilen c nicht. smile

(Um Vorzeichen der ganzen Zahlen musst du dich selber kümmern.)
Herausforderung an alle: wer kann die Aufgabe mit weniger schweren Geschützen knacken ?

01.08.2017, 12:16

HAL 9000

Auf diesen Beitrag antworten »

Hmm, nur ein paar anfängliche Gedanken:

Zitat:

Original von gandalf24
Folgendes weiß ich:
$\begin{eqnarray*} ggt(a,b,c) = 1 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} \exists u, v, w: ua + vb + wc = 1 \end{eqnarray*}$ .

Damit ist

$\begin{align*} u(a+bx) + (v-ux)b + wc = 1 \end{align*}$ .

Gelingt es nun, ein $\begin{align*} x \end{align*}$ mit $\begin{align*} c \mid (v-ux)b \end{align*}$ zu finden, ist man fertig. Aber vermutlich habe ich mit diesen Überlegungen das Problem nur verlagert statt es zu vereinfachen. Augenzwinkern

EDIT: Klappt aber z.B. für u=0 überhaupt nicht. Also wohl doch nur ein unbrauchbarer Schnellschuss.

02.08.2017, 18:42

Elvis

Auf diesen Beitrag antworten »

@gandalf24
Hast du die Behauptung schon für die "trivialen" Fälle bewiesen ? Ich würde gerne sehen, wie du das machst.

02.08.2017, 22:12

123Gast456

Auf diesen Beitrag antworten »

Ein Hinweis wäre, sich für gegebenes $\begin{eqnarray*} x \in \mathbb Z \end{eqnarray*}$ die Menge aller Primzahlen anzusehen, die gleichzeitig $\begin{eqnarray*} c \end{eqnarray*}$ und $\begin{eqnarray*} a+bx \end{eqnarray*}$ teilen...
Eine solche Primzahl kann dann $\begin{eqnarray*} b \end{eqnarray*}$ nicht teilen - Warum?

03.08.2017, 18:39

123Gast456

Auf diesen Beitrag antworten »

Sorry, habe einen Fehler gefunden, der das Ganze ziemlich verfälscht...

Man sollte sich die Menge aller Primzahlen p anschauen, die c teilen und es eine ganze Zahl x gibt, sodass a+bx ebenfalls von p geteilt wird.

Jetzt sollte klar sein, was ich meine...

Neue Frage »

Antworten »

ggT Beweis

Verwandte Themen