Größter gemeinsamer Teiler zweier Potenzen

01.06.2012, 16:54

Benutzername123

Größter gemeinsamer Teiler zweier Potenzen

Ich habe eine Frage: Gilt $\begin{eqnarray*} ggT(a^k, b^k) = ggT(a, b)^k \end{eqnarray*}$ ?

Meine Überlegungen hierzu: Es seien $\begin{eqnarray*} T_a, T_b \end{eqnarray*}$ die Teilermengen von a und b.

Die Teilermengen von $\begin{eqnarray*} a^k \end{eqnarray*}$ und $\begin{eqnarray*} b^k \end{eqnarray*}$ lassen sich darstellen als
$\begin{eqnarray*} T_{a^k} = \{x^i | x \in T_a \wedge i \in [1,k] \cap \mathbb N\} \end{eqnarray*}$
$\begin{eqnarray*} T_{b^k} = \{x^i | x \in T_b \wedge i \in [1,k] \cap \mathbb N\} \end{eqnarray*}$

Bezeichnen $\begin{eqnarray*} g_1, g_2, ..., g_n \end{eqnarray*}$ mit $\begin{eqnarray*} g_n = ggT(a,b) \end{eqnarray*}$ die gemeinsamen Teiler von a und b. Da jedes $\begin{eqnarray*} g_j \end{eqnarray*}$ a und b teilt, sind alle $\begin{eqnarray*} (g_j)^i \end{eqnarray*}$ mit $\begin{eqnarray*} i \in [1,k] \cap \mathbb N \end{eqnarray*}$ die gemeinsamen Teiler von a^k und b^k (da $\begin{eqnarray*} g_j \in T_a, T_b \Rightarrow (g_j)^i \in T_{a^k},T_{b^k} \end{eqnarray*}$ , s. Definition der Teilermengen von a^k und b^k oben). Die größte dieser Zahlen ist $\begin{eqnarray*} (g_n)^k = ggT(a,b)^k \end{eqnarray*}$ .

01.06.2012, 17:05

HAL 9000

Auf diesen Beitrag antworten »

Die Behauptung $\begin{eqnarray*} \operatorname{ggT}(a^k,b^k) = (\operatorname{ggT}(a,b))^k \end{eqnarray*}$ ist richtig, dein Beweis leider nicht.

Die Probleme beginnen bereits beim Start:

Zitat:

Original von Benutzername123
$\begin{eqnarray*} T_{a^k} = \{x^i | x \in T_a \wedge i \in [1,k] \cap \mathbb N\} \end{eqnarray*}$

Das ist i.a. falsch - Gegenbeispiel:

$\begin{eqnarray*} a=6,k=2 \end{eqnarray*}$ , dann sagst du mit dieser Formel

$\begin{eqnarray*} T_{6^2} \stackrel{?}{=} \{ 1,2,3,6,4,9,36 \} \end{eqnarray*}$ ,

tatsächlich ist aber

$\begin{eqnarray*} T_{36} = \{ 1,2,3,4,6,9,12,18,36 \} \end{eqnarray*}$ ,

d.h. so vergisst so einige Teiler.

Alternative: Mit $\begin{eqnarray*} g:=\operatorname{ggT}(a,b) \end{eqnarray*}$ folgt, dass es teilerfremde Zahlen $\begin{eqnarray*} c,d \end{eqnarray*}$ mit $\begin{eqnarray*} a=cg,b=dg \end{eqnarray*}$ gibt. Mit denen folgt dann

$\begin{eqnarray*} \operatorname{ggT}(a^k,b^k) = \operatorname{ggT}(c^kg^k,d^kg^k) = g^k \cdot \operatorname{ggT}(c^k,d^k) \end{eqnarray*}$ ,

und wie geht's wohl weiter...

01.06.2012, 17:07

Mystic

Auf diesen Beitrag antworten »

RE: Größter gemeinsamer Teiler zweier Potenzen
Betrachtet man auf der Menge $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ die binären Operationen der Multiplikation und der Bildung des ggT, so ist die Multiplikation distributiv gegenüber dem ggT, d.h.,

$\begin{eqnarray*} c \cdot ggT(a,b) =ggT(ca,cb) \quad \forall a,b \in \mathbb N \end{eqnarray*}$

Das steckt hier dahinter und das gilt es zu beweisen...

Edit: Meine Antwort bezog sich dabei auf den Threadersteller, die von HAL hatte ich noch nicht gesehen...

01.06.2012, 17:20

Benutzername123

Auf diesen Beitrag antworten »

Zitat:

und wie geht's wohl weiter...

