Eulersche Phi Funktion - Ordnung von Elementen in Restklassengruppe

16.11.2015, 18:17	Matheneuling1991	Auf diesen Beitrag antworten »
Eulersche Phi Funktion - Ordnung von Elementen in Restklassengruppe Es geht um folgendes; Es sei gegeben ein t aus den natürlichen Zahlen und m sei definiert als $\begin{eqnarray} m=2^{v(t)+2} \end{eqnarray}$ wobei v(t) die Anzahl bezeichne, wie oft der Faktor 2 in der Primfaktorzerlegung in t enthalten ist; Als Beispiel nehmen wir $\begin{eqnarray} t=8=2^3 \end{eqnarray}$ , dann wäre $\begin{eqnarray} m=2^{3+2}=32 \end{eqnarray}$ oder bei $\begin{eqnarray} t=24=2^33 \end{eqnarray}$ , wäre $\begin{eqnarray} m=2^{3+2}=32 \end{eqnarray}$ , also identisch; Nun will ich beweisen, dass für jede Zahl a mit ggT(a,m)=1 gilt, dass $\begin{eqnarray} a^t \equiv 1 \end{eqnarray}$ (mod m); Nun mein Ansatz: Wenn m definiert wäre als $\begin{eqnarray} m=2^{v(t)+1} \end{eqnarray}$ , so wüsste ich, dass $\begin{eqnarray} 2^{v(t)} \end{eqnarray}$ t teilt; Außerdem weiß ich, dass: $\begin{eqnarray} a^{\phi(m)} \equiv 1 \end{eqnarray}$ (mod m); und $\begin{eqnarray} \phi(m)=(2-1)2^{v(t)+1-1}=2^{v(t)} \end{eqnarray}$ und somit bekomme ich: $\begin{eqnarray} a^t=a^{2^{v(t)}k}=(a^{\phi(m)})^k \equiv 1^k =1 \end{eqnarray}$ (mod m)... Aber dies ist nicht gegeben; (weil +2 anstatt +1) In meinem Fall kann ich $\begin{eqnarray} a^t \end{eqnarray}$ nur auf -1 und 1 eingrenzen, ohne -1 ausschlißen zu können; Dies kann ich zeigen wie folgt; $\begin{eqnarray} a^{\phi(m)}=a^{2^{v(t)+1}}=a^{2^{v(t)}2}=a^{ti2}=(a^{t})^{2i}=1 \end{eqnarray}$ (mod m) Wodurch folgt, dass a^t -1 oder 1 sein muss... Hat da jemand eine Idee? EDIT: Ich habe ein paar Tippfehler korrigiert, die so nicht gepasst haben
16.11.2015, 18:34	HAL 9000	Auf diesen Beitrag antworten »
Für ungerade $\begin{align} t \end{align}$ , also $\begin{align} v(t)=0 \end{align}$ , ist die Behauptung falsch - für gerade $\begin{align} t \end{align}$ und damit $\begin{align} v(t)\geq 1 \end{align}$ dürfte sie aber richtig sein. ------------------------------------------------------ Ok, das ganze mal kompakt zusammengefasst: Du willst $\begin{align} a^{2^ku} \equiv 1\bmod \left( 2^{k+2} \right) \end{align}$ für alle ungeraden Zahlen $\begin{align} a,u \end{align}$ beweisen. Offenbar ist es hinreichend, das für $\begin{align} u=1 \end{align}$ zu beweisen: $\begin{align} a^{2^k} \equiv 1\bmod \left( 2^{k+2} \right) \end{align}$ . Ist eigentlich sehr einfach per Vollständiger Induktion über $\begin{align} k \end{align}$ zu erledigen, mit Induktionsanfang $\begin{align} k=1 \end{align}$
16.11.2015, 18:38	Matheneuling1991	Auf diesen Beitrag antworten »
Stimmt, ich meinte, dass der Faktor 2 in t enthalten ist und damit insbesondere t gerade ist; Induktion probiere ich gerade; Ich hasse mich, wenn das schon wieder so einfach geht...
16.11.2015, 18:58	Matheneuling1991	Auf diesen Beitrag antworten »
Hey.... Hat geklappt, vielen Dank...
16.11.2015, 19:21	HAL 9000	Auf diesen Beitrag antworten »
Schön.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »