modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | ggt(a,m) =1 [mm] \gdw [/mm] es existiert ein [mm] x\in \IZ [/mm] : [mm] \overline{a}*\overline{x}= \overline{1} [/mm] in [mm] \IZ/m [/mm] |
Hallo,
ich hab da wieder so ein Problemchen. Meiner Meinung müsste doch die Idealdarstellung helfen können, oder hat jemand nen besseren Rat? Wär echt super enn mir jemand nen kleinen Ansatz geben könnte. Vieln Dank im Voraus!
Gruß, KommissarLachs
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:04 Mo 25.06.2007 | | Autor: | felixf |
Hallo!
> ggt(a,m) =1 [mm]\gdw[/mm] es existiert ein [mm]x\in \IZ[/mm] :
> [mm]\overline{a}*\overline{x}= \overline{1}[/mm] in [mm]\IZ/m[/mm]
>
> Hallo,
>
> ich hab da wieder so ein Problemchen. Meiner Meinung müsste
> doch die Idealdarstellung helfen können, oder hat jemand
> nen besseren Rat?
Wenn ihr hattet, dass das Ideal, was von $a, b [mm] \in \IZ$ [/mm] erzeugt wird, gleich dem Ideal ist, das von $ggT(a, b)$ erzeugt wird, dann ja. Ansonsten eher nicht.
> Wär echt super enn mir jemand nen kleinen
> Ansatz geben könnte. Vieln Dank im Voraus!
Weisst du, dass in dem Fall, dass $ggT(a, b) = d$ ist, es $x, y [mm] \in \IZ$ [/mm] gibt mit $d = x a + y b$? Damit bekommst du die Richtung [mm] ``$\Rightarrow$'' [/mm] hin.
Fuer die Rueckrichtung beachtest du: gibt es $x, y [mm] \in \IZ$ [/mm] mit $1 = a x + b y$, so ist $ggT(a, b) = 1$. (Dazu nimmst du dir einen gemeinsamen Teiler von $a$ und $b$ und zeigst, dass er auch $1$ teilt.)
Und dann musst du dich noch fragen, was die Existenz solcher $x, y [mm] \in \IZ$ [/mm] zu tun hat mit [mm] $\exists [/mm] x [mm] \in \IZ [/mm] : [mm] \overline{a} \overline{x} [/mm] = [mm] \overline{1} \in \IZ/m\IZ$. [/mm] (Tipp: $b = m$.)
LG Felix
|
|
|
| |
|
Hallo,
besten Dank erstmal für die Hilfe. Allerdings weiß ich trotzdem nicht was ich damit anfangen soll bzw kann. Den angesprochenen Satz hatten wir, auch den Satz dass der ggt von allen anderen gemeinsamen Teilern geteilt wird. Wie soll ich die denn jetzt darauf anwenden? Darf ich bei der ,,=>" Richtung schon darauf zurückgreifen, dass es sich um [mm] \IZ/m [/mm] handelt?
Sorry für diese Fragenflut!
Gruß, KommissarLachs
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:14 Mi 27.06.2007 | | Autor: | wauwau |
Also der Euklidische Algorithmus besagt ja, dass
[mm] ggt(a,m)=x_1*a+x_2*m [/mm] also eine LInearkombination von a und m ist, dass es also solche [mm] x_1 [/mm] und [mm] x_2 [/mm] gibt
ist ggt(a,m)=1 so gibt es [mm] x_1 [/mm] und [mm] x_2 [/mm] sodass
1= [mm] x_1*a+x_2*m [/mm]
Diese Gleichung modulo m genommen ergibt die Existenz eins [mm] x_1 [/mm] sodass [mm] x_1*a \equiv [/mm] 1 mod m ist
|
|
|
| |
|
Hallo,
ich glaub die => Richtung hab ich verstanden:
ggt(a,m)=1 => es existieren [mm] x_{1},x_{2} [/mm] mit [mm] x_{a}a +x_{2}m=1. [/mm] Division mit Rest durch m ergibt: [mm] x_{1}\equiv [/mm] 1 mod m. Das bedeutet [mm] \overline{x_{1}a}=\overline{1}.
[/mm]
Für die <= Richtung habe ich aber noch nicht genau verstanden worauf ihr hinaus wollt. Sorry. Wär super, wenn ihr mir da noch mal helfen würdet. Viel Dank!
Gruß, KommissarLachs
|
|
|
| |
|
> Hallo,
>
> ich glaub die => Richtung hab ich verstanden:
> ggt(a,m)=1 => es existieren [mm]x_{1},x_{2}[/mm] mit [mm]x_{a}a +x_{2}m=1.[/mm]
> Division mit Rest durch m ergibt: [mm]x_{1}\equiv[/mm] 1 mod m. Das
> bedeutet [mm]\overline{x_{1}a}=\overline{1}.[/mm]
>
> Für die <= Richtung habe ich aber noch nicht genau
> verstanden worauf ihr hinaus wollt.
Du kannst die Voraussetzung, dass [mm]\overline{a}\cdot \overline{x}=\overline{1}[/mm] in [mm]\IZ/m[/mm] auch so formulieren: es gibt [mm]k_a,k_x, k\in \IZ[/mm] mit [mm](a+k_a\cdot m)\cdot (x+k_x\cdot m)=1+k\cdot m[/mm], was nichts anderes besagt als [mm]x\cdot a + (\ldots)\cdot m = 1[/mm], wobei [mm]x,(\ldots)\in\IZ[/mm]. Was wiederum besagt, dass [mm]ggT(a,m)= 1[/mm]
|
|
|
|
