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.

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.

Bashar

@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 $n$ . Dann kann man die Restklassen bezüglich, oder modulo, $n$ bilden, die Restklasse von 4 mod 5 wäre bspw. die Menge $\{\ldots, -6, -1, 4, 9, \ldots\}$ -- alle ganzen Zahlen die bei der ganzzahligen Division durch 5 den Rest 4 lassen. Man schreibt $4 + 5\mathbb{Z}$ , oder einfach $\overline 4$ .

Mit Restklassen modulo $n$ kann man rechnen: $\overline a + \overline b = \overline{a+b}$ , $\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 $n$ einen Ring ( $\mathbb{Z}/n\mathbb{Z}$ ) bilden.

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

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

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

$a\cdot x = 1 + n\cdot k$

Wenn $n$ prim ist, (und außerdem $0\leq a < n$ , was man immer erreichen kann, da die Restklasse einen solchen Vertreter enthält) dann haben $a$ und $n$ den größten gemeinsamen Teiler $1$ , also gibt es nach dem Erweiterten Euklidischen Algorithmus ganze Zahlen $x$ und $k$ , die die obige Gleichung lösen. Das $k$ kann man wegwerfen, das $x$ ist ein Vertreter der zu $\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+b$ , die Inversen $-a$ und die n-fache Verknüpfung mit sich selbst $na$ schreibt, mehr nicht. Das macht man per Konvention gelegentlich, wenn die Gruppe kommutativ ist. Wenn nicht, schreibt man meistens multiplikativ, also mit $ab$ , $a^{-1}$ , $a^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 $(\mathbb{Z},+)$ gibt. Ja, es gibt eine: $\{ 0\}$ . Aber nur diese. Alle Untergruppe von $(\mathbb{Z},+)$ haben die Form $n\mathbb{Z} := \{ na \mid a\in\mathbb{Z} \}$ für ein gewisses $n\in\mathbb{Z}$ , alle außer $\{0\}$ sind also unendlich.