Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Prime Restklassengruppe
Autor
Universität/Hochschule J Prime Restklassengruppe
OliverFuchs
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2020
Mitteilungen: 162
Wohnort: Wien, Österreich
  Themenstart: 2021-09-15

\(\begingroup\)\(\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\bs}{\backslash} \newcommand{\ga}{\gamma} \newcommand{\de}{\delta} \newcommand{\ep}{\varepsilon} \newcommand{\ze}{\zeta} \newcommand{\et}{\eta} \newcommand{\io}{\iota} \newcommand{\ka}{\kappa} \newcommand{\la}{\lambda} \newcommand{\rh}{\rho} \newcommand{\si}{\sigma} \newcommand{\ta}{\tau} \newcommand{\ph}{\varphi} \newcommand{\ch}{\chi} \newcommand{\ps}{\psi} \newcommand{\om}{\omega} \newcommand{\Ga}{\Gamma} \newcommand{\De}{\Delta} \newcommand{\Th}{\Theta} \newcommand{\La}{\Lambda} \newcommand{\Si}{\Sigma} \newcommand{\Ph}{\Phi} \newcommand{\Ps}{\Psi} \newcommand{\Om}{\Omega} \newcommand{\NN}{\mathbb N} \newcommand{\ZZ}{\mathbb Z} \newcommand{\QQ}{\mathbb Q} \newcommand{\RR}{\mathbb R} \newcommand{\CC}{\mathbb C} \newcommand{\HH}{\mathbb H} \newcommand{\DD}{\mathbb D} \newcommand{\TT}{\mathbb T} \newcommand{\KK}{{\mathbb K}} \newcommand{\oo}{{\infty}} \newcommand{\PP}{\mathbb P} \newcommand{\BB}{\mathbb B} \newcommand{\MM}{\mathbb M} \newcommand{\alt}{\operatorname{alt}} \newcommand{\dom}{\operatorname{Dom}} \newcommand{\ceil}{\operatorname{ceil}} \newcommand{\Diff}{\operatorname{Diff}} \newcommand{\ev}{\operatorname{ev}} \newcommand{\floor}{\operatorname{floor}} \newcommand{\ggT}{\operatorname{ggT}} \newcommand{\grad}{\operatorname{grad}} \newcommand{\graph}{\operatorname{Graph}} \newcommand{\im}{\operatorname{Im}} \newcommand{\id}{\operatorname{id}} \newcommand{\incl}{\operatorname{incl}} \newcommand{\kgV}{\operatorname{kgV}} \newcommand{\li}{\operatorname{li}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\ptp}{\operatorname{ptp}} \newcommand{\rang}{\operatorname{rang}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\sym}{\operatorname{sym}} \newcommand{\trg}{\operatorname{Trg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\card}{\operatorname{card}} \newcommand{\R}{\Rightarrow} \newcommand{\L}{\Leftarrow} \newcommand{\gdw}{\Leftrightarrow} \) Hallo, Professor Summerer weist darauf hin, dass die Kongruenz $ax\equiv 1(\mod m)$ genau dann lösbar ist, wenn $\ggT(a,m)=1$ ist. Dann meint er, dass man diese Kongruenz auch als Gleichung $\overline{a}\overline{x}=\overline{1}$ in $\ZZ_m$ interpretieren kann. Dann bedeutet diese Gleichung, dass $\overline{a}$ in $\ZZ_m$ multiplikativ invertierbar ist und $\overline{a}$ das inverse Element ist. So weit so klar. Dann definiert er, dass wenn $R$ ein kommutativer Ring mit Eins ist so soll $R*$ die Menge der invertierbaren Elemente in $R$ sein. Anschließend wird der Satz bewiesen, dass $(R*,\cdot)$ eine kommutative Gruppe ist. So weit so gut. Nun schließe ich selber. Nun habe ich in der Vorlesung einen anderen Zugang zu $\ZZ_m$ kennen gelernt. Man kann diese Menge als die Menge der Äquivalenzklassen bezüglich der Kongruenzrelation $ \equiv (\mod m)$ sehen. Nun war mir aber die Schreibweise $a+m\ZZ=\overline{a}$ neu. Nach dem was bisher gesagt wurde ist mir aber klar, dass $\ZZ_m^*=\{\overline{a}:\ggT(a,m)=1\}=\{a+m\ZZ:\ggT(a,m)=1\}$ ist. Nun meint Prof. Summerer dass, wegen $\ggT(a+km)=\ggT(a,m)$ folgt $\ZZ_m^*=\{a+m\ZZ\vert \ggT(a,m)=1\}$. Mir ist nun nicht klar, warum es notwendig ist, $\ggT(a+km)=\ggT(a,m)$ zu zeigen? Danke. lg Oliver 🙂 \(\endgroup\)


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7272
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2021-09-15

