4. Modulare Arithmetik

Modulare Arithmetik

  • S

    Also folgende eher kleine problemchen.
    11mod5 zu rechnen ist ja jetzt nicht schwer.
    Probleme bekomme ich bei: (13+x*19)^31 = 3 (mod 4)
    Berechnen sie "x". Klar gibts da viele werte. Ich brauch aber nur den kleinsten.

    Kann mir das jemand anschaulich erklären?

    Danke schon mal

    Sqwan

    0
  • ?

    Hmmm,
    wäre ggT(13+x*19,4)=1 (für alle x in Z), dann könnte man das einfach lösen. Leider versagt das ja zB schon für x=1. Vielleicht fällt mir gleich was ein ...

    0
  • V

    (13+x*19)^31 = 3 (mod 4)

    Substituieren.

    y:=13+x*19

    y^31 = 3 (mod 4)

    Hierfür kenne ich abe rnichts schnelles.

    Da ich am ende mod 4 rechne, kann ich auch
    vorher vor und nach jedem + und * nach
    Belieben %4 einfügen.

    (y%4)^31 = 3 (mod 4)
    also reicht es, für y die Werte 0,1,2 und 3 zu testen.

    0: 0,0,0,... kann es nicht sein.
    2: bleibt eine gerade Zahl, kann es nicht sein.
    1: bleibt 1, kann es nicht sein.
    3(=-1): y^0=1, y^1=-1, y^2=1, y^3=-1 ... y^31=-1=3

    Also, ich würde sagen, y=3+n*4.

    y:=13+x19
    3+n*4=13+x*19
    3=13+x    19 (mod 4)
    3=13+x3 (mod 4)
    2=x    3 (mod 4)
    (erweiterter euklidischer Algorithmus)
    oder
    2=x*(-1) (mod 4)
    -2=x (mod 4)
    x=-2 (mod 4)

    x=2

    0
  • S

    Ich dank dir sehr...
    Leider hilft das so nicht weiter... Ich muss ja jede belibige aufgabe lösen können.

    (a) Welche Ziffern x=0,1,...,9 erfüllen: 13 + x×17 = 0 (mod 4) ?
    (b) Welche Prüfziffer p macht 7-3215-4181-p zu einer gültigen ISBN ?
    (c) Es wird die ISBN 7-8215-418z-p eingegeben (mit dem p aus Teil (b)), also ein Einzelfehler
    an der zweiten Stelle und ein weiterer Fehler (z) an der vorletzten Stelle. Für welche Ziffern z
    erkennt die Prüfung NHLQHQ Fehler, obwohl die ISBN falsch ist?

    Das beispielsweise sind übungsaufgaben. Ich möchte garkeine lösungen. Zumal ich die so wie so habe. Problem ist, ich finde keinen lösungsweg um zu diesen Lösungen zu kommen.
    http://www.gm.fh-koeln.de/~konen/
    Die aufgaben kommen von hier, und hier gibts auch lösungen. Nur halt ohne weg 😞
    Ich versteh einfach nicht wie das allgemein gehen soll.

    0
  • V

    Sprich, Du willst ein allgemeines Modulo-Rechnung-Verständnis-Implantat. Soweit mir bekannt ist, gibt es die derzeit noch nicht zu kaufen. Es gibt noch nichtmal einen Königsweg zur Mathematik. Oh, schon wieder ist Euklid im Spiel.

    0
  • S

    lol ... ja so kann man es bezeichnen.
    Ich möchte Modulare Arithmetik verstehen. Dachte so wie so das hier einzelne Aufgaben nicht gelöst werden.

    Allerdings frag ich mich dann was ich in der uni will wenn es keine allgemeine methode gibt "modular" zu rechnen...

    Und keine Regeln was man machen darf und was nicht.

    Ich hatte gehoft, das es eine möglichkeit gibt dazu eine Gleichung aufzustellen die ich dann nach x auflösen kann.

    Statt dessen krieg ich hier so nen blöden Satz über implantate 😞

    Gut, die hier kann man einfach probieren. Aber das bringt mir ja nicht mehr viel wenns mal komplizierter wird...

    0
  • S

    ok... an der ersten habe ich jetzt mal gepfuscht...

    13%4 + x%4 * 17%4 = 4
  1  + x%4 *   1  = 4     | -1    
       x%4        = 3
       x          = 3

    so... nun alles in dem bereich. Also

    3-4 = -1  =>  nicht mehr drin.
