Geschickte Ausnutzung des Satzes von Euler, Verständnisproblem ( elemetare Zahlentheorie)

04.04.2010, 13:37

Kerstin H.

Geschickte Ausnutzung des Satzes von Euler, Verständnisproblem ( elemetare Zahlentheorie)

Hallo allerseits und erstmal Frohe Ostern,

ich hatte in der letzten Klausur folgende Aufgaben:

1. Zeige, dass $\begin{eqnarray*} x^7 \end{eqnarray*}$ und $\begin{eqnarray*} x^3 \end{eqnarray*}$ für alle $\begin{eqnarray*} x \in ~\mathbb N \end{eqnarray*}$ immer die gleiche Einerstelle haben.

Mein Lösungsansatz war folgender:

wenn $\begin{eqnarray*} x^7 \end{eqnarray*}$ und $\begin{eqnarray*} x^3 \end{eqnarray*}$ die gleiche Einerstelle haben, kann man auch sagen:

$\begin{eqnarray*} x^7 \equiv x^3 \, (mod \, 10) \end{eqnarray*}$

Die Definition von Kongruenzen liefert dann :

$\begin{eqnarray*} 10 | x^7 -x^3 \end{eqnarray*}$
Dort kam ich dann nicht weiter. Mein Dozent gab nun folgenden Hinweis:

Ausklammer von x^3 bringt:

$\begin{eqnarray*} 10|x^3(x^4-1) \end{eqnarray*}$ soweit klar. Dannach macht man eine Fallunterscheidung.

Fall 1: $\begin{eqnarray*} x \equiv 0 (mod 10) \rightarrow x^3 \equiv 0(mod 10) \end{eqnarray*}$

Daraus folgt dann in der Restklassenmultiplikation $\begin{eqnarray*} x^3 (x^4-1) \equiv 0 (mod 10) \end{eqnarray*}$

Fall 2: $\begin{eqnarray*} x \not\equiv 0 (mod 10) \end{eqnarray*}$ In dem Fall nutzt man Euler aus und sagt $\begin{eqnarray*} x^{\varphi{(10)}} \equiv 1 (mod 10) \end{eqnarray*}$

Und dies liefert (rein zufällig natürlich) $\begin{eqnarray*} x^4 \equiv 1 (mod 10) \end{eqnarray*}$ bzw. somit $\begin{eqnarray*} x^4-1\equiv 0 (mod 10) \end{eqnarray*}$

Dieser Fall fürht dann wegen den Regeln der Restklassenmultiplikation zu
$\begin{eqnarray*} x^3 (x^4-1) \equiv 0 (mod 10) \end{eqnarray*}$

Damit soll dann gezeigt sein, dass x^3 und x^7 immer die gleiche Einerstelle haben.

Was ich nun nicht verstehe ist, warum man im ersten Fall von $\begin{eqnarray*} x \equiv 0 (mod 10 ) \end{eqnarray*}$ ausgehen kann und warum es nur diese beiden Fälle gibt.

$\begin{eqnarray*} x^{\varphi{(10)}} \equiv 1 \end{eqnarray*}$ geht doch nur bei $\begin{eqnarray*} ggT(x, 10) =1 \end{eqnarray*}$ Oder??

Aber z.B. für x=4 gilt weder $\begin{eqnarray*} x \equiv 0 (mod 10) \end{eqnarray*}$ noch kann man die Eulersche Phi-funktion nutzen, da $\begin{eqnarray*} ggT(4,10)\not=1 \end{eqnarray*}$

Also habe ich wohl irgendwo einen Verständnisfehler?

Wenn ich das verstanden hätte, könnte ich wohl die zweite Aufgabe lösen.

2. Hier heißt es: Finde ein n für das gilt: Bei $\begin{eqnarray*} x^n \end{eqnarray*}$ und $\begin{eqnarray*} x^2 \end{eqnarray*}$ sind die letzten beiden Stellen gleich.

Dies würde ja heißen:

