Maior divisor comum - Greatest common divisor

Em matemática , o maior divisor comum ( GCD ) de dois ou mais inteiros , que nem todos são zero, é o maior inteiro positivo que divide cada um dos inteiros. Para dois inteiros x , y , o maior divisor comum de x e y é denotado . Por exemplo, o GCD de 8 e 12 é 4, ou seja ,.

No nome "máximo divisor comum", o adjetivo "maior" pode ser substituído por "mais alto", e a palavra "divisor" pode ser substituída por "fator", de modo que outros nomes incluam o fator comum mais alto ( hcf ), etc. Historicamente, outros nomes para o mesmo conceito incluíram a maior medida comum .

Esta noção pode ser estendida para polinômios (consulte Polinômio máximo divisor comum ) e outros anéis comutativos (consulte § Em anéis comutativos abaixo).

Visão geral

Definição

O maior divisor comum (GCD) de dois inteiros diferentes de zero a e b é o maior inteiro positivo d tal que d é um divisor de a e b ; ou seja, existem inteiros e e f tais que a = de e b = df , e d é o maior desses inteiros. O GCD de um e b é geralmente indicado GCD ( a , b ) .

Esta definição também se aplica quando um de a e b é zero. Nesse caso, o GCD é o valor absoluto do número inteiro diferente de zero: mdc ( a , 0) = mdc (0, a ) = | a | . 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, portanto, zero não tem maior divisor. No entanto, zero é o seu próprio maior divisor se o maior for 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 ( a , b ) gera o mesmo ideal que { a , b } . Esta convenção é seguida por muitos sistemas de álgebra computacional . No entanto, alguns autores deixam mdc (0, 0) indefinido.

O GCD de um e b é o seu maior divisor comum positiva na relação pré-venda de divisibilidade . Isto significa que os divisores comuns de um e b são exatamente os divisores de sua 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.

Exemplo

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

Assim, a lista completa de divisores de 54 é . Da mesma forma, os divisores de 24 são . Os números que essas duas listas têm em comum são os divisores comuns de 54 e 24, ou seja,

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 .

Números coprime

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

Uma visão geométrica

"Retângulo alto e delgado dividido em uma grade de quadrados. O retângulo tem dois quadrados de largura e cinco quadrados de altura."
Um retângulo de 24 x 60 é coberto com dez ladrilhos quadrados de 12 x 12, onde 12 é o GCD de 24 e 60. Mais geralmente, um retângulo a -by- b pode ser coberto com ladrilhos quadrados de comprimento lateral c apenas se c é um divisor comum de a e b .

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).

Formulários

Reduzindo frações

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

Mínimo múltiplo comum

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

Cálculo

Usando fatorações primárias

Os maiores divisores comuns podem ser calculados determinando as fatorações principais dos dois números e comparando os fatores. Por exemplo, para calcular 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.

Least common multiple.svg

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

Algoritmo de Euclides

O método introduzido por Euclides para calcular maiores divisores comuns baseia-se no fato de que, dados dois inteiros positivos a e b tal que a > b , os divisores comuns de um e b são os mesmos que os divisores comuns de um - b 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:

Portanto, mdc (48, 18) = 6 .

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

Animação mostrando uma aplicação do algoritmo Euclidiano para encontrar o máximo divisor comum de 62 e 36, que é 2.

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

Denotando esse resto como um mod b , o algoritmo substitui ( a , b ) por ( b , a mod b ) repetidamente até que o par seja ( d , 0) , onde d é o maior 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

O algoritmo de Lehmer é baseado na observação de que os quocientes iniciais produzidos pelo algoritmo de Euclides podem ser determinados com base apenas nos primeiros dígitos; isso é ú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 . 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 única 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

Os binários usa algoritmo GCD única subtração e divisão por 2. O método é o seguinte: Deixe um e b são os dois inteiros não negativos. Deixe o inteiro d ser 0. Existem cinco possibilidades:

  • a = b .

