Lemma von Zolotareff

Das Lemma von Zolotareff ist ein mathematischer Satz aus der Zahlentheorie, der eine Verbindung zwischen dem Legendre-Symbol und dem Vorzeichen einer Permutation herstellt. Das Lemma erlaubt einen einfachen Beweis des quadratischen Reziprozitätsgesetzes zur Ermittlung quadratischer Reste. Es ist nach dem russischen Mathematiker Jegor Iwanowitsch Zolotareff benannt, der das Lemma und diesen Beweis 1872 vorlegte. Ferdinand Georg Frobenius verallgemeinerte diese Resultate 1914 für das Jacobi-Symbol.

Lemma

Ist eine ganze Zahl und eine ungerade Primzahl, die nicht teilt, dann stellt die Abbildung

$\pi _{a,p}:~\mathbb {Z} _{p}^{\times }\to \mathbb {Z} _{p}^{\times },\quad \pi _{a,p}({\bar {k}}):=a\,{\bar {k}}={\overline {a\,k}}=\{a\,k+m\,p;~m\in \mathbb {Z} \}$

eine Permutation der Elemente der primen Restklassengruppe $\Z_p^\times$ (der Zahlen von bis p-1 ) dar. Das Lemma von Zolotareff besagt nun, dass das Legendre-Symbol $\left(\tfrac{a}{p}\right)$ gleich dem Vorzeichen dieser Permutation ist, das heißt,

$\left(\frac{a}{p}\right) = \operatorname{sgn}(\pi_{a,p})$ .

Beispiel

Kennzahlen der Permutationen π_a,7
	π_a,7	Zykeltyp	Vorzeichen
1	(1, 2, 3, 4, 5, 6)	1⁶	1
2	(2, 4, 6, 1, 3, 5)	3²	1
3	(3, 6, 2, 5, 1, 4)	6¹	−1
4	(4, 1, 5, 2, 6, 3)	3²	1
5	(5, 3, 1, 6, 4, 2)	6¹	−1
6	(6, 5, 4, 3, 2, 1)	2³	−1

Das Legendre-Symbol dient zur Untersuchung quadratischer Reste modulo . Für einen quadratischen Rest modulo ist das zugehörige Legendre-Symbol gleich , für einen quadratischen Nichtrest ist es gleich . Im Folgenden seien die Zahlen $1, \ldots , p-1$ die Repräsentanten der primen Restklassen modulo . Dann sind beispielsweise für p=7 wegen

$1^2 \equiv 1 \pmod {7}$

$2^2 \equiv 4 \pmod {7}$

$3^2 \equiv 2 \pmod {7}$

die Zahlen 1,2 und quadratische Reste, während die Zahlen 3,5 und quadratische Nichtreste sind. Das Vorzeichen einer Permutation ist gleich dem Produkt der Vorzeichen ihrer disjunkten Zyklen, wobei ein Zyklus der Länge das Vorzeichen $(-1)^{l-1}$ besitzt. Nach dem Lemma von Zolotareff ergibt sich nun beispielsweise für a=2 die Permutation

$\pi_{2,7} = (2,4,6,1,3,5) = (1~2~4)(3~6~5)$

mit zwei Zyklen der Länge . Damit gilt

$\left(\frac{2}{7}\right) = \operatorname{sgn}(\pi_{2,7}) = (-1)^2 \cdot (-1)^2 = 1$

und ist ein quadratischer Rest modulo . Für a=5 ist die zugehörige Permutation

$\pi_{5,7} = (5,3,1,6,4,2) = (1~5~4~6~2~3)$

ein Zyklus der Länge . Damit gilt

$\left(\frac{5}{7}\right) = \operatorname{sgn}(\pi_{5,7}) = (-1)^5 = -1$

und ist ein quadratischer Nichtrest modulo .

Beweis

Bezeichnet die Ordnung von in der primen Restklassengruppe $\Z_p^\times$ , dann zerfällt die Permutation $\pi_{a,p}$ in (p-1)/l Zyklen der Länge . Daraus ergibt sich für das Vorzeichen von $\pi_{a,p}$

$\operatorname{sgn}(\pi_{a,p}) = (-1)^{(l-1)(p-1)/l}$ .

Ist nun gerade, dann ergibt sich

$\operatorname{sgn}(\pi_{a,p}) = (-1)^{(p-1)/l} \equiv (a^{l/2})^{(p-1)/l} \pmod p\equiv a^{(p-1)/2} \pmod p$ .