$\begin{eqnarray*} x^n \equiv x^2 (mod 100) \end{eqnarray*}$ bzw. $\begin{eqnarray*} 100| x^n - x^2 \end{eqnarray*}$
$\begin{eqnarray*} \rightarrow 100| x^2 (n^{(n-2)} -1) \end{eqnarray*}$

Dann sollte der Ansatz sein: Für $\begin{eqnarray*} ggT(n, 100) = 1 \end{eqnarray*}$ gilt $\begin{eqnarray*} x^{\varphi {(100)}} \equiv 1 (mod 100) \end{eqnarray*}$ bzw. $\begin{eqnarray*} x^{\varphi {(100)}}-1 \equiv 0 (mod 100) \end{eqnarray*}$

Warum $\begin{eqnarray*} ggt(n,100) = 1 \end{eqnarray*}$ und nicht $\begin{eqnarray*} ggT (x,100)=1 \end{eqnarray*}$ ???

Nun hat man also wieder die gleiche Fallunterscheidung wie in Aufgabe 1, die ich schon dort nicht verstanden habe.

Entweder $\begin{eqnarray*} x \equiv 0 (mod 100) \rightarrow x^2 \equiv 0 (mod 100) \end{eqnarray*}$

Und somit liefert die Restklassenmultiplikation, dass $\begin{eqnarray*} x^2(x^{\varphi{(100)}}-1) \equiv 0 (mod 100) \end{eqnarray*}$

bzw. Fall 2:
$\begin{eqnarray*} x\equiv 0 (mod 100) \rightarrow x^2 \equiv 0 (mod 100) \end{eqnarray*}$

und die Restklassenmultiplikation liefert dann $\begin{eqnarray*} x^2(x^{\varphi{(100)}}-1) \equiv 0 (mod 100) \end{eqnarray*}$

Einsetzen von $\begin{eqnarray*} \varphi{(100)} = 40 \end{eqnarray*}$ und ausmultiplizieren der Klammern liefert dann $\begin{eqnarray*} n= 42 \end{eqnarray*}$

Dennoch habe ich hier das gleiche Problem wie bei 1. Wieso hat man nun alle Fälle abgedeckt? Denke seit etwa 20 Stunden darüber nach und es dreht sich nur noch alles. Ich vermute mal, es ist verdammt simpel?

Vielen Dank für die Hilfe.

LG

Kerstin

04.04.2010, 14:37

MLRS

Auf diesen Beitrag antworten »

RE: Geschickte Ausnutzung des Satzes von Euler, Verständnisproblem ( elemetare Zahlentheorie)
@ Mods: Weil es eine Klausuraufgabe war und bereits eine Lösung vorgeschlagen wurde habe ich mir erlaubt eine Komplettlösung zu schreiben

Ich habe deine Lösung nicht genau angesehen - dafür aber einen alternativen Weg:

Zitat:

Original von Kerstin H.
1. Zeige, dass $\begin{eqnarray*} x^7 \end{eqnarray*}$ und $\begin{eqnarray*} x^3 \end{eqnarray*}$ für alle $\begin{eqnarray*} x \in ~\mathbb N \end{eqnarray*}$ immer die gleiche Einerstelle haben.

$\begin{eqnarray*} 10 | x^7 -x^3 \end{eqnarray*}$

Ab hier folgendes:

$\begin{eqnarray*} x^7 -x^3=x^3(x^4-1)=x^3(x^2-1)(x^2+1)=x^3(x+1)(x-1)(x^2+1) \end{eqnarray*}$

Außerdem ist $\begin{eqnarray*} 10| x^2+1 \iff 10| x^2-9 \end{eqnarray*}$

und $\begin{eqnarray*} x^2-9=(x-3)(x+3) \end{eqnarray*}$

Wir haben also:
$\begin{eqnarray*} 10| x^7 -x^3 \iff 10| (x-3)(x-1)x^3(x+1)(x+3) \end{eqnarray*}$

