Wie berechne ich modulo n einer Zahl mit großem Exponenten?

Question

Aufgabe

Hallo ich muss bei der Aufgabe 7^7654321 (mod 6) den kleinsten nichtnegativen Teilungsrest modulo n bestimmen. (ohne Taschenrechner)

Problem/Ansatz:

Grundsätzlich habe ich verstanden, dass ich den Rest angeben muss. Ich habe auch verstanden, dass ich den Exponenten aufteilen kann. Da ich 7654321 in dem Fall jedoch weder durch 2 noch durch 3 teilen kann, um so den Exponenten schrittweise zu Zerlegen stehe ich nun leider auf dem Schlauch.

Bisher habe ich immer z.B. bei 17⁷ (mod 5)

1.Schritt (17 mod 5)⁷ mod 5 gerechnet → 2⁷ mod 5

2. Schritt (2³ mod 5 * 2⁴ mod 5) mod 5 = 3

Da ich bei der gestellten Aufgabe 7^7654321 (mod 6) dennoch nicht weiter komme, hoffe ich, dass mir jemand helfen kann :)

Vielen lieben Dank !!!

Answer 1

Das schöne ist, du kannst bereits die Basis modulo 6 rechnen

Also

7^7654321 mod 6

= (7 mod 6)^7654321 mod 6

= 1^7654321 mod 6

= 1

Comments

Oh man, ja logisch !!! :)))

Vielen lieben Dank !!

Answer 2

7 = 6+1

                              .