Zeigen/Widerlegen der Bijektivität einer Abbildung in Restklassen

07.05.2018, 09:33

SoulOfMidgard

Zeigen/Widerlegen der Bijektivität einer Abbildung in Restklassen

Meine Frage:
Die Frage ist ob die Abbildung x->x^17 in den ganzen Zahlen modulo 451 bijektiv ist und dies soll entweder widerlegt werden oder eine Umkehrabbildung gefunden werden.

Meine Ideen:
451 ist keine Primzahl (451=41*11). Ich hatte Ansätze zur Zerlegung und Lösen in Z mod 11 aber das trug keine Früchte. Ich habe ein Programm geschrieben welches 0-126 hoch 17 rechnete und überprüft ob x_i^17=x_j^17 gefunden werden konnte für ungleiche i und j. Dort fand ich keine (Rechenaufwand darüber ließ mein Rechner nicht zu). Demnach vermute ich dass die Abbildung bijektiv ist. Nun weiss ich aber nicht genau wie ich es zeigen kann. Lemma von Bezout zur Finden von Inversen half mir bis jetzt auch nicht weiter.

07.05.2018, 11:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von SoulOfMidgard
oder eine Umkehrabbildung gefunden werden.

Es ist $\begin{eqnarray*} \lambda(451) = \operatorname{kgV}(11-1,41-1)=40 \end{eqnarray*}$ die maximale Ordnung der Gruppenelemente von $\begin{eqnarray*} \left(\mathbb{Z}/451\mathbb{Z}\right)^* \end{eqnarray*}$ (siehe Carmichael-Funktion). Wegen $\begin{eqnarray*} 17^{-1}\equiv 33\bmod 40 \end{eqnarray*}$ richten wir daher nun unsere Aufmerksamkeit auf $\begin{eqnarray*} \left( x^{17} \right)^{33} = x^{561} \end{eqnarray*}$ :

Aus dem Kleinen Fermat $\begin{eqnarray*} x^p\equiv x\bmod p \end{eqnarray*}$ folgt ja auch $\begin{eqnarray*} x^{m(p-1)+1}\equiv x\bmod p \end{eqnarray*}$ für alle nichtnegativen ganzen Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ . Damit haben wir $\begin{eqnarray*} x^{561} = x^{14\cdot 40+1} \equiv x\bmod p \end{eqnarray*}$ sowohl für $\begin{eqnarray*} p=11 \end{eqnarray*}$ als auch $\begin{eqnarray*} p=41 \end{eqnarray*}$ , gültig für alle $\begin{eqnarray*} x \end{eqnarray*}$ .

EDIT: De facto haben wir damit hier eine RSA-Verschlüsselung vorliegen, natürlich mit viel zu kleinen Primzahlen $\begin{eqnarray*} p,q \end{eqnarray*}$ . Augenzwinkern

07.05.2018, 13:11

SoulOfMidgard

Auf diesen Beitrag antworten »

Mehr grundlegend..
Danke erstmal HAL 9000. Eine Frage hätte ich jedoch. Ist es (wenn auch weniger elegant) möglich das ganze mit einfacheren Grundlagen zu Zeigen? Sache ist, wir hatten diese Carmichael-Funktion in der Vorlesung nicht und damit darf ich sie zum Beweis auch nicht verwenden. Aktuell behandelten wir erst Primitivwurzeln, Ordnungen o.ä. Haben Sie vielleicht eine Idee?

07.05.2018, 13:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von SoulOfMidgard
Ist es (wenn auch weniger elegant) möglich das ganze mit einfacheren Grundlagen zu Zeigen? Sache ist, wir hatten diese Carmichael-Funktion in der Vorlesung nicht und damit darf ich sie zum Beweis auch nicht verwenden.

Aber ja doch: Der ganze erste Abschnitt dient ja nur als Motivation, warum man zu Exponent 33 kommt. Dass es diese 33 dann auch tut, wird ja im zweiten Abschnitt bewiesen. D.h., aus rein beweistechnischer Sicht ist der erste Abschnitt unnötig. Augenzwinkern

07.05.2018, 14:48

SoulOfMidgard

Auf diesen Beitrag antworten »

Ja okay das stimmt natürlich. Ist übrigens ein sehr schöner und verständlicher Beweis! Lieben Dank!

Neue Frage »

Antworten »

Zeigen/Widerlegen der Bijektivität einer Abbildung in Restklassen

Verwandte Themen