Artigos

1.5: O Maior Divisor Comum - Matemática


Nesta seção, definimos o máximo divisor comum (mdc) de dois inteiros e discutimos suas propriedades. Também provamos que o máximo divisor comum de dois inteiros é uma combinação linear desses inteiros.

Dois inteiros (a ) e (b ), não ambos (0 ), podem ter apenas finitos divisores (consulte Exercício [exer: sizeofdivisors]) e, portanto, podem ter apenas finitos divisores em comum. Nesta seção, estamos interessados ​​no maior desses divisores comuns.

Dado (a, b in ZZ ), não ambos zero, o maior divisor comum é o maior inteiro que divide (a ) e (b ), e é escrito ( gcd (a, b) ) (ou às vezes apenas ((a, b) )).

Quando torna algumas fórmulas mais simples, escreveremos ( gcd (0,0) = 0 ).

[por exemplo: gcda] O máximo divisor comum de 24 e 18 é 6. Em outras palavras ( gcd (24,18) = 6 ).

(a, b in ZZ ) são considerados relativamente nobre if ( gcd (a, b) = 1 ).

[por exemplo: gcdb] O máximo divisor comum de 9 e 16 é 1, portanto, eles são relativamente primos.

Observe que cada número inteiro tem divisores positivos e negativos. Se (a ) é um divisor positivo de (m ), então (- a ) também é um divisor de (m ). Portanto, por nossa definição do máximo divisor comum, podemos ver que ( gcd (a, b) = gcd (| a |, | b |) ).

Podemos usar o mdc de dois inteiros para fazer inteiros relativamente primos:

[thm: dividebygcd] Se (a, b in ZZ ) tiver ( gcd (a, b) = d ) então ( gcd (a / d, b / d) = 1 ).

Corrija (a, b in ZZ ). Mostraremos que (a / d ) e (b / d ) não têm divisores positivos comuns além de (1 ). Seja (k in NN ) um divisor de (a / d ) e (b / d ), então ( existe m, n in NN ) tal que [a / d = km hspace {0,3 cm} mbox {and} b / d = kn ] Assim, obtemos que [a = kmd hspace {0,3 cm} mbox {e} b = knd. ] Logo, (kd ) é um divisor comum de (a ) e (b ). Além disso, (kd geq d ). No entanto, (d ) é o máximo divisor comum de (a ) e (b ). Como resultado, obtemos que (k = 1 ).

O próximo teorema mostra que o máximo divisor comum de dois inteiros não muda quando adicionamos um múltiplo de um dos dois inteiros ao outro.

Seja (a, b, c in ZZ ). Então ( gcd (a, b) = gcd (a + cb, b) ).

Mostraremos que cada divisor de (a ) e (b ) também é um divisor de (a + cb ) e (b ) e vice-versa. Portanto, eles têm exatamente os mesmos divisores. Assim, obtemos que o máximo divisor comum de (a ) e (b ) também será o máximo divisor comum de (a + cb ) e (b ). Seja (k ) um divisor comum de (a ) e (b ). Pelo teorema [thm: divisibilitylincombs], (k mid (a + cb) ) e, portanto, (k ) é um divisor de (a + cb ). Agora suponha que (l ) é um divisor comum de (a + cb ) e (b ). Também pelo teorema [thm: divisibilitylincombs] temos, [l mid ((a + cb) -cb) = a. ] Como resultado, (l ) é um divisor comum de (a ) e (b ) e o resultado segue.

[por exemplo: gcdc] Observe que ( gcd (4,14) = gcd (4,14-3 cdot 4) = gcd (4,2) = 2 ).

Apresentamos agora um teorema que prova que o máximo divisor comum de dois inteiros pode ser escrito como uma combinação linear dos dois inteiros.

[thm: gcdislincomb] Sejam (a, b in ZZ ) não ambos sendo zero. Então ( gcd (a, b) ) é o menor número natural que tem a forma (d = ma + nb ) para algum (m, n em ZZ ).

Suponha, sem perda de generalidade, que (a, b in NN ) são inteiros positivos. Considere o conjunto [S = {d in NN mid d = ma + nb text { para algum } m, n in ZZ } . ] (S ) é não- vazio, pois (a = 1 cdot a + 0 cdot b ) e (b = 0 cdot a + 1 cdot b ) estão ambos em (S ). Seja (d in NN ) o menor elemento de (S ), cuja existência é garantida pelo princípio da boa ordenação. Observe (d = ma + nb ) para algum (m, n in ZZ ), uma vez que (d in S ). Ainda devemos provar que (d ) divide ambos (a ) e (b ) e que é o maior divisor comum.