hm, weil $\begin{eqnarray*} c \end{eqnarray*}$ und $\begin{eqnarray*} d \end{eqnarray*}$ teilerfremd sind, sind $\begin{eqnarray*} c^k \end{eqnarray*}$ und $\begin{eqnarray*} d^k \end{eqnarray*}$ teilerfremd. Also $\begin{eqnarray*} ggT(c^k, d^k) = 1 \end{eqnarray*}$ , woraus $\begin{eqnarray*} g^k \cdot ggT(c^k, d^k) = g^k = (ggT(a,b))^k \end{eqnarray*}$ folgt.
Allerdings muss ich doch auch noch beweisen, dass $\begin{eqnarray*} c^k \end{eqnarray*}$ und $\begin{eqnarray*} d^k \end{eqnarray*}$ teilerfremd sind (was im Grunde genommen das Beweisen eines Spezialfalls der ursprünglichen Aussage ist..)....

01.06.2012, 17:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Benutzername123
was im Grunde genommen das Beweisen eines Spezialfalls der ursprünglichen Aussage ist..

Ja, aber ein sehr einfacher Spezialfall. Augenzwinkern

01.06.2012, 18:03

Benutzername123

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Benutzername123
was im Grunde genommen das Beweisen eines Spezialfalls der ursprünglichen Aussage ist..

Ja, aber ein sehr einfacher Spezialfall. Augenzwinkern

Sind $\begin{eqnarray*} c \end{eqnarray*}$ und $\begin{eqnarray*} d \end{eqnarray*}$ teilerfremd, so besitzen sie keine gemeinsamen Primfaktoren. Sind $\begin{eqnarray*} p_1, p_2, ..., p_m \end{eqnarray*}$ die Primfaktoren von $\begin{eqnarray*} c \end{eqnarray*}$ und $\begin{eqnarray*} q_1, q_2, ..., q_n \end{eqnarray*}$ jene von $\begin{eqnarray*} d \end{eqnarray*}$ , dann ist $\begin{eqnarray*} c = (p_1)^k \cdot ... \cdot (p_m)^k \end{eqnarray*}$ (keine Ahnung, wie man hier ein Produktzeichen herbeizaubert) und $\begin{eqnarray*} d^k = (q_1)^k \cdot ... (q_n)^k \end{eqnarray*}$ .
Da $\begin{eqnarray*} p_x \neq q_y \end{eqnarray*}$ für alle $\begin{eqnarray*} x,y \in \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} 1 \leq x \leq m \end{eqnarray*}$ , $\begin{eqnarray*} 1 \leq y \leq n \end{eqnarray*}$ gilt $\begin{eqnarray*} (p_x)^k \neq (q_y)^k \end{eqnarray*}$ . Somit besitzen $\begin{eqnarray*} c^k \end{eqnarray*}$ und $\begin{eqnarray*} d^k \end{eqnarray*}$ keine gemeinsamen Primfaktoren. Also sind sie teilerfremd.

01.06.2012, 18:06

Benutzername123

Auf diesen Beitrag antworten »

Zitat:

Original von Benutzername123

$\begin{eqnarray*} c = (p_1)^k \cdot ... \cdot (p_m)^k \end{eqnarray*}$ (keine Ahnung, wie man hier ein Produktzeichen herbeizaubert)

Gemeint ist natürlich
$\begin{eqnarray*} c^k = (p_1)^k \cdot ... \cdot (p_m)^k \end{eqnarray*}$

01.06.2012, 18:06

HAL 9000

Auf diesen Beitrag antworten »

Genau.

Man könnte es auch als indirekten Beweis formulieren: Angenommen, es gäbe eine Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ mit $\begin{eqnarray*} p \mid \operatorname{ggT}(c^k,d^k) \end{eqnarray*}$ , dann ...

01.06.2012, 18:19

Benutzername123

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Genau. Freude

... dann folgt daraus, dass $\begin{eqnarray*} p \end{eqnarray*}$ Primfaktor von $\begin{eqnarray*} c^k \end{eqnarray*}$ und $\begin{eqnarray*} d^k \end{eqnarray*}$ ist. Folglich ist es auch Primfaktor von $\begin{eqnarray*} c \end{eqnarray*}$ und $\begin{eqnarray*} d \end{eqnarray*}$ . Widerspruch zur Teilerfremdheit von $\begin{eqnarray*} c \end{eqnarray*}$ und $\begin{eqnarray*} d \end{eqnarray*}$ .

01.06.2012, 18:21

HAL 9000

Auf diesen Beitrag antworten »

Genau.

01.06.2012, 18:24

Benutzername123

Auf diesen Beitrag antworten »

Dann bleibt mir nichts weiter zu sagen, als mich für die Hilfe zu bedanken Augenzwinkern

(hm, komisch, dass dieses Thema in den Hochschulmathematik-Bereich verschoben wurde, bin ich doch nur ein Mittelstufenschüler, der aus Langeweile einen Beweis für die Aussage im ersten Beitrag suchte und das Thema im Bereich "Schulmathematik - Sonstiges" eröffnete... naja, egal)

Neue Frage »

Antworten »

Größter gemeinsamer Teiler zweier Potenzen

Verwandte Themen