Finde alle selbstinversen Elemente im Ring Z/nZ wobei n ein Produkt von 2 Primzahlen ist.

Question

Aufgabe:

Finde alle selbstinversen Elemente im Ring Z/nZ wobei n ein Produkt von 2 Primzahlen ist, dh: n=p*q

Problem/Ansatz:

Ich glaube es können nur {1, -1} sein, aber ich kann es nicht richtig begründen.

Für ein a \in Z/nZ* müsste ja sonst gelten, dass a*a = 1, dh a*a-1 müsste ein Vielfaches von n sein... Und weiter fällt mir nichts mehr ein.

Kann mir vielleicht jdm helfen? Oder ist mein Ansatz schon komplett falsch?

Comments

Aber es ist z.B. 4 selbstinvers in Z15 !

---

hm. Simmt. Danke :)

Answer 1

Dein Ansatz ist ja schon gut  a^2 - 1 Vielfaches von n oder sogar gleich n

gibt (a-1)(a+1) = n = p*q

Das geht ja jedenfalls, wenn a-1=p und a+1=q

also           a=p+1 und a=q-1

==>              p+1 = q-1

==>             2 = q - p

Also geht das zumindest immer, wenn p und q

sog. Primzahlzwillinge sind, also etwa 3 und 5

oder 5 und 7 etc.

Comments

Ah! Klar, die erste Umformung zu (a-1)(a+1) ist schlau.

Vielen Dank, das hilft sehr! :)

---

Aber noch eine Frage: Ich will es gerade formell aufschreiben, aber ich tue mir etwas schwer damit, falls (a-1)(a+1) = x*n sind (also ein Vielfaches von n)

<=> (a-1)(a+1) 0= x*p*q, und jetzt?

An sich kann ich doch dann nichts mehr genau über p & q aussagen, oder?

---

Das ändert ja nicht daran, dass es bei Primzahlzwillingen

jedenfalls immer klappt. Über andere Fälle

müsste man wohl noch was nachdenken.

Answer 2

Ich denke, man sollte im Falle \(p\neq q\) mit dem chinesischen Restsatz

arbeiten: \(Z/pqZ\cong Z/pZ\times Z/qZ\). Für die invertierbaren Elemente gilt

dann \((Z/pqZ)^*\cong (Z/pZ)^*\times (Z/qZ)^*\).

Selbstinvers sind dann die Elemente, die den Paaren

\((1,1), (1,-1),(-1,1)\) und \((-1,-1)\) des Gruppenprodukts

entsprechen.

Beispiel: \(p=3\) und \(q=7\):

\(a\equiv 1\) mod \(3\), \(a\equiv 1\) mod \(7\) liefert \(a\equiv 1\) mod \(21\),
\(a\equiv 1\) mod \(3\), \(a\equiv -1\) mod \(7\) liefert \(a\equiv 13\) mod \(21\),
\(a\equiv -1\) mod \(3\), \(a\equiv 1\) mod \(7\) liefert \(a\equiv 8\) mod \(21\),
\(a\equiv -1\) mod \(3\), \(a\equiv -1\) mod \(7\) liefert \(a\equiv 20\equiv -1\) mod \(21\),

Also findet man als betragsmäßig kleinste selbstinverse Reste:

\(\pm 1,\; \pm 8\).