Pelo algoritmo de divisão, ( existe q, r in ZZ ) tal que [a = qd + r, 0 leq r

O mesmo tipo de argumento mostrará que (d mid b ).

Agora observe que se houver um divisor (c ) que divide (a ) e (b ). Então, (c ) divide qualquer combinação linear de (a ) e (b ) pelo Teorema [thm: divisibilitylincombs]. Portanto, (c mid d ). Isso prova que qualquer divisor comum de (a ) e (b ) divide (d ). Portanto, (c leq d ), e (d ) é o máximo divisor comum.

Existe uma aplicação simples que será muito útil no futuro:

[cor: intlincombrelprime] Se (a, b in ZZ ) são relativamente primos, então ( existe m, n in ZZ ) tal que (ma + nb = 1 ).

Para alguns (n in NN ), deixe (a_1, a_2, dots, a_n in ZZ ) não ser tudo (0 ). O maior divisor comum desses inteiros é o maior inteiro que divide todos eles e é denotado como ( gcd (a_1, dots, a_n) ).

Para alguns (n in NN ), (a_1, a_2, dots, a_n in ZZ ) são considerados mutuamente relativamente primos if ( gcd (a_1, a_2, dots, a_n) = 1 ).

[por exemplo: mutrelprime] Os inteiros (3, 6, 7 ) são mutuamente relativamente primos, uma vez que ((3,6,7) = 1 ) embora ((3,6) = 3 ).

Para alguns (n in NN ), (a_1, a_2, dots, a_n in ZZ ) são chamados par relativamente primo if ( forall i, j in NN ) tal que (i le n ), (j le n ), e (i neq j ), temos ( gcd (a_i, a_j) = 1 ).

[por exemplo: pairwiserelprime] Os inteiros (3,14,25 ) são pares relativamente primos. Observe também que esses inteiros são mutuamente relativamente primos.

Para (n in NN ) e (a_1, dots, a_n in ZZ ), se (a_1, a_2, dots, a_n ) são pares relativamente primos, então eles são mutuamente relativamente primos.

Exercícios para §5

Encontre o máximo divisor comum de 15 e 35.

Encontre o máximo divisor comum de 100 e 104.

Encontre o máximo divisor comum de -30 e 95.

Let (m in NN ). Encontre o máximo divisor comum de (m ) e (m + 1 ).

Seja (m in NN ), encontre o máximo divisor comum de (m ) e (m + 2 ).

Mostre que se (m, n in ZZ ) tem ( gcd (m, n) = 1 ), então ( gcd (m + n, mn) = 1 ) ou (2 )

Mostre que se (m em NN ), então (3m + 2 ) e (5m + 3 ) são relativamente primos.

Mostre que se (a, b in ZZ ) são relativamente primos, então ( gcd (a + 2b, 2a + b) = 1 ) ou (3 ).

Mostre que se (a_1, a_2, dots, a_n in ZZ ) não são todos (0 ) e (c in NN ), então ( gcd (ca_1, ca_2, dots , ca_n) = c cdot gcd (a_1, a_2, dots, a_n). )


Máximo divisor comum (GCD) - problemas matemáticos


    A sala de aula tem 9 metros de comprimento. A largura da sala de aula é menor e pode ser passada em etapas igualmente longas de 55 CM ou 70 CM. Determine a largura da sala de aula.
    O terreno, que tem dimensões de 220 me 308 m, o proprietário pretende dividir em lotes quadrados igualmente grandes e com a maior área possível. Quanto tempo vai durar um lado da trama?
    A colônia de jardinagem com dimensões de 180 me 300 m deve ser totalmente dividida em áreas quadradas igualmente grandes com a maior área possível. Calcule quantas dessas áreas quadradas podem ser obtidas e determine o comprimento lateral do quadrado.
    Nas duas salas de jantar do edifício recreativo, há cadeiras igualmente dispostas ao redor das mesas. Um máximo de 78 pessoas podem jantar na primeira sala de jantar e 54 pessoas na segunda. Quantas cadeiras podem haver em torno de uma mesa?
    A partir de duas varetas de 240 cm e 210 cm de comprimento, é necessário cortar as estacas mais compridas possíveis para as flores para que não fiquem resíduos. Quantas cavilhas serão?
    O bloco de madeira mede 12 cm, 24 cm e 30 cm. Peter quer cortá-lo em vários cubos idênticos. Pelo menos quantos cubos ele consegue?
    A partir do menor número de cubos idênticos cujo comprimento da borda é expresso por um número natural, podemos construir um bloco com dimensões 12dm x 16dm x 20dm?
    Quantas das maiores folhas quadradas o encanador cortou o favo de mel de 16 dm e 96 dm?
    O lar infantil recebeu um presente para Nicholas de 54 laranjas, 81 estatuetas de chocolate e 135 maçãs. Cada criança recebeu o mesmo presente e não sobrou nada. a) Quantos pacotes podem ser preparados? b) o que as crianças encontraram na embalagem?
    Encontre o quociente antes do colchete - o maior divisor 51 a + 34 b + 68 121y-99z-33
    Às 6h, três linhas de ônibus partem da estação. A primeira linha tem um intervalo de 24 minutos. A segunda linha tem intervalo de 15 minutos. A terceira linha funciona em intervalos regulares de mais de 1 minuto. A terceira linha é executada ao mesmo tempo que t
    Encontre todos os divisores comuns dos números 30 e 45.
    Qual é o menor comprimento de uma corda que podemos cortar em 18 partes iguais e até 27 partes iguais (em decímetros)?
    Escreva sete números de 4 dígitos que são divisíveis por 3 e, ao mesmo tempo, por 4.
    Os ingressos para o espetáculo custavam algum número inteiro maior que 1. Além disso, a soma do preço dos ingressos infantil e adulto, bem como de seu produto, era a potência do número primo. Encontre todos os preços de ingressos possíveis.
    Roman caminhou na ponte. Ao ouvir o apito, ele se virou e viu Kamil correndo no início da ponte. Se ele fosse até ele, eles se encontrariam no meio da ponte. Roman, porém, correu e por isso não quis perder tempo voltando 150m.
    Uma engrenagem grande será usada para girar uma engrenagem menor. A engrenagem grande fará 75 rotações por minuto. A engrenagem menor deve fazer 384 revoluções por minuto. Encontre o menor número de dentes que cada engrenagem pode ter. [Dica: Use GCF ou LCM. ]
    É dado o número C = 281, D = 201. Encontre o maior número natural S de modo que o C: S, D: S estejam com o resto de 1,
    Divida um papel retangular com dimensões de 220 mm e 308 mm em quadrados do mesmo tamanho para que sejam os maiores possíveis. Especifique o comprimento do lado do quadrado.
    Quatro choupos estão crescendo ao longo do caminho. As distâncias entre eles são 35 m, 14 m e 91 m. Pelo menos quantos choupos precisam ser largados para criar o mesmo espaçamento entre as árvores? Quantos metros serão?

