Kalkulator współczynników Bezout

O tym kalkulatorze

Tożsamość Bezouta mówi, że dla dowolnych liczb całkowitych a i b istnieją liczby całkowite x i y — współczynniki Bezouta — spełniające ax + by = gcd(a, b). Ten kalkulator znajduje x, y i NWD za pomocą rozszerzonego algorytmu Euklidesa, który uruchamia zwykły algorytm NWD w przód, śledząc jednocześnie współczynniki wstecz przez każdy krok reszty.

Poza teorią liczb współczynniki Bezouta to standardowy sposób obliczania odwrotności multiplikatywnej modulo — niezbędnej w RSA i innych generowaniach kluczy kryptograficznych — i leżą u podstaw rozwiązywania liniowych równań diofantycznych postaci ax + by = c.