Ist ungerade, dann ist ein Teiler von p-1 und es ergibt sich

$\operatorname{sgn}(\pi_{a,p}) = 1 \equiv (a^{l})^{(p-1)/2l} \pmod p \equiv a^{(p-1)/2} \pmod p$ .

In beiden Fällen folgt dann die Übereinstimmung mit dem Legendre-Symbol nach dem eulerschen Kriterium

$\left({\frac {a}{p}}\right)\equiv a^{{(p-1)/2}}{\pmod p}$ .

Anmerkung

Die Abbildung $a \mapsto \operatorname{sgn}(\pi_{a,p})$ stellt einen surjektiven Homomorphismus von der primen Restklassengruppe $\Z_p^\times$ in die Gruppe $(\{ 1, -1 \}, \cdot)$ dar. Die Surjektivität folgt daraus, dass für eine Primitivwurzel modulo die Permutation $\pi_{a,p}$ einen (p-1) -Zyklus mit Vorzeichen darstellt. Der Kern dieser Abbildung ist daher eine Untergruppe von $\Z_p^\times$ mit Index . Nachdem aber $\Z_p^\times$ zyklisch ist, ist die einzige Untergruppe dieser Art die multiplikative Gruppe der quadratischen Reste. Daraus folgt dann ebenfalls die Übereinstimmung mit dem Legendre-Symbol.

Verwendung

Quadratisches Reziprozitätsgesetz

Permutation τ_5,7 in Matrixform
	0	1	2	3	4	5	6
0	0	5	10	15	20	25	30
1	1	6	11	16	21	26	31
2	2	7	12	17	22	27	32
3	3	8	13	18	23	28	33
4	4	9	14	19	24	29	34

Permutation α_5,7 in Matrixform
	0	1	2	3	4	5	6
0	0	15	30	10	25	5	20
1	21	1	16	31	11	26	6
2	7	22	2	17	32	12	27
3	28	8	23	3	18	33	13
4	14	29	9	24	4	19	34

α_5,7 nach Spaltenversetzungen
	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	21	22	23	24	25	26	27
2	7	8	9	10	11	12	13
3	28	29	30	31	32	33	34
4	14	15	16	17	18	19	20

Zolotareff verwendete das Lemma, um das quadratische Reziprozitätsgesetz zu beweisen. Seien hierzu und zwei verschiedene ungerade Primzahlen. Nach dem chinesischen Restsatz lässt sich jede Zahl $z \in \Z_{pq}$ eindeutig in der Form z = qi+j mit $i \in \Z_p$ und $j \in \Z_q$ darstellen. Nun werden auf $\Z_{pq}$ die beiden Permutationen

$\tau_{p,q}(qi+j) \equiv i + pj \pmod {pq}$

und

$\alpha_{p,q}(qi+j) \equiv q^{-1}qi + p^{-1}pj \pmod {pq}$

betrachtet, wobei $p^{{-1}}$ das inverse Element zu in $\Z_q$ und $q^{{-1}}$ das inverse Element zu in $\mathbb {Z} _{p}$ bezeichnen. Werden die Werte dieser Permutationen jeweils in einer rechteckigen Matrix, bestehend aus Zeilen und Spalten, angeordnet, dann entspricht $\tau_{p,q}$ einer spaltenweisen und $\alpha_{p,q}$ einer diagonalen Aufzählung der Zahlen von $0$ bis pq-1 (eine zeilenweise Aufzählung würde gerade der identischen Permutation entsprechen). Die Permutation $\tau_{p,q}$ ist die Transpositionspermutation, die Zeilen und Spalten einer $(q \times p)$ -Matrix vertauscht. Das Vorzeichen von $\tau_{p,q}$ ist

$\operatorname{sgn}(\tau_{p,q}) = (-1)^{\tbinom{p}{2}\tbinom{q}{2}} = (-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}} = \operatorname{sgn}(\tau_{q,p})$ ,

da jedes Paar zweielementiger Teilmengen $\{ i, i' \} \subseteq \Z_p$ und $\{ j, j' \} \subseteq \Z_q$ genau einen Fehlstand erzeugt. In den Spalten der Permutation $\alpha_{p,q}$ finden sich zyklisch versetzt die Werte der Permutation $\pi^{-1}_{q,p}$ (mit $0$ als zusätzlichem Fixpunkt) mit multipliziert und jeweils um den Spaltenindex erhöht. Die zyklischen Versetzungen können mit Hilfe spaltenweiser zyklischer Permutationen rückgängig gemacht werden, ohne dass sich das Vorzeichen von $\alpha_{p,q}$ verändert, da zyklische Permutationen ungerader Länge stets gerade sind. Auf diese Weise entsteht die identische Permutation, bei der die Zeilen gemäß der Permutation $\pi^{-1}_{q,p}$ vertauscht sind. Für das Vorzeichen von $\alpha_{p,q}$ gilt daher