Prática

Listando os fatores

Questões

  1. Encontre o maior fator comum de 18 e 27.
  2. Encontre o maior fator comum de 25, 75 e 125.
  3. Encontre o maior fator comum de 19 e 32.

Soluções

  1. Os fatores positivos de 18 são 1, 2, 3, 6, 9 e 18.
    Os fatores positivos de 27 são 1, 3, 9 e 27.
    O maior número que aparece em ambas as listas é 9, então esse é o maior fator comum.
  2. Os fatores positivos de 25 são 1, 5 e 25.
    Os fatores positivos de 75 são 1, 3, 5, 25 e 75.
    Os fatores positivos de 125 são 1, 5, 25 e 125.
    O maior número em todas as três listas é 25, então esse é o maior fator comum.
  3. Os fatores positivos de 19 são 1 e 19.
    Os fatores positivos de 32 são 1, 2, 4, 8, 16 e 32.
    O maior e único número que aparece em ambas as listas é 1, então esse é o maior fator comum. Portanto, 19 e 32 são coprime.

Usando Fatoração Prime

Questões

  1. Encontre o maior fator comum de 1272 e 294.
  2. Encontre o maior fator comum de 900, 360 e 729.
  3. Encontre o maior fator comum de 72, 144, 258 e 824.

Soluções

  1. A fatoração principal de 1272 é 2x2x2x3x53.
    A fatoração principal de 294 é 2x3x7x7.
    Ambos 1272 e 294 contêm um 2 e um 3, então o maior fator comum é 2 & # 2153 = 6.
  2. A fatoração principal de 900 é 2x2x3x3x5x5.
    A fatoração principal de 360 ​​é 2x2x2x3x3x5.
    A fatoração principal de 729 é 3x3x3x3x3x3.
    Todas as três formas fatoradas incluem dois 3s, então o maior fator comum é 3 & # 2153 = 9.
  3. A fatoração principal de 72 é 2x2x2x3x3.
    A fatoração principal de 144 é 2x2x2x2x3x3.
    A fatoração principal de 258 é 2x3x43.
    A fatoração principal de 824 é 2x2x2x103.

Nesse caso, o único número que aparece em todas as quatro formas fatoradas é 2, que é o maior fator comum.


O Pulverizador

Obteremos muita quilometragem com o seguinte fato-chave:

O maior divisor comum de (a ) e (b ) é uma combinação linear de (a ) e (b ). Isso é,

para alguns inteiros (s ) e (t ).

Já sabemos do Lema 8.1.2.2 que toda combinação linear de (a ) e (b ) é divisível por qualquer fator comum de (a ) e (b ), por isso é certamente divisível pelo maior desses divisores comuns. Uma vez que qualquer múltiplo constante de uma combinação linear também é uma combinação linear, o Teorema 8.2.2 implica que qualquer múltiplo do mdc é uma combinação linear, dando:

Corolário 8.2.3. Um inteiro é uma combinação linear de (a ) e (b ) se for um múltiplo de ( text(a, b) ).

Provamos o Teorema 8.2.2 diretamente explicando como encontrar (s ) e (t ). Este trabalho é realizado por uma ferramenta matemática que remonta à Índia do século VI, onde era chamada kuttak, que significa & ldquoO Pulverizador. & rdquo Hoje, o Pulverizador é mais comumente conhecido como & ldquothe algoritmo Euclidiano gcd estendido & rdquo porque está muito próximo do algoritmo Euclid & rsquos.

Por exemplo, seguindo o algoritmo de Euclides & rsquos, podemos calcular o mdc de 259 e 70 da seguinte maneira:

O Pulverizer passa pelas mesmas etapas, mas requer alguma contabilidade extra ao longo do caminho: conforme calculamos ( text(a, b) ), acompanhamos como escrever cada um dos restantes (49, 21 e 7, no exemplo) como uma combinação linear de (a ) e (b ). Isso vale a pena, porque nosso objetivo é escrever o último resto diferente de zero, que é o GCD, como tal combinação linear. Para nosso exemplo, aqui está esta contabilidade extra:

