Multiplikative Inverse < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:44 Fr 01.03.2013 | | Autor: | Jack159 |
Hallo,
Wir haben in der Vorlesung festgehalten, dass es nicht zu jeder modularen Arithmetik eine multiplikative Inverse x^-1 zu x gibt.
Der Satz von Lemma von Bézout besagt nun:
[mm] \operatorname{ggT}(a,b) [/mm] = s [mm] \cdot [/mm] a + t [mm] \cdot [/mm] b mit [mm] s,t\in\mathbb{Z}.
[/mm]
Sind a und b teilerfremd, dann existieren [mm] s,t\in\mathbb{Z}, [/mm] sodass
1 = s [mm] \cdot [/mm] a + t [mm] \cdot [/mm] b
Der zweite Teil dieses Satzes ist klar. Damit könnte man nun mithilfe des erw. eukl. Alg. z.B. die multiplikative Inverse b^-1 von b mod a berechnen, sodass b*b^-1 [mm] \equiv [/mm] 1 mod a gilt oder umgekehrt könnte man auch die multiplikative Inverse a^-1 von a mod b berechnen, sodass a*a^-1 [mm] \equiv [/mm] 1 mod b gilt.
Meine Frage zielt eher auf den Fall ab, falls a und b nicht teilerfremd sind.
Beispiel:
ggT(125, 110)=5
Der Erw. Eukl. Alg. liefert:
8*110-7*125=5
Ich kann doch dann folgendes schreiben:
8*110 [mm] \equiv [/mm] mod 5
Dann wäre doch 8 die multiplikative Inverse von 110 in [mm] \IZ_{5}, [/mm] oder nicht?
Oder existiert die multiplikative Inverse grundsätzlich nur, falls ggT(a.b)=1 ist?
|
|
| |
|
Hallo Jack,
da ist irgendetwas kraus, sei es Deine Formulierung oder die Überlegung dahinter.
> Wir haben in der Vorlesung festgehalten, dass es nicht zu
> jeder modularen Arithmetik eine multiplikative Inverse x^-1
> zu x gibt.
>
>
> Der Satz von Lemma von Bézout besagt nun:
Was denn jetzt, Satz oder Lemma? 
> [mm]\operatorname{ggT}(a,b)[/mm] = s [mm]\cdot[/mm] a + t [mm]\cdot[/mm] b mit
> [mm]s,t\in\mathbb{Z}.[/mm]
>
> Sind a und b teilerfremd, dann existieren [mm]s,t\in\mathbb{Z},[/mm]
> sodass
>
> 1 = s [mm]\cdot[/mm] a + t [mm]\cdot[/mm] b
>
>
>
> Der zweite Teil dieses Satzes ist klar. Damit könnte man
> nun mithilfe des erw. eukl. Alg. z.B. die multiplikative
> Inverse b^-1 von b mod a berechnen, sodass b*b^-1 [mm]\equiv[/mm] 1
> mod a gilt oder umgekehrt könnte man auch die
> multiplikative Inverse a^-1 von a mod b berechnen, sodass
> a*a^-1 [mm]\equiv[/mm] 1 mod b gilt.
>
> Meine Frage zielt eher auf den Fall ab, falls a und b nicht
> teilerfremd sind.
>
> Beispiel:
>
> ggT(125, 110)=5
>
> Der Erw. Eukl. Alg. liefert:
>
> 8*110-7*125=5
>
> Ich kann doch dann folgendes schreiben:
>
> 8*110 [mm]\equiv[/mm] mod 5
Da fehlt doch was. Rechts des Äquivalenzzeichens nämlich. Da müsste eine Null stehen.
> Dann wäre doch 8 die multiplikative Inverse von 110 in
> [mm]\IZ_{5},[/mm] oder nicht?
Nein, dazu müsste ja gelten [mm] 8*110\equiv 1\mod{5}.
[/mm]
Das ist aber falsch.
> Oder existiert die multiplikative Inverse grundsätzlich
> nur, falls ggT(a.b)=1 ist?
Hier ist die krause Frage. Sie ist zu ungenau.
In der Tat existiert ein multiplikatives Inverses zu [mm] a\mod{b} [/mm] nur dann, wenn [mm] \ggT{(a,b)}=1 [/mm] ist; entsprechend für [mm] b\mod{a}.
[/mm]
Das Lemma von Bézout besagt das Folgende zwar nicht, aber das solltest Du leicht herleiten können:
Ist [mm] \ggt{(a,b)}\not=1, [/mm] so hat $1=s*a+t*b$ mit [mm] s,t\in\IZ [/mm] keine Lösung.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:55 Fr 01.03.2013 | | Autor: | Jack159 |
> > Ich kann doch dann folgendes schreiben:
> >
> > 8*110 [mm]\equiv[/mm] mod 5
>
> Da fehlt doch was. Rechts des Äquivalenzzeichens nämlich.
> Da müsste eine Null stehen.
>
Du hast recht, habe ich übersehen.
> > Dann wäre doch 8 die multiplikative Inverse von 110 in
> > [mm]\IZ_{5},[/mm] oder nicht?
>
> Nein, dazu müsste ja gelten [mm]8*110\equiv 1\mod{5}.[/mm]
> Das ist
> aber falsch.
>
> > Oder existiert die multiplikative Inverse grundsätzlich
> > nur, falls ggT(a.b)=1 ist?
>
> Hier ist die krause Frage. Sie ist zu ungenau.
> In der Tat existiert ein multiplikatives Inverses zu
> [mm]a\mod{b}[/mm] nur dann, wenn [mm]\ggT{(a,b)}=1[/mm] ist; entsprechend
> für [mm]b\mod{a}.[/mm]
Gut, so meinte ich das auch, habe mich nur zu grob ausgedrückt ;)
Dann ist alles klar, danke dir!
|
|
|
|
![[]](/images/popup.gif){kind=small}
Emma von Schwarz-Pick