Question

Welcher Rest entsteht bei Division von 11^{11^11} durch 7?

Answer 1

Aloha :)

Ich kenne mich mit Modulo-Rechnung nicht wirklich aus, habe aber trotzdem eine Lösung gefunden. Es kann also sein, dass es noch elegantere Lösungen gibt. Im Folgenden sollen alle Variablen natürliche Zahlen sein.

$$(a\cdot m+b)^n\text{ mod } m=\left(\sum\limits_{k=0}^n\left(\begin{array}{c}n\\k\end{array}\right)(a\cdot m)^{n-k}b^k\right)\text{ mod } m$$$$=\left(\sum\limits_{k=0}^{n-1}\left(\begin{array}{c}n\\k\end{array}\right)(a\cdot m)^{n-k}b^k+b^n\right)\text{ mod } m=b^n\text{ mod } m$$Die Summe enthält in jedem Summanden den Faktor \(m\) mindestens 1-mal und ist daher durch \(m\) teilbar, deswegen bleibt nur \(b^n\) übrig. Damit folgt:$$11^n\text{ mod } 7=(7+4)^n\text{ mod } 7=4^n\text{ mod } 7$$

Betrachte nun:$$(4^3\cdot a)\text{ mod } 7=(64\cdot a)\text{ mod } 7=(63\cdot a+a)\text{ mod } 7=a\text{ mod } 7$$$$\Rightarrow\quad\left\{\begin{array}{l}4^{3k} &\text{ mod } 7 & = (4^{3k}\cdot1)\text{ mod }7 & = 1\text{ mod }7 &=1\\4^{3k+1}&\text{ mod } 7 & = (4^{3k}\cdot4)\text{ mod }7 & = 4\text{ mod }7 &=4\\4^{3k+2}&\text{ mod } 7 & = (4^{3k}\cdot16)\text{ mod }7 & = 16\text{ mod }7 &=2\end{array}\right.$$Damit haben wir bisher:

$$11^n\text{ mod } 7=4^n\text{ mod } 7=\left\{\begin{array}{l}1 &\text{falls} & n\text{ mod }3=0\\4 &\text{falls} & n\text{ mod }3=1\\2 &\text{falls} & n\text{ mod }3=2\end{array}\right.$$Hier ist der Exponent nun \(n=11^{11}\) und nach dem oben gezeigten gilt:

$$n\text{ mod }3=11^{11}\text{ mod }3=(3\cdot3+2)^{11}\text{ mod }3=2^{11}\text{ mod }3=2048\text{ mod }3=2$$Damit liest man aus der Tabelle ab:$$11^{11^{11}}\text{ mod }7=2$$

Answer 2

Es kann also sein, dass es noch elegantere Lösungen gibt.

Ja ich denke schon. Da gibt es den Satz von Euler und Fermat, der da lautet:$$a^{\varphi(n)} \equiv 1 \mod n \quad a, n \in \mathbb{N}$$wobei \(\varphi\) die Eulersche Phi-Funktion ist. Und bei einer Primzahl \(p\) ist \(\varphi(p)=p-1\). Somit ist schon mal$$\begin{aligned} 11^{11^{11}} &\equiv x \mod 7 \\ \implies 11^k &\equiv x \mod 7 \quad  \text{mit} \quad 11^{11} \equiv k \mod 6 \color{grey}{= 7-1}\end{aligned}$$Mit Hilfe des oben erwähnten Satzes und \(\varphi(6)=2\) folgt:$$\begin{aligned} 11^{11} &\equiv k \mod 6 \\ 11^{2\cdot 5 + 1} &\equiv k \mod 6 \\ 11 &\equiv k \mod 6 \\ \implies k&= 5\end{aligned}$$ und mit der Tatsache dass man bei der Basis auch den Modulo anwenden kann (s. Antwort von Tschakabumba) geht es weiter$$\begin{aligned} 11^5&\equiv x \mod 7\\ 4^5 &\equiv x \mod 7\end{aligned}$$das geht schon fast im Kopf, wenn man sich auf den Rest nach der Division durch \(7\) beschränkt:$$\begin{aligned} 4^0 \equiv 1 \mod 7\\ 4^1 \equiv 4 \mod 7 \\ 4^2 \equiv 2 \mod 7  \\ 4^3 \equiv 1 \mod 7\end{aligned}$$d.h. beim Exponenten von \(3\) wiederholt sich das Ergebnis. Folglich ist$$\begin{aligned} 4^{5} &\equiv x \mod 7\\ 4^{3+2} &\equiv x \mod 7\\ 4^{2} &\equiv x \mod 7 \quad \implies x=2 \space \text{(s.o.)}\\ \implies 11^{11^{11}} &\equiv 2 \mod 7\end{aligned}$$