Euklidischer Algo - Restklasse < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:16 Sa 25.10.2008 | | Autor: | kittycat |
| Aufgabe | (a) Aus dem erweiterten Euklidischen Algorithmus folgt, dass für zwei Zahlen a, b [mm] \in \IZ [/mm] gilt:
[mm] \exists [/mm] c, d [mm] \in \IZ [/mm] mit ggT(a,b)=ca+db.
Folgern Sie daraus
[mm] (\IZ/m\IZ)\*={[a] | 0 < a < m , ggT(a,m)=1}.
[/mm]
(b) Listen Sie in den beiden Fällen m=15 und m=28 jeweils die Elemente von [mm] (\IZ/m\IZ)\* [/mm] und ihre Inversen auf. |
Hallo liebe Mathefreunde,
Ich habe mir dazu mal das folgende Beispiel angeschaut:
[mm] (\IZ/9\IZ)\*={[1],[2],[4],[5],[7].[8]}
[/mm]
Das heißt ja dann, dass [mm] (\IZ/m\IZ)\* [/mm] aus allen Elementen besteht, die mit m teilerfremd sind, also hat [a] keinen gemeinsamen Teiler mit m (so wie es ja auch schon in der Aufgabe steht  )
Aber wie kann ich das aus dem erweiterten Euklidischen Algorithmus folgern?
Wäre über jeden Hinweis sehr dankbar.
Lg Kittycat
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:11 Sa 25.10.2008 | | Autor: | Fry |
Hallo !
Der Beweis:
[Dateianhang nicht öffentlich]
Gruß
Christian
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:48 So 26.10.2008 | | Autor: | Riley |
Hallo,
ich hab mir diese Aufgabe mal für ein Beispiel angeschaut, aber noch Fragen dazu.
z.B. m=6, dann ist [mm] (\mathbb{Z}/6 \mathbb{Z}) [/mm] = [mm] \{ [1],[2],[3],[4],[5] \} [/mm] und [mm] (\mathbb{Z}/6 \mathbb{Z})^\* [/mm] = [mm] \{[1]\}
[/mm]
m=15:
[mm] (\mathbb{Z}/15 \mathbb{Z}) [/mm] = [mm] \{ [1],[2],[3],[4],...,[14] \}
[/mm]
[mm] (\mathbb{Z}/6 \mathbb{Z})^\* [/mm] = [mm] \{ [1],[2],[4],[7],[8],[13] \}
[/mm]
Aber laut der Behauptung sind ja alle [a] drin, mit ggT(a,m) = 1, d.h. [7] und [14] müssten auch in der Einheitenmenge sein? Ich hab aber kein b gefunden, so dass 7 b = 1 bzw 14b = 1 ???
Und den Beweis von fry versteh ich noch nicht ganz. Bedeutet a + n [mm] \mathbb{Z} [/mm] darin, das gleiche wie [a] ?
Kann man das nicht vielleicht auch direkter zeigen?
Also wir haben
[mm] (\mathbb{Z}/m \mathbb{Z}) [/mm] = [mm] \{ a \in (\mathbb{Z}/m \mathbb{Z}) | \exists b \in (\mathbb{Z}/m \mathbb{Z}) \quad \mbox{mit} \quad a \cdot b = 1 \} [/mm] nach Definition und das soll äquivalent sein zu der Menge
[mm] \{ [a] | 0 < a < m, ggT(a,m) = 1 \}.
[/mm]
Aus dem erweiterten euklidischen ALGO wissen wir noch, dass für zwei Zahlen a,b [mm] \in \mathbb{Z} [/mm] gilt, dass es dann auch c,d [mm] \in \mathbb{Z} [/mm] gibt, so dass ggT(a,b) = ca + db.
Hat vielleicht jemand einen Hinweis, wie man die Beh. damit nun selbst zeigen kann ?? Das wäre super
Viele Grüße,
Riley
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:49 Di 28.10.2008 | | Autor: | kittycat |
Hallo Riley,
also ich habe für m=15 folgende Elemente raus:
{[1],[2],[4],[7],[8],[11],[13],[14]} und die Inversen in der selben Reihenfolge dazu {[1],[8],[4],[13],[2],[11],[7],[14]}
Hoffe das stimmt so
Lg Kittycat
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:51 Di 28.10.2008 | | Autor: | kittycat |
Hallo liebe Mathefreund,
hallo Fry!
Irgendwie verstehe ich deinen Ansatz noch nicht so richtig. Ich muss doch die Folgerung zeigen ???
Wie auch Riley hab ich Probleme das (a+mIZ) richtig einzuordnen :-(
Kann uns noch jemand einen Tipp geben wie man diese Aufgabe theoretisch lösen kann ... also dass das gilt ist mir ja irgendwie klar,
Lg Kittycat
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:09 Di 28.10.2008 | | Autor: | andreas |
hallo
> Irgendwie verstehe ich deinen Ansatz noch nicht so richtig.
> Ich muss doch die Folgerung zeigen ???
> Wie auch Riley hab ich Probleme das (a+mIZ) richtig
> einzuordnen :-(
es ist $[a] = a + [mm] m\mathbb{Z}$, [/mm] nur eine andere schreibweise.
> Kann uns noch jemand einen Tipp geben wie man diese Aufgabe
> theoretisch lösen kann ... also dass das gilt ist mir ja
> irgendwie klar,
was ist denn an dem von Fry angegebenen beweis unklar? was habt ihr euch bisher für gedanken gemacht? falls [mm] $\textrm{ggT}(a, [/mm] m) = 1$, so erhält man mit dem erweiterten euklidischen algorithmus $c, d [mm] \in \mathbb{Z}$ [/mm] mit $ca + dm = 1$. was ergibt diese gleichung modulo $m$?
grüße
andreas
|
|
|
|
