geichung mit modulo umstellen?



  • @Wade1234 sagte in geichung mit modulo umstellen?:

    @Bushmaster https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

    beispiel für a = 7:

    11 = 1 x 7 + 4
    7 = 1 x 4 + 3
    4 = 1 x 3 + 1
    3 = 3 x 1 + 0

    erkenntnis: größter gemeinsamer teiler = 1, zahlen sind teilerfremd, multiplikatives inverses existiert.

    1 = 4 - 1 x 3
    1 = 4 - 1 x (7 - 1 x 4) = 4 - 7 + 4 = 2 x 4 - 7
    1 = 2 x 4 - (11 - 1 x 4)
    1 = 2 x 4 - 11 + 1 x 4 = 3 x 4 - 11
    1 = 3 x (11 - 7) - 11
    1 = 2 x 11 - 3 * 7

    a = 11
    b = 7
    s = 2
    t = -3 = 8

    probe: a * a^-1 mod 11 = 7 * 8 mod 11 = 56 mod 11 = 1

    danke, damit muss ich mich mal auseinandersetzen.



  • @Bushmaster wenn du ein negatives t bekommst, einfach den modulus (im beispiel 11) addieren.



  • @Wade1234 sagte in geichung mit modulo umstellen?:

    @Bushmaster wenn du ein negatives t bekommst, einfach den modulus (im beispiel 11) addieren.

    du hast mir sehr geholfen. ich habe eine extended gcd-implementation in java gefunden. damit kann ich alle inversen meiner mini-gruppe erzeugen:
    das ist mein testcode:

    import java.util.ArrayList;
    
    public class ExtGCD
    {
        public static long[] xgcd(long a, long b)
        {
            long[] retvals={0,0,0};
            long[] aa ={1, 0};
            long[] bb ={0, 1};
            long q=0;
            while(true)
            {
                q = a / b; a = a % b;
                aa[0] = aa[0] - q*aa[1];  bb[0] = bb[0] - q*bb[1];
                if (a == 0)
                {
                    retvals[0] = b; retvals[1] = aa[1]; retvals[2] = bb[1];
                    return retvals;
                }
                q = b / a; b = b % a;
                aa[1] = aa[1] - q*aa[0];  bb[1] = bb[1] - q*bb[0];
                if (b == 0)
                {
                    retvals[0] = a; retvals[1] = aa[0]; retvals[2] = bb[0];
                    return retvals;
                }
            }
        }
    
        public static int getInverse (int mod, int b)
        {
            long[] retvals;
            retvals = xgcd (mod,b);
            System.out.println("   "+String.valueOf(retvals[0])+" = "
                    +mod+"*("+String.valueOf(retvals[1])+") + "
                    +b+"*("+String.valueOf(retvals[2])+")");
            if (retvals[2] < 0)
                retvals[2] = mod+retvals[2];
            return (int)retvals[2];
        }
    
        public static void main(String[] args)
        {
            int group[] = {4,5,9,3,1};
            ArrayList<Integer> inv = new ArrayList<> ();
            for (int a: group)
            {
                inv.add (getInverse (11, a));
            }
            System.out.println (inv);  // [3, 9, 5, 4, 1]
        };
    }
    


  • Sry, ich las x mod 11 = 1? Prinzip ist aber das gleiche, einfach ax durch x substituieren und dann kommt Dirks Lösung raus.



  • @Wade1234 sagte in geichung mit modulo umstellen?:

    @Bushmaster wenn du ein negatives t bekommst, einfach den modulus (im beispiel 11) addieren.

    Wieso? Negative Zahlen erfüllen das doch auch?



  • @TGGC sagte in geichung mit modulo umstellen?:

    @Wade1234 sagte in geichung mit modulo umstellen?:

    @Bushmaster wenn du ein negatives t bekommst, einfach den modulus (im beispiel 11) addieren.

    Wieso? Negative Zahlen erfüllen das doch auch?

    in zyklischen gruppen die durch eine natürlich zahl mod m erzeugt wurden, kommt keine negative zahl vor.
    beim potenzieren von i (imaginäre einheit) kriegst du eine gruppe mit negativer zahl: {i, -1, -i, 1} 🙂



  • Aber man kann auch negativen Zahlen eine eindeutige Restklasse zuordnen. Durch welches Symbol diese Restklasse dann visualisiert ist, interessiert doch gar nicht. Auch das man die normal mit 0 bis n-1 durchnummeriert ist reine Konvention.



  • @It0101 sagte in geichung mit modulo umstellen?:

    Die Mathematik kennt aber keine ganzzahlige Division.

    Vielleicht verwechselst du grad Mathematik und lineare Algebra?



  • @hustbaer sagte in geichung mit modulo umstellen?:

    @It0101 sagte in geichung mit modulo umstellen?:

    Die Mathematik kennt aber keine ganzzahlige Division.

    Vielleicht verwechselst du grad Mathematik und lineare Algebra?

    Gut möglich. 😉 Wenn ich aber an den Mathematik-Unterricht zurückdenke, fällt mir ehrlich gesagt kein Fall ein, bei dem wir ganzzahlige Division betrieben. Allenfalls noch in der Grundschule... Ist aber sehr lange her. Und in der Mathematik in der Sekundarstufe (2), wo man dann mit Brüchen rechnet, wurden die eigentlich nie aufgelöst. Sondern das Ergebnis war dann eigentlich immer 5 / 2 und nie 2,5. Und schon gar nicht 2 😃



  • @TGGC sagte in geichung mit modulo umstellen?:

    Aber man kann auch negativen Zahlen eine eindeutige Restklasse zuordnen. Durch welches Symbol diese Restklasse dann visualisiert ist, interessiert doch gar nicht. Auch das man die normal mit 0 bis n-1 durchnummeriert ist reine Konvention.

    ist aber ein anderes thema. restklassen ordnet man als körper ein. die haben nebenbei auch zwei verknüpfungen. was ich hier habe ist eine endliche multipikative gruppe (hat nur eine verknüpfung, das *).

    ich habe man gehört dass die ganzen zahlen Z bezüglich der addition ebenfalls als gruppe gelten. da sind dann auch negative zahlen dabei. muss ja, weil es für jedes element ein inverses geben muss. 0 ist dann das neutrale element und zu sich selbst invers.

    aber ich glaube es gibt keine endichen additiven gruppen, da das ergebnis der verknüpfung immer in der gruppe selbst liegen muss. folglich kann eine teilmenge von Z mit + keine gruppe sein, oder?



  • Ganzahlige Definition is definiert: a = b*q+r mit ganzen Zahlen und 0 <= r < b. Zu jedem a/b gibts dann genau ein passendes Paar q;r die man Quotient und Rest nennt.



  • @It0101 sagte in geichung mit modulo umstellen?:

    Sondern das Ergebnis war dann eigentlich immer 5 / 2 und nie 2,5. Und schon gar nicht 2

    5/2 geht ja noch als kommazahl 2.5. aber 1/3 sollte man besser so stehen lassen. nachher kommst du noch auf 123.9999986 oder so, wo eigentlich eine 124 hingehört. 😃



  • @It0101 Naja wir haben in der Schule auch keine Graphentheorie gemacht. Aber versuch mal nem Mathematiker zu erzählen dass Graphentheorie kein Teil der Mathematik ist. Bzw. wenn er grösser ist als du, versuch es lieber nicht 😉



  • @hustbaer sagte in geichung mit modulo umstellen?:

    @It0101 Naja wir haben in der Schule auch keine Graphentheorie gemacht. Aber versuch mal nem Mathematiker zu erzählen dass Graphentheorie kein Teil der Mathematik ist. Bzw. wenn er grösser ist als du, versuch es lieber nicht 😉

    mathematiker sind freundliche menschen. wade1234 ist bestimmt mathematiker.



  • @Bushmaster sagte in geichung mit modulo umstellen?:

    @TGGC sagte in geichung mit modulo umstellen?:

    Aber man kann auch negativen Zahlen eine eindeutige Restklasse zuordnen. Durch welches Symbol diese Restklasse dann visualisiert ist, interessiert doch gar nicht. Auch das man die normal mit 0 bis n-1 durchnummeriert ist reine Konvention.

    ist aber ein anderes thema. restklassen ordnet man als körper ein. die haben nebenbei auch zwei verknüpfungen. was ich hier habe ist eine endliche multipikative gruppe (hat nur eine verknüpfung, das *).

    Ich glaub ich sortiere das mal. Fixiere erstmal eine natürliche Zahl nn. Dann kann man die Restklassen bezüglich, oder modulo, nn bilden, die Restklasse von 4 mod 5 wäre bspw. die Menge {,6,1,4,9,}\{\ldots, -6, -1, 4, 9, \ldots\} -- alle ganzen Zahlen die bei der ganzzahligen Division durch 5 den Rest 4 lassen. Man schreibt 4+5Z4 + 5\mathbb{Z}, oder einfach 4\overline 4.

    Mit Restklassen modulo nn kann man rechnen: a+b=a+b\overline a + \overline b = \overline{a+b}, ab=ab\overline a\cdot \overline b = \overline{a\cdot b}.

    Es gelten die bekannten Rechengesetze (Kommutativitiät, Assoziativität, Distributivität), so dass die Restklassen modulo nn einen Ring (Z/nZ\mathbb{Z}/n\mathbb{Z}) bilden.

    Manche Restklassen a\overline a haben eine multiplikative Inverse, also eine Restklasse a1\overline a^{-1}, so dass aa1=1\overline a\cdot\overline a^{-1} = \overline 1 gilt. Aber nicht jede: Modulo 44 gibt es die Restklassen 0,,3\overline 0, \ldots, \overline 3, und man kann einfach alle 4 durchprobieren, um zu sehen, dass 2a=1\overline 2\cdot\overline a = \overline 1 nicht lösbar ist.

    Es stellt sich heraus, dass jede Restklasse 0\neq\overline 0 invertierbar ist, wenn nn eine Primzahl ist. Dann ist der Restklassenring modulo nn also ein Körper.

    Das Problem, die Inverse zu einer Restklasse a\overline a modulo nn zu bestimmen, lässt sich ohne Restklassen so schreiben:

    ax=1+nka\cdot x = 1 + n\cdot k

    Wenn nn prim ist, (und außerdem 0a<n0\leq a < n, was man immer erreichen kann, da die Restklasse einen solchen Vertreter enthält) dann haben aa und nn den größten gemeinsamen Teiler 11, also gibt es nach dem Erweiterten Euklidischen Algorithmus ganze Zahlen xx und kk, die die obige Gleichung lösen. Das kk kann man wegwerfen, das xx ist ein Vertreter der zu a\overline a inversen Restklasse.

    ich habe man gehört dass die ganzen zahlen Z bezüglich der addition ebenfalls als gruppe gelten. da sind dann auch negative zahlen dabei. muss ja, weil es für jedes element ein inverses geben muss. 0 ist dann das neutrale element und zu sich selbst invers.

    Das ist richtig.

    aber ich glaube es gibt keine endichen additiven gruppen, da das ergebnis der verknüpfung immer in der gruppe selbst liegen muss. folglich kann eine teilmenge von Z mit + keine gruppe sein, oder?

    "Additiv" zu sein ist keine (strukturelle) Eigenschaft einer Gruppe, das ist nur Notation. Additiv bedeutet, dass man die Verknüpfung als a+ba+b, die Inversen a-a und die n-fache Verknüpfung mit sich selbst nana schreibt, mehr nicht. Das macht man per Konvention gelegentlich, wenn die Gruppe kommutativ ist. Wenn nicht, schreibt man meistens multiplikativ, also mit abab, a1a^{-1}, ana^n.

    Man nennt auch die Gruppe, die man bekommt, wenn man von einem Ring die Multiplikation vergisst, die additive Gruppe des Rings.

    Deine Frage scheint zu meinen, ob es endliche Untergruppen von (Z,+)(\mathbb{Z},+) gibt. Ja, es gibt eine: {0}\{ 0\}. Aber nur diese. Alle Untergruppe von (Z,+)(\mathbb{Z},+) haben die Form nZ:={naaZ}n\mathbb{Z} := \{ na \mid a\in\mathbb{Z} \} für ein gewisses nZn\in\mathbb{Z}, alle außer {0}\{0\} sind also unendlich.



  • @Bashar sagte in geichung mit modulo umstellen?:

    Deine Frage scheint zu meinen, ob es endliche Untergruppen von (Z,+)(\mathbb{Z},+)(Z,+) gibt. Ja, es gibt eine: {0}{ 0}{0}. Aber nur diese. Alle Untergruppe von (Z,+)(\mathbb{Z},+)(Z,+) haben die Form nZ:={na∣a∈Z}n\mathbb{Z} := { na \mid a\in\mathbb{Z} }nZ:={na∣a∈Z} für ein gewisses n∈Zn\in\mathbb{Z}n∈Z, alle außer {0}{0}{0} sind also unendlich.

    aber nimmt man "addition mod n", dann sind wieder unendlich viele endliche gruppen möglich. siehe: https://www.youtube.com/watch?v=2POgCMpHRh0
    gruppeneigenschaften sind erfüllt (abgeschlossenheit, neutrales e, jedes element hat ein inverses und assoziativität gilt auch innerhalb der gruppe).

    ich habe es nicht ausprobiert, aber mit negativen zahlen solte das auch gehen. {-2,-1,0,1,2} mit der verknüpfung (a+b)mod6 sollte auch eine gruppe sein.



  • @Bushmaster sagte in geichung mit modulo umstellen?:

    aber nimmt man "addition mod n", dann sind wieder unendlich viele endliche gruppen möglich. siehe: https://www.youtube.com/watch?v=2POgCMpHRh0
    gruppeneigenschaften sind erfüllt (abgeschlossenheit, neutrales e, jedes element hat ein inverses und assoziativität gilt auch innerhalb der gruppe).

    Ja, man kann zu jeder Untergruppe nZn\mathbb{Z} die Quotientengruppe bzw. Restklassengruppe Z/nZ\mathbb{Z}/n\mathbb{Z} bilden. Das hatte ich im vorherigen Posting als Restklassenring bezeichnet, aber man kann ja die Multiplikation einfach ignorieren.

    Allerdings ist die Verknüpfung ++ in diesen Gruppen nicht identisch zur Addition auf den ganzen Zahlen. Es handelt sich um die Addition von Restklassen. (Das bezieht sich darauf, dass ich nicht genau weiß, was du unter einer "additiven" Gruppe verstehst -- dein Text las sich so als sollte die Gruppe exakt die Addition von Z\mathbb{Z} übernehmen -- was natürlich auch so nicht ganz stimmt, es wäre wenn schon eine Einschränkung dieser Addition, aber das dürfte sich immer noch deutlich näher an der Addition auf Z\mathbb{Z} anfühlen als der Übergang zur Addition von Restklassen.)

    ich habe es nicht ausprobiert, aber mit negativen zahlen solte das auch gehen. {-2,-1,0,1,2} mit der verknüpfung (a+b)mod6 sollte auch eine gruppe sein.

    Das klappt so nicht, z.B. ist (2+2) mod 6 = 4, was nicht in dieser Menge enthalten ist. Außerdem sollten es 6 Elemente sein. Prinzipiell kann man sowas in der Art natürlich schon hinkriegen, du musst an der Verknüpfung noch etwas herumdoktern, z.B. so dass die Ergebnisse der Addition mod 6, die größer als 3 sind, nochmal um 6 verringert werden. Sauberer ist es aber, statt mit endlichen Teilmengen von Z\mathbb{Z} und ad-hoc-definierten Verknüpfungen mit den entsprechenden Restklassengruppen Z/nZ\mathbb{Z}/n\mathbb{Z} (s.o.) zu arbeiten.



  • @Bashar sagte in geichung mit modulo umstellen?:

    Das klappt so nicht, z.B. ist (2+2) mod 6 = 4, was nicht in dieser Menge enthalten ist. Außerdem sollten es 6 Elemente sein. Prinzipiell kann man sowas in der Art natürlich schon hinkriegen, du musst an der Verknüpfung noch etwas herumdoktern, z.B. so dass die Ergebnisse der Addition mod 6, die größer als 3 sind, nochmal um 6 verringert werden.

    das stimmt. allerdings ist es wichtig dass die verknüpfung immer assoziativ bleibt, sonst ist es keine gruppe mehr. nicht mal mehr ein monoid.
    gibt es überhaupt eine algebraische struktur mit singulärer verknüpfung, ohne die forderung nach assoziativität? ich glaube nicht. ist wohl auch ziemlich unsinnig.
    beispiele für gruppen mit subtraktion als verknüpfung habe ich jedenfalls bisher noch nicht gesehen.

    btw, bist du mathematiker? ich bin diesbezüglich nur hobbyist. also bei antworten bitte nicht zu viel wissen voraussetzen. 🙂



  • @Bushmaster sagte in geichung mit modulo umstellen?:

    das stimmt. allerdings ist es wichtig dass die verknüpfung immer assoziativ bleibt, sonst ist es keine gruppe mehr. nicht mal mehr ein monoid.
    gibt es überhaupt eine algebraische struktur mit singulärer verknüpfung, ohne die forderung nach assoziativität? ich glaube nicht. ist wohl auch ziemlich unsinnig.
    beispiele für gruppen mit subtraktion als verknüpfung habe ich jedenfalls bisher noch nicht gesehen.

    Strukturen mit einer binären Verknüpfung, an die man nicht die Forderung der Assoziativität stellt, heißen Magma. Die ganzen Zahlen mit der Subtraktion sind ein Beispiel dafür. Ich hab allerdings noch nichts von einer systematischen Theorie von Magmen gehört. Meistens fordert man mindestens eine assoziative Verknüpfung, also eine Halbgruppe.

    btw, bist du mathematiker? ich bin diesbezüglich nur hobbyist. also bei antworten bitte nicht zu viel wissen voraussetzen. 🙂

    Ich habe Mathematik studiert, aber ich versuche hier überhaupt nichts vorauszusetzen bis auf das, was meiner Meinung nach aus dem was du schon geschrieben hast hervorgeht.



  • @Bashar sagte in geichung mit modulo umstellen?:

    Strukturen mit einer binären Verknüpfung, an die man nicht die Forderung der Assoziativität stellt, heißen Magma. Die ganzen Zahlen mit der Subtraktion sind ein Beispiel dafür. Ich hab allerdings noch nichts von einer systematischen Theorie von Magmen gehört.

    ich glaube der begriff 'magma' ist gut gewählt. die ursuppe der abstrakten algebra.


Log in to reply