geichung mit modulo umstellen?



  • @It0101 sagte in geichung mit modulo umstellen?:

    Daher stelle ich mir das "invertieren" kompliziert vor.

    ist jedenfalls nicht eindeutig. 'mod n' kann n-1 resultate ausspucken.



  • x = 1 + a*11



  • @Bushmaster

    ax = (n*11) + 1

    x = (n*11+1)/a

    Das n darfst du dir aussuchen



  • @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



  • @TGGC sagte in geichung mit modulo umstellen?:

    x = 1 + a*11

    leider nein. ergebnisse sind viel zu groß. und mod11 sind sie alle 1

    ich habe z.b eine multplikative gruppe mod11: {4,5,9,3,1}, die 1 ist das neutrale element, generator ist 3.
    die inversen sind in gleicher reihenfolge: {3,9,5,4,1}, also 4 und 3 sind gegenseitig invers usw. 1 ist invers zu sich selbst, wie üblich bei multiplikation.

    @ Wade, das mit dem euklidschen gcd sieht vielversprechend aus. bloß wie mache ich das?



  • @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.


Log in to reply