ggT von Summen

05.07.2024, 10:08

KonverDiv

ggT von Summen

Hallo

,

innerhalb eines Beweises bin ich an einem Punkt angelangt, wo ich eine Frage habe, die ich hier gerne stellen möchte.

Zunächst ist $\begin{eqnarray*} f(X) = a_0 + a_1 X + a_2 X^2 + ... a_n X^N \end{eqnarray*}$ und $\begin{eqnarray*} g(X) = b_0 + b_1 X + b_2 X^2 + ... b_n X^n \end{eqnarray*}$ , wobei $\begin{eqnarray*} a_i, b_i \in \mathbb{Z} \end{eqnarray*}$ . Ich betrachte nun $\begin{eqnarray*} d = ggT(a_0,a_1,...,a_n) \cdot ggT(b_0, b_1, ..., b_n) \end{eqnarray*}$ und $\begin{eqnarray*} d' = ggT\left(a_0 b_0, \sum_{i + j = 1} a_i b_j, \sum_{i + j = 2} a_i b_j, ..., \sum_{i + j = 2n} a_i b_j \right) \end{eqnarray*}$ , meine Frage ist, ob $\begin{eqnarray*} d = d' \end{eqnarray*}$ gilt?

Ich dachte mir, um zu zeigen, dass $\begin{eqnarray*} d = d' \end{eqnarray*}$ gilt, könnte ich mir die Eigenschaften des ggT ansehen und hier vielleicht eine nützliche finden. Ich habe bisher keine Eigenschaft gefunden, die in diese Richtung gehen würde, außer evtl $\begin{eqnarray*} ggT(a,b) = ggT(a, b + an) \end{eqnarray*}$ für $\begin{eqnarray*} n \in \mathbb{Z} \end{eqnarray*}$ .