Começamos inicializando duas variáveis, (x = a ) e (y = b ). Nas duas primeiras colunas acima, executamos o algoritmo de Euclides & rsquos. Em cada etapa, calculamos ( text(x, y) ) que é igual a (x - text(x, y) cdot y ). Então, nesta combinação linear de (x ) e (y ), substituímos (x ) e (y ) por combinações lineares equivalentes de (a ) e (b ), que já havíamos calculado. Depois de simplificar, ficamos com uma combinação linear de (a ) e (b ) igual a ( text(x, y) ), conforme desejado. A solução final está embalada.

Isso deve deixar bem claro como e por que o Pulverizer funciona. Se você tiver dúvidas, pode ajudar trabalhar com o Problema 8.13, onde o Pulverizer é formalizado como uma máquina de estados e então verificado usando um invariante que é uma extensão daquele usado para o algoritmo de Euclides.

Como o Pulverizador requer apenas um pouco mais de computação do que o algoritmo de Euclides, você pode & ldquopulverizar & rdquo números muito grandes muito rapidamente usando este algoritmo. Como veremos em breve, sua velocidade torna o Pulverizer uma ferramenta muito útil no campo da criptografia.

Agora podemos reformular o Lema dos Jarros de Água 8.1.5 em termos do maior divisor comum:

Corolário 8.2.4. Suponha que temos jarros de água com capacidades (a ) e (b ). Então a quantidade de água em cada jarro é sempre um múltiplo de ( text(a, b) ).

Por exemplo, não há como formar 4 galões usando jarras de 3 e 6 galões, porque 4 não é um múltiplo de ( text(3, 6) = 3).


Algoritmo de Euclides para o maior divisor comum

De acordo com o algoritmo de Euclides para o maior divisor comum, o GCD de dois inteiros positivos (a, b) pode ser calculado como:

  • Se a = 0, então GCD (a, b) = b como GCD (0, b) = b.
  • Se b = 0, então GCD (a, b) = a como GCD (a, 0) = a.
  • Se a ≠ 0 e b ≠ 0, escrevemos 'a' na forma de resto de quociente (a = b × q + r) onde q é o quociente er é o resto, e a & gtb.
  • Encontre o GCD (b, r) como GCD (b, r) = GCD (a, b)
  • Repetimos esse processo até obter o restante como 0.

Exemplo: Encontre o GCD de 12 e 10 usando o Algoritmo de Euclides.
Solução: O GCD de 12 e 10 pode ser encontrado usando as etapas abaixo:
a = 12 e b = 10
a ≠ 0 eb ≠ 0
Na forma de resto de quociente, podemos escrever 12 = 10 × 1 + 2
Assim, GCD (10, 2) deve ser encontrado, como GCD (12, 10) = GCD (10, 2)

Agora, a = 10 e b = 2
a ≠ 0 eb ≠ 0
Na forma de resto de quociente, podemos escrever 10 = 2 × 5 + 0
Assim, GCD (2,0) deve ser encontrado, como GCD (10, 2) = GCD (2, 0)

Agora, a = 2 e b = 0
a ≠ 0 e b = 0
Assim, GCD (2,0) = 2

GCD (12, 10) = GCD (10, 2) = GCD (2, 0) = 2

Assim, GCD de 12 e 10 é 2.

O algoritmo de Euclides é muito útil para encontrar GCD de números maiores, pois nele podemos facilmente decompor os números em números menores para encontrar o maior divisor comum.

Tópicos relacionados ao maior divisor comum

Confira estes artigos interessantes para saber mais sobre o máximo divisor comum (GCD) e seus tópicos relacionados.


Calculadora do maior divisor comum

A calculadora GCD permite que você encontre rapidamente o maior divisor comum de um conjunto de números. Você pode inserir entre dois e dez inteiros diferentes de zero entre -2147483648 e 2147483647. Os números devem ser separados por vírgulas, espaços ou tabulações ou podem ser inseridos em linhas separadas.

Pressione o botão 'Calcular GCD' para iniciar o cálculo ou 'Reiniciar' para esvaziar o formulário e começar novamente.

Como para muitas outras ferramentas neste site, seu navegador deve ser configurado para permitir javascript para o programa funcionar.

Qual é o maior divisor comum?

O maior divisor comum (também conhecido como maior fator comum, maior divisor comum ou maior fator comum) de um conjunto de números é o maior número inteiro positivo que divide todos os números no conjunto sem resto. É o maior múltiplo de todos os números do conjunto.

O GCD é mais frequentemente calculado para dois números, quando é usado para reduzir as frações aos seus termos mais baixos. Quando o maior divisor comum de dois números é 1, os dois números são considerados coprime ou relativamente nobre.

Como o máximo divisor comum é calculado?

Esta calculadora usa Algoritmo de Euclides. Para saber mais sobre o algoritmo de Euclides ou o GCD, consulte este artigo da Wikipedia.

O GCD também pode ser calculado usando o mínimo múltiplo comum usando esta fórmula:


Uma das coisas mais úteis é quando queremos simplificar uma fração:

Exemplo: como podemos simplificar 1230?