Weil mind. 1 der 5 Faktoren rechts immer gerade ist (Klar?) muss nur noch Teilbarkeit durch 5 überprüft werden.

aber mod 5 gilt:
$\begin{eqnarray*} (x-3)(x-1)x^3(x+1)(x+3) \equiv (x+2)(x+4)x^3(x+1)(x+3) \end{eqnarray*}$

...und jetzt sollte es klar sein. Augenzwinkern

hoffe, ich hab jetzt keinen fehler gemacht

05.04.2010, 06:26

Kerstin H.

Auf diesen Beitrag antworten »

Fast geschafft, aber noch ein kleines Problem im letzten Absatz...
Guten morgen allerseits,vielen Dank erstmal an MLRS für die Hilfe,

Dennoch versuche ich weiter, die Lösung mit der $\begin{eqnarray*} Eulerschen \varphi -Funktion \end{eqnarray*}$ zu verstehen, da ich sonst in Aufgabe 2 an meine Grenzen stoße. Ich denke allerdings, dass ich den Tipp meines Dozenten zu sehr als Lösung anstatt als Lösungsansatz verstanden habe. Also alles auf Anfang:

Für Aufgabe 1 gilt ja nun, zu zeigen, dass immer gilt

$\begin{eqnarray*} 10|x^3 (x^4-1) \end{eqnarray*}$

Dies kann gezeigt werden, indem man zeigt $\begin{eqnarray*} 2|x^3 (x^4-1) \end{eqnarray*}$ in jedem Fall und $\begin{eqnarray*} 5|x^3 (x^4-1) \end{eqnarray*}$ in jedem Fall, da die Primfaktorzerlegung von $\begin{eqnarray*} 10= 2 \cdot 5 \end{eqnarray*}$

Die Teilbarkeit durch 2 ist ja schnell gezeigt, durch die beiden Fälle
a) $\begin{eqnarray*} 2|x \end{eqnarray*}$
in dem Fall ist $\begin{eqnarray*} x \end{eqnarray*}$ durch 2 teilbar, also auch $\begin{eqnarray*} x^3 \end{eqnarray*}$ teilbar und somit auch das Produkt $\begin{eqnarray*} x^3 (x^4-1) \end{eqnarray*}$

b) $\begin{eqnarray*} 2\not| x \end{eqnarray*}$

Das kann man mit Kongruenzen zeigen, ist aber auch klar, wenn $\begin{eqnarray*} x \end{eqnarray*}$ ungerade ist, ist auch $\begin{eqnarray*} x^4 \end{eqnarray*}$ undgerade, allerdings $\begin{eqnarray*} (x^4-1) \end{eqnarray*}$ gerade. Es gilt also $\begin{eqnarray*} 2|x^4-1 \end{eqnarray*}$ und somit auch

Die Teilbarkeit durch 5 ist auch schnell gezeigt, ebenfalls durch eine Fallunterscheidung.

c) Gilt $\begin{eqnarray*} 5|x \end{eqnarray*}$ , geht es analog zu a) weiter und es gilt auch $\begin{eqnarray*} 5|x^3 (x^4-1) \end{eqnarray*}$

d) Gilt $\begin{eqnarray*} 5\not| x \end{eqnarray*}$

sind $\begin{eqnarray*} 5 \end{eqnarray*}$ und $\begin{eqnarray*} x \end{eqnarray*}$ teilerfremd und es greift die $\begin{eqnarray*} Eulersche \varphi -Funktion \end{eqnarray*}$

(Ich denke, hier war nun mein Denkfehler, da $\begin{eqnarray*} \varphi (5) = 4 \end{eqnarray*}$ und $\begin{eqnarray*} \varphi (10) = 4 \end{eqnarray*}$ )

Weil gilt $\begin{eqnarray*} x^{\varphi{(5)}} \equiv 1 (mod 5) \end{eqnarray*}$

gilt also $\begin{eqnarray*} 5| x^{\varphi (5)} - 1 \end{eqnarray*}$ und somit auch $\begin{eqnarray*} 5|x^3 (x^4-1) \end{eqnarray*}$