3+4 =  7  =>  enthalten
7+4 = 11  =>  nicht mehr enthalten

    Damit wäre die Lösung dann 3 und 7!
    Bei den anderen hänge ich noch...

    0
  • S

    So auch die anderen sind gelöst...
    Danke @ volkard
    Das mit %4 an jeder stelle hat sich gelohnt 🙂

    0
  • ?

    Sqwan schrieb:

    gepfuscht...

    In der Tat! Du darfst nicht so einfach rumrechnen. Gib mal deine Gleichung zB in Google ein und für x=3 kommt da sicherlich nicht 3 raus.

    Ließ dir die Wiki Artikel zur Moduloarithmetik durch, ebenso ganz wichtig:

    • Satz von Euler
    • Eulerische-Funktion
    • Kleiner Fermat
    • Euklid
    • etc...

    Schau dir mal den Thread hier an: http://www.c-plusplus.net/forum/viewtopic-var-t-is-269569-and-highlight-is-.html

    und dann als Beispiel nehmen wir nochmal deine Gleichung leicht abgeändert:
    (13+x*17)^31 ≡ 3 (mod 4)

    Jetzt brechen wir erstmal die ^31 runter. Dafür benutzen wir den Satz von Euler.
    Der besagt nämlich das a^φ(n) ≡ 1 (mod n) ist. Aber nur für ggT(a,n) = 1

    In unserem Beispiel:
    ggT(13+x*17,4) -> Passt für alle x ( mit Induktionen oder wie auch immer zu beweisen).

    Also:
    (13+x17)^φ(4) ≡ 1 (mod 4)
    (13+x    17)^2 ≡ 1 (mod 4)

    Nun ein bissl Potenzrechnung:
    (13+x17)^31 ≡ 3 (mod 4)
    (13+x*17)^(2*15+1) ≡ 3 (mod 4)
    (13+x*17)^(2*15) * (13+x    17)^1 ≡ 3 (mod 4)
    ((13+x*17)2)15 * (13+x*17)^1 ≡ 3 (mod 4)

    ... und da wir wissen das (13+x*17)^2 ≡ 1 (mod 4) ist

    (1)^15 * (13+x17)^1 ≡ 3 (mod 4)
    13+x    17 ≡ 3 (mod 4)

    Schön, da ist keine ^31 mehr 🙂
    Nun, nur noch x rauskriegen. Schau dir dazu mal den verlinkten Thread an. Vielleicht kriegst du es ja dann noch selbst gelöst 😉

    PS: Zu faul für Latex ...

    0
  • ?

    Sqwan schrieb:

    Lösung 3

    Nochmals:

    [] 13 + 319 = 70
    [] 70%4 = 2
    [    ] 2^31 = 2 147 483 648
    [*] 2 147 483 648 % 4 = 0 != 3

    Aufegedröselt uns so früh wie möglich modulo machts den Taschenrechnern einfacher.

    0
  • V

    KasF schrieb:

    Sqwan schrieb:

    Lösung 3

    Nochmals:

    [] 13 + 319 = 70
    [] 70%4 = 2
    [    ] 2^31 = 2 147 483 648
    [*] 2 147 483 648 % 4 = 0 != 3

    Aufegedröselt uns so früh wie möglich modulo machts den Taschenrechnern einfacher.

    Du bist herrlich zusammenhanglos. Wahrscheinlich hat Du zwei Aufgaben vermischt und Zahlen vertauscht. Aber da Du nicht oder (was mir mehr Zeit geraubt hat) aus freier Phantasie quotest, ist das nicht einfach nachzuvollziehen. 🤡

    0
  • S

    drei ist die lösung für 13 + x * 17

    Es war zufall das meine Beispielaufgabe der a) auf der Probeklausur so ähnlich ist. Die hatte ich vorher noch nicht gesehen gehabt.

    @KasF
    Ich bin dir echt dankbar für jegliche Hilfe. Aber ich habe das Gefühl, das ist ein riesen Durcheinander in deinem Beitrag. Leider kann ich da keinen roten Faden erkennen.

    0
  • O

    Naja, was KasF sagte ist nichts weiter als: du musst die Eigenschaften des Körpers kennen, in dem du rechnest. in diesem Fall war das der Satz von Euler.

    In modulokörpern sind viele Dinge nicht mehr so einfach, wie im normalen Raum. bereits dass du dort sowas wie

    y^31=3 (mod 4)

    stehen hast ist kritisch. stände da nicht (mod 4) sondern (mod 546432) dann könntest du an der Aufgabe sehr sehr sehr lange rechnen, weil das diskrete Logarithmusproblem NP-Hart ist. Es gibt halt nicht mehr Tipps als: lerne die Theoreme des Körpers(die wichtigsten hat KasF aufgezählt) und dann setze sie intelligent ein.

    0
  • S

    Nun, recht hast du sicherlich. Leider schaffe ich das nicht mehr rechtzeitig.
    Deshalb wäre es schön wenn KasF noch mal etwas ausführlicher beschreiben könnte wie er die Potenz zerlegt hat.

    Das habe ich noch nicht ganz verstanden.
    Also wie aus

    ^31 = 3 (mod 4) 