Anteriormente, descobrimos que os fatores comuns de 12 e 30 são 1, 2, 3 e 6, e assim o O maior fator comum é 6.

Então o maior número que podemos dividir 12 e 30 exatamente por é 6, assim:

÷ 6
1230 = 25
÷ 6

O maior fator comum de 12 e 30 é 6.

E entao 1230 pode ser simplificado para 25


Primeiro, encontraremos a fatoração primária de 1 e 5. Depois, calcularemos os fatores de 1 e 5 e encontraremos o maior número de fator comum.

Etapa 2: Fatoração principal de 5

Os fatores principais de 5 são 5. Fatoração principal de 5 na forma exponencial é:

Etapa 3: Fatores de 1

Lista de fatores inteiros positivos de 1 que divide 1 sem resto.

Etapa 4: Fatores de 5

Lista de fatores inteiros positivos de 5 que divide 1 sem resto.

Etapa final: maior número de fator comum

Encontramos os fatores e a fatoração principal de 1 e 5. O maior número de fator comum é o GCF número.
Então o maior fator comum 1 e 5 é 1.


Relação com o mínimo múltiplo comum

O produto do maior divisor comum e do mínimo múltiplo comum de dois números é igual ao produto dos dois números. Assim, uma das maneiras mais fáceis (e mais sistemáticas) de encontrar o mínimo múltiplo comum é calcular o maior divisor comum e então dividir o produto dos números por esse valor. Essa relação é evidente ao usar o método de fatoração principal para calcular o maior fator comum e o mínimo múltiplo comum (usando a fatoração principal, os divisores com as maiores potências são multiplicados juntos), já que todos os divisores principais são usados ​​no GCF ou no LCM.


Planilhas do maior fator comum (GCF)

Uma grande coleção de planilhas do GCF é meticulosamente elaborada para alunos do 5º ao 8º ano. GCF também é conhecido como 'maior divisor comum' (GCD), 'maior fator comum' (HCF), 'maior medida comum' (GCM) ou 'divisor comum mais alto' (HCD). Baixe e imprima essas planilhas do GCF para encontrar o GCF de dois números, três números e mais. Experimente alguns desses folhetos gratuitamente!

Liste os fatores para cada par de números. Em seguida, compare para determinar o GCF dos dois números. As planilhas imprimíveis são categorizadas em três níveis com base no intervalo de números.

Use o método de fatoração principal para encontrar o GCF para cada par de números. Este lote de PDFs de planilha multinível contém um total de 150 problemas para alunos de 5ª e 6ª séries. Use a resposta para validar suas soluções.

Anote os fatores para cada par de números no diagrama de Venn. Em seguida, liste os fatores comuns na interseção. O maior fator listado na região de sobreposição é o GCF. Este conjunto inclui números de até 25.

Ilumine sua aula de matemática usando os Diagramas de Venn para encontrar o GCF de dois números. Apresentando números de até 99, esta compilação requer que os alunos listem os fatores, coloquem os fatores comuns na região de sobreposição e encontrem o GCF.

Encontre o GCF para o numerador e o denominador da fração fornecida neste conjunto de planilhas para impressão. Em seguida, reduza a fração ao seu termo mais baixo dividindo o numerador e o denominador pelo GCF. Números de até 25 estão incluídos nesta seção.

Facilite um melhor entendimento do GCF revisando sua habilidade com este pacote de planilhas para impressão que apresenta números até 99. Pratique encontrar o GCF e simplificar a fração usando o GCF.

Neste grupo de planilhas de pdf de 7ª e 8ª séries, determine o GCF para o conjunto de três números. Aplique o método de fatoração principal para listar os fatores comuns. Multiplique os fatores comuns para obter o GCF dos três números.

É hora de se familiarizar com o GCF de três números, elaborando os exercícios nesses pdfs cobrindo números até 99. Elabore o GCF encontrando o produto dos fatores primos comuns a todos os três números.

Ganhe um conhecimento profundo em encontrar o maior fator comum de polinômios com essas planilhas de ensino médio disponíveis em níveis fáceis e moderados, encontre o GCF de dois ou três monômios, GCF de polinômios, encontre o GCF usando o método de divisão e muito mais!


Conteúdo

Edição de Definição

O maior divisor comum (GCD) de dois inteiros diferentes de zero aeb é o maior inteiro positivo d tal que d é um divisor de aeb, ou seja, existem números inteiros e e f tais que uma = de e b = df e d é o maior desses números inteiros. O GCD de a e b é geralmente denotado por gcd (uma, b) . [9]

Esta definição também se aplica quando um de a e b é zero. Neste caso, o GCD é o valor absoluto do número inteiro diferente de zero: gcd (uma, 0) = mdc (0, uma) = | uma | . Este caso é importante como a etapa final do algoritmo euclidiano.

A definição acima não pode ser usada para definir mdc (0, 0), uma vez que 0 × n = 0 e zero, portanto, não tem o maior divisor. No entanto, zero é seu próprio maior divisor se o melhor é entendido no contexto da relação de divisibilidade, então mdc (0, 0) é comumente definido como 0. Isso preserva as identidades usuais para GCD, e em particular a identidade de Bézout, ou seja, aquele mdc (uma, b) gera o mesmo ideal que <uma, b>. [10] [11] [12] Esta convenção é seguida por muitos sistemas de álgebra computacional. [13] No entanto, alguns autores deixam mdc (0, 0) indefinido. [14]

