0 Daumen
1,2k Aufrufe

Aufgabe:

Screenshot_3.png


Problem/Ansatz:

Screenshot_4.png

Wie kommt man hier von phi(10) = 4 auf 2007 kongruent 3 (mod 4) und auf die Folgerung, dass das ganze auch bei (mod 10) gilt? Also von 72007 auf 73 ? bzw. wieso nimmt man überhaupt phi(10) was interessieren denn die teilerfremden Zahlen?

Avatar von

2 Antworten

+1 Daumen
 
Beste Antwort

Wegen ggT(7,10)=1 gilt nach dem Satz von Euler-Fermat $$7^{\varphi(10)}=7^4\equiv 1 \text{ (mod 10)}.$$Das hätte man natürlich auch völlig ohne diesen Satz durch Nachrechnen wissen können, aber so wird der Zusammenhang mit der Eulerschen phi-Funktion deutlich.

Wenn wir das nun wissen, folgt sofort$$7^{2007}\equiv 7^{2007\text{ (mod 4)}}\equiv 7^3 \equiv 343 \equiv 3 \text{ (mod 10)}.$$

Avatar von 26 k

Wie kommt man von 7≡ 1 (mod 10) zu 72007(mod 4) woher kommt die mod 4 plötzlich? 

woher kommt die mod 4 plötzlich? 

wenn Du die 7 mit sich selbst malnimmst und dabei nur die letzte Stelle (im Dezimalsystem) betrachtest, gibt das diese Folge $$7 \to (4)9 \to (6)3 \to (2)1 \to 7$$d.h. es ist eine ständige Wiedeholung der 4'er-Sequenz \(7,\, 9,\, 3,\, 1\). Für die letzte Dezimalstelle ist es also irelevant ob man die \(7\) mit \(3\) oder mit \(501 \cdot 4 + 3 = 2007\) potenzierst. Das Ergebnis ist immer \(=3\).

0 Daumen

Betrachte (xi) = (f(1), ..., f(n)) mit f(i) = 7i (mod 10) für i = 1, ..., n und n ∈ ℵ. Die hinterste Stelle einer Multiplikation a * b hängt eben nur von den letzten beiden Ziffern von jeweils a und b ab, sodass wir uns Rechenarbeit sparen können. Es gilt also:

(xi) = (7, 9, 3, 1, 7 ...)

Wie man sieht, wiederholt sich die Folge nach der vierten Zahl. 10 hat also nur 4 teilerfremde Zahlen, bzw. φ(10) = 4.

D.h. für jedes vierte i ist f(i) die selbe Zahl. Anders gesagt: f(i) = f(i mod φ(10)) = f(i mod 4).

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community