\quoteon(2021-09-15 15:13 - OliverFuchs im Themenstart) Mir ist nun nicht klar, warum es notwendig ist, $\ggT(a+km)=\ggT(a,m)$ zu zeigen? \quoteoff Warum soll das denn auch gelten?


   Profil
OliverFuchs
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2020
Mitteilungen: 162
Wohnort: Wien, Österreich
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-16

Hallo, Das gilt aber. Ich konnte es zeigen. LG Oliver 🙂


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7272
Wohnort: Milchstraße
  Beitrag No.3, eingetragen 2021-09-16

\quoteon(2021-09-16 00:50 - OliverFuchs in Beitrag No. 2) Das gilt aber. Ich konnte es zeigen. \quoteoff Ich sehe jetzt erst, dass dein Prof. oder du sich verschrieben hat und eigentlich $ggT(a+km,m)=ggT(a,m)$ meint. Da der ggT üblicherweis zwei Argumente hat, hatte ich intuitiv $ggT(a,km)=ggT(a,m)$ gelesen. Siehe auch hier: https://matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=255495&post_id=1855755


   Profil
OliverFuchs
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2020
Mitteilungen: 162
Wohnort: Wien, Österreich
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-16

\(\begingroup\)\(\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\bs}{\backslash} \newcommand{\ga}{\gamma} \newcommand{\de}{\delta} \newcommand{\ep}{\varepsilon} \newcommand{\ze}{\zeta} \newcommand{\et}{\eta} \newcommand{\io}{\iota} \newcommand{\ka}{\kappa} \newcommand{\la}{\lambda} \newcommand{\rh}{\rho} \newcommand{\si}{\sigma} \newcommand{\ta}{\tau} \newcommand{\ph}{\varphi} \newcommand{\ch}{\chi} \newcommand{\ps}{\psi} \newcommand{\om}{\omega} \newcommand{\Ga}{\Gamma} \newcommand{\De}{\Delta} \newcommand{\Th}{\Theta} \newcommand{\La}{\Lambda} \newcommand{\Si}{\Sigma} \newcommand{\Ph}{\Phi} \newcommand{\Ps}{\Psi} \newcommand{\Om}{\Omega} \newcommand{\NN}{\mathbb N} \newcommand{\ZZ}{\mathbb Z} \newcommand{\QQ}{\mathbb Q} \newcommand{\RR}{\mathbb R} \newcommand{\CC}{\mathbb C} \newcommand{\HH}{\mathbb H} \newcommand{\DD}{\mathbb D} \newcommand{\TT}{\mathbb T} \newcommand{\KK}{{\mathbb K}} \newcommand{\oo}{{\infty}} \newcommand{\PP}{\mathbb P} \newcommand{\BB}{\mathbb B} \newcommand{\MM}{\mathbb M} \newcommand{\alt}{\operatorname{alt}} \newcommand{\dom}{\operatorname{Dom}} \newcommand{\ceil}{\operatorname{ceil}} \newcommand{\Diff}{\operatorname{Diff}} \newcommand{\ev}{\operatorname{ev}} \newcommand{\floor}{\operatorname{floor}} \newcommand{\ggT}{\operatorname{ggT}} \newcommand{\grad}{\operatorname{grad}} \newcommand{\graph}{\operatorname{Graph}} \newcommand{\im}{\operatorname{Im}} \newcommand{\id}{\operatorname{id}} \newcommand{\incl}{\operatorname{incl}} \newcommand{\kgV}{\operatorname{kgV}} \newcommand{\li}{\operatorname{li}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\ptp}{\operatorname{ptp}} \newcommand{\rang}{\operatorname{rang}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\sym}{\operatorname{sym}} \newcommand{\trg}{\operatorname{Trg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\card}{\operatorname{card}} \newcommand{\R}{\Rightarrow} \newcommand{\L}{\Leftarrow} \newcommand{\gdw}{\Leftrightarrow} \) Hallo, Ja da habe ich mich scheinbar verschrieben. Es soll natürlich $\ggT(a+mk,m)=\ggT(a,m)$ heissen, was ich basismäßig über die Definittion zeigen konnte. Mir ist nur nicht klar warum das hier nötig sein sollt. LG Oliver 🙂\(\endgroup\)


   Profil