O GCD de aeb é seu maior divisor comum positivo na relação de divisibilidade de pré-ordem. Isso significa que os divisores comuns de aeb são exatamente os divisores de seu GCD. Isso é comumente provado usando o lema de Euclides, o teorema fundamental da aritmética ou o algoritmo euclidiano. Este é o significado de "maior" que é usado para generalizações do conceito de GCD.

Edição de exemplo

O número 54 pode ser expresso como um produto de dois inteiros de várias maneiras diferentes:

54 × 1 = 27 × 2 = 18 × 3 = 9 × 6.

Destes, o maior é 6, por isso é o maior divisor comum:

Calcular todos os divisores dos dois números dessa maneira geralmente não é eficiente, especialmente para números grandes com muitos divisores. Métodos muito mais eficientes são descritos em § Cálculo.

Edição de números coprime

Dois números são chamados de relativamente primos, ou coprimos, se seu maior divisor comum for igual a 1. [15] Por exemplo, 9 e 28 são relativamente primos.

Uma vista geométrica Editar

Por exemplo, uma área retangular de 24 por 60 pode ser dividida em uma grade de: quadrados 1 por 1, quadrados 2 por 2, quadrados 3 por 3, quadrados 4 por 4, 6 por -6 quadrados ou quadrados 12 por 12. Portanto, 12 é o maior divisor comum de 24 e 60. Uma área retangular de 24 por 60 pode ser dividida em uma grade de quadrados de 12 por 12, com dois quadrados ao longo de uma borda (24/12 = 2) e cinco quadrados ao longo do outro (60/12 = 5).

Edição de redução de frações

O maior divisor comum é útil para reduzir as frações aos termos mais baixos. [16] Por exemplo, mdc (42, 56) = 14, portanto,

Edição múltipla menos comum

O máximo divisor comum pode ser usado para encontrar o mínimo múltiplo comum de dois números quando o máximo divisor comum é conhecido, usando a relação, [1]

Usando fatorações primárias Editar

Os maiores divisores comuns podem ser calculados determinando as fatorações principais dos dois números e comparando os fatores. Por exemplo, para calcular o mdc (48, 180), encontramos as fatorações principais 48 = 2 4 · 3 1 e 180 = 2 2 · 3 2 · 5 1 o GCD é então 2 min (4,2) · 3 min ( 1,2) · 5 min (0,1) = 2 2 · 3 1 · 5 0 = 12, conforme mostrado no diagrama de Venn. O LCM correspondente é então 2 máx. (4,2) · 3 máx. (1,2) · 5 máx. (0,1) = 2 4 · 3 2 · 5 1 = 720.

Na prática, esse método só é viável para números pequenos, pois o cálculo das fatorações primos leva muito tempo.

Algoritmo de Euclides Editar

O método introduzido por Euclides para calcular os maiores divisores comuns é baseado no fato de que, dados dois inteiros positivos a e b tais que uma & gt b , os divisores comuns de a e b são os mesmos que os divisores comuns de umab e B .

Portanto, o método de Euclides para calcular o maior divisor comum de dois inteiros positivos consiste em substituir o maior número pela diferença dos números e repetir isso até que os dois números sejam iguais: esse é seu maior divisor comum.

Por exemplo, para calcular mcd (48,18), procede-se da seguinte forma:

Este método pode ser muito lento se um número for muito maior que o outro. Portanto, a variante a seguir é geralmente preferida.

Algoritmo Euclidiano Editar

Um método mais eficiente é o Algoritmo euclidiano, uma variante em que a diferença dos dois números a e b é substituída pelo restante da divisão euclidiana (também chamada de divisão com resto) de a por b.

Denotando este resto como uma mod b , o algoritmo substitui (uma, b) de (b, uma mod b) repetidamente até que o par seja (d, 0), onde d é o máximo divisor comum.

Por exemplo, para calcular o gcd (48,18), o cálculo é o seguinte:

Isso novamente dá mdc (48, 18) = 6.

Algoritmo GCD de Lehmer Editar

O algoritmo de Lehmer é baseado na observação de que os quocientes iniciais produzidos pelo algoritmo de Euclides podem ser determinados apenas com base nos primeiros dígitos, o que é útil para números maiores do que uma palavra de computador. Em essência, extrai-se os dígitos iniciais, normalmente formando uma ou duas palavras de computador, e executam-se os algoritmos de Euclides nesses números menores, desde que seja garantido que os quocientes sejam iguais aos que seriam obtidos com os números originais. Esses quocientes são coletados em uma pequena matriz de transformação 2 por 2 (que é uma matriz de inteiros de uma única palavra), para usá-los todos de uma vez para reduzir os números originais [ esclarecimento necessário ] Este processo é repetido até que os números sejam pequenos o suficiente para que o algoritmo binário (veja abaixo) seja mais eficiente.

