Euler-Phi in Aufgabe

26.02.2005, 16:14	Frager	Auf diesen Beitrag antworten »
Euler-Phi in Aufgabe Hi Leute, habe folgende Aufgabe: $\begin{eqnarray} p, q \in \mathbb{P}_3 \end{eqnarray}$ , z.z.: $\begin{eqnarray} a^q \equiv 1 \bmod p \Rightarrow a\equiv 1 \bmod p \vee p \equiv 1 \bmod q \end{eqnarray}$ . Meine 1. Variante (dabei wegen $\begin{eqnarray} p\in\mathbb{P} \end{eqnarray}$ ist $\begin{eqnarray} \mathbb{Z}_p \end{eqnarray}$ Körper, also integer) : $\begin{eqnarray} a^q \equiv 1 \bmod p \Leftrightarrow a^q-1=(a-1)(a^{q-1}+\dots+a+1)\equiv 0 \bmod p \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow a\equiv 1 \bmod p \vee a^{q-1}+\dots+a+1\equiv 0 \bmod p \end{eqnarray}$ . Komme aber dann nicht recht weiter... Meine zweite Variante (mit Euler/Fermat: $\begin{eqnarray} a^{\varphi(p)}\equiv 1 \bmod p \end{eqnarray}$ und $\begin{eqnarray} a^q\equiv 1 \bmod p \end{eqnarray}$ lt. Vor.): $\begin{eqnarray} a^q \equiv 1 \bmod p \Rightarrow q\mid \varphi(p)=p-1 \Rightarrow p-1 \equiv 0 \bmod q \Rightarrow p \equiv 1 \bmod q \end{eqnarray}$ Aber dazu zwei Fragen: 1. Wo bleibt die Möglichkeit $\begin{eqnarray} a\equiv 1 \bmod p \end{eqnarray}$ ? 2. $\begin{eqnarray} a^q\equiv 1 \bmod p \Rightarrow q \mid \varphi(p) \end{eqnarray}$ gilt doch nur, da $\begin{eqnarray} q\in\mathbb{P} \end{eqnarray}$ , oder?
27.02.2005, 11:33	quarague	Auf diesen Beitrag antworten »
zu 1. $\begin{eqnarray} a^q\equiv 1 \bmod p \Rightarrow q \mid \varphi(p) \end{eqnarray}$ gilt nur für $\begin{eqnarray} a \neq 1 \end{eqnarray}$ da kriegst du den Fall a=1 bei der zweiten bin ich mir nicht sicher, aber es sieht irgendwie gut aus ;-)

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »