Modulare Exponentation

Question

wie kann ich 238 hoch 238 hoch 238 mod 59 berechnen? (Kann es hier nicht richtig darstellen)

Bei 238^238 wüsste ich es, aber hier fehlt mir das Verständnis.

Danke und Gruß

Comments

$$ {238^{238}}^{238} \mod 59$$

Answer 1

benutze die Formel $$ (a^n)\mod(k)=\Big((a)\mod(k)\Big)^n \mod(k) $$
Unter diesen Umständen musst du die Formel mehrmals anwenden, um dann auf den Rest zu kommen. Hier mal ein kleineres Beispiel:
$$ (8^{8^8}) \mod (7)=\Big((8^8)\mod(7)\Big)^8\mod(7)\\=\Bigg(\Big((8)\mod(7)\Big)^8\mod(7)\Bigg)^8\mod(7)\\=\Bigg(\Big(1^8\Big)\mod(7)\Bigg)^8\mod(7)\\=\Bigg((1)\mod(7)\Bigg)^8\mod(7)\\=\Bigg(1^8\Bigg)\mod(7)\\=(1)\mod(7)=1$$

Answer 2

  Potenzieren ist nicht assoziativ; vernünftiger wäre es, das mit Klammern zu schreiben.

    (  238  ^  (  238  ^  238  )  )       (  1  )

    Der  ===>  Restklassenkörper

     F_59  :=  |Z  /  59  |Z       (  2  )

   enthält die multiplikative Gruppe G_59  der 58.  ===>  Einheitswurzeln  alle außer der Null . Daher gilt allgemein

      x  ^  58  =  1       (  3  )

        (  Das folgt bereits aus   ° G = 58 )

    238  =  2  mod  59       (  4a  )

     238  =  4  X  58  +  6     (  4b  )

   238  ^  238  =  2  ^  (  58  X  4  +  6  )  =  (  4c  )

   =  (  2  ^  58  )  ^ 4  X  2  ^  6  =    (  4d  )

      =  1  ^  4  X  5  =  5      (  4e  )

   Summa summarum willst du also  2  ^  5 bilden  , und das ist  (  -  27  )

Comments

https://www.wolframalpha.com/input/?i=238%5E238%5E238+mod+59

Ergebnis ist 57, was auch mit der Lösung meines Dozenten übereinstimmt.

---

  Ich mache jetzt mal einen heuristischen Anlauf; wer einen systematischen Ansatz weiß, melde sich .  Mein letztes richtiges Ergebnis

     x  ^  238  =  x  ^  6       (  2.1a  )

     und induktiv aus ( 2.1a )

     x  ^  (  238  ^  k  )  =  x  ^  (  6  ^  k  )     (  2.1b  )

     Und   das macht die ganze Chose erträglich .  G_59   enthält  58 Einheitswurzeln - mit  Berücksichtigung des Vorzeichwns Plus / Minus effektiv nur 29 . Davon geht die 1 ab als Fixpunkt; unser Zyklus ist höchstens 28 Elemente lang .

    Ich meine mit Wolframs Hilfe werden wir die Folge  <  2 ^ (  6  ^  k  )  >  aufstellen - wie war das genau mit dem Fixpunkt?

     Könnte es sein, dass wir uns auf einen Fixpunkt fest beißen

      x  ^  6  =  x  ===>  x  ^  5  =  1        (  2.2a  )

    In jeder Gruppe G ist die Ordnung einer Untergruppe  U ein Teiler

     °  U  |  °  G           (  2.2b  )

    Die Einheitswurzelgruppen   G_p   der ===>  Galoisfelder F_p  sind zyklisch; hier gilt auch die Umkehrung .  Zu jedem Teiler t  von G_p   gibt es genau eine Untergruppe   G_p ( t )  der t-ten einheitswurzeln .  Wir haben 58 = 2 * 29 ;  5 ist kein Teiler von 58 .  Daher kann es nur die triviale 5. Einheitswurzel  1  geben ;  und unsere Sexerfolge bildet tatsächlich einen Zyklus .

    2  ^  (  6  ^  0  )  =  2            (  2.3a  )

    2  ^  (  6  ^  1  )  =  2  ^  6  =  5        (  2.3b  )

   2  ^  6  ²  =  5  ^  6  =  (  -  10  )      (  2.3c  )

   2  ^  6  ³  =  10  ^  6  =  9      (  2.3d  )

   2  ^  (  6  ^  4  )  =  9  ^  6  =  28        (  2.3e  )

  2  ^  (  6  ^  5  )  =  28  ^  6  =  16        (  2.3f  )
  2  ^  (  6  ^  6  )  =  16  ^  6  =  ( - 24 )        (  2.3g  )

  2  ^  (  6  ^  7  )  =  24  ^  6  =  29        (  2.3h  )
  2  ^  (  6  ^  8  )  =  29  ^  6  =  12        (  2.3i  )

  2  ^  (  6  ^  9  )    =  12  ^  6  =   ( - 6 )        (  2.3j  )
  2  ^  (  6  ^  10  )  =    6  ^  6  =  ( - 13 )        (  2.3k  )

  2  ^  (  6  ^  11  )  =  13  ^  6  =  19        (  2.3l  )
  2  ^  (  6  ^  12  )  =  19  ^  6  =  ( - 11 )        (  2.3m  )

  2  ^  (  6  ^  13  )  =  11  ^  6  =  27        (  2.3n  )
  2  ^  (  6  ^  14  )  =  27  ^  6  =  ( - 2 )        (  2.3o  )

   Also vom der Idea her doch richtig. Die Periodenlänge der 6. Potenz beträgt  14 nach ( 2.3o )  Hier wer kann noch großes 1 X 1 ?  119  =  7  X  17  ;  238  =  14  X  17 - quasi das ganz große 1 X  1  .  Und zwar bekommst du ei Minuszeichen immer bei einem ungeraden Vielfachen von 14 - in ( 2.3o )  1 X 14 , in der 238_er Periode 17 X 14 .