Aussage über den ggT

Neue Frage »

14.12.2021, 20:57

Malcang

Auf diesen Beitrag antworten »

Aussage über den ggT

Guten Abend zusammen smile

ich hänge an folgendem:

Zitat:

Sei $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ und sei $\begin{eqnarray*} 1\leq i<\sqrt[3]{n} \end{eqnarray*}$ .
Weiterhin seien $\begin{eqnarray*} s,t \end{eqnarray*}$ ganze Zahlen mit $\begin{eqnarray*} t\not\equiv 0\pmod n \end{eqnarray*}$ so, dass $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ gilt. Man zeige, dass $\begin{eqnarray*} ggT(s+t, n) > 1 \end{eqnarray*}$ gilt.

Mein Ansatz:
Ich konnte durch geeignete Abschätzungen bereits zeigen, dass $\begin{eqnarray*} ggT(s+t, n)<n \end{eqnarray*}$ gilt.
Mir ist nur leider aktuell gar nicht klar, wie ich das für ggT > 1 gilt.
Ich kann mir auch gerade keinen Zusammenhang erklären. Bedeutet das $\begin{eqnarray*} ggT(s+t, i) = 1 \end{eqnarray*}$ ?
Ich bin gerade überfragt und um jeden Schubs dankbar smile

14.12.2021, 21:58

IfindU

Auf diesen Beitrag antworten »

RE: Aussage über den ggT
Setze $\begin{eqnarray*} s = 3 \end{eqnarray*}$ und $\begin{eqnarray*} t = -2 \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} (s+t)(s-t) = 5 \end{eqnarray*}$ .

Wir nehmen dann mal $\begin{eqnarray*} n= 5 \end{eqnarray*}$ und $\begin{eqnarray*} i=1 \end{eqnarray*}$ und damit $\begin{eqnarray*} (s+t)(s-t) = i \cdot n \end{eqnarray*}$ . Aber $\begin{eqnarray*} ggT( s+t, n)= ggT(1, 5) = 1 \end{eqnarray*}$ .

Überseh ich was?

14.12.2021, 22:00

HAL 9000

Auf diesen Beitrag antworten »

Bist mir etwas zuvorgekommen, aber ich poste meine vorbereiteten Überlegungen mal unverändert:

Ich weiß nicht, wieso das gelten sollte: Nehmen wir irgendeine ungerade Zahl $\begin{eqnarray*} n>2 \end{eqnarray*}$ , $\begin{eqnarray*} i=1 \end{eqnarray*}$ sowie $\begin{eqnarray*} s = \frac{1+n}{2} \end{eqnarray*}$ und $\begin{eqnarray*} t = \frac{1-n}{2} \end{eqnarray*}$ .

Dann ist $\begin{eqnarray*} s+t=1 \end{eqnarray*}$ , $\begin{eqnarray*} s-t=n \end{eqnarray*}$ und damit $\begin{eqnarray*} \operatorname{ggT}(s+t,n)=1 \end{eqnarray*}$ .

Vielleicht geht es nur um positive $\begin{eqnarray*} s,t \end{eqnarray*}$ . verwirrt

15.12.2021, 00:30

Malcang

Auf diesen Beitrag antworten »

Guten Abend ihr beiden,

ich muss mich entschuldigen. Es handelt sich in der Tat um natürliche zahlen s,t.
Ich hatte das erst geschrieben, dann gedacht ich hätte mich vertan und es daher auf "ganze" geändert. Ist mir aufgefallen, aber geändert hab ich es nicht unglücklich

Entschuldigt bitte.

15.12.2021, 07:38

HAL 9000

Auf diesen Beitrag antworten »

Dann ist das doch sehr einfach indirekt zu beweisen:

Aus $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ mit $\begin{eqnarray*} i>0 \end{eqnarray*}$ folgt zunächst mal $\begin{eqnarray*} s+t>0 \end{eqnarray*}$ und $\begin{eqnarray*} s-t>0 \end{eqnarray*}$ . Angenommen, es gilt $\begin{eqnarray*} \operatorname{ggT}(s+t,n)=1 \end{eqnarray*}$ , d.h. Teilerfremdheit. Dann folgt aus $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ zwingend $\begin{eqnarray*} n\mid (s-t) \end{eqnarray*}$ , und damit insbesondere $\begin{eqnarray*} s-t\geq n \end{eqnarray*}$ . Das bedeutet via Produkt $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ dann aber $\begin{eqnarray*} s+t\leq i \end{eqnarray*}$ mit der Folge $\begin{eqnarray*} 2t = (s+t)-(s-t) \leq i-n < 0 \end{eqnarray*}$ , Widerspruch zu $\begin{eqnarray*} t\geq 0 \end{eqnarray*}$ .

