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\,}$ gegeben, so sind die ganzzahligen Lösungen ${\displaystyle \,x\,}$ der Kongruenz

${\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}}}$

gegeben.

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

Sind

${\displaystyle a=4}$

${\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}}}$

eine Lösung.

Denn es ist

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