Student10023
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.11.2020
Mitteilungen: 115
  Beitrag No.5, eingetragen 2021-09-16

Damit die Definition von Prof. Summerer überhaupt Sinn ergibt musst du dir Gedanken darüber machen, ob diese Sinvoll ist. Die Menge besteht aus allen Mengen der Form [a] (Achtung: das sind Mengen !!) für die gilt ggT(a,m) = 1. Die Frage ist nun, wenn [a] = [b] und ggT(a,m) = 1 gilt dann auch ggT(b,m) = 1 ? Wenn das nicht so wäre, wäre diese Menge nicht wohldefiniert, weil zwar [a] = [b] aber [a] ist in der Menge und b nicht. Du musst also zeigen, dass die Menge wohldefiniert ist und dazu ist die Aussage über die GGts hilfreich. hilft das ? LG PS: ich schreibe [a] = a+Zm


   Profil
OliverFuchs
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2020
Mitteilungen: 162
Wohnort: Wien, Österreich
  Beitrag No.6, vom Themenstarter, eingetragen 2021-09-22

\(\begingroup\)\(\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\bs}{\backslash} \newcommand{\ga}{\gamma} \newcommand{\de}{\delta} \newcommand{\ep}{\varepsilon} \newcommand{\ze}{\zeta} \newcommand{\et}{\eta} \newcommand{\io}{\iota} \newcommand{\ka}{\kappa} \newcommand{\la}{\lambda} \newcommand{\rh}{\rho} \newcommand{\si}{\sigma} \newcommand{\ta}{\tau} \newcommand{\ph}{\varphi} \newcommand{\ch}{\chi} \newcommand{\ps}{\psi} \newcommand{\om}{\omega} \newcommand{\Ga}{\Gamma} \newcommand{\De}{\Delta} \newcommand{\Th}{\Theta} \newcommand{\La}{\Lambda} \newcommand{\Si}{\Sigma} \newcommand{\Ph}{\Phi} \newcommand{\Ps}{\Psi} \newcommand{\Om}{\Omega} \newcommand{\NN}{\mathbb N} \newcommand{\ZZ}{\mathbb Z} \newcommand{\QQ}{\mathbb Q} \newcommand{\RR}{\mathbb R} \newcommand{\CC}{\mathbb C} \newcommand{\HH}{\mathbb H} \newcommand{\DD}{\mathbb D} \newcommand{\TT}{\mathbb T} \newcommand{\KK}{{\mathbb K}} \newcommand{\oo}{{\infty}} \newcommand{\PP}{\mathbb P} \newcommand{\BB}{\mathbb B} \newcommand{\MM}{\mathbb M} \newcommand{\alt}{\operatorname{alt}} \newcommand{\dom}{\operatorname{Dom}} \newcommand{\ceil}{\operatorname{ceil}} \newcommand{\Diff}{\operatorname{Diff}} \newcommand{\ev}{\operatorname{ev}} \newcommand{\floor}{\operatorname{floor}} \newcommand{\ggT}{\operatorname{ggT}} \newcommand{\grad}{\operatorname{grad}} \newcommand{\graph}{\operatorname{Graph}} \newcommand{\im}{\operatorname{Im}} \newcommand{\id}{\operatorname{id}} \newcommand{\incl}{\operatorname{incl}} \newcommand{\kgV}{\operatorname{kgV}} \newcommand{\li}{\operatorname{li}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\ptp}{\operatorname{ptp}} \newcommand{\rang}{\operatorname{rang}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\sym}{\operatorname{sym}} \newcommand{\trg}{\operatorname{Trg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\card}{\operatorname{card}} \newcommand{\R}{\Rightarrow} \newcommand{\L}{\Leftarrow} \newcommand{\gdw}{\Leftrightarrow} \) Lieber Student 10023 ! Danke für deine Antwort. Leider hat das nicht viel geholfen. Ich möchte hier kurzt erklären warum. Bemerkung1: Ich versuche auf das Argument von Student 100023 von Mathplanet einzugehen. Dieser meinte, dass $A$ aus den Mengen der Form $(a+m\ZZ)$ besteht. Nun hat er die Gleichung $(a+m\ZZ)=(b+m\ZZ)$ betrachtet. Da diese für $a=b$ selbstverständlich gilt, nehme ich $a\neq b$ an. Nun hat Student 100023 gemeint, dass wenn zwei solche Restklassen übereinstimmen, dass wenn für die erste $\ggT(a,m)=1$ gilt, dass dann für die andere auch $\ggT(b,m)=1$ gelten muss. Das stimmt mit folgender Betrachtung überein. Man kann das auch so sehen, dass $a,b$ zwei unterschiedliche Vertreter der selben Restklasse sind. Dann gilt aber $a\equiv b(\mod m)\gdw m\vert (b-a)$. Nun nehme ich an, dass $\ggT(a,m)=d$ ist. Es gilt $d\vert m$ und mit $d\vert a$ auch $d\vert b$. Also ist $d$ ein gemeinsamer Teiler von $b,m$.\\ Es sei nun $s$ ein beliebiger gemeinsamer Teiler von $b$ und $m$. Dann gilt $s\vert b\wedge s\vert m\wedge m\vert (a-b)\> s\vert a$. Also ist $s$ auch ein gemeinsamer Teiler von $a,m$. Somit gilt aber $s\vert d$. Damit ist $d$ ein gemeinsamer Teiler von $b,m$ der von allen solchen Teilern geteilt wird und also $\ggT(b,m)=d$. Somit haben wir $\ggT(a,m)=\ggT(b,m)$ gezeigt. Das gilt dann natürlich auch für $\ggT(a,m)=1$. Damit habe ich aber das folgende Lemma gezeigt. \blem Es seinen $a,b\in(a+m\ZZ)\in\ZZ_m$ zwei Elemente aus einer Restklasse $(a+m\ZZ)$. Dann gilt $$ \ggT(a,m)=\ggT(b,m) $$ \elem \bbw s. Bemerkung. \ebw Bemerkung 2: Nun weiter zum Argument von Student 100023. Ich habe die Menge $A=\{(a+m\ZZ)\vert \ggT(a,m)=1\}$ wie folgt aufgefasst. Die Mengen $(a+m\ZZ)$ sind, nach meiner Auffassung nicht beliebige Mengen. Es gilt für mich $A\subseteq \ZZ_m$ Also sind die Elemente in $A$ nicht nur Mengen, sondern sogar Restklassen $\mod m$. Und das laut Definition, da ich ja das Symbol $(a+m\ZZ)$ für die Bezeichnung der Mengen in $A$ verwende und dies für die Restklassen $\mod m$ definiert ist. Daher handelt es sich bei den Elementen von $A$ nicht nur um allgemeine Mengen sondern um Restklassen aus $\ZZ_m$. Für solche habe ich aber nach dem Lemma schon $[a]=(a+m\ZZ)=(b+m\ZZ)=[b]\> \ggT(a,m)=\ggT(b,m)$ gezeigt. Die Frage ob aus $\ggT(a,m)=1$ auch $\ggT(b,m)=1$ folgt, ist damit geklärt. Auch die Wohldefiniertheit brauche ich nicht zeigen, weil sie für die Restklassen gilt.\\ Stelle ich mich aber mal, naiv, auf den Standpunkt reiner Teilmengen, wo $\ggT(a,m)=1$ das definierende Element sein soll, und vergesse auf die Restklassenstruktur, so geht mir viel Information verloren. Ich versuche es dennoch. Als einzige Möglichkeit fällt mir $A'=\{B\subset\ZZ\vert \forall x\in B\> \ggT(x,m)=1\}$ ein. Dann haben die $B's$ eben nicht mehr die Struktur der Restklassen. Hier bin ich aber in einem Fall gelandet der mich eher verwirrt und nach meiner Meinung mit den Anwendungen nicht mehr viel zu tun hat. Wenn ich die Menge $C=\{x\in\ZZ\vert (\ggT(x,m)=1)\}$ betrachte. So wird die Menge $C$ die Menge all jener Zahlen in $\ZZ$ sein die als Vertreter für invertierbare Restklassen in $\ZZ_m$ dienen können. Es wird wohl $C=\Cup_{\ggT(a,m)=1}(a+,\ZZ)$ gelten. $C$ kann also auch als Vereinigung aller Zahlen die in invertierbaren Restklassen liegen, aufgefasste werden. Die Menge $A'$ ist dann die Menge aller Teilmengen von $C$. Das macht tatsächlich kaum Sinn. Wenn ich da weiter denke verliere ich mich ganz. Daher glaube ich mein Ansatz $A$ als Menge von Restklassen aufzufassen ist passender. Dann ist aber die Wohldefiniertheit kein Problem und wie man sieht $\ggT(a,m)=1=\ggT(b,m)$ eine Folge. Somit bringt mich das nicht weiter und ich sehe die Notwendigkeit des Argumentes $\ggT(a+km,m)=\ggT(a,m)$ nicht ein. Ich würde sogar so weit gehen, das als Trivialität ab zu tun. Denn wenn ich eine Restklasse habe, so sind ihre Eigenschaften bezüglich der Addition und der Multiplikation eben vom Vertreter unabhängig. Die Eigenschaft gegenüber der Multiplikation invertierbar zu sein, ist dann eben auch vom Vertreter unabhängig. Da aber $(a+mk)$ genau dann invertierbar ist, wenn $\ggT(a,m)=1$ ist, muss das eben für jeden Vertreter $b=a+mk\in(a+m\ZZ)$ gelten. Also muss auch $\ggT(b,m)=1$ sein. Damit ist aber $\ggT(a+mk,m)=\ggT(a,m)=1$ eine Folge der Wohldefiniertheit der Restklassen und nicht umgekehrt. Ich glaube daher das hier der Professor irrt. Ich hoffe das war nicht zu verwirrend. Ich bin etwas aus der Übung. lg Oliver🙂 \(\endgroup\)


   Profil
