Restklassen

Guten Abend !

Ich habe es so gemacht:

Dies kann man im Kopf rechnen :     2^1   modulo 7 = 2

                                                              2^2        "          = 4

                                                              2^3         "         = 1

                                                              2^4         "         =  2

                                                              2^5         "         =  4

                                                              2^6         "         =  1  

                                         und so weiter !

Es ist immer die gleiche Reihenfolge :  2-4-1    -2-4-1    -2-4-1     -2-4-1....

Hier die Exponenten. die zum Ergebnis  2  führen:    1   4   7  10   13   16  ...   94   97   100

Ergebnis:       $2^{100}modulo7=2$

Gruß radix !       Bestimmt gibt es eine elegantere Lösung !

Hallo  heureka !

Der Button  "Neue Antwort erstellen " ist bei mir wieder zu sehen und zu benutzen !!

Weshalb sollte es bei dir nicht so sein ????

Gruß radix !

Ich soll 2 hoch 100 modulo 7 ohne Taschenrechner rechnen wie mache ich das?

$\begin{array}{rcll} 2^{100}\pmod 7 \end{array}$

Da 7 und die 2 teilerfremd sind, bzw. der größte gemeinsame Teiler ggT (7, 2)  = 1 ist,

erhält man sofort  mit $\varphi(7) = 6$ den zweier Exponenten mit $2^6 \equiv 1 \pmod 7.$

wann der Rest 1 ist.

$\varphi{(n)}$ ist die Eulersche PHI-Funktion.

(Satz von Euler) 

Es sei $m \in N$,  $a \in Z$ und  ggT(a, m) = 1.

Dann ist  $a^{\varphi(m)} \equiv 1 \pmod m$.

Jetzt zerlegen wir den Exponenten, die 100, in ein Vielfaches von 6 und einem Rest. 

$100 = 6\cdot 16 + 4$

Wir erhalten:

$\begin{array}{rcll} 2^{6\cdot16 + 4}\pmod 7 \\ \equiv & 2^{6\cdot16}\cdot 2^{4}\pmod 7 \\ \equiv & (\underbrace{2^{6}}_{=1})^{16}\cdot 2^{4}\pmod 7 \qquad & | \qquad 2^6 \equiv 1 \pmod 7\\ \equiv & (1)^{16}\cdot 2^{4}\pmod 7 \qquad & | \qquad 1^{16} = 1 \\ \equiv & 1\cdot 2^{4}\pmod 7 \\ \equiv & 2^{4}\pmod 7 \\ \equiv & 16 \pmod 7 \\ \equiv & 2 \pmod 7 \\ \end{array}$

Der gesuchte Rest ist die 2