Kongruenz, Potenzen

29.11.2009, 18:11

Faculty

Kongruenz, Potenzen

Hallo,
hänge grad an zwei kleinen Aufgaben:

a) Wie viele Elemente $\begin{eqnarray*} x \end{eqnarray*}$ mit der Eigenschaft $\begin{eqnarray*} x^2 = x \end{eqnarray*}$ hat der Ring $\begin{eqnarray*} \mathbb{Z}/15015\mathbb{Z} \end{eqnarray*}$ ? Geben Sie vier solche Elemente explizit an.

b) Man beweise oder widerlege die Behauptung: $\begin{eqnarray*} x^{200} \equiv x^8 \mod 221 \end{eqnarray*}$

Ich find nicht wirklich was, was ich auf die Potenzen anwenden kann, kann mir jemand einen Tipp geben?

Grüße

29.11.2009, 18:17

Auf diesen Beitrag antworten »

Zu a) $\begin{eqnarray*} x^2 = x \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}/15015\mathbb{Z} \end{eqnarray*}$ bedeutet umgeschrieben in die Sprache der Teilbarkeit ganzer Zahlen

$\begin{eqnarray*} 15015 \mid x(x-1) \end{eqnarray*}$ .

Angesichts von $\begin{eqnarray*} 15015 = 3\cdot 5\cdot 7\cdot 11\cdot 13 \end{eqnarray*}$ sowie der Tatsache, dass die beiden Faktoren $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} (x-1) \end{eqnarray*}$ teilerfremd sind, kann man sich überlegen, wie man bei einer Lösungssuche weiter verfahren könnte.

Und zu b): Aus dem kleinen Fermat

$\begin{eqnarray*} x^p \equiv x \bmod p \end{eqnarray*}$

kann induktiv

$\begin{eqnarray*} x^{k(p-1)+1} \equiv x \bmod p \end{eqnarray*}$ für beliebige $\begin{eqnarray*} k\in\mathbb{N} \end{eqnarray*}$

gefolgert werden, und zwar für beliebige $\begin{eqnarray*} x \end{eqnarray*}$ . Im Zusammenhang mit $\begin{eqnarray*} 221 = 13\cdot 17 \end{eqnarray*}$ lässt sich damit das sogar noch etwas schärfere

$\begin{eqnarray*} x^{193} \equiv x \bmod 221 \end{eqnarray*}$

für alle $\begin{eqnarray*} x \end{eqnarray*}$ nachweisen.

29.11.2009, 19:59

Faculty

Auf diesen Beitrag antworten »

Hallo Arthur, danke erstmal für deine Hilfe.

Zu a) Ich kann, wie du gesagt hast, $\begin{eqnarray*} 15015 = 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \end{eqnarray*}$ so zerlegen. Nun gibt es $\begin{eqnarray*} 2^5 = 32 \end{eqnarray*}$ Elemente, für die die Eigenschaft $\begin{eqnarray*} x^2 \equiv x \mod 15015 \end{eqnarray*}$ erfüllt ist, da:
$\begin{eqnarray*} x^2 \equiv x \mod 3 \end{eqnarray*}$ genau 2 Lösungen hat,
$\begin{eqnarray*} x^2 \equiv x \mod 5 \end{eqnarray*}$ genau 2 Lösungen hat,
$\begin{eqnarray*} x^2 \equiv x \mod 7 \end{eqnarray*}$ genau 2 Lösungen hat,
$\begin{eqnarray*} x^2 \equiv x \mod 11 \end{eqnarray*}$ genau 2 Lösungen hat,
$\begin{eqnarray*} x^2 \equiv x \mod 13 \end{eqnarray*}$ genau 2 Lösungen hat, jeweils $\begin{eqnarray*} x \in \{0, 1\} \end{eqnarray*}$ .
Aber wie finde ich jetzt die Lösungen? $\begin{eqnarray*} x \in \{0, 1\} \end{eqnarray*}$ ist klar.
Ich hab ein wenig rumprobiert und komm bei $\begin{eqnarray*} x^2 \equiv x \mod y \end{eqnarray*}$ für $\begin{eqnarray*} y = 15 = 3 \cdot 5 \end{eqnarray*}$ auf die Lösungen $\begin{eqnarray*} x \in \{0, 1, 6, 10\} \end{eqnarray*}$ , für $\begin{eqnarray*} y = 21 = 3 \cdot 7 \end{eqnarray*}$ auf die Lösungen $\begin{eqnarray*} x \in \{0, 1, 7, 15\} \end{eqnarray*}$ , für $\begin{eqnarray*} y = 35 = 5 \cdot 7 \end{eqnarray*}$ auf die Lösungen $\begin{eqnarray*} x \in \{0, 1, 15, 21\} \end{eqnarray*}$ , kann hier aber leider kein Muster erkennen.