Student10023
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.11.2020
Mitteilungen: 115
  Beitrag No.7, eingetragen 2021-09-22

Hey, Auf folgendes wollte ich hinaus (wie wollen zeigen: [a] = [b] und ggt (a,m) = 1 (oder allgemeiner d) impliziert ggt(b,m) = d): Sei [a] = [b] und ggt(a,m) = 1 (oder allgemeiner d). Dann gilt b\el\ [a] d.h es gibt ein k\el\ \IZ mit b = a +km. Also gilt mit der Bemerkung von Deinem Prof. ggT(b,m) = ggT(a+km,m) = ggT(a,m) = 1 (bzw. d). So ist das denke ich gemeint, aber natürlich kannst du auch sagen, dass ist "trivial" nur muss man damit immer vorsichtig sein, weil das immer aber insbesondere in der Mathematik vom Betrachter abhängt. Ich hoffe jetzt ist es klarer, wie ich es gemeint habe. (Ohne deinen Beweis in Gänze durchdrungen zu haben, sieht er aber ganz gut aus, wahrscheinlich stimmt das also auch.) Ist damit Bemerkung 2 auch erledigt oder gibt es noch offenen Fragen ? Lg


   Profil
OliverFuchs
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.03.2020
Mitteilungen: 162
Wohnort: Wien, Österreich
  Beitrag No.8, vom Themenstarter, eingetragen 2021-09-22

Hallo, Danke für die Zurechtweisung. Ich mag das Wort trivial eigentlich auch nicht nur bin ich in der Arbeit gesessen und da ist mir nichts besseres eingefallen. Ich glaube so passt das schon, aber wenn ein Prof. Was behauptet tue ich mir schwer anzunehmen dass er sich geirrt haben könnte. Da sehe ich es mir lieber nochmals an oder diskutiere es. Aber für die Prüfungsvorbereitung lasse ich es einmal damit bewenden LG Oliver 🙂


   Profil
OliverFuchs hat die Antworten auf ihre/seine Frage gesehen.
OliverFuchs hat selbst das Ok-Häkchen gesetzt.
OliverFuchs wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]