[Zahlentheorie] Ein spezieller Homomorphismus

Christoph

Hi,

das Thema ist Zahlentheorie, spezieller das quadratische Reziprozitätsgesetz.

Ich habe folgenden Homomorphismus von $(\mathbb{Z}/n\mathbb{Z})^\times$ bzgl. Multiplikation gegeben:
$\psi(a + n\mathbb{Z}) := a^{\frac{n-1}2}\left(\frac{a}{n}\right) + n\mathbb{Z}$
Wobei $\left(\frac{a}{n}\right)$ für das Jacobi-Symbol steht und n > 1 ungerade ist.

Ist n prim, so ist psi(a + nZ) = 1 + nZ für alle a, wie aus der eulerschen Identität folgt. Dieser Teil ist noch recht einfach, sofern ich da nichts übersehen habe.

Das eigentliche Problem lautet nun:
* Ist n nicht prim, so gibt es ein $a \in (\mathbb{Z}/n\mathbb{Z})^\times$ , sodass psi(a) != 1 mod n.

Ich rätsel seit Samstag an dieser Aufgabe, habe schon verschiedene Ansätze durch. Der erfolgsversprechendste (jüngste) Ansatz sah so aus:

1. Fall: Angenommen, phi(n) ist kein Teiler von n - 1 (siehe [1]). Sei g eine Primitivwurzel, so ist $g^{\frac{n-1}2} \neq \pm1$ . Da das Jacobi-Symbol nur $\pm1$ sein kann, ist also psi(g + nZ) != 1 + nZ.

2. Fall: Angenommen phi(n) ist ein Teiler von n - 1. Dann muss n quadratfrei sein. Psi lässt sich dann so schreiben:
$\psi(a + n\mathbb{Z}) = \left(a^{\frac{\phi(n)}2}\right)^k\left(\frac{a}{n}\right) + n\mathbb{Z}$
mit $k = \frac{n-1}{\phi(n)}$ .

Jetzt kann man noch unterscheiden zwischen "k gerade" bzw. "k ungerade". Der Fall "k gerade" müsste funktionieren und dazu führen, dass man sich ein passendes a basteln kann, der Fall "k ungerade" ist ebenfalls noch nicht mit Sicherheit gezeigt, da ich im Moment nicht sicher bin, ob $a \mapsto a^{\frac{\phi(n)}{2}}$ tatsächlich einen Epimorphismus nach {1,-1} darstellt, bei dem die Quadrate auf 1 und die Nicht-Quadrate auf -1 gehen. Ich denke sogar, dass ist nur dann so, wenn n prim ist.

Das problematischste ist nun der 1. Fall. Denn im Allgemeinen existiert für (Z/nZ) gar keine Primitivwurzel. Jedes andere Element dieser Gruppe hat aber eine kleinere Ordnung als phi(n), weswegen $a^{\frac{n-1}2}$ dann doch wieder 1 ergeben könnte.
Außerdem ist wie beschrieben der 2. Fall leider auch noch etwas lückenhaft.

Hat vielleicht jemand Tipps, wie man da geschickter vorgehen könnte?

Ich hatte auch schon überlegt, ob psi(2) immer != 1 ist, aber selbst das ist bei zahlreichen n nicht der Fall (kleinstes Gegenbeispiel: n = 561).

Tipp: Carmichael-Zahl, chinesischer Restsatz

Christoph

tipp schrieb:

Tipp: Carmichael-Zahl, chinesischer Restsatz

Würdest du das etwas näher erläutern?

Den Tipp mit dem chinesischen Restsatz zu argumentieren habe ich auch schon probiert. Es funktioniert insoweit (unter Vorbehalt), dass man mit seiner Hilfe immer eine Zahl a finden kann, für die $\left(\frac{a}{n}\right) = 1$ gilt, obwohl a kein Quadrat modulo n ist. Auch dann muss man aber wissen, ob $a^{\frac{n-1}2}$ nicht doch immer 1 ergibt.

Wie die Carmichael-Zahlen damit zu tun haben, sehe ich allerdings noch nicht.

Ich sollte vielleicht noch dazusagen, dass chinesischer Restsatz und Reziprozitätsgesetz die beiden großen Themen sind, die für diese Aufgabe vom Autor als "bekannt" vorausgesetzt werden. Ich weiß zwar in etwa, was Carmichael-Zahlen auszeichnet, aber in besagtem Buch kamen sie bisher nicht vor. Deswegen bin ich mir nicht sicher, ob zur Lösung der Aufgabe tatsächlich Aussagen über Carmichael-Zahlen nötig sein sollten.

Wenn für eine zusammengesetzte Zahl das doch gelten würde, wäre sie eine Carmichaelzahl, also quadratfrei n = pqr... mit (p-1)|(n-1), (q-1)|(n-1), ...

daraus kannst du dann ein Gegenbeispiel konstruieren,