Mathematics

 

Euclid's Algorithm

Euclid's Algorithm is one of the oldest algorithms known to  mankind. It was found in Euclid's Elements, something dates back to 300 B.C.

When Euclid came up with the algorithm, mathematics was not known as it is today; in fact, he used geometrical methods in his discovery, as algebra was not known at that time, as a branch of mathematics.

Euclid's algorithm is used to find the HCF - Highest Common Factor - or GCD - Greatest Common Divider - of two numbers.

The following animation shows how it determines the HCF of two numbers:

 

euclid's algorithm

 

The corresponding flow chart for the Euclid algorithm is as follows:

 

euclid's algorithm flowchart

 

Please work out the following questions to complement what you have just learnt.

 

and

 

 

 

Recommended Reading


 

Maths is challenging; so is finding the right book. K A Stroud, in this book, cleverly managed to make all the major topics crystal clear with plenty of examples; popularity of the book speak for itself - 7th edition in print.

Recommended - GCSE & iGCSE


 

This is the best book available for the new GCSE(9-1) specification and iGCSE: there are plenty of worked examples; a really good collection of problems for practising; every single topic is adequately covered; the topics are organized in a logical order.

Recommended for A Level


 

This is the best book that can be recommended for the new A Level - Edexcel board: it covers every single topic in detail;lots of worked examples; ample problems for practising; beautifully and clearly presented.