Dann habe ich mir überlegt, sei $\begin{eqnarray*} n=1 \end{eqnarray*}$ , dann haben wir $\begin{eqnarray*} f(X) = a_0 + a_1 X, g(X) = b_0 + b_1 X \end{eqnarray*}$ und $\begin{eqnarray*} d = ggT(a_0,a_1) \cdot ggT(b_0, b_1) \end{eqnarray*}$ und $\begin{eqnarray*} d' = ggT(a_0 b_0, a_0 b_1 + a_1 b_0, a_1 b_1) \end{eqnarray*}$ . Mit der Identität von Berzout würde ich jetzt auf folgendes kommen: $\begin{eqnarray*} d = (a_0 x + a_1 y)(b_0 x' + b_1y') = a_0 b_0 xx' + a_0 b_1 xy' a_1 b_0 x'y + a_1 b_1 yy' \end{eqnarray*}$ , wobei $\begin{eqnarray*} x,x',y,y' \in \mathbb{Z} \end{eqnarray*}$ . Für $\begin{eqnarray*} d' = (a_0 b_0 x' + ((a_0 b_1 + a_1 b_0)x + a_1 b_1 y)y' \end{eqnarray*}$ , wobei $\begin{eqnarray*} x,x',y,y' \in \mathbb{Z} \end{eqnarray*}$ . Wenn man das weiter umstellt und beachtet, dass es sich bei $\begin{eqnarray*} x,x',y,y' \end{eqnarray*}$ um Elemente aus $\begin{eqnarray*} \mathbb{Z} \end{eqnarray*}$ handelt, dann könnte ich mir gut vorstellen, dass $\begin{eqnarray*} d=d' \end{eqnarray*}$ gilt. Das könnte man vielleicht allgemeiner über vollständige Induktion zeigen, oder?

Danke! smile

05.07.2024, 10:41

HAL 9000

Auf diesen Beitrag antworten »

RE: ggT von Summen
Kurz gesagt fragst du dich, ob die Produkte der ggT der Koeffizienten von $\begin{eqnarray*} f,g \end{eqnarray*}$ dem ggT der Koeffizienten von $\begin{eqnarray*} f\cdot g \end{eqnarray*}$ entspricht.

Ok, benennen wir ein paar Werte $\begin{eqnarray*} A= \operatorname{ggT}\left(a_0,a_1,\ldots,a_n\right) \end{eqnarray*}$ , $\begin{eqnarray*} B= \operatorname{ggT}\left(b_0,b_1,\ldots,b_n\right) \end{eqnarray*}$ und $\begin{eqnarray*} C= \operatorname{ggT}\left(c_0,c_1,\ldots,c_{2n}\right) \end{eqnarray*}$ mit $\begin{eqnarray*} c_k = \sum_{i+j=k} a_ib_j \end{eqnarray*}$

Wir können o.B.d.A. von $\begin{eqnarray*} A=1,B=1 \end{eqnarray*}$ ausgehen, andernfalls teilen wir alle Koeffizienten von $\begin{eqnarray*} f \end{eqnarray*}$ durch $\begin{eqnarray*} A \end{eqnarray*}$ bzw. von $\begin{eqnarray*} g \end{eqnarray*}$ durch $\begin{eqnarray*} B \end{eqnarray*}$ , das entspricht dann dem Teilen aller Koeffizienten von $\begin{eqnarray*} f\cdot g \end{eqnarray*}$ durch $\begin{eqnarray*} A\cdot B \end{eqnarray*}$ .

Die Frage ist nun, ob dann zwingend $\begin{eqnarray*} C=1 \end{eqnarray*}$ gilt, bzw. indirekt, ob man $\begin{eqnarray*} C>1 \end{eqnarray*}$ zum Widerspruch führen kann.

EDIT: Der angedachte indirekte Beweis ausgehend von $\begin{eqnarray*} C>1 \end{eqnarray*}$ ist überraschend einfach. Vielleicht hilft es, ein paar Beispiele anzusehen. Augenzwinkern

EDIT2: Schlussindex bei den $\begin{eqnarray*} c_k \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ auf $\begin{eqnarray*} 2n \end{eqnarray*}$ geändert, nach dankenswertem Hinweis von KonverDiv.

05.07.2024, 11:12

KonverDiv

Auf diesen Beitrag antworten »

RE: ggT von Summen

Zitat:

Original von HAL 9000
EDIT: Der angedachte indirekte Beweis ausgehend von $\begin{eqnarray*} C>1 \end{eqnarray*}$ ist überraschend einfach. Vielleicht hilft es, ein paar Beispiele anzusehen. Augenzwinkern

Tatsächlich? Mit Beispielen meinst du jetzt konkrete mit "echten" Werten? Würde ich mir mal ansehen.

05.07.2024, 11:25

HAL 9000

Auf diesen Beitrag antworten »

Noch ein Hinweis: Im Fall $\begin{eqnarray*} C>1 \end{eqnarray*}$ existiert ein Primfaktor $\begin{eqnarray*} p \end{eqnarray*}$ von $\begin{eqnarray*} C \end{eqnarray*}$ . Jetzt schau dir mal jeweils getrennt für $\begin{eqnarray*} a_0,a_1,\ldots \end{eqnarray*}$ sowie $\begin{eqnarray*} b_0,b_1,\ldots \end{eqnarray*}$ die jeweils kleinsten Indizes an, wo diese Koeffizienten nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar sind: D.h., warum muss es diese Indizes überhaupt geben, und wie kann man damit ein $\begin{eqnarray*} c_k \end{eqnarray*}$ finden mit $\begin{eqnarray*} p\nmid c_k \end{eqnarray*}$ , was schließlich im Widerspruch zu $\begin{eqnarray*} p\mid C\mid c_k \end{eqnarray*}$ steht.

05.07.2024, 11:38

KonverDiv

Auf diesen Beitrag antworten »

Mir ist noch etwas aufgefallen, oben schreibst du

$\begin{eqnarray*} C= \operatorname{ggT}\left(c_0,c_1,\ldots,c_n\right) \end{eqnarray*}$

aber es müsste heißen

$\begin{eqnarray*} C= \operatorname{ggT}\left(c_0,c_1,\ldots,c_{2n}\right) \end{eqnarray*}$

hast du das berücksichtigt?

EDIT: Ich überlege mir gerade ein paar Beispiele, sagen wir $\begin{eqnarray*} n=1, C = p > 1 \end{eqnarray*}$ , dann haben wir $\begin{eqnarray*} p(c_0/p, c_1/p,...,c_2/p) \end{eqnarray*}$ , dann müsste $\begin{eqnarray*} (a_0 b_0)/p \end{eqnarray*}$ , $\begin{eqnarray*} (a_0b_1 + a_1 b_0)/p \end{eqnarray*}$ und $\begin{eqnarray*} (a_1 b_1) /p \end{eqnarray*}$ gelten...

05.07.2024, 12:19

HAL 9000

Auf diesen Beitrag antworten »

Ja Ok, $\begin{eqnarray*} 2n \end{eqnarray*}$ ist da gemeint, oder von mir auch noch größer. Es gilt außerdem die stillschweigende Übereinkunft, dass $\begin{eqnarray*} a_k=0 \end{eqnarray*}$ und $\begin{eqnarray*} b_k=0 \end{eqnarray*}$ für alle $\begin{eqnarray*} k>n \end{eqnarray*}$ gilt, das vereinfacht ein wenig die Indexbetrachtung in den Formeln.

05.07.2024, 12:26

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Noch ein Hinweis: Im Fall $\begin{eqnarray*} C>1 \end{eqnarray*}$ existiert ein Primfaktor $\begin{eqnarray*} p \end{eqnarray*}$ von $\begin{eqnarray*} C \end{eqnarray*}$ .

Ja, das kann ich nachvollziehen. Sagen wir $\begin{eqnarray*} n=1 \end{eqnarray*}$ , $\begin{eqnarray*} C=p>1 \end{eqnarray*}$ , dann haben wir $\begin{eqnarray*} p(c_0/p,c_1/p,...,c_2/p) \end{eqnarray*}$

Zitat:

Original von HAL 9000
Jetzt schau dir mal jeweils getrennt für $\begin{eqnarray*} a_0,a_1,\ldots \end{eqnarray*}$ sowie $\begin{eqnarray*} b_0,b_1,\ldots \end{eqnarray*}$ die jeweils kleinsten Indizes an, wo diese Koeffizienten nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar sind

Es müsste $\begin{eqnarray*} (a_0b_0)/p \end{eqnarray*}$ , $\begin{eqnarray*} (a_0b_1+a_1b_0)/p \end{eqnarray*}$ und $\begin{eqnarray*} (a_1b_1)/p \end{eqnarray*}$ gelten, aber der Term in der Mitte könnte zu Problemen führen.

05.07.2024, 13:06

HAL 9000

Auf diesen Beitrag antworten »

Machen wir es ganz konkret: Es gelte $\begin{eqnarray*} p\mid a_i \end{eqnarray*}$ für $\begin{eqnarray*} 0\leq i < i_0 \end{eqnarray*}$ sowie $\begin{eqnarray*} p\nmid a_{i_0} \end{eqnarray*}$ , außerdem $\begin{eqnarray*} p\mid b_j \end{eqnarray*}$ für $\begin{eqnarray*} 0\leq j < j_0 \end{eqnarray*}$ sowie $\begin{eqnarray*} p\nmid b_{j_0} \end{eqnarray*}$ . (Die Frage, warum es solche $\begin{eqnarray*} i_0 \end{eqnarray*}$ bzw. $\begin{eqnarray*} j_0 \end{eqnarray*}$ geben muss, steht noch immer ).

Für welches $\begin{eqnarray*} k \end{eqnarray*}$ kann man damit nun sicher nachweisen, dass

$\begin{eqnarray*} c_k = a_0b_k + a_1b_{k-1} + \ldots + a_kb_0 \end{eqnarray*}$

nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar ist?

Nehmen wir mal als ganz konkretes Beispiel $\begin{eqnarray*} f(X) = 2 + 4X - X^2 + 2X^3 \end{eqnarray*}$ und $\begin{eqnarray*} g(X) = 4 - 2X + 6X^2 + 5X^3 \end{eqnarray*}$ , da ist bezogen auf $\begin{eqnarray*} p=2 \end{eqnarray*}$ dann $\begin{eqnarray*} i_0=2 \end{eqnarray*}$ sowie $\begin{eqnarray*} j_0=3 \end{eqnarray*}$ . Welche Koeffizienten von $\begin{eqnarray*} f\cdot g \end{eqnarray*}$ sind dann nicht durch $\begin{eqnarray*} p=2 \end{eqnarray*}$ teilbar? Man kann sich auf den konzentrieren, wo das erstmalig geschieht (von unten beginnend zählen).

05.07.2024, 13:10

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Für welches $\begin{eqnarray*} k \end{eqnarray*}$ kann man damit nun sicher nachweisen, dass

$\begin{eqnarray*} c_k = a_0b_k + a_1b_{k-1} + \ldots + a_kb_0 \end{eqnarray*}$

nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar ist?

Ich würde sagen für $\begin{eqnarray*} k \geq i_0 , j_0 \end{eqnarray*}$ .

05.07.2024, 13:12

HAL 9000

Auf diesen Beitrag antworten »

Mit dem Komma kann ich da nichts anfangen. Meine Antwort lautet $\begin{eqnarray*} k=i_0+j_0 \end{eqnarray*}$ .

$\begin{eqnarray*} c_{i_0+j_0} = {\color{red}a_0b_{i_0+j_0} + a_1b_{i_0+j_0-1} + \ldots + a_{i_0-1}b_{j_0+1}}~+ a_{i_0}b_{j_0}+~ {\color{blue}a_{i_0+1}b_{j_0-1} + \ldots + a_{i_0+j_0-1}b_1 + a_{i_0+j_0}b_0} \end{eqnarray*}$

Die roten Terme sind wegen $\begin{eqnarray*} p\mid a_i \end{eqnarray*}$ für $\begin{eqnarray*} i<i_0 \end{eqnarray*}$ durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar, die blauen wegen $\begin{eqnarray*} p\mid b_j \end{eqnarray*}$ für $\begin{eqnarray*} j<j_0 \end{eqnarray*}$ . Übrig bleibt zwischendrin $\begin{eqnarray*} a_{i_0}b_{j_0} \end{eqnarray*}$ , was nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar ist.

05.07.2024, 13:23

KonverDiv

Auf diesen Beitrag antworten »

Ja stimmt, $\begin{eqnarray*} k = i_0 + j_0 \end{eqnarray*}$ . Ich wollte mit dem Komma sowas sagen wie, $\begin{eqnarray*} k \geq i_0 \end{eqnarray*}$ oder $\begin{eqnarray*} k \geq j_0 \end{eqnarray*}$ .

Es ist $\begin{eqnarray*} (2+4x-x^2+2x^3)(4-2x+6x^2+5x^3) = 10 x^6 + 7 x^5 + 10 x^4 + 44 x^3 + 12 x + 8 \end{eqnarray*}$ , also ist bei $\begin{eqnarray*} c_4 = 7 \end{eqnarray*}$ nicht gegeben, dass 2 die 7 teilt.

Aber warum gibt es die $\begin{eqnarray*} i_0 \end{eqnarray*}$ und $\begin{eqnarray*} j_0 \end{eqnarray*}$ , etwa wegen unserer Annahme des Falls $\begin{eqnarray*} C > 1 \end{eqnarray*}$

05.07.2024, 13:31

HAL 9000

Auf diesen Beitrag antworten »

Der rote Anteil ist natürlich leer, wenn $\begin{eqnarray*} i_0=0 \end{eqnarray*}$ , analog der blaue leer, wenn $\begin{eqnarray*} j_0=0 \end{eqnarray*}$ . Aber das tut der Begründung keinen Abbruch. Sofern

Zitat:

Original von HAL 9000
Die Frage, warum es solche $\begin{eqnarray*} i_0 \end{eqnarray*}$ bzw. $\begin{eqnarray*} j_0 \end{eqnarray*}$ geben muss

klar ist, sind wir damit mit dem indirekten Beweis fertig.

05.07.2024, 13:33

KonverDiv

Auf diesen Beitrag antworten »

Achso, das läuft wieder auf so einen "typischen" Existenzbeweis $\begin{eqnarray*} x \neq 0 \end{eqnarray*}$ hinaus, was heißt $\begin{eqnarray*} x \end{eqnarray*}$ existiert. Nur eben im Fall von $\begin{eqnarray*} i_0 \end{eqnarray*}$ und $\begin{eqnarray*} j_0 \end{eqnarray*}$ . Ich hatte an etwas ganz anderes gedacht, irgendwas zahlentheoretisches.

05.07.2024, 13:50

HAL 9000

Auf diesen Beitrag antworten »

Ich weiß nicht, was der "typische" Existenzbeweis sein soll. Für mich ist die Existenz klar, weil ansonsten $\begin{eqnarray*} p \end{eqnarray*}$ alle $\begin{eqnarray*} a_i \end{eqnarray*}$ teilen müsste, was deren ggT $\begin{eqnarray*} A=1 \end{eqnarray*}$ widerspricht. Analog bei den $\begin{eqnarray*} b_j \end{eqnarray*}$ und $\begin{eqnarray*} B=1 \end{eqnarray*}$ .

05.07.2024, 13:59

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
weil ansonsten $\begin{eqnarray*} p \end{eqnarray*}$ alle $\begin{eqnarray*} a_i \end{eqnarray*}$ teilen müsste

Da hatte ich auch dran gedacht smile

Zitat:

Original von HAL 9000
..., was deren ggT $\begin{eqnarray*} A=1 \end{eqnarray*}$ widerspricht.

Da hatte ich nicht mehr dran gedacht, ist aber plausibel. Ich hatte nur noch an $\begin{eqnarray*} C > 1 \end{eqnarray*}$ gedacht und nicht mehr die Annahme für $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ berücksichtig

Vielen Dank für deine Hilfe!

Neue Frage »

Antworten »

ggT von Summen

Verwandte Themen