Rozszerzony algorytm Euklidesa umożliwia obliczanie całkowito-liczbowych współczynników x i y, takich, że:
d = gcd (a, b) = ax + by.
Pseudokod rozszerzonego algorytmu Euklidesa: Ext_Euclid (a, b)
{
if(b = 0)
then return (a, 1, 0);
(d\ x’,y’) : = Ext_Euclid (b, a mod b); (d, x,y) : - (d\ y\ x’ - \_a /b\ y’); return (d, x, y);
}_
Niech a. h i n będą liczbami całkowitymi ( a, b, n e $ ) oraz n > 0. Notacja:
a =b (mod n)
oznacza, że a i b przystają do siebie według modułu n (są kongruentne modulo n), i równoważna jest temu, że n I (a - b).
Relacja = nosi nazwę kongruencji.
Przykłady:
19 s 7 (mod 12)42 = -9 (mod 17) -14 = 26 (mod 4)