Somit gilt für alle x die Teilbarkeit durch 2 und 5 und daraus folgt die Teilbarkeit durch 10. Der Fall ist also gezeigt.

Bei Aufgabe 2 habe ich dennoch ein Problem.
Dies kann ja nun (fast?) analog gezeigt werden.

Da $\begin{eqnarray*} 100 = 2^2 \cdot 5^2 \end{eqnarray*}$ , und $\begin{eqnarray*} 100| x^2 (x^{(n-2)} -1) \end{eqnarray*}$ muss also gezeigt werden, dass für alle $\begin{eqnarray*} x^2 \end{eqnarray*}$ bzw. $\begin{eqnarray*} (x^{(n-2)} -1) \end{eqnarray*}$ die Teilbarkeit durch $\begin{eqnarray*} 2^2 \end{eqnarray*}$ und $\begin{eqnarray*} 5^2 \end{eqnarray*}$ gegeben ist??, wobei wir für $\begin{eqnarray*} (x^{(n-2)} -1) \end{eqnarray*}$ folgendes einsetzen: $\begin{eqnarray*} x^{\varphi (100)} \end{eqnarray*}$ , und $\begin{eqnarray*} \varphi (100) = 40 \end{eqnarray*}$ , also $\begin{eqnarray*} x^{40} \end{eqnarray*}$ .

Ich benenne die nachweise jetzt analog zu Aufgabe 1 mit a) $\begin{eqnarray*} ( 2|x) \end{eqnarray*}$ , b) $\begin{eqnarray*} (2 \not | x) \end{eqnarray*}$ , c) $\begin{eqnarray*} ( 5|x) \end{eqnarray*}$ und d) $\begin{eqnarray*} (5 \not | x) \end{eqnarray*}$

Die Fälle a) und c) sind klar.

wenn gilt, $\begin{eqnarray*} 2|x \end{eqnarray*}$ , dann gilt auch $\begin{eqnarray*} 2|x^2 \end{eqnarray*}$ bzw. sogar $\begin{eqnarray*} 2^2|x^2 \end{eqnarray*}$ und somit auch $\begin{eqnarray*} 2^2| x^2 (x^{40} -1) \end{eqnarray*}$

das kann auch analog für c) gezeigt werden.

Nun habe ich nur noch Schwierigkeiten mit den Fällen b) und d)

Ich kann zwar zeigen, dass $\begin{eqnarray*} 2| x^{40} -1 \end{eqnarray*}$ , aber wie zeige ich, dass $\begin{eqnarray*} 2^2| x^{40} -1 \end{eqnarray*}$ ?

Das gleiche gilt für $\begin{eqnarray*} 5 \end{eqnarray*}$ bzw. $\begin{eqnarray*} 5^2 \end{eqnarray*}$

Ich vermute, dass man irgendwas ausklammern muss?

P.S.: Ich weiß jetzt auch, dass man die $\begin{eqnarray*} Eulersche \varphi -Funktion \end{eqnarray*}$ benutzten kann, weil man zunächst die Teilbarkeit durch $\begin{eqnarray*} 2 \end{eqnarray*}$ modulo $\begin{eqnarray*} 2 \end{eqnarray*}$ untersucht für die Fälle $\begin{eqnarray*} 2|x \end{eqnarray*}$ und $\begin{eqnarray*} 2 \not |x \end{eqnarray*}$ und danach die Teilbarkeit durch $\begin{eqnarray*} 5 \end{eqnarray*}$ modulo $\begin{eqnarray*} 5 \end{eqnarray*}$ untersucht für die Fälle $\begin{eqnarray*} 5|x \end{eqnarray*}$ und $\begin{eqnarray*} 5 \not |x \end{eqnarray*}$ Ich denke, da war mein Hauptdenkfehler am Anfang....

06.04.2010, 09:40

Auf diesen Beitrag antworten »

