Auf welche Ziffer endet die Zahl 20072007?

Question

Aufgabe:

Problem/Ansatz:

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 7²⁰⁰⁷ auf 7³ ? bzw. wieso nimmt man überhaupt phi(10) was interessieren denn die teilerfremden Zahlen?

Answer 1

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)}.$$

Comments

Wie kommt man von 7⁴ ≡ 1 (mod 10) zu 7^{2007(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$.

Answer 2

Betrachte (x_i) = (f(1), ..., f(n)) mit f(i) = 7ⁱ (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:

(x_i) = (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).