Calculadora de MDC

24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5 ⇒ mdc(24, 36, 60) = 2² × 3 = 12, e os divisores comuns dos três são 1, 2, 3, 4, 6, 12

24, 36, 60

Os números a comparar, de dois a dez, cada um um número inteiro de 1 a 1.000.000. Eles são separados por espaços, vírgulas ou pontos e vírgulas, então 24 36 60 e 24, 36, 60 são a mesma entrada. Um ponto decimal ou uma barra de fração é recusado em vez de arredondado, e o 0 também — não existe uma convenção única para mdc(0, 0), e esta página não vai escolher uma por você

2³ × 3

A fatoração em primos de 24: três fatores dois e um fator três. Todo número inteiro acima de 1 tem exatamente uma decomposição assim, e é isso que faz o segundo método funcionar

2² × 3

A parte em que as três fatorações concordam: dois dois e um três, logo 4 × 3 = 12. A regra é tomar a menor potência de cada primo compartilhado, e não a maior — o fator precisa dividir todos os números, então nunca pode ser mais do que o mais sovina deles permite

1, 2, 3, 4, 6, 12

Todos os divisores comuns, em ordem crescente. O último é o máximo divisor comum, e a lista é a conferência: 12 divide 24, 36 e 60 sem deixar resto, e o divisor seguinte acima dele, o 18, divide apenas 36

mdc(a, b, c) = mdc(mdc(a, b), c)

Como mais de dois números são tratados: dois a dois, levando a resposta corrente para dentro do número seguinte. Não é um método separado, é o método de dois números aplicado repetidamente, e é por isso que a página dá a mesma resposta para três números que daria para qualquer par por onde você comece

coprimos

O nome de um par cujo único divisor comum é 1, de modo que o máximo divisor comum é 1. 9 e 20 são coprimos mesmo sem nenhum dos dois ser primo, e quaisquer dois números inteiros consecutivos são sempre coprimos

Reduzir uma fração à forma irredutível é o uso do dia a dia: 24/36 vira 2/3 depois de dividir as duas partes por 12, e esse mesmo passo é a primeira coisa que toda página de frações daqui faz. Reduzir uma receita ou um desenho à sua menor razão de números inteiros é a mesma operação com outra roupa — uma mistura escrita 24 : 36 : 60 é a mesma mistura que 2 : 3 : 5, e a segunda versão é a que cabe em um rótulo. Nos exercícios de aritmética o fator é pedido diretamente, e a lista impressa de divisores comuns é o desenvolvimento: ela mostra que a resposta foi encontrada comparando divisores, e não adivinhada. Há mais dois lugares em que ele aparece. Ladrilhar um retângulo com o maior quadrado possível é uma pergunta de máximo divisor comum disfarçada, e a resposta é o tamanho do ladrilho. E na teoria dos números, dois números serem coprimos é a condição que faz vários outros resultados funcionarem, inclusive o que sustenta a criptografia RSA — um módulo só é seguro quando é coprimo em relação ao expoente usado com ele. Quando os números são incômodos, 1.071 e 462 por exemplo, decompô-los à mão deixa de ser prático e o algoritmo de Euclides assume; os exemplos da página mostram os dois caminhos chegando ao mesmo 21. Quando você quer só o maior divisor e não a lista, a Calculadora de MDC desta mesma página já é a versão curta; quando a pergunta é o menor múltiplo em vez do maior divisor, a Calculadora de MMC é a página irmã.

1. O máximo divisor comum de 24, 36 e 60

   1. Divisores de 24: 1, 2, 3, 4, 6, 8, 12, 24
   2. Divisores de 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
   3. Divisores de 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
   4. Fique com os que as três listas contêm: 1, 2, 3, 4, 6, 12
   5. O maior deles é 12, então o máximo divisor comum é 12

   A entrada padrão, e a que a tabela abaixo percorre por inteiro. Fazendo por fatoração em primos: 24 é 2³ × 3, 36 é 2² × 3², 60 é 2² × 3 × 5, os três compartilham 2² e um 3, e 2² × 3 é 12. A lista de divisores comuns é a parte que vale guardar — é a única saída que mostra que a resposta é o maior, e não apenas um divisor compartilhado, já que 8 e 9 dividem dois dos três números cada um, mas não todos.

2. Números incômodos: 1.071 e 462

   1. 1.071 ÷ 462 = 2 com resto 147
   2. 462 ÷ 147 = 3 com resto 21
   3. 147 ÷ 21 = 7 com resto 0 — o resto chegou a zero, então pare
   4. O último resto diferente de zero é 21, então o máximo divisor comum é 21
   5. Confira decompondo os dois: 1.071 = 3 × 3 × 7 × 17 e 462 = 2 × 3 × 7 × 11, então a parte compartilhada é 3 × 7

   É por causa deste par que o algoritmo de Euclides está na página: nenhum dos dois números é decomponível de relance, e listar divisores à mão seria lento e sujeito a erro. Três divisões resolvem. A resposta 21 é também o maior número que divide os dois, e a lista compartilhada é curta — 1, 3, 7, 21 —, o que costuma ser o sinal de que dois números têm pouco em comum.

3. Números coprimos: 9 e 20

   1. Divisores de 9: 1, 3, 9
   2. Divisores de 20: 1, 2, 4, 5, 10, 20
   3. O único divisor que as duas listas compartilham é 1
   4. O máximo divisor comum é, portanto, 1

   Uma resposta igual a 1 é uma resposta de verdade, não uma falha — os dois números são coprimos. Isso acontece sempre que os números não compartilham nenhum primo, e é comum: dois números inteiros consecutivos são sempre coprimos, e um primo emparelhado com qualquer número que não seja múltiplo dele também. Nesta página um par coprimo volta com a menor lista de divisores comuns possível, um único 1.