So wie ich das sehe, hast du im allerletzten Satz deinen Denkfehler schon selbst gefunden:

Zitat:

Original von Kerstin H.
Fall 2: $\begin{eqnarray*} x \not\equiv 0 (mod 10) \end{eqnarray*}$ In dem Fall nutzt man Euler aus und sagt $\begin{eqnarray*} x^{\varphi{(10)}} \equiv 1 (mod 10) \end{eqnarray*}$

Das stimmt nämlich nicht: Den Satz von Euler kannst du nur anwenden, wenn $\begin{eqnarray*} x \end{eqnarray*}$ teilerfremd zu 10 ist - dazu genügt aber $\begin{eqnarray*} x \not\equiv 0 \bmod 10 \end{eqnarray*}$ nicht, sondern $\begin{eqnarray*} x \end{eqnarray*}$ darf weder durch 2 noch durch 5 teilbar sein.

Kurz gesagt:

Die Aussagen $\begin{eqnarray*} x\not\equiv 0 \bmod n \end{eqnarray*}$ sowie " $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ sind teilerfremd" sind nur dann äquivalent, falls $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl ist. Und davon kann bei $\begin{eqnarray*} n=10 \end{eqnarray*}$ keine Rede sein. Augenzwinkern

06.04.2010, 09:51

Kerstin H.

Auf diesen Beitrag antworten »

Genau das habe ich dann in meinem nächsten Post versucht anzuwenden, in dem ich bei Aufgabe die Teilbarkeit durch 2 und durch 5 getrennt nachweise. Aber Bei Aufgabe 2 stoße ich trotzdem auf ein Problem, da ich zwar für den Fall $\begin{eqnarray*} 2|x \rightarrow 2^2 | x^2 \end{eqnarray*}$ und analog dazu 5|x usw. schnell fertig bin, aber ich bekomme irgendwie nicht die Teilbarkeit $\begin{eqnarray*} 2^2| x^{\varphi (100)}-1 = 2^2 | x^{40} -1 \end{eqnarray*}$ und das gleiche für $\begin{eqnarray*} 5^2 \end{eqnarray*}$ nachgewiesen.....

Oder habe ich in meinem zweiten Post bezüglich Aufgabe 1 noch immer einen Fehler?

Würde mich auch nicht wundern. Augenzwinkern

Auf jeden Fall schon einmal DANKE!!

06.04.2010, 11:02

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Kerstin H.
[...] aber ich bekomme irgendwie nicht die Teilbarkeit $\begin{eqnarray*} 2^2| x^{\varphi (100)}-1 = 2^2 | x^{40} -1 \end{eqnarray*}$ und das gleiche für $\begin{eqnarray*} 5^2 \end{eqnarray*}$ nachgewiesen.....

Das ist ja auch nicht richtig und von daher ist es auch nicht erstaunlich, dass es dir nicht gelingt, das zu zeigen... Irgendwie kommst du mir vor wie ein Bogenschütze, der 20 Schüsse auf das Ziel abfeuert, in der Hoffnung, einer von ihnen möge schon ins Schwarze treffen, statt einmal, und sei es auch nur ein einziges Mal, richtig zu zielen...

Tatsächlich ist es so, dass das Polynom

$\begin{eqnarray*} x^2(x^{n-2}-1) \in \mathbb{Z}_{25}[x] \end{eqnarray*}$

genau dann identisch verschwindet, wenn

$\begin{eqnarray*} n =2+20k \ (k \in \mathbb N) \end{eqnarray*}$

ist, sodass also n=22 die kleinste in Frage kommende Lösung ist, da die zweite Bedingung, nämlich die Teilbarkeit von $\begin{eqnarray*} x^2(x^{n-2}-1) \end{eqnarray*}$ durch 4 für beliebiges ganzes x, für gerade n überhaupt automatisch erfüllt ist...

06.04.2010, 12:51

Kerstin H.

Auf diesen Beitrag antworten »

