Berechne mit Rechenschritten: 7^8008 mod 5500.

Question

Aufgabe:

Berechne 7⁸⁰⁰⁸ mod 5500.

In einer Teilaufgabe davor wurde bereits φ(5500) = 2000 berechnet, woraus mit 8008 = 4 · 2000 + 8 dann
7⁸⁰⁰⁸ ≡ (7²⁰⁰⁰)⁴ · 7⁸ ≡ 7⁸ mod 5500

Kommt man hier mit Hirnschmalz weiter ohne den Taschenrechner zu benutzen?

Answer 1

7²⁰≡1 mod 5500

7^20·400≡1 mod 5500

7⁸≡801 mod 5500

7⁸⁰⁰⁸≡801 mod 5500.