What is Euclid's Algorithm?

Updated: 4/28/2022
User Avatar

Wiki User

14y ago

Best Answer

Euclid's algorithm is a popular algorithm to compute the GCD of two numbers.


Gcd(a,b) = Gcd(b, a mod b), where a>=b and

Gcd(a,0) = a

Say we want to find the GCD of 72 and 105. 105 mod 72 = 33, so GCD(72,105) = GCD(33,72) 72 mod 33 = 6, so GCD(33,72) = GCD(6,33) 33 mod 6 = 3 so GCD(6,33) = GCD(3,6) 6 mod 3 = 0 so GCD(3,6) = GCD(0,3) = 3. So the GCD of 72 and 105 is 3.

User Avatar

Wiki User

14y ago
This answer is:
User Avatar
Study guides


14 cards

Is glucose solution a homogenous mixture

Hearing sight sound and smell are examples of that you can use to make observations

What type of chemical weathering is caused when rocks sit in a pool of saltwater

Which of the following is not a step in the inquiry process

See all cards
148 Reviews

Add your answer:

Earn +20 pts
Q: What is Euclid's Algorithm?
Write your answer...
Still have questions?
magnify glass
Related questions

What is euclids theory?

need a simple explanation of Euclids theory.

Who are euclids parents?


Books written by euclid?

euclids elements

What were euclids favorite areas of mathematics?


What was euclids major maths discoveries?


Title of thirteenth book in euclids elements?


Whats the oldest plane in the world?

euclids elements

What were some of euclids accomplishments?

His major accomplishment was in philosophy and mathematics

How many books in euclids eiements?

There are 13 books in Euclid's Elements.

What is the name of the guy who wrote Euclids elements?

'Elements' was written by Euclid.

What is euclids area of expertise?

Euclids has expertise in server transaction performance monitor(Internet operations services for enterprise) for its expertise yodlee has selected Euclids for its transaction management performance monitoring.For more query and problems related to any educational to your assignments just log on to for online homework help and online assignment help.

What is euclids full name?

Euclid of Alexandria or Eukleides