$\operatorname{sgn}(\alpha_{p,q}) = \operatorname{sgn}(\pi^{-1}_{q,p})^q = \operatorname{sgn}(\pi_{q,p}) = \left(\frac{q}{p}\right)$ .

In den Zeilen der Permutation $\alpha_{p,q}$ finden sich entsprechend zyklisch versetzt die Werte der Permutation $\pi^{-1}_{p,q}$ (mit $0$ als zusätzlichem Fixpunkt) mit multipliziert und um den Spaltenindex erhöht. Wird die Permutation $\alpha_{p,q}$ mit Hilfe der Permutation $\tau_{q,p}$ transponiert, dann ergibt sich analog zu vorher das Vorzeichen der transponierten Permutation zu

$\operatorname{sgn}(\alpha_{p,q} \circ \tau_{q,p}) = \left(\frac{p}{q}\right)$ .

Mit der Verkettungseigenschaft sowie der Invarianz unter Inversion des Vorzeichens folgt aus

$\operatorname{sgn}(\alpha_{p,q}) = \operatorname{sgn}(\alpha_{p,q} \circ \tau_{q,p} \circ \tau^{-1}_{q,p}) = \operatorname{sgn}(\alpha_{p,q} \circ \tau_{q,p}) \cdot \operatorname{sgn}(\tau_{q,p})$

dann das quadratische Reziprozitätsgesetz

$\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) \cdot (-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}}$ .

Jacobi-Symbol

Mit Hilfe des Lemmas von Zolotareff lässt sich das Legendre-Symbol zum Jacobi-Symbol verallgemeinern, für das auch üblicherweise die gleiche Notation verwendet wird. Ist hierzu eine ungerade Zahl und eine beliebige ganze Zahl, die teilerfremd zu ist, dann kann das Jacobi-Symbol durch

$\left(\frac{a}{n}\right) = \operatorname{sgn}(\pi_{a,n})$

definiert werden. Im Fall, dass ungerade ist, gilt für das Jacobi-Symbol ebenfalls das quadratische Reziprozitätsgesetz.

Literatur

Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden. de Gruyter, 2013, ISBN 978-3-11-031261-4.

Basierend auf einem Artikel in:

Wikipedia.de

	0	1	2	3	4	5	6
0	0	5	10	15	20	25	30
1	1	6	11	16	21	26	31
2	2	7	12	17	22	27	32
3	3	8	13	18	23	28	33
4	4	9	14	19	24	29	34

	0	1	2	3	4	5	6
0	0	15	30	10	25	5	20
1	21	1	16	31	11	26	6
2	7	22	2	17	32	12	27
3	28	8	23	3	18	33	13
4	14	29	9	24	4	19	34

	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	21	22	23	24	25	26	27
2	7	8	9	10	11	12	13
3	28	29	30	31	32	33	34
4	14	15	16	17	18	19	20

	0	1	2	3	4	5	6
0	0	5	10	15	20	25	30
1	1	6	11	16	21	26	31
2	2	7	12	17	22	27	32
3	3	8	13	18	23	28	33
4	4	9	14	19	24	29	34

	0	1	2	3	4	5	6
0	0	15	30	10	25	5	20
1	21	1	16	31	11	26	6
2	7	22	2	17	32	12	27
3	28	8	23	3	18	33	13
4	14	29	9	24	4	19	34

	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	21	22	23	24	25	26	27
2	7	8	9	10	11	12	13
3	28	29	30	31	32	33	34
4	14	15	16	17	18	19	20

	0	1	2	3	4	5	6
0	0	5	10	15	20	25	30
1	1	6	11	16	21	26	31
2	2	7	12	17	22	27	32
3	3	8	13	18	23	28	33
4	4	9	14	19	24	29	34

	0	1	2	3	4	5	6
0	0	15	30	10	25	5	20
1	21	1	16	31	11	26	6
2	7	22	2	17	32	12	27
3	28	8	23	3	18	33	13
4	14	29	9	24	4	19	34

	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	21	22	23	24	25	26	27
2	7	8	9	10	11	12	13
3	28	29	30	31	32	33	34
4	14	15	16	17	18	19	20