Como mdc ( a , a ) = a , o GCD desejado é a × 2 d (já que a e b são alterados nos outros casos, e d registra o número de vezes que a e b foram divididos por 2 no próximo passo, o GCD do par inicial é o produto de um e 2 d ).

  • Ambos a e b são pares.

Então 2 é um divisor comum. Dividir ambos um e b por 2, incremento d por um para gravar o número de vezes que 2 é um divisor comum e continuar.

  • a é par eb é ímpar.

Então 2 não é um divisor comum. Divida a por 2 e continue.

  • a é ímpar eb é par.

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

  • Tanto a quanto b são ímpares.

Como mdc ( a , b ) = mdc ( b , a ), se a < b , troque a e b . O número c = a - b é positivo e menor que a . Qualquer número que divide um e b também deve dividir c assim que cada divisor comum de um e b é também um divisor comum de b e c . Da mesma forma, um = b + c e cada divisor comum de b e c é também um divisor comum de um e b . Assim, os dois pares ( a , b ) e ( b , c ) têm os mesmos divisores comuns e, portanto, mdc ( a , b ) = mdc ( b , c ). Além disso, como um e b são ambos estranho, c é ainda, o processo pode ser continuado com o par ( a , b ) substituído pelos números menores ( C / 2, b ) sem alterar o GCD.

Cada uma das etapas acima reduz pelo menos um de a 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 a = b , o caso de parada. Então o GCD é a × 2 d .

