Kongruenzbeweis

28.05.2005, 19:44	Spieky	Auf diesen Beitrag antworten »
Kongruenzbeweis Hallo, wir haben folgende Aufgabe: Zeige, dass für $\begin{eqnarray} \forall x\in \mathbb Z \end{eqnarray}$ gilt $\begin{eqnarray} x^{7} \equiv x(42) \end{eqnarray}$ Ich habe mir überlegt, dass man das mit volständiger Induktion zeigen könnte. Jedoch komme ich da beim Induktionsschluss nicht weiter. Kann mir jemand einen Tipp geben, bzw. gibt es eine einfachere Möglichkeit um das zu zeigen?
29.05.2005, 12:16	Anirahtak	Auf diesen Beitrag antworten »
RE: Kongruenzbeweis Hallo $\begin{eqnarray} x^7\equiv x\ \mathrm{mod} \ 42 \end{eqnarray}$ ist doch gleichbedeutend mit $\begin{eqnarray} x^7-x\equiv 0 \ \mathrm{mod}\ 42 \end{eqnarray}$ Und es gilt: $\begin{eqnarray} x^7-x=x(x^6-1)=x(x^3-1)(x^3+1) \end{eqnarray}$ Jetzt musst du argumentieren, dass 2,3,7 jeweils einen der Faktoren teilen. Zum Bsp: x gerade, dann fertig, x ungerade, dann x^3 ungerade und x^3-1 und x^3+1 gerade Insgesamt teilt 2 also x^7-x Ähnliche Überlegungen für 3 und 7 sollten zum Ergebnis führen. Gruß Anirahtak
29.05.2005, 13:31	AD	Auf diesen Beitrag antworten »
Noch etwas weiter zerlegt gilt $\begin{eqnarray} x^7-x=(x-1)x(x+1)(x^2-x+1)(x^2+x+1) \end{eqnarray}$ Damit sind modulo 2 und 3 erledigt. Und für modulo 7 kann man dann noch $\begin{eqnarray} x^2+x+1\equiv x^2+x-6=(x+3)(x-2) \mod 7 \end{eqnarray}$ $\begin{eqnarray} x^2-x+1\equiv x^2-x-6=(x-3)(x+2) \mod 7 \end{eqnarray}$ also insgesamt $\begin{eqnarray} x^7-x\equiv (x-3)(x-2)(x-1)x(x+1)(x+2)(x+3) \mod 7 \end{eqnarray}$ nutzen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »