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² - 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$.