Exemplo: ( a , 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 a = 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 é e a complexidade é, portanto,

.

Outros métodos

ou a função de Thomae. A hachura na parte inferior indica elipses (ou seja, omissão de pontos devido à densidade extremamente alta).

Se a e b forem diferentes de zero, o maior divisor comum de a e b pode ser calculado usando o mínimo múltiplo comum (LCM) de ab :

,

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

Usando a função de Thomae f ,

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

Keith Slavin mostrou que para um ímpar  ≥ 1:

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

é uma função inteira na variável b para todos os inteiros positivos a onde c d ( k ) é a soma de Ramanujan .

Complexidade

A complexidade computacional do cálculo dos maiores divisores comuns tem sido amplamente estudada. Se usarmos o algoritmo euclidiano e os algoritmos elementares para multiplicação e divisão, o cálculo do maior divisor comum de dois inteiros de no máximo n bits é. Isso significa que o cálculo do maior divisor comum tem, até um fator constante, o mesmo complexidade como a 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 leva um tempo de T ( n ) , então o algoritmo mais rápido conhecido para o maior divisor comum tem uma complexidade. Isso implica que o algoritmo mais rápido conhecido tem uma complexidade de

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 . A fortiori , o problema de decisão correspondente pertence à classe P de problemas solucionáveis ​​em tempo polinomial. O problema GCD não é conhecido por estar em NC e, portanto, não há maneira conhecida de paralelizá- lo de forma eficiente; nem é conhecido como P-completo , o que implicaria que é improvável que seja possível paralelizar com eficiência o cálculo de GCD. Shallcross et al. mostraram que um problema relacionado (EUGCD, determinando a seqüência restante que surge durante o algoritmo Euclidiano) é NC-equivalente ao problema de programação linear inteira com duas variáveis; se um dos problemas estiver em NC ou P-completo , o outro também estará. Como NC contém NL , também não se sabe se existe um algoritmo de espaço eficiente para calcular o GCD, mesmo para máquinas de Turing não determinísticas.

Embora não se saiba que o problema está no NC , existem algoritmos paralelos assintoticamente mais rápidos que o algoritmo euclidiano; o algoritmo determinístico mais rápido conhecido é o de Chor e Goldreich, que (no modelo CRCW-PRAM ) pode resolver o problema em tempo O ( n / log n ) com processadores n 1 + ε . Algoritmos randomizados podem resolver o problema em tempo O ((log n ) 2 ) nos processadores (isso é superpolinomial ).

Propriedades

  • Cada divisor comum de um e b é um divisor de mdc ( a , b ) .
  • GCD ( a , b ) , onde um e b não são ambos zero, pode ser definido em alternativa e de forma equivalente como o menor número inteiro positivo d qual pode ser escrito sob a forma d = umap + bq , em que p e q são inteiros. Essa expressão é chamada de identidade de Bézout . Números p e q como este pode ser calculado com o algoritmo de Euclides estendido .
  • mdc ( a , 0) = | a | , para a ≠ 0 , uma vez que qualquer número é um divisor de 0, e o maior divisor de a é | a |. Isso geralmente é usado como o caso base no algoritmo euclidiano.
  • Se a divide o produto bc , e mdc ( a , b ) = d , então a / d divide c .
  • Se m for um número inteiro não negativo, então mdc ( ma , mb ) = m ⋅gcd ( a , b ) .
  • Se m for qualquer inteiro, então mdc ( a + mb , b ) = mdc ( a , b ) .
  • Se m é um divisor comum positivo de um e b , em seguida, gcd ( um / m , b / m ) = GCD ( a , b ) / m .
  • O GCD é uma função multiplicativa no seguinte sentido: se a 1 e a 2 são relativamente primos, então mdc ( a 1a 2 , b ) = mdc ( a 1 , b ) ⋅gcd ( a 2 , b ) . Em particular, lembrando que GCD é uma função de valor inteiro positivo, obtemos que mdc ( a , bc ) = 1 se e somente se mdc ( a , b ) = 1 e mdc ( a , c ) = 1 .
  • O GCD é uma função comutativa : mdc ( a , b ) = mdc ( b , a ) .
  • O GCD é uma função associativa : mdc ( a , mdc ( b , c )) = mdc (mdc ( a , b ), c ) . Assim, gcd ( a , b , c , ...) pode ser usado para denotar o GCD de vários argumentos.
  • mdc ( a , b ) está intimamente relacionado ao lcm múltiplo menos comum ( a , b ) : temos
    mdc ( a , b ) ⋅lcm ( a , b ) = | ab | .
Esta fórmula é freqüentemente usada para computar menos múltiplos comuns: primeiro calcula-se o GCD com o algoritmo de Euclides e depois divide o produto dos números dados por seu GCD.
  • As seguintes versões de distributividade são verdadeiras:
    mdc ( a , lcm ( b , c )) = lcm (mdc ( a , b ), mdc ( a , c ))
    lcm ( a , mdc ( b , c )) = mdc (lcm ( a , b ), lcm ( a , c )) .
  • Se temos os fatorações únicas principais de um = p 1 e 1 p 2 e 2 ⋅⋅⋅ p m e m e b = p 1 f 1 p 2 f 2 ⋅⋅⋅ p m f m , onde e i ≥ 0 e f i ≥ 0 , então o GCD de a e b é
    mdc ( a , b ) = p 1 min ( e 1 , f 1 ) p 2 min ( e 2 , f 2 ) ⋅⋅⋅ p m min ( e m , f m ) .
  • Às vezes é útil definir gcd (0, 0) = 0 e lcm (0, 0) = 0 porque então os números naturais se tornam uma rede distributiva completa com GCD como encontro e LCM como operação de junção. Esta extensão da definição também é compatível com a generalização para anéis comutativos dada abaixo.
  • Em um sistema de coordenadas cartesiano , mdc ( a , b ) pode ser interpretado como o número de segmentos entre pontos com coordenadas inteiras no segmento de linha reta que une os pontos (0, 0) e ( a , b ) .
  • Para inteiros não negativos a e b , onde a e b não são ambos zero, demonstrável considerando o algoritmo euclidiano na base  n :
    mdc ( n a - 1, n b - 1) = n mdc ( a , b ) - 1 .
  • Uma identidade envolvendo a função totiente de Euler :

Probabilidades e valor esperado

Em 1972, James E. Nymann mostrou que k inteiros, escolhidos independentemente e uniformemente de {1, ...,  n }, são coprimes com probabilidade 1 / ζ ( k ) conforme n vai para o infinito, onde ζ se refere ao zeta de Riemann função . (Veja coprime para uma derivação.) Este resultado foi estendido em 1987 para mostrar que a probabilidade de k inteiros aleatórios terem o maior divisor comum d é d −k / ζ ( k ).

Usando essas informações, o valor esperado da função do maior divisor comum pode ser visto (informalmente) como não existindo quando k  = 2. Neste caso, a probabilidade de que o GCD seja igual a d é d −2 / ζ (2), e desde ζ (2) = π 2 /6 fizemos

Este último somatório é a série harmônica , que diverge. No entanto, quando k  ≥ 3, o valor esperado é bem definido e, pelo argumento acima, é

Para k  = 3, isso é aproximadamente igual a 1,3684. Para k  = 4, é aproximadamente 1,1106.

Se um argumento do GCD for fixado em algum valor , ele se tornará uma função multiplicativa na outra variável e pode ser mostrado que

Aqui, denota o produto sobre todos os poderes principais de tal forma que , mas

Em anéis comutativos

A noção de máximo divisor comum pode ser mais geralmente definida para elementos de um anel comutativo arbitrário , embora em geral não precise existir um para cada par de elementos.

Se R é um anel conmutativo, e um e b são em R , em seguida, um elemento de d de R é chamado um divisor comum de um e b se divide tanto um e b (isto é, se há elementos x e y em R de tal modo que d · x  =  um e d · y  =  b ). Se d é um divisor comum de um e b , e cada divisor comum de um e b divide d , então d é chamado de máximo divisor comum de um e b .

Com esta definição, dois elementos a e b pode muito bem ter vários maiores divisores comuns, ou mesmo nenhum. Se R for um domínio integral , quaisquer dois GCDs de a e b devem ser elementos associados , uma vez que, por definição, um deve dividir o outro; na verdade, se existe um GCD, qualquer um de seus associados também é um GCD. A existência de um GCD não é garantida em domínios integrais arbitrários. No entanto, se R for um domínio de fatoração único , quaisquer dois elementos têm um GCD e, de maneira mais geral, isso é verdadeiro em domínios de GCD . Se R é um domínio euclidiano no qual a divisão euclidiana é dada algoritmicamente (como é o caso, por exemplo, quando R = F [ X ] onde F é um campo , ou quando R é o anel de inteiros gaussianos ), então os maiores divisores comuns podem ser calculado usando uma forma do algoritmo euclidiano baseado no procedimento de divisão.

A seguir está um exemplo de um domínio integral com dois elementos que não têm um GCD:

Os elementos 2 e 1 +  −3 são dois divisores comuns máximos (ou seja, qualquer divisor comum que seja um múltiplo de 2 é associado a 2, o mesmo vale para 1 +  −3 , mas eles não estão associados, então há não é o maior divisor comum de ab .

Correspondente à propriedade Bézout que podem, em qualquer anel conmutativo, considerar o conjunto de elementos da forma de pa  +  QB em que, p e q gama sobre o anel. Este é o ideal gerado por um e b , e é indicado simplesmente ( umb ). Em um anel cujos ideais são todos principais (um domínio ideal principal ou PID), esse ideal será idêntico ao conjunto de múltiplos de algum elemento do anel d ; então este d é o máximo divisor comum de a e b . Mas o ideal ( ab ) pode ser útil mesmo quando não há maior divisor comum de a e b . (Na verdade, Ernst Kummer usou este ideal como um substituto para um GCD em seu tratamento do Último Teorema de Fermat , embora ele o visse como o conjunto de múltiplos de algum elemento d anel hipotético ou ideal , de onde vem o termo teórico do anel.)

Veja também

Notas

Referências

Leitura adicional