Formel von Woronoi

Im mathematischen Teilgebiet der Zahlentheorie befasst sich die Formel von Woronoi (englisch Voroni's formula) 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.

Beschreibung der Formel

Sie lässt sich wie folgt beschreiben:

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

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

alle durch die Formel

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

Beispiel

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

Sind

$a=4$

$m=37$

gegeben, so ist

$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

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

Literatur

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