P.S.: Es wurde nur $\begin{eqnarray*} 1\leq i < n \end{eqnarray*}$ benötigt statt des strengeren $\begin{eqnarray*} i<\sqrt[3]{n} \end{eqnarray*}$ .

15.12.2021, 14:47

Malcang

Auf diesen Beitrag antworten »

Guten Tag zusammen,

ich danke euch beiden dass ihr euch die Zeit nehmt.

Zitat:

Original von HAL 9000
Dann ist das doch sehr einfach indirekt zu beweisen:

Aus $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ mit $\begin{eqnarray*} i>0 \end{eqnarray*}$ folgt zunächst mal $\begin{eqnarray*} s+t>0 \end{eqnarray*}$ und $\begin{eqnarray*} s-t>0 \end{eqnarray*}$ . Angenommen, es gilt $\begin{eqnarray*} \operatorname{ggT}(s+t,n)=1 \end{eqnarray*}$ , d.h. Teilerfremdheit. Dann folgt aus $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ zwingend $\begin{eqnarray*} n\mid (s-t) \end{eqnarray*}$ , und damit insbesondere $\begin{eqnarray*} s-t\geq n \end{eqnarray*}$ . Das bedeutet via Produkt $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ dann aber $\begin{eqnarray*} s+t\leq i \end{eqnarray*}$ mit der Folge $\begin{eqnarray*} 2t = (s+t)-(s-t) \leq i-n < 0 \end{eqnarray*}$ , Widerspruch zu $\begin{eqnarray*} t\geq 0 \end{eqnarray*}$ .

P.S.: Es wurde nur $\begin{eqnarray*} 1\leq i < n \end{eqnarray*}$ benötigt statt des strengeren $\begin{eqnarray*} i<\sqrt[3]{n} \end{eqnarray*}$ .

HAL 9000, ich bin hellauf begeistert von dieser Lösung. Ich bedanke mich herzlich!
Darüber hinaus bin ich immer wieder erstaunt, mit welcher Leichtfertigkeit du soetwas aus dem Hut zauberst.

Als ich die zweite Zeile deines Beweis las dachte ich "Ah na klar, ich weiß worauf es hinausläuft", aber es passierte dann doch etwas anderes. Daher möchte ich hier meine Alternative vorstellen, aufbauend auf deinen Ausführungen.
Da $\begin{eqnarray*} s,t \end{eqnarray*}$ natürliche Zahlen sind und $\begin{eqnarray*} t\neq 0 \end{eqnarray*}$ , folgt $\begin{eqnarray*} s+t>s-t \end{eqnarray*}$ .
Aus $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ mit $\begin{eqnarray*} i>0 \end{eqnarray*}$ folgt zunächst mal $\begin{eqnarray*} s+t>0 \end{eqnarray*}$ und $\begin{eqnarray*} s-t>0 \end{eqnarray*}$ . Angenommen, es gilt $\begin{eqnarray*} \operatorname{ggT}(s+t,n)=1 \end{eqnarray*}$ , d.h. Teilerfremdheit. Dann folgt aus $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ zwingend $\begin{eqnarray*} n\mid (s-t) \end{eqnarray*}$ , und damit insbesondere $\begin{eqnarray*} s-t\geq n \end{eqnarray*}$ . Das bedeutet via Produkt $\begin{eqnarray*} (s+t)(s-t) = i\cdot n \end{eqnarray*}$ dann aber $\begin{eqnarray*} (s+t)(s-t) > n^2 \end{eqnarray*}$ , woraus i $\begin{eqnarray*} i>n \end{eqnarray*}$ folgt.

15.12.2021, 15:13

HAL 9000

Auf diesen Beitrag antworten »

Ja klar, geht ebenfalls. Ist man einmal auf dem sicheren Weg zum Widerpruch, dann kann man den im Detail variieren. Augenzwinkern

15.12.2021, 15:35

Malcang

Auf diesen Beitrag antworten »

Sehr interessant! Vielen Dank! Freude

Neue Frage »

Antworten »

Aussage über den ggT

Verwandte Themen