4. Um número emparelhado consigo mesmo: 36 e 36

   1. Divisores de 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
   2. As duas entradas da lista são o mesmo número, então as duas listas de divisores são idênticas
   3. O maior divisor compartilhado é o próprio 36

   O extremo superior do que a resposta pode ser: o máximo divisor comum de uma lista nunca pode ser maior que o menor número dela, e ele alcança esse teto exatamente quando o menor número divide todos os outros. Repetir um número na entrada não muda nada — o MDC de 36 e 36 é 36, o mesmo de uma lista com um único número.

Cada número precisa ser um número inteiro de 1 a 1.000.000, e é preciso haver entre dois e dez deles. O zero é recusado, e isso é uma decisão, não um descuido: mdc(0, 5) é 5 sob uma convenção comum e indefinido sob outras, e mdc(0, 0) é 0 em alguns livros e simplesmente não definido no resto. Imprimir qualquer uma dessas respostas estaria errado para um leitor que segue outra convenção, então a página pede números positivos. Os números negativos são recusados pelo mesmo tipo de razão — o MDC de −24 e 36 é 12 na maior parte dos tratamentos, mas as regras de sinal são uma convenção à parte que esta página não enuncia. Decimais e frações são recusados em vez de arredondados: um máximo divisor comum é uma afirmação sobre números inteiros dividindo números inteiros, e 2,5 ÷ 1,25 não deixa resto, o que tornaria a resposta sem sentido. Os separadores podem ser espaços, vírgulas ou pontos e vírgulas, misturados ou não; qualquer outra coisa é tratada como parte de um número e torna a entrada ilegível. A tabela de referência abaixo é fixa em 24, 36 e 60 e não acompanha o que você digitou — o painel responde aos seus números, a tabela mostra o método. Entradas repetidas são permitidas e não mudam nada. A resposta é exata, nunca arredondada: todo valor desta página é um inteiro bem dentro da faixa que uma máquina guarda exatamente. A lista de divisores comuns é impressa como texto puro, sem separador de milhar, enquanto o máximo divisor comum é impresso como número e segue a grafia numérica do idioma.

Como acho o máximo divisor comum à mão?

Liste os divisores de cada número e fique com o maior que todos compartilham. Para 24, 36 e 60 essas listas terminam em 12, então o máximo divisor comum é 12. O caminho mais rápido para números grandes é o algoritmo de Euclides: divida o maior pelo menor, troque o maior pelo resto e repita até o resto ser zero — para 1.071 e 462 isso são três divisões e a resposta é 21. Os dois caminhos dão o mesmo número, e os dois aparecem nos exemplos acima.

O que significa um MDC igual a 1?

Que os números são coprimos, o que é uma resposta normal e não um sinal de que algo deu errado. 9 e 20 não compartilham nenhum primo, então 1 é o único número que divide os dois. Isso acontece muito: quaisquer dois números inteiros consecutivos são coprimos, e um primo emparelhado com qualquer coisa que não seja múltiplo dele também. A lista de divisores comuns volta como um único 1 nesse caso.

Por que a página recusa 0 e números negativos?

Porque a resposta dependeria de uma convenção que esta página não enuncia. mdc(0, 5) é 5 em muitos livros e indefinido em outros, e mdc(0, 0) é 0 em alguns tratamentos e não definido no resto. Os negativos trazem um conjunto separado de regras de sinal. Em vez de escolher uma convenção e imprimi-la em silêncio, a página pede números inteiros de 1 para cima, onde todas as fontes concordam.

Como funciona o método da fatoração em primos?

Decomponha cada número em primos e fique com os primos que aparecem em todos os números, tomando a menor potência de cada um. Para 24, 36 e 60 isso é 2² e 3, então a resposta é 12. A razão de ter de ser a menor potência é que o fator precisa dividir todos os números da lista: 36 tem 3², mas 24 tem apenas um 3, então um segundo 3 quebraria a divisão de 24. A fatoração é mais lenta que o algoritmo de Euclides em números incômodos, mas ela explica a resposta.

A resposta pode ser maior que o menor número da lista?

Não. Um divisor comum de uma lista precisa dividir o menor número dela, então nunca pode passar desse número, e o MDC alcança exatamente esse teto quando o menor número divide todos os outros. O MDC de 36 e 36 é 36, e o de 12, 24 e 36 é 12. Ele também nunca é menor que 1, já que 1 divide todo número inteiro.

Para que serve o máximo divisor comum?

Reduzir uma fração à forma irredutível é o uso mais comum: dividir as duas partes de 24/36 por 12 dá 2/3, o mesmo valor com o menor denominador possível. Reduzir uma razão é o mesmo passo — 24 : 36 : 60 é a mesma mistura que 2 : 3 : 5. E dois números serem coprimos, o que é o mesmo que o MDC deles ser 1, é a condição de que vários resultados da teoria dos números precisam, inclusive o que sustenta a criptografia RSA.

• Greatest common divisor — the definition, the Euclidean algorithm, and the prime factorization method — Wolfram MathWorld (United States)
• Divisor — what it means for one whole number to divide another exactly, and how divisors are listed in pairs — Wolfram MathWorld (United States)
• Divisors of n arranged as a triangle — the sequence 1; 1, 2; 1, 3; 1, 2, 4; … that the divisor column of the table below is taken from, catalogued as OEIS A027750 — OEIS Foundation Inc. (United States)