^2  = 1 (mod 4)

    wurde.
    Das andere sollte ich verstanden haben. Kanns dann jedenfalls mal selber mit was anderem testen...

    Muss das dann nachlernen 😞 wird im Studium sicher wiederkommen. Ist bei uns im Script leider als Vorwissen markiert, weshalb es nicht in der Vorlesung vor kam...

    0
  • V

    Sqwan schrieb:

    Also wie aus

    ^31 = 3 (mod 4) 
^2  = 1 (mod 4)

    wurde.

    Normale Potenzenrechnung.
    x^31
    =x*x*x*x...*x(31 Stück)
    =x*x*x*...*x(15 Stück) * x*x*x*...*x(15 Stück) * x
    =x^15 * x^15 * x^1
    =(x15)2 * x^1
    UUps, er hat es ja andersrum zerlegt
    =x*x * x*x * x*x * ... * x*x(15 Päärchen) * x
    =(x*x)^15 * x
    =(x2)15 *x^1
    Ups, Frage nicht verstanden und nur einen kleinen Aspekt beleuchtet.

    0
  • O

    Das ist eine wichtige Eigenschaft endlicher Körper, die leider nicht so einfach zu beweisen ist. Insbesondere weil dein modulo nicht prim ist, muss man da sehr viel Theorie durchschleifen.

    Aber nur mal als Skizze: Man kann beweisen, dass wenn man für ein beliebiges Element a mit ggt(a,n)=1 (n ist der Modulowert) die Reihe a^1 a^2 a^3... berechnet man eine Zahlenreihe bekommt, bei der am Ende immer die 1 steht und die dann zyklisch weiter geht. Dies geht relativ einfach durch einen Widerspruchsbeweis den ich einfach mal skizziere:
    für jedes Element a mit ggt(a,n)=1 gibt es ein Inverses a^-1(Eigenschaft der multiplikativen Gruppe).
    Angenommen, die Aussage ist falsch, dann gibt es kein i für das gilt: 1=ai=a(i-1)*a=a^-1*a eine Potenz von a ist dann niemals die Inverse von a.
    Nun kommt ein Schubladenargument: in einem finiten Körper kann es nur endlich viele Rechenergebnisse geben. Wenn wir also ausschließen, dass die Inverse das Ergebnis sein kann, dann muss(!) ein Ergebnis doppelt rauskommen. Das kann aber nicht sein, weil wir eine Gruppe haben und damit x*a!=y*a für x!=y gelten muss! => Widerspruch zur Annahme.
    Das i für das a^i=1 gilt, nennt man die "Elementordnung" von a.

    Dann kann man lustig weiterbeweisen und zeigen, dass die Elementordnung immer die Anzahl der Elemente einer Gruppe teilt. Die Gruppenordnung erhälst du durch die Eulersche Phi-Funktion und damit schließt sich der Kreis: aphi(n)=a(i*x)=(ai)x=1^x=1
    In deinem Fall ist phi(n)=2 (kannst du dir überlegen: 1 ist drin, 2 ist nicht drin wegen 2*2=0 und 3 ist wieder drin wegen 3*3=9 mod 4=1). Und nun schauste dir das von KasF nochmal an.

    0
  • S

    Danke volkard, aber das grade nicht gemeint.
    Das hattest du mir damals mal so gut erklärt das hab ich behalten 😉

    Mir gehts eigentlich darum wie man phi berechnet...
    otze hat da schon mal sehr geholfen.
    Leider passt es noch nicht ganz.

    Wenn ich mod 4 habe kann ich mir das noch recht einfach ausdenken. So wie ich das jetzt verstanden habe. Die frage ist nur, kann ich das auch berechnen.

    Sicher bin ich mir nicht...
    http://de.wikipedia.org/wiki/Eulersche_φ-Funktion
    Da habe ich mich mal umgesehen.
    Also da scheint nicht zu stehen wie es geht. Allerdings gibt es dort eine liste von 1 bis 99.
    Da kann ich jetzt mit zerlegung arbeiten. War was ist bei potenzen die sehr hoch sind? 5681 zum beispiel?

    Dann stellt sich mir die frage, wie genau wird dieser ggt berechnet...
    Weil X ist ja unbekannt 😕

    vllt kann mir noch mal einer sagen wie genau für die funktion (13 + x * 17)^31 der ggt berechnet wird. und anschließend wie ich aus a^φ(4) oder auch 6 oder 10 mein phi berechne...

    Das will mir einfach noch nicht so ganz klar werden...

    EDIT: was mir noch aufgefallen ist:
    bei ^32 hätte ich ein problem da 2*16+0 raus käme 😕

    0
  • V

    Sqwan schrieb:

    Da kann ich jetzt mit zerlegung arbeiten. War was ist bei potenzen die sehr hoch sind? 5681 zum beispiel?

    Irgendwie ganz einfach irgendwie, nur ist Wikipedia-Mathematik wie immer nicht lesen.
    Zum Testsn, ob deine Vermutung stimmt, bietet sich schonmal
    http://www.wolframalpha.com/input/?i=phi(5681)
    an.
    Und bestimmt auch
    http://www.wolframalpha.com/input/?i=factor(5681)
    Ach ,ja, dann ist es einfach 12*18*22

    Bei Primzahlenpotentzen drin wie bei 13*13*1317=37349 gehts ein wenig anders.
    Irgendwie kommt 12*13*13    16 raus. Als wenn ein Primfaktor nur einmal das Recht hätte, als p-1 aufzutauchen und bei allen folgenden das nicht mehr darf.

    Ob das Sinn ergibt? Mal phi(27) anschauen.
    27=3*3*3.
    Es fallen nur 9 Zahlen raus, nämlich die durch 3 teilbaren. Durch 9 teilbare oder durch 27 teilbare sind ja schon raus, weil die ebenfalls durch 3 teilbar sind.
    Das würde zur Formel phi(pk)=pk-p^(k-1) führen. Ah, so stehts in Wikipedia.

    Meine ist gleich, wegen pk-p(k-1) = p*p(k-1)-1*p(k-1) = (p-1)*p^(k-1)

    Edit: Bisher dachte ich immer, man müsse zuerst die Primfaktoren sammeln und danach die Formel anwenden.
    Anscheinen nicht. Mal den Trick eingetippt.

    unsigned int phi(unsigned int n){
	unsigned int result=1;
	for(unsigned int t=2;n!=1;++t){
		if(n%t==0){
			result*=(t-1);
			n/=t;
			while(n%t==0){
				result*=t;
				n/=t;
			}
		}
	}
	return result;
}
    0
  • O

    Sqwan schrieb:

    EDIT: was mir noch aufgefallen ist:
    bei ^32 hätte ich ein problem da 2*16+0 raus käme 😕

    Ja, für ^32 hat die Gleichung auch keine Lösung.

    es muss ja auch nicht immer eine Lösung geben 🙂

    0
  • ?

    Hmmm,
    war das echt so durcheinander 🙂 ... naja, wie auch immer.

    Nochmal zum Trick mit dem Runterbrechen der Potenz.

    Du hasst ja folgende Gleichung:
    (13+x*17)^31 ≡ 3 (mod 4) [1]

    und dank Euler weißt du folgendes:
    (13+x*17)^2 ≡ 1 (mod 4) [2]

    Nun müssen wir den Euler irgendwie in unsere Gleichung einbringen. Um [2] in [1] einsetzen zu können, müssen wir [1] in eine Form bringen, in die wir [2] einsetzen können. Dh wir brauchen irgendwie in [1] > (13+x*17)^2 < drin. Also irgendwie ein ^2 😉

    Dafür wenden wir die Potenzgesetze an [1] an:
    (13+x*17)^31 ≡ 3 (mod 4)

    (13+x*17)^(2*15+1) ≡ 3 (mod 4) -- Dort steht ne 2, das ist für uns gut

    (13+x*17)^(2*15) * (13+x*17)^(1) ≡ 3 (mod 4) -- Addition der Exponenten, ist Multiplikation der Potenzen

    ((13+x*17)2)15 * (13+x*17)^(1) ≡ 3 (mod 4) -- Mutli Multi macht Expo Expo 🙂

    Nun da steht jetzt unsere tolle (13+x*17)^2 und dank Euler wissen wir das dies modulo 4 gleich 1 ist. Also 1 einsetzen:

    (1)^15 * (13+x17)^(1) ≡ 3 (mod 4)
    (13+x    17)^(1) ≡ 3 (mod 4)
    13+x*17 ≡ 3 (mod 4)

    0
Anmelden zum Antworten