wars das jetzt? Letzte Zeile....
Also das mit dem Bogenschützen ist ein netter Vergleich, aber ich versuche ja auch die Aufgabe "von hinten" aufzurollen, da mir mein Dozent ja Hinweise gegeben hat, mit denen ich offensichtlich nicht zurecht komme.

Aber mal wieder eine weitere Idee zu Aufgabe 2.

Die Frage war ja nach einem n, das so gewählt ist, dass $\begin{eqnarray*} 100| x^2 (x^{(n-2)} -1) \end{eqnarray*}$ erfüllt ist. Dazu setzt man praktischer weise $\begin{eqnarray*} x^{(n-2)} = x^{\varphi (100)} \end{eqnarray*}$ , da wir die Teilbarkeit durch 100 zeigen wollen (also bei Rechnen mit Kongruenzen modulo 100).

Nun habe ich in meinem anderen Post schon dargelegt, dass $\begin{eqnarray*} 100| x^2 (x^{40} -1) \end{eqnarray*}$ schnell gezeigt ist für den Fall, dass $\begin{eqnarray*} 2|x \end{eqnarray*}$ bzw. $\begin{eqnarray*} 5|x \end{eqnarray*}$ . Nun wollte ich also Zeigen, dass gilt $\begin{eqnarray*} 5^2|(x^{40} -1) \end{eqnarray*}$ , wenn $\begin{eqnarray*} ggT(5,x) = 1 \rightarrow ggT(25,x)=1 \end{eqnarray*}$ und $\begin{eqnarray*} 2^2|(x^{40} -1) \end{eqnarray*}$ wenn gilt, $\begin{eqnarray*} ggT(2,x) = 1 \rightarrow ggT(4,x)=1 \end{eqnarray*}$ , da dann auch gilt $\begin{eqnarray*} 100|x^{40} -1) \end{eqnarray*}$ , so dass auch in diesem Fall gilt $\begin{eqnarray*} 100| x^2 (x^{40} -1) \end{eqnarray*}$ , denn dann hätte man ja das n gefunden.
(Denn wenn dies alles gilt, kann man ja die Klammer wieder ausmultiplizieren und erhält $\begin{eqnarray*} 100| x^2 (x^{40} -1) = x^{42} - x^2 \end{eqnarray*}$ und dann würde gelten $\begin{eqnarray*} x^2 \equiv x^{42} (mod100) \end{eqnarray*}$ , also $\begin{eqnarray*} n = 42 \end{eqnarray*}$ )

Ich glaube, ich habe es auch gelöst:
für den Fall $\begin{eqnarray*} 5 \not | x \end{eqnarray*}$
$\begin{eqnarray*} ggT(5,x) = 1 \rightarrow ggT(25,x)=1 \end{eqnarray*}$ Dazu sagt Euler:

$\begin{eqnarray*} x ^{\varphi (25)} \equiv 1 (mod 25), \varphi (25) = 20 \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow (x^{20})^2 \equiv 1^{2} (mod 25) \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow x^{40} \equiv 1 (mod 25) \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow 25 |x^{40} - 1 \end{eqnarray*}$

Für den Fall $\begin{eqnarray*} 2 \not | x \end{eqnarray*}$
$\begin{eqnarray*} ggT(2,x) = 1 \rightarrow ggT(4,x)=1 \end{eqnarray*}$ Dazu sagt Euler wieder:

$\begin{eqnarray*} x ^{\varphi (4)} \equiv 1 (mod 4) \end{eqnarray*}$ , $\begin{eqnarray*} \varphi (4) = 2 \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow (x^{2})^{20} \equiv 1^{20} (mod 4) \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow x^{40} \equiv 1 (mod 4) \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow 4 |x^{40} - 1 \end{eqnarray*}$

Da $\begin{eqnarray*} 25|x^{40} - 1 \end{eqnarray*}$ und $\begin{eqnarray*} 4 |x^{40} - 1 \rightarrow 100 |x^{40} - 1 \end{eqnarray*}$

