# Euclidean algorithm's algorithm in Pascal

Maybe Pascal isn't as popular today, but it's great for educational purposes. It is on his example that one of the main algorithms for cryptography will be shown, namely the Euclidean algorithm

## What is Euclidean's algorithm

Euclidean's algorithm is the fastest way to find the largest common divisor (NOD) of two numbers. Unlike the usual search, Euclidean's algorithm looks for an answer ten times faster.

A little bit about history. Euclidean was a mathematician who was born in 325 B.C. Euclidean's algorithm was published in his "beginning" writings, where, by the way, the theory of an infinite set of prime numbers was put forward.

## Scope of the algorithm

For programmers, NOD is not only a familiar topic from elementary school. The principles of divisor search are laid down in cryptographic methods of encryption, namely in the type of encryption RSA.

### Euclidean's subtraction algorithm

Let's look at the algorithm with an example. We need to find the greatest common divisor in the numbers 68 and 323:

A = 68

B = 323

1. A>B – No, then b = 323 – 68 = 255;

2. A>B – No, then b = 255 – 68 = 187;

3. A>B – No, then b = 187 – 68 = 119;

4. A>B – No, then b = 119 – 68 = 51;

5. A>B – Yes, then a = 68 – 51 = 17;

6. A>B – No, then b = 51 – 17 = 34;

7. A > B – No, then b = 34 – 17 = 17

8. A = B, Yes, then NOD = A = 17

Answer: NOD = 17

### Euclidean's algorithm with division

**Let's check with the same example:**

A = 68

B = 323

1. A>B – no, then B = 323 modulo 68 = 51;

2. A > B – Yes, then A = 68 modulo 51 = 17;

3. A>B – No, then B = 51 modulo 17 = 0;

4. A and B = 0, then the answer is 17 + 0 = 17.

Answer: NOD(68,323) = 17

This method is much faster than the first.

## Comparison with brute force

Now let's find the NOD in the most primitive way – by searching. Our numbers are 68, 323. Unexpectedly?

To be sure that our method works, we need to check 68 operations. And Euclidean managed in just 5. That's the difference. No one uses the brute-force method.

## Implementation on Pascal

**All that's left is to execute the code in pascal:**

vara, b: integer;

begin

write(‘a = ‘);

readln(a);

write(‘b = ‘);

readln(b);

while a <> b do

if a > b then

a := a – b

else

b := b — a; writeln(‘NOD = ‘, a);

end.

## Conclusion

Euclidean's algorithm is the most practical way to find the largest common divisor. It is necessary to know everyone who wants to learn the basics of algorithms in programming.