Modulo vereinfachen?

Hallo,

dass bspw. 16 mod 21 zu (16-21) mod 21 umgeformt werden kann leuchtet mir ein. Warum funktioniert das aber auch bei:

16^n mod 21 = (16-21)^n mod 21? Gibt es eine Herleitung / Erklärung?

Answer 1

[Mathmaninoff, UserMod Light]

Beim binomischen Lehrsatz

$\left(a + b\right)^n = \sum_{k=0}^n\binom{n}{k}a^kb^{n-k}$ ist auf der rechten Seite nur ein Summand nicht durch b teilbar und zwar der für k = n. Dabei ist b ein Vielfaches von dem Modul; hier b = -21. Alle Summanden bis auf aⁿ sind ohne Rest durch 21 teilbar. Um den Rest zu bestimmen, muss deshalb nur dieser Summand betrachtet werden.

Bzw in dem Fall $\left(-5 + 21\right)^n = \left(-5\right)^n + 21 \cdot \left( \dots \right)$

Comments

[Thalexweiler]

Super Erklärung! Danke