# The greatest common divisor of two integers

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

### Esta página existe graças aos esforços das seguintes pessoas:

#### Timur

Criado: 2011-06-22 09:48:56, Ultima atualização: 2021-03-09 20:21:56

Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.

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 the Euclidean algorithm.

The euclidean algorithm is straightforward.
You start building a sequence of numbers. The first one is the greatest of two integers; the second is the opposite; the third is the remainder of the division of two previous numbers; the fourth is the remainder of the division of the second and third one, etc. The 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. The third member is the remainder of the division of 17 to 13
17, 13, 4

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

4 step. The fifth member is the remainder of the 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

#### The greatest common divisor

GCD

URL copiado para a área de transferência