Aufgabe: Berechnen Sie 211103 mod 101.

Question

wie berechne ich 211^103 mod 101?

Kann ich die Aufgabe so lösen: 211 mod 101 = 9  =>  211^103 mod 101 = 9^103 mod 101

Ist die Folgerung richtig? Und bringt Sie überhaupt etwas?

Comments

Ich kann auf die Schnelle nicht beweisen, dass das stimmt; hätte es wohl auch so gemacht und mindestens WolframAlpha kann etwas mit 9^103 mod 101 anfangen.

Allerdings kann man dort auch direkt 211^103 mod 101 eingeben.

https://www.wolframalpha.com/input/?i=211%5E103+mod+101

Das ging nun sogar wesentlich schneller, was daran liegen dürfte, dass sich WolframAlpha die Fragegeschichte merken kann.

Answer 1

habe auch keinen Lösungsweg, aber zum Spass etwas ausprobiert: 9^100 mod 101 gibt 1, könnte man somit "wegkürzen". 9^3 mod 101 ist dann trivial, gibt 22 und ist auch tatsächlich die Lösung.

Wenn man nun irgendwie beweisen könnte, wieso 9^100 mod 101 = 1 ist wäre das wohl eine Möglichkeit.

Übrigens ist auch 9^10'000 mod 101 = 1, 9^1000 aber nicht.

Answer 2

Man könnte das mit dem binomischen Lehrsatz begründen. Dabei genügt es sich zu überlegen, welche Potenzen von 202 und 9 zusammen vorkommen.

211^103 = (202 + 9)^103 = 202^103 + a202^102*9 + b 202^101 * 9^2 +… +x 202*9^102 + 9^103

9^103 ist hier der einzige Summand, der nicht durch 101 teilbar ist und hat somit modulo 101 den gleichen Wert wie 211^103

Comments

 

Fortsetzung, da 9¹⁰³ für meinen Taschenrechner noch zu gross:

In diesem Sinn kann man weitermachen. Mischprodukte, die den Faktor 101 enthalten jeweils weglassen. Binomische Formel und Distributivgesetz bedenken.

9¹⁰³ = 3²⁰⁶ = (3⁵)⁴⁰ * 3⁶

= 243⁴⁰ * 729

= (202 + 41)⁴⁰ * (707 + 22)                           |modulo 101 

41⁴⁰ * 22

1681²⁰ * 22

(1616 + 65)²⁰ * 22                                         |modulo 101

65²⁰ * 22

4225¹⁰ * 22

(4141 + 84)¹⁰ * 22                                         |modulo 101

84¹⁰ * 22

7056⁵ * 22

(6969 + 87)⁵ * 22                                         |modulo 101

87⁵ * 22

7569² * 87 * 22

(7474 + 95)² *1914

(7474 + 95)² *(1818 + 96)                         |modulo 101  : Mischprodukte aus Distributivgesetz alle weglassen

95² * 96

866'400 mod 101 = 22              schafft jetzt sogar mein Taschenrechner.

22 + 8578*101 = 866'400

 

 

Answer 3

Nach den Homomorphie-Regeln gilt:

(a * b) mod n = (a mod n * b mod n) mod n

Damit ist

211¹⁰³ mod 101 = (211 mod 101)¹⁰³ mod 101 = 9¹⁰³

Nun gilt aber:

9¹ mod 101 = 9
9² mod 101 = 81
9⁴ mod 101 = 81² mod 101 = 6561 mod 101 = 97
9⁸ mod 101 = 97² mod 101 = 9409 mod 101 = 16
9¹⁶ mod 101 = 16² mod 101 = 256 mod 101 = 54
9³² mod 101 = 54² mod 101 = 2916 mod 101 = 88
9⁶⁴ mod 101 = 88² mod 101 = 7744 mod 101 = 68

Bei der folgenden Rechnung machen wir uns zunutze, dass wir auch immer wieder Modulo 101 rechnen dürfen.

9¹⁰³ mod 101 = ((((9⁶⁴ * 9³²) mod 101 * 9⁴) mod 101 * 9²) mod 101 * 9¹) mod 101 = 22
9¹⁰³ mod 101 = ((((68 * 88) mod 101 * 97) mod 101 * 81) mod 101 * 9) mod 101 = 22