Este algoritmo melhora a velocidade, porque reduz o número de operações em números muito grandes e pode usar aritmética de hardware para a maioria das operações. Na verdade, a maioria dos quocientes são muito pequenos, então um bom número de etapas do algoritmo euclidiano pode ser coletado em uma matriz 2 por 2 de inteiros de uma palavra. Quando o algoritmo de Lehmer encontra um quociente muito grande, ele deve retornar a uma iteração do algoritmo euclidiano, com uma divisão euclidiana de números grandes.

Algoritmo Binário GCD Editar

O algoritmo binário GCD usa apenas subtração e divisão por 2. O método é o seguinte: Let uma e b ser os dois inteiros não negativos. Deixe o inteiro d seja 0. Existem cinco possibilidades:

Como gcd (uma, uma) = uma, o GCD desejado é uma × 2 d (Como uma e b são alterados nos outros casos, e d registra o número de vezes que uma e b foram divididos por 2 na próxima etapa, o GCD do par inicial é o produto de uma e 2 d ).

Então 2 é um divisor comum. Divida os dois uma e b por 2, incremento d por 1 para registrar o número de vezes que 2 é um divisor comum e continuar.

Então 2 não é um divisor comum. Dividir uma por 2 e continue.

Então 2 não é um divisor comum. Dividir b por 2 e continue.

Como gcd (uma,b) = gcd (b,uma), E se uma & lt b então troque uma e b. O número c = umab é positivo e menor que uma. Qualquer número que divide uma e b também deve dividir c então cada divisor comum de uma e b também é um divisor comum de b e c. Similarmente, uma = b + c e cada divisor comum de b e c também é um divisor comum de uma e b. Então, os dois pares (uma, b) e (b, c) têm os mesmos divisores comuns e, portanto, gcd (uma,b) = gcd (b,c) Além disso, como uma e b são ambos estranhos, c é uniforme, o processo pode ser continuado com o par (uma, b) substituídos pelos números menores (c/2, b) sem alterar o GCD.

Cada uma das etapas acima reduz pelo menos um dos uma e b embora os deixe não negativos e, portanto, só podem ser repetidos um número finito de vezes. Assim, eventualmente, o processo resulta em uma = b, o caso de parada. Então o GCD é uma × 2 d .

Exemplo: (uma, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) o GCD original é, portanto, o produto 6 de 2 d = 2 1 e uma= b= 3.

O algoritmo binário GCD é particularmente fácil de implementar em computadores binários. Sua complexidade computacional é

A complexidade computacional é geralmente dada em termos do comprimento n da entrada. Aqui, este comprimento é n = log ⁡ a + log ⁡ b, < displaystyle n = log a + log b,> e a complexidade é assim

Outros métodos Editar

Se uma e b são ambos diferentes de zero, o maior divisor comum de uma e b pode ser calculado usando o mínimo múltiplo comum (LCM) de uma e b:

mas mais comumente o LCM é calculado a partir do GCD.

que generaliza para uma e b números racionais ou números reais comensuráveis.

Keith Slavin mostrou que por estranho uma ≥ 1:

que é uma função que pode ser avaliada para b. [18] Wolfgang Schramm mostrou que

é uma função inteira na variável b para todos os inteiros positivos uma Onde cd(k) é a soma de Ramanujan. [19]

Complexidade Editar

A complexidade computacional do cálculo dos maiores divisores comuns tem sido amplamente estudada. [20] Se alguém usar o algoritmo Euclidiano e os algoritmos elementares para multiplicação e divisão, o cálculo do máximo divisor comum de dois inteiros de no máximo n bits é O (n 2). < displaystyle O (n ^ <2>).> Isso significa que o cálculo do maior divisor comum tem, até um fator constante, a mesma complexidade da multiplicação.

No entanto, se um algoritmo de multiplicação rápida for usado, pode-se modificar o algoritmo euclidiano para melhorar a complexidade, mas o cálculo de um maior divisor comum torna-se mais lento do que a multiplicação. Mais precisamente, se a multiplicação de dois inteiros de n bits levar um tempo de T(n), então o algoritmo conhecido mais rápido para o maior divisor comum tem uma complexidade O (T (n) log ⁡ n). < displaystyle O left (T (n) log n right).> Isso implica que o algoritmo conhecido mais rápido tem uma complexidade de O (n (log ⁡ n) 2). < displaystyle O left (n , ( log n) ^ <2> right).>

Complexidades anteriores são válidas para os modelos usuais de computação, especificamente máquinas de Turing multitape e máquinas de acesso aleatório.

