geichung mit modulo umstellen?

@Wade1234 sagte in geichung mit modulo umstellen?:

du musst das multiplikative inverse von a mod 11 berechnen

das habe ich vor. kann ich bloß mangels wissens noch nicht.

@Wade1234 sagte in geichung mit modulo umstellen?:

und das tust du mit dem erweiterten algorithmus von euklid.

hört sich gut an. aber wie wende ich den hier an?

bisher finde ich die inversen durch ausprobieren. aber das ist bei riesigen gruppen wohl nicht so toll.

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

TGGC

x = 1 + a*11

DirkB

@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]
    };
}

TGGC

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

TGGC

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

TGGC

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.

hustbaer

@It0101 sagte in geichung mit modulo umstellen?:

Die Mathematik kennt aber keine ganzzahlige Division.

Vielleicht verwechselst du grad Mathematik und lineare Algebra?

It0101

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

TGGC

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.

hustbaer

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