The Euclidean algorithm involves an iterative subtraction process:
948-292=656, replace 948 with 656:
656-292=364, replace 656 with 364:
364-292=72, replace 364 with 72:
292-72=220, replace 292 with 220:
220-72=148, replace 220 with 148:
148-72=76, replace 148 with 76:
76-72=4, replace 76 with 4:
72-4=68, replace 72 with 68:
68-4=64, ... eventually:
4-4=0 showing 4 to be the GCD (or HCF).
A faster method:
948/292=3 rem 72. Replace 948 with 72:
|72-292|=220 replaces 948-292.
Now 292 is the larger number:
292/220=1 rem 72. 72 replaces 292.
|72-220|=148 replaces 292-220.
Now 220 is the larger number.
220/148=1 rem 72, which replaces 220.
|72-148|=76.
148/76=1 rem 72, which replaces 148.
|72-76|=4.
76/4=19 rem 0, implying 4 is GCD.
The general procedure can be expressed as an algorithm:
GCD(a,b→c)
START
start:
a→c; hold a
IF a=b THEN GOTO exit:
IF a<b THEN
BEGIN
; exchange values a and b
b→a; transfer a value to b
c→b; transfer c value to a
END
a mod b→a; divide a by b and put remainder in a
ABS(b-a)→a; put absolute difference between a and b into a
GOTO start
exit:
RETURN c
FINISH
This is an illustration and example using a hypothetical language. It may not be the most efficient algorithm but it works for all positive integers a and b.