Formel von Woronoi

Im mathematischen Teilgebiet der Zahlentheorie befasst sich die Formel von Woronoi (englisch Voroni's formula)^{[A 1]} mit der Beschreibung der Lösung von linearen Kongruenzen eines speziellen Typs. Die Formel wurde von dem Mathematiker Georgi Feodosjewitsch Woronoi (1868–1908) etwa um das Jahr 1900 vorgelegt.^[1]

Sie lässt sich wie folgt beschreiben:^[1]

Sind teilerfremde natürliche Zahlen ${\displaystyle ,円a,,円,円m>0,円}${\displaystyle ,円a,,円,円m>0,円} gegeben, so sind die ganzzahligen Lösungen ${\displaystyle ,円x,円}${\displaystyle ,円x,円} der Kongruenz

${\displaystyle a\cdot x\equiv 1{\pmod {m}}}${\displaystyle a\cdot x\equiv 1{\pmod {m}}}

alle durch die Formel

${\displaystyle x\equiv \left(3-2\cdot a+6\cdot {\sum _{k=1}^{a-1}{\left\lfloor {\frac {mk}{a}}\right\rfloor }^{2}}\right){\pmod {m}}}${\displaystyle x\equiv \left(3-2\cdot a+6\cdot {\sum _{k=1}^{a-1}{\left\lfloor {\frac {mk}{a}}\right\rfloor }^{2}}\right){\pmod {m}}}

gegeben.

Dem Mathematiker James Joseph Tattersall zufolge funktioniert die Woronoi'sche Formel am besten für kleines ${\displaystyle ,円a,円}${\displaystyle ,円a,円} und großes ${\displaystyle ,円m,円}${\displaystyle ,円m,円}, wie etwa in dem folgenden Beispiel:^[1]

Sind

${\displaystyle a=4}${\displaystyle a=4}

${\displaystyle m=37}${\displaystyle m=37}

gegeben, so ist

${\displaystyle x=3-8+6\cdot \left({\left\lfloor {\frac {37}{4}}\right\rfloor }^{2}+{\left\lfloor {\frac {74}{4}}\right\rfloor }^{2}+{\left\lfloor {\frac {111}{4}}\right\rfloor }^{2}\right)=-5+6\cdot (9^{2}+18^{2}+27^{2})=-5+6\cdot 1134=6799\equiv 28{\pmod {37}}}${\displaystyle x=3-8+6\cdot \left({\left\lfloor {\frac {37}{4}}\right\rfloor }^{2}+{\left\lfloor {\frac {74}{4}}\right\rfloor }^{2}+{\left\lfloor {\frac {111}{4}}\right\rfloor }^{2}\right)=-5+6\cdot (9^{2}+18^{2}+27^{2})=-5+6\cdot 1134=6799\equiv 28{\pmod {37}}}

eine Lösung.

Denn es ist

${\displaystyle 4\cdot 28=112=3\cdot 37+1\equiv 1{\pmod {37}}}${\displaystyle 4\cdot 28=112=3\cdot 37+1\equiv 1{\pmod {37}}} .

• James J. Tattersall: Elementary number theory in nine chapters. Cambridge University Press, Cambridge 1999, ISBN 0-521-58531-7 (MR1720399). 

1. ↑ ^{a b c} J. J. Tattersall: Elementary number theory in nine chapters. 1999, S. 171.

1. ↑ Die Transkription des russischen Namens von Woronoi ins Englische ist uneinheitlich. Hier findet man auch Voronoi und sogar Voronoy.

• Zahlentheorie