Teilbarkeitsregel bei ggT

11.08.2022, 12:09

KonverDiv

Teilbarkeitsregel bei ggT

Hallo,

in einem Beweis von $\begin{eqnarray*} a^b \equiv 1 \text{ (mod } m) \end{eqnarray*}$ wird behauptet, dass es hierbei ausreicht, dass der $\begin{eqnarray*} \text{ggT}(a,m)=1 \end{eqnarray*}$ ist.

Hierfür wird $\begin{eqnarray*} d = \text{ggT}(a,m) \end{eqnarray*}$ gesetzt und gesagt, dass wenn $\begin{eqnarray*} d|a \end{eqnarray*}$ und $\begin{eqnarray*} d|m \end{eqnarray*}$ dann ist $\begin{eqnarray*} d|1 \end{eqnarray*}$ und damit $\begin{eqnarray*} d=1 \end{eqnarray*}$ .

Meine Frage ist, mit welcher Teilbarkeitsregel kann man denn aus $\begin{eqnarray*} d|a \end{eqnarray*}$ und $\begin{eqnarray*} d|m \end{eqnarray*}$ das hier folgern: $\begin{eqnarray*} d|1 \end{eqnarray*}$

11.08.2022, 12:49

IfindU

Auf diesen Beitrag antworten »

RE: Teilbarkeitsregel bei ggT
Bist du sicher, dass das so geschrieben ist und keine Anforderung ist? Denn $\begin{eqnarray*} m^b \equiv 0 (\bmod m) \end{eqnarray*}$ für alle $\begin{eqnarray*} b > 0 \end{eqnarray*}$ . D.h. die Aussage gilt nicht, wenn $\begin{eqnarray*} a,m \end{eqnarray*}$ zu viel gemeinsam haben.

11.08.2022, 12:52

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} d\mid a \end{eqnarray*}$ und $\begin{eqnarray*} d\mid m \end{eqnarray*}$ bedeutet nichts anderes als dass $\begin{eqnarray*} d \end{eqnarray*}$ ein gemeinsamer Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ ist. Jeder gemeinsame Teiler ist nun aber ein Teiler des größten gemeinsamen Teilers dieser Zahlen, es gilt also allgemein

$\begin{eqnarray*} d\mid a\,\wedge\,d\mid m\; \Longrightarrow\; d\mid\operatorname{ggT}(a,m) \end{eqnarray*}$ .

Das gilt insbesondere auch im Fall $\begin{eqnarray*} \operatorname{ggT}(a,m)=1 \end{eqnarray*}$ .

11.08.2022, 12:55

KonverDiv

Auf diesen Beitrag antworten »

RE: Teilbarkeitsregel bei ggT
Hallo @IfindU,

hier einmal ein Auszug:

[attach]55737[/attach]

Hallo @HAL 9000,

Zitat:

Jeder gemeinsame Teiler ist nun aber ein Teiler des größten gemeinsamen Teilers dieser Zahlen

Das macht es klarer!

11.08.2022, 12:56

HAL 9000

Auf diesen Beitrag antworten »

"for some integer $\begin{eqnarray*} b \end{eqnarray*}$ " ist natürlich die entscheidende Formulierung, über die du oben großzügig hinweggegangen bist. Augenzwinkern

11.08.2022, 13:01

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
"for some integer $\begin{eqnarray*} b \end{eqnarray*}$ " ist natürlich die entscheidende Formulierung, über die du oben großzügig hinweggegangen bist. Augenzwinkern

Mein Fehler. Augenzwinkern

11.08.2022, 13:02

IfindU

Auf diesen Beitrag antworten »

Das klingt so als ob man allgemeine Gruppentheorie verwendet. D.h. $\begin{eqnarray*} a \end{eqnarray*}$ ist invertierbar in Restklassenring $\begin{eqnarray*} Z_m \end{eqnarray*}$ , genau dann wenn $\begin{eqnarray*} ggT(a,m) = 1 \end{eqnarray*}$ ist. Die Aussage oben ist ja einfach $\begin{eqnarray*} a^{b-1} \end{eqnarray*}$ ist das multiplikative Inverse von $\begin{eqnarray*} a \end{eqnarray*}$ . Insb. ist $\begin{eqnarray*} a \end{eqnarray*}$ invertierbar.