und damit auch $\begin{eqnarray*} 100 |x^2 (x^{40} - 1) \end{eqnarray*}$

Aber habe ich jetzt gezeigt, dass dies immer gilt und meine Wahl $\begin{eqnarray*} n = 42 \end{eqnarray*}$ rechtfertigt?

kiste: ggT-Ausdrücke korrigiert

06.04.2010, 14:51

Mystic

Auf diesen Beitrag antworten »

RE: wars das jetzt? Letzte Zeile....
Ich würde mal so sagen: Es ist insgesamt alles da, was man braucht, um diese Aufgabe zu lösen, die Art, wie du das Ganze in Einzelteile auseinanderbrichst, will mir aber einfach nicht gefallen...

Machen wir's doch mal umgekehrt, ich stelle eine Reihe von Feststellungen zusammen und du sagst mir, wo wir genau auseinander divergieren (wenn überhaupt)...

Feststellung 1:

Für jede Primzahl p hat die Kongruenz

$\begin{eqnarray*} x^2(x^{n-2}-1) \equiv 0 \mod p^2 \quad (*) \end{eqnarray*}$

genau dann alle ganzen Zahlen als Lösung, wenn gilt

$\begin{eqnarray*} n \equiv 2 \mod p(p-1) \end{eqnarray*}$

Beweis: Dies ist für $\begin{eqnarray*} p|x \end{eqnarray*}$ wegen $\begin{eqnarray*} p^2|x^2 \end{eqnarray*}$ trivial und folgt für $\begin{eqnarray*} p \not | x \end{eqnarray*}$ aus $\begin{eqnarray*} x^{\varphi(p^2)} \equiv 1 \mod p^2 \end{eqnarray*}$ unter Verwendung von $\begin{eqnarray*} \varphi(p^2) = p(p-1) \end{eqnarray*}$ . (Man benötigt hier, dass $\begin{eqnarray*} \varphi(p^2) = p(p-1) \end{eqnarray*}$ nicht nur die Ordnung, sondern sogar der Exponent der primen Restklassengruppe mod $\begin{eqnarray*} p^2 \end{eqnarray*}$ ist!)

Feststellung 2:

Die Kongruenz

$\begin{eqnarray*} x^2(x^{n-2}-1) \equiv 0 \mod 100 \end{eqnarray*}$

hat genau dann für ein n alle ganzen Zahlen x als Lösung, wenn dies für das fragliche n für die Kongruenzen (*) im Falle p=2 und p=5 zutrifft.

Beweis: Folgt in einfacher Weise aus $\begin{eqnarray*} 100 = 2^2 \cdot 5^2 \end{eqnarray*}$ .

Feststellung 3:

Wegen $\begin{eqnarray*} \varphi(25)=20 \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(4)=2 \end{eqnarray*}$ , sowie 2|20, ist der Fall p=2 im Fall p=5 bereits enthalten, weshalb nur mehr der Fall p=5 betrachtet werden muss. Die Lösungen dafür sind alle n>2, für welche

$\begin{eqnarray*} n \equiv 2 \mod 20 \end{eqnarray*}$

gilt... Insbesondere ist die kleinste in Frage kommende Lösung n=22... Aber natürlich ist auch n=42 Lösung der Aufgabe, denn diese Zahl ist ja bekanntlich die Antwort auf alles und jedes... Augenzwinkern

06.04.2010, 15:40

Kerstin H.

Auf diesen Beitrag antworten »

du bist zu schlau für mich
Also Feststellung 1 und 2 kriege ich ja noch hin....

Feststellung 3 durchschaue ich noch nicht so ganz....

Warum ich das so aufbrösel? - Weil ich mir das Rechnen mit Kongruenzen in einer Hand voll Übungsgruppen selbst zusammenreimen musste, und es schlichtweg nicht besser kann -weil meine Bearbeitungen der Übungsblätter und die später erhaltenen Musterlösungen auch so aussahen, z.B. zeige, dass immer gilt $\begin{eqnarray*} 42|n^7 -n \end{eqnarray*}$ , indem gezeigt wird, dass neben $\begin{eqnarray*} 7| n^7 -n \end{eqnarray*}$ wegen Fermat auch gilt, dass $\begin{eqnarray*} 3| n^7 -n \end{eqnarray*}$ und $\begin{eqnarray*} 2| n^7 -n \end{eqnarray*}$ .

