The Euclidean Algorithm an ancient Greek method for finding the greatest common divisor of two numbers. In spite of its age, it is still of great importance in modern mathematics and computing, for example in encryption algorithms such as RSA.

There is a great video from James Tanton explaining the algorithm here.

Below is TI-Basic implementation of the algorithm.

0->A:1->B
Repeat A>=B
    ClrHome
    Disp "ENTER A AND B, WITH A>=B"
    Prompt A,B
End
While A!=B
    A-B->C
    max(B,C)->A
    min(B,C)->B
End
Disp A

You can download the 8XP (TI-Basic) file here.

There is a more efficient version which uses division instead of subtraction, but this version is generally easier to follow. It takes a while for most people to really understand how particular algorithms work, so be patient with yourself and try tracing the algorithm using specific examples – e.g. what are the values for A, B & C when you try to find GCD(24, 18)?

Let me know how you get on in the comments.

Sharing is caring!