Es ist aber auch seltsam geschrieben...

11.08.2022, 13:06

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Es ist aber auch seltsam geschrieben...

Ja, das finde ich auch. HALs Antwort lässt da jetzt keine weitere Interpretation des Textes zu, so wie HAL es formuliert, ist es klar!

11.08.2022, 13:22

IfindU

Auf diesen Beitrag antworten »

Ich muss sagen ich verstehs nicht. Wir sagen $\begin{eqnarray*} d = ggT(a,m) \end{eqnarray*}$ . Dann folgt natürlich $\begin{eqnarray*} d | a \end{eqnarray*}$ und $\begin{eqnarray*} d | m \end{eqnarray*}$ . Aber im Allgemeinen folgt daraus nicht $\begin{eqnarray*} d |1 \end{eqnarray*}$ , sondern eben genau wenn $\begin{eqnarray*} d = ggT(a,m) = 1 \end{eqnarray*}$ , es wirkt zirkelschlüssig...

Oder meinen die $\begin{eqnarray*} d = ggT(a,m) \end{eqnarray*}$ . Falls $\begin{eqnarray*} e | a \end{eqnarray*}$ und $\begin{eqnarray*} e | m \end{eqnarray*}$ , folgt daraus (wegen einer nicht genauer spezifizierten Begründung) $\begin{eqnarray*} e|1 \end{eqnarray*}$ und damit $\begin{eqnarray*} e = 1 \end{eqnarray*}$ und damit $\begin{eqnarray*} d = 1 \end{eqnarray*}$ , weil $\begin{eqnarray*} d \end{eqnarray*}$ auch ein Teiler ist? Super schlecht geschrieben...

11.08.2022, 13:39

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Ich muss sagen ich verstehs nicht. Wir sagen $\begin{eqnarray*} d = ggT(a,m) \end{eqnarray*}$ . Dann folgt natürlich $\begin{eqnarray*} d | a \end{eqnarray*}$ und $\begin{eqnarray*} d | m \end{eqnarray*}$ . Aber im Allgemeinen folgt daraus nicht $\begin{eqnarray*} d |1 \end{eqnarray*}$ , sondern eben genau wenn $\begin{eqnarray*} d = ggT(a,m) = 1 \end{eqnarray*}$ , es wirkt zirkelschlüssig...

Mir ist auch keine Teilbarkeitsregel bekannt, nach der aus $\begin{eqnarray*} d | a \end{eqnarray*}$ und $\begin{eqnarray*} d | m \Longrightarrow d |1 \end{eqnarray*}$ folgt.

Aber im Kontext macht es Sinn:

Ich verstehe es so, weil $\begin{eqnarray*} d \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ ist und gleichzeitig $\begin{eqnarray*} d \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} m \end{eqnarray*}$ , ist auch $\begin{eqnarray*} d \end{eqnarray*}$ ein Teiler des größten gemeinsamen Teilers.

11.08.2022, 13:45

IfindU

Auf diesen Beitrag antworten »

Genau, das ist die allgemeine Definition des $\begin{eqnarray*} ggT \end{eqnarray*}$ .
$\begin{eqnarray*} d \end{eqnarray*}$ ist ggT von $\begin{eqnarray*} a,m \end{eqnarray*}$ wenn
a) $\begin{eqnarray*} d| a \end{eqnarray*}$ und $\begin{eqnarray*} d|m \end{eqnarray*}$ , d.h. es ist ein Teiler.
b) Für jeden weiteren Teiler $\begin{eqnarray*} d' \end{eqnarray*}$ mit $\begin{eqnarray*} d'| a \end{eqnarray*}$ und $\begin{eqnarray*} d'|m \end{eqnarray*}$ gilt $\begin{eqnarray*} d'| d \end{eqnarray*}$ . D.h. es ist der größte.

Wie dem auch sei, die Aussage ist "richtig", ob der Beweis so stimmt, ist nebensächlich Augenzwinkern

Neue Frage »

Antworten »

Teilbarkeitsregel bei ggT

Verwandte Themen