O cálculo dos maiores divisores comuns pertence, portanto, à classe de problemas solucionáveis ​​em tempo quase-linear. Uma fortiori, o problema de decisão correspondente pertence à classe P de problemas solucionáveis ​​em tempo polinomial. O problema GCD não é conhecido como NC e, portanto, não há maneira conhecida de paralelizá-lo de forma eficiente nem como P-completo, o que implicaria que é improvável que seja possível paralelizar com eficiência a computação de GCD. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables if either problem is in NC or is P-complete, the other is as well. [21] Since NC contains NL, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.

Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in O(n/log n) time with n 1+ε processors. [22] Randomized algorithms can solve the problem in O((log n) 2 ) time on exp ⁡ ( O ( n log ⁡ n ) ) > ight) ight)> processors [ esclarecimento necessário ] (this is superpolynomial). [23]

  • Every common divisor of uma e b is a divisor of gcd(uma, b) .
  • gcd(uma, b) , where uma e b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = umap + bq , Onde p e q são inteiros. This expression is called Bézout's identity. Números p e q like this can be computed with the extended Euclidean algorithm.
  • gcd(uma, 0) = | uma | , para uma ≠ 0 , since any number is a divisor of 0, and the greatest divisor of uma is | uma |. [3][6] This is usually used as the base case in the Euclidean algorithm.
  • Se uma divides the product bc, and gcd(uma, b) = d , então uma/d divide c.
  • Se m is a non-negative integer, then gcd(muma, mb) = m⋅gcd(uma, b) .
  • Se m is any integer, then gcd(uma + mb, b) = gcd(uma, b) .
  • Se m is a positive common divisor of uma e b, then gcd(uma/m, b/m) = gcd(uma, b)/m .
  • The GCD is a multiplicative function in the following sense: if uma1 e uma2 are relatively prime, then gcd(uma1uma2, b) = gcd(uma1, b)⋅gcd(uma2, b) In particular, recalling that GCD is a positive integer valued function we obtain that gcd(uma, bc) = 1 if and only if gcd(uma, b) = 1 and gcd(uma, c) = 1 .
  • The GCD is a commutative function: gcd(uma, b) = gcd(b, uma) .
  • The GCD is an associative function: gcd(uma, gcd(b, c)) = gcd(gcd(uma, b), c) Thus gcd(uma, b, c,. ) can be used to denote the GCD of multiple arguments.
  • gcd(uma, b) is closely related to the least common multiple lcm(uma, b) : we have gcd(uma, b)⋅lcm(uma, b) = | umab | .
  • The following versions of distributivity hold true: gcd(uma, lcm(b, c)) = lcm(gcd(uma, b), gcd(uma, c)) lcm(uma, gcd(b, c)) = gcd(lcm(uma, b), lcm(uma, c)) .
  • If we have the unique prime factorizations of uma = p1e1p2e2 ⋅⋅⋅ pmem e b = p1f1p2f2 ⋅⋅⋅ pmfm Onde eeu ≥ 0 e feu ≥ 0 , then the GCD of uma e b is gcd(uma,b) = p1 min(e1,f1) p2 min(e2,f2) ⋅⋅⋅ pm min(em,fm) .
  • It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a completedistributive lattice with GCD as meet and LCM as join operation. [24] This extension of the definition is also compatible with the generalization for commutative rings given below.
  • In a Cartesian coordinate system, gcd(uma, b) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (uma, b) .
  • For non-negative integers uma e b, Onde uma e b are not both zero, provable by considering the Euclidean algorithm in base n: [25] gcd(numa − 1, nb − 1) = n gcd(uma,b) − 1 .
  • An identity involving Euler's totient function: gcd ( a , b ) = ∑ k | a and k | b φ ( k ) . >k|b>varphi (k).>

In 1972, James E. Nymann showed that k integers, chosen independently and uniformly from <1, . n>, are coprime with probability 1/ζ(k) Como n goes to infinity, where ζ refers to the Riemann zeta function. [26] (See coprime for a derivation.) This result was extended in 1987 to show that the probability that k random integers have greatest common divisor d é d −k /ζ(k). [27]

Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the GCD equals d é d −2 /ζ(2), and since ζ(2) = π 2 /6 we have

This last summation is the harmonic series, which diverges. Porém, quando k ≥ 3, the expected value is well-defined, and by the above argument, it is

Para k = 3, this is approximately equal to 1.3684. Para k = 4, it is approximately 1.1106.

The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ring, although in general there need not exist one for every pair of elements.

If R is a commutative ring, and a and b are in R , then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = uma e d·y = b) If d is a common divisor of a and b , and every common divisor of a and b divides d , then d is called a greatest common divisor of a and b.

With this definition, two elements a and b may very well have several greatest common divisors, or none at all. If R is an integral domain then any two GCD's of a and b must be associate elements, since by definition either one must divide the other indeed if a GCD exists, any one of its associates is a GCD as well. Existence of a GCD is not assured in arbitrary integral domains. However, if R is a unique factorization domain, then any two elements have a GCD, and more generally this is true in GCD domains. If R is a Euclidean domain in which euclidean division is given algorithmically (as is the case for instance when R = F[X] where F is a field, or when R is the ring of Gaussian integers), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.

The following is an example of an integral domain with two elements that do not have a GCD:

The elements 2 and 1 + √ −3 are two maximal common divisors (that is, any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √ −3 , but they are not associated, so there is no greatest common divisor of a and b.

Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring. This is the ideal generated by a and b , and is denoted simply (uma, b) In a ring all of whose ideals are principal (a principal ideal domain or PID), this ideal will be identical with the set of multiples of some ring element d then this d is a greatest common divisor of a and b. But the ideal (uma, b) can be useful even when there is no greatest common divisor of a and b. (Indeed, Ernst Kummer used this ideal as a replacement for a GCD in his treatment of Fermat's Last Theorem, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d , whence the ring-theoretic term.)


Assista o vídeo: MDC - Máximo Divisor Comum (Outubro 2021).