Euclid's algorithm determines the greatest common divisor of two integers. The algorithm is based on the observation that, if x divides both a and b, then x divides their difference a – b. The trick is to find the largest such x.

Assume (without loss of generality) that a > b. If x divides a – b, then it also divides a – qb, where q is an integer. Let r = a – qb. If n ≠ 0, and x divides a – qb, then x divides r. We have now reduced the problem of finding the largest x such that x divides a and b to the problem of finding the largest x such that x divides b and r. (To see this, realize that if x divides b and r, then x divides qb + r, or a.) We iterate until r is 0. Then x is the greatest common divisor of a and b.

If we take q to be the integer portion of a/b, these operations can form a simple table, as follows.

The algorithm (in pseudocode) is as follows.

function gcd(a : integer, b : integer) : integer;
var r : integer;
    rprev: integer;
begin
rprev := r := 1;
while r <> 0 do begin
    rprev := r;
    r := a mod b;
    write 'a = ', a, 'b =', b, 'quotient = ', a div b,
          'remainder = ', r, endline;
    a := b;
    b := r;
end;
gcd := rprev;
end.

The “write” corresponds to the lines in the tables in the examples above.

The Extended Euclidean Algorithm determines two integers x and y such that

In order for these integers to exist and be unique, the greatest common divisor of a and b must be 1. The following algorithm (in pseudocode) returns x and y.

proc eeuclid(a : integer, b : integer,
                var x : integer, var y : integer) : integer;
var q, u: integer;
       xprev, yprev, uprev: integer;
       xtmp, ytmp, utmp: integer;
begin
       uprev := a; u := b;
       xprev := 0; x := 1; yprev := 1; y := 0;
       write 'u = ', uprev, 'x = ', xprev, 'y = ', yprev,
                endline;
       write 'u = ', u, 'x = ', x, 'y = ', y;
       while u <> 0 do begin
             q := uprev div u;
             write 'q = ', q, endline;
             utmp := uprev – u * q; uprev := u; u := utmp;
             xtmp := xprev – x * q; xprev := x; x := xtmp;
             ytmp := yprev – y * q; yprev := y; y := ytmp;
             write 'u = ', u, 'x = ', x, 'y = ', y;
       end;
       write endline;
       x := xprev; y := yprev;
end.

The “write” corresponds to the lines in the tables in the examples below. The variable u contains xa + yb at each step.

Recall that if ax mod n = 1, then there exists an integer k such that ax = 1 + kn. Rewriting this, ax – kn = 1. Define j = –k, to yield ax + jn = 1. So, to find x and j, use the Extended Euclidean Algorithm. As before, a and n must be relatively prime.

From the fundamental laws of modular arithmetic,

Thus, if x solves the equation ax mod n = 1, we can multiply both sides by b to get

So, we first solve ax mod n = 1 for x and then compute bx mod n.