6161619793

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);

}_

KONGRUENCJE

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)