Aufgabe: Berechnen Sie 211^103 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^103 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^103 = 3^206 = (3^5)^40 * 3^6

= 243^40 * 729

= (202 + 41)^40 * (707 + 22)                           |modulo 101 

41^40 * 22

1681^20 * 22

(1616 + 65)^20 * 22                                         |modulo 101

65^20 * 22

4225^10 * 22

(4141 + 84)^10 * 22                                         |modulo 101

84^10 * 22

7056^5 * 22

(6969 + 87)^5 * 22                                         |modulo 101

87^5 * 22

7569^2 * 87 * 22

(7474 + 95)^2 *1914

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

95^2 * 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^103 mod 101 = (211 mod 101)^103 mod 101 = 9^103

Nun gilt aber:

9^1 mod 101 = 9
9^2 mod 101 = 81
9^4 mod 101 = 81^2 mod 101 = 6561 mod 101 = 97
9^8 mod 101 = 97^2 mod 101 = 9409 mod 101 = 16
9^16 mod 101 = 16^2 mod 101 = 256 mod 101 = 54
9^32 mod 101 = 54^2 mod 101 = 2916 mod 101 = 88
9^64 mod 101 = 88^2 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^103 mod 101 = ((((9^64 * 9^32) mod 101 * 9^4) mod 101 * 9^2) mod 101 * 9^1) mod 101 = 22
9^103 mod 101 = ((((68 * 88) mod 101 * 97) mod 101 * 81) mod 101 * 9) mod 101 = 22