+1 Daumen
331 Aufrufe


Welcher Rest entsteht bei Division von 1111^11 durch 7?

Ich weiß nicht, wie ich die Aufgabe berechnen soll, komme echt nicht weiter.

Kann mir jemand bitte helfen?

Mit freundlichen Grüßen

von

2 Antworten

+5 Daumen

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\mbox{ 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)\mbox{ 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)\mbox{ mod } m=b^n\mbox{ 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\mbox{ mod } 7=(7+4)^n\mbox{ mod } 7=4^n\mbox{ mod } 7$$

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

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

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

von 3,5 k
+3 Daumen

Hallo,

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{align} 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{align}$$Mit Hilfe des oben erwähnten Satzes und \(\varphi(6)=2\) folgt:$$\begin{align} 11^{11} &\equiv k \mod 6 \\ 11^{2\cdot 5 + 1} &\equiv k \mod 6 \\ 11 &\equiv k \mod 6 \\ \implies k&= 5\end{align}$$ und mit der Tatsache dass man bei der Basis auch den Modulo anwenden kann (s. Antwort von Tschakabumba) geht es weiter$$\begin{align} 11^5&\equiv x \mod 7\\ 4^5 &\equiv x \mod 7\end{align}$$das geht schon fast im Kopf, wenn man sich auf den Rest nach der Division durch \(7\) beschränkt:$$\begin{align} 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{align}$$d.h. beim Exponenten von \(3\) wiederholt sich das Ergebnis. Folglich ist$$\begin{align} 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{align}$$

von 19 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...