homechevron_rightStudychevron_rightMath

The greatest common divisor of two integers

This calculator determines the greatest common divisor of two integers using Euclidean algorithm

Creative Commons Attribution/Share-Alike License 3.0 (Unported)

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/323/. Also, please do not modify any references to the original work (if any) contained in this content.

The greatest common divisor of two integers m and n is the largest integer that divides them both.
This calculator determines the greatest common divisor of two integers using Euclidean algorithm

Euclidean algorithm is very simple.
You start building sequence of numbers. First one is greatest of two integers, second is opposite, third is remainder of division of two previous numbers, forth is remainder of division of second and third one, etc. Last remainder before zero is the answer.

I'll show by example.
Suppose we need to find GCD for 13 and 17

1 step. Create initial sequence
17, 13

2 step. Third member is the remainder of division of 17 to 13
17, 13, 4

3 step. Forth member is the remainder of division of 13 to 4
17, 13, 4, 1

4 step. Fifth member is the remainder of division of 4 to 1
17, 13, 4, 1, 0

1 is the last remainder before 0, so, this is our answer.
And numbers those GCD is 1 are called prime numbers

PLANETCALC, The greatest common divisor

The greatest common divisor

GCD
 

URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, The greatest common divisor of two integers

Comments