Deshalb auch hier meine Vorgehensweise, die Teilbarkeiten einzeln zu zeigen.

Ich habe allerdings noch ein Problem mit der Lösung, weil ich nicht verstehe, dass es nun mit diesen n für alle x gilt. Man untersucht doch nur die Fälle, $\begin{eqnarray*} 2|x \end{eqnarray*}$ und $\begin{eqnarray*} 5|x \end{eqnarray*}$ und ich in meinem Fall $\begin{eqnarray*} ggT (x,100)=1 \end{eqnarray*}$ . Was ist aber, wenn $\begin{eqnarray*} 2|x \end{eqnarray*}$ aber $\begin{eqnarray*} 5 \not |x \end{eqnarray*}$ ? Dann wäre ja weder der erste Fall noch der zweite Fall gegeben. Versteh so langsam garnix mehr....

Trotzdem vielen Dank.

Verwirrte Grüße

Kerstin

06.04.2010, 15:42

Auf diesen Beitrag antworten »

@Kerstin H.

Editiere mal deinen vorletzten Beitrag dahingehend, dass überall der Wert $\begin{eqnarray*} 100 \end{eqnarray*}$ in den $\begin{eqnarray*} ggT \end{eqnarray*}$ durch $\begin{eqnarray*} x \end{eqnarray*}$ ersetzt wird. Eine Zeile wie

$\begin{eqnarray*} ggT(5,100) = 1 \rightarrow ggT(25,100)=1 \end{eqnarray*}$

mag zwar eine logisch richtige Implikation sein ("aus falsch folgt falsch"), aber du hattest wohl doch eher

$\begin{eqnarray*} ggT(5,x) = 1 \rightarrow ggT(25,x)=1 \end{eqnarray*}$

im Sinn, oder? Momentan sieht das jedenfalls alles ziemlich grauenhaft aus. unglücklich

06.04.2010, 15:50

Kerstin H.

Auf diesen Beitrag antworten »

Autsch
@Arthur Dent: Kann ich leider nicht mehr editieren. Geht nur 15 Minuten lang, nachdem man den Beitrag verfasst hat.

06.04.2010, 15:57

Auf diesen Beitrag antworten »

Zitat:

Original von Kerstin H.
Was ist aber, wenn $\begin{eqnarray*} 2|x \end{eqnarray*}$ aber $\begin{eqnarray*} 5 \not |x \end{eqnarray*}$ ?

Das mag ein Problem bei deiner Art Fallunterscheidung sein, aber nicht bei der von Mystic. Augenzwinkern

Durch die getrennte Untersuchung nach Primzahlpotenzmodulen gibt es pro Primteiler $\begin{eqnarray*} p \end{eqnarray*}$ nur die Fälle $\begin{eqnarray*} p|x \end{eqnarray*}$ sowie $\begin{eqnarray*} ggT(x,p^2)=1 \end{eqnarray*}$ .

In der dir angesprochene Situation $\begin{eqnarray*} 2|x \end{eqnarray*}$ und zugleich $\begin{eqnarray*} 5 \not |x \end{eqnarray*}$ bedeutet das: Es gilt $\begin{eqnarray*} 2|x \end{eqnarray*}$ einerseits und $\begin{eqnarray*} ggT(x,25)=1 \end{eqnarray*}$ andererseits.

06.04.2010, 16:20

Kerstin H.

Auf diesen Beitrag antworten »

So langsam verstehe ich es....

Neue Frage »

Antworten »

Geschickte Ausnutzung des Satzes von Euler, Verständnisproblem ( elemetare Zahlentheorie)

Verwandte Themen