Zu b) Wie folgerst du das induktiv? Ich hab mich mal dran versucht und hab das hier, ist das ausreichend?

$\begin{eqnarray*} x^{p-1} = 1 \mod p \end{eqnarray*}$

Behauptung: $\begin{eqnarray*} x^{k(p-1)} \equiv 1 \mod p \end{eqnarray*}$ mit $\begin{eqnarray*} k \in \mathbb{N} \end{eqnarray*}$

IA: $\begin{eqnarray*} k = 1 \end{eqnarray*}$ , $\begin{eqnarray*} x^{p-1} \equiv 1 \mod p \end{eqnarray*}$ (nach dem kleinen Fermat.

IS: $\begin{eqnarray*} 1 \equiv x^{p-1} \cdot 1 \equiv x^{p-1} \cdot x^{k(p-1)} \equiv x^{k(p-1) + (p-1)} \equiv x^{(k+1)(p-1)} \mod p \end{eqnarray*}$

Daraus folgt dann: $\begin{eqnarray*} x^{k(p-1)+1} \equiv x \mod p \end{eqnarray*}$

Es ist: $\begin{eqnarray*} x^{193} \equiv x^{16(13-1)+1} \equiv x \mod 13 \end{eqnarray*}$
als auch: $\begin{eqnarray*} x^{193} \equiv x^{12(17-1)+1} \equiv x \mod 17 \end{eqnarray*}$

Nach dem chin. Restsatz gilt folglich $\begin{eqnarray*} x^{193} \equiv x \mod 221 \end{eqnarray*}$ .

29.11.2009, 20:05

Auf diesen Beitrag antworten »

Zu a)

Für jede der 5 Einzelkongruenzen hast du jeweils zwei Lösungen. Nach chinesischem Restsatz kannst du nun jedem 5-Tupel von Lösungen eine Lösung modulo 15015 zuordnen, ingesamt macht das 32 Lösungen.

Zitat:

Original von Faculty
IS: $\begin{eqnarray*} 1 \equiv x^{p-1} \cdot 1 \equiv x^{p-1} \cdot x^{k(p-1)} \equiv x^{k(p-1) + (p-1)} \equiv x^{(k+1)(p-1)} \mod p \end{eqnarray*}$

Das ist leider nicht richtig für durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbare $\begin{eqnarray*} x \end{eqnarray*}$ . Entweder betrachtest du diesen Fall extra, oder schreibst deine Zeile etwas geschickter auf: Augenzwinkern

I.S. $\begin{eqnarray*} (k-1)\to k: \end{eqnarray*}$

$\begin{eqnarray*} x^{k(p-1)+1} = x^{p-1} \cdot x^{(k-1)(p-1)+1} \stackrel{IV}{\equiv } x^{p-1}\cdot x = x^p \equiv x \bmod p \end{eqnarray*}$ für alle (!) $\begin{eqnarray*} x \end{eqnarray*}$ .

Der Rest ist an sich Ok.

29.11.2009, 20:39

Faculty

Auf diesen Beitrag antworten »

Mmh, kannst du mir meinen Fehler im IS etwas genauer erläutern, bitte? Ich komm nicht drauf.

zur a) Gibt es hier eine einfache Methode, zur Bestimmung der Lösungen? Ich soll ja auch noch 4 Elemente angeben.

29.11.2009, 20:42

Auf diesen Beitrag antworten »

Zitat:

Original von Faculty
Mmh, kannst du mir meinen Fehler im IS etwas genauer erläutern, bitte? Ich komm nicht drauf.

Das hab ich doch gesagt: Im Fall $\begin{eqnarray*} x\equiv 0 \bmod p \end{eqnarray*}$ ist dein

$\begin{eqnarray*} 1 \equiv x^{p-1} \bmod p \end{eqnarray*}$

doch offensichtlich falsch!!!

29.11.2009, 20:56

Faculty

Auf diesen Beitrag antworten »

Ok, sorry, habs verstanden Hammer

Neue Frage »

Antworten »

Kongruenz, Potenzen

Verwandte Themen