Question

Berechnen Sie z = 47²⁰¹ mod 11

Leider weiß ich hier kein Vorgehen, wie man die Potenz am besten auflöst.

Comments

$$ 47^{201}=\\12350070736587273937001679395270743486095013091697468851075098354568\\811210880269470278553888165291647203370115353221534145763110014944529\\889258804245703895182196842190708390435978578701660708737064158578272\\564318390053612777300840616063240338328246147355836390977638859332254\\70954644411784956646589995284626566506525941600398762553328047$$

Nun nur noch durch 11 dividieren ...    ;-)

---

Alternierende Quersumme ist -41 also ist die Potenz kongruent 3 mod 11

---

Python meint dazu:

>>> print(47**201)
1235007073658727393700167939527074348609501309169746885107509835456881121088026947027855388816529164720337011535322153414576311001494452988925880424570389518219684219070839043597857870166070873706415857827256431839005361277730084061606324033832824614735583639097763885933225470954644411784956646589995284626566506525941600398762553328047
>>> print(47**201%11)
3

Answer 1

Kleiner Satz von Fermat:

\(a^{p-1}\equiv\;1\;mod \;p\)

Kleiner Tipp vom Zaunpfahl: 11 ist eine Primzahl und a kann durchaus auch 47 sein.

"Verkürzte" Lösung: Es gilt \(47\equiv\;3\;mod \;11\)

Daraus folgt

\(47^2\equiv\;9\;mod \;11\)

\(47^4\equiv\;81\;\equiv\;4\;mod \;11\)

\(47^5\equiv\;4\cdot 3\equiv\;12\equiv\;1\;mod \;11\)

Damit hast du den Rest 1 schon bei der 5. Potenz (und nicht erst bei der 10. Potenz mit dem kleinen Fermat).

Answer 2

47^201 mod 11

Nach dem kleinen Fermat gilt 47^{11 - 1} mod 11 = 47^10 mod 11 = 1

= 47^200 * 47 mod 11

= (47^10)^20 * 47 mod 11

= 1^20 * 3 mod 11 = 3