Aulas particulares Idiomas Música Apoio Escolar Esporte Artes e Lazer
Compartilhar

Entendendo os princípios do Máximo Divisor Comum

De Fernando, publicado dia 23/07/2019 Blog > Apoio Escolar > Matemática > O que é o algoritmo de Euclides e para que serve?

“O que é afirmado sem prova, pode ser negado sem prova.”  Euclides, matemático grego, 300 a.C.

Um dos maiores pensadores da história da ciência matemática, Euclides é o autor de Os Elementos, escrito por volta de 300 a.C., e provavelmente, um dos livros matemáticos mais marcantes de todos os tempos.

Desde o início da imprensa, em meados do século XV, Os Elementos, de Euclides, foi o trabalho didático mais impresso depois da Bíblia, com mais de mil edições até hoje.

O tratado consiste em 13 livros dedicados à geometria plana – triângulos, linhas paralelas, propriedades do círculo, aritmética – incluindo primos, o máximo divisor comum (MDC) e o método de subtrações sucessivas repetidas, hoje resumidos sob o nome de divisão euclidiana.

Euclides viveu entre os séculos III e II a.C., na época em que a Grécia Antiga dominava a bacia do Mediterrâneo. Torna-se inegável o fato que seu conhecimento invadiu todo o mundo conhecido à época e foi absorvido pelas civilizações que o sucederam, especialmente a Roma Antiga.

Euclides influenciou o mundo da ciência da Renascença até os dias atuais, de Copérnico a Kepler, de Galileu a Newton, passando por Spinoza e Bertrand Russel.

Neste artigo, vamos nos concentrar em um ponto da obra de Euclides responsável por ter construído sua fama internacional: a divisão euclidiana, um conceito presente da matemática mais básica até os mais complexos estudos de programação.

Um euclidiano precisa compreender princípios gregos A Grécia Antiga foi o berço de grandes matemáticos e sua obra influencia até hoje muitos dos complexos cálculos de programação.

Encontre aqui o melhor curso de matematica!

Divisão euclidiana: definição e princípios

A divisão euclidiana, também conhecida como divisão inteira ou divisão com resto, é um assunto essencial dos exercícios de matemática nos primeiros anos de aprendizado, mas que nem sempre é dominado logo nas aulas iniciais.

Eu tenho cerca de dez morangos e três filhos. Quantos frutos cada um receberá?

Esta é a famosa operação que usa dois inteiros naturais – dividendo e divisor – e associa dois outros: o quociente e o resto. (matematica ensino medio)

É definido  que todos os números inteiros podem ser divididos por um inteiro natural diferente de zero (≠ 0) e ter como resultado um quociente e um resto, no qual o resto sempre deve ser menor que o divisor.

O algoritmo de Euclides é aprendido como uma das quatro operações básicas da matemática, já nas aulas dos anos iniciais do ensino fundamental. No geral, os alunos são introduzidos aos conceitos de divisão utilizando cenários: como dividir um bolo de 8 pedaços em 3 pratos, como distribuir 47 bolinhas para 4 pessoas, e por aí vai… (matematica ensino fundamental)

Então, os alunos aprendem como fazer uma divisão de um inteiro natural por outro – a divisão euclidiana –, colocando, portanto, a operação no papel.

Esta etapa do curso de matemática envolve dominar ou aprender as tabelas de multiplicação de cor, mas também as regras básicas de cálculo: adição, subtração, decomposição de números inteiros (analisando e diferenciando números pares e números ímpares), e assim por diante.

A técnica de divisão permite encontrar todos os divisores de um número sem usar uma calculadora.

Para isso, são procuradas quantas vezes podemos encontrar uma determinada quantidade dentro de um valor maior.

Por exemplo, como calcular a divisão de 30 por 4 ou 75 por 7? Quando se é uma criança de 6 ou 7 anos, encontrar o resultado pode parecer algo não tão óbvio assim.

Quando calculamos pequenos números naturais, tudo bem, mas quando tentamos determinar quantas vezes o número 4357 contém o número 28 apenas com o cálculo mental, devemos ter assimilado muito bem a técnica da divisão.

A partir de então, os conhecimentos sobre números relativos – os inteiros naturais, positivos ou negativos – virão, e os alunos então passarão para um próximo nível, sabendo analisar e realizar uma divisão de decimais e de cálculo fracionário.

Em outras palavras, perceba que fazer uma divisão euclidiana também é distribuir de forma justa uma quantidade “n” entre várias entidades, como a possibilidade de oferecer 53 bolas para 5 pessoas – ou seja, 53 é o dividendo e 5 o divisor.

Por divisão básica, uma bola pode ser dada a cada uma das cinco pessoas. Agora que cada um tem uma bola e restam 47 bolas. Então nós começamos de novo até que todos tenham um número igual de bolas. Conceitualmente, é algo bem tranquilo de se perceber, não é?

Na última distribuição, percebemos que cada um tem dez bolas e que há um estoque de três bolinhas após a operação. Eles podem ser distribuídos, mas duas pessoas seriam prejudicadas. Então é dito que o resto dessa operação é 3.

Cada criança, portanto, tem dez bolas e 10 é o quociente.

Assim, realizar a divisão euclidiana de 53 por 5 pode ser escrita como 53 = 5 × 10 + 3, depois de verificar que 3 é menor do que 5. O resto deve ser sempre inferior ao divisor, não se esqueça!

Está gostando do conteúdo? Descubra também a definição da função afim!

O resto é normal para a operação matemática Como distribuir bolinhas e não prejudicar ninguém? Fazendo a divisão correta!

Como resolver uma divisão euclidiana?

O método de subtração sucessivo específico do algoritmo euclideano consegue simplificar uma operação que é, a princípio, complexa.

Além disso, é a magia da matemática tornar acessível um processo que, inicialmente, parece irrealizável.

Eu tenho que dividir um inteiro de cinco dígitos por outro número de três dígitos. Como fazer sem usar a calculadora?

Dividindo passo a passo

Por exemplo, faça a seguinte operação: divida 273 por 17. Procuramos quantas vezes o número 17 está presente entre 17 e 273.

Para encontrar o resultado, a demonstração é a seguinte:

Passo 1 : Começamos a divisão com o dividendo 273 à esquerda da primeira coluna e o divisor 17 à direita.

Passo 2 : Nós vemos que 2, primeiro número do nosso dividendo, é menor que 17, nosso divisor, então temos que descobrir quantas vezes 17 está contido em 27, já que o divisor sempre deve ser menor que o dividendo na divisão de números inteiros:

17 x 1 = 17, 17 x 2 = 34

E como 34 é maior do que 27, vamos escrever o 1 sob o divisor – iniciando a composição do quociente –- e fazemos a seguinte subtração: 27 – 17. O resto para essa operação é 10.

Passo 3 : escrevemos 10 para o resto.

Então nós incluímos o número da unidade ainda não analisada do dividendo – 3  – na frente do resto inicial 10: obtemos então 103, que agora vamos dividir por 17. Então nós temos 17 x  6 =  102: nós incluímos o 6 no quociente e fazemos a subtração 103 (o divisor dessa etapa) – 102.

E se você fizesse um curso de matematica basica?

Restou 1.

O resultado então é 273/17 = 17 x 16 + 1, podemos escrever: o quociente inteiro de 273 por 17 é, portanto, 16, e seu restante é 1.

Uma divisão euclidiana é aceita, se e somente se, o resto for menor que o divisor, caso contrário, isso significa que ainda é possível fazer uma divisão.

Outra peculiaridade: quando o resto da divisão de “a” por “b” é zero, por exemplo, 20 dividido por 4, dizemos que:

  • a  é divisível por  b,
  • a  é um múltiplo de  b,
  • b  é um divisor de  a.

Aqui temos 20/4 = 5, então 20 é divisível por 4, mas também temos 20/5 = 4, então 20 também é divisível por 5 e 5 é também um divisor de 20.

Essa ginástica mental, possibilidades de diversas variáveis verdadeiras, possibilita ampliar o campo de possibilidades, em vez de representar uma multiplicação e uma divisão em cada operação para o conjunto de números: esses são os critérios de divisibilidade.

Confira aula de matematica no portal da comunidade Superprof! Temos os melhores professores de matemática para você!

Aplicando a divisibilidade

Podemos encontrar para qualquer número real uma aritmética modular graças à relação de congruência dos inteiros.

Para detectar rapidamente se um número é um divisor de outro, algumas regras podem ser aplicadas.

Um inteiro é divisível por :

  • 2 se o dígito das unidades for par, isto é: 0, 2, 4, 6 ou 8,
  • 4 se o número formado pelos dois últimos dígitos for divisível por 4,
  • 5 se o dígito das unidades for 0 ou 5,
  • 3 se a soma dos dígitos que a compõem for divisível por 3,
  • 9 se a soma dos dígitos que a compõem for divisível por 9,
  • 10 se o seu dígito de unidades for 0.

Esse é um tema tão básico mas tão fundamental na aritmética que convidamos você a descobrir outros mais. Espie aqui a definição de geometria!

divisor, dividendo, resto e quociente precisam estar organizados Monte a sua divisão no papel como um quebra-cabeças, cada peça em seu lugar!

Como encontrar o máximo divisor comum de um número?

O Máximo Divisor Comum (MDC) de dois números inteiros diferentes de zero é um princípio básico na aritmética elementar, permitindo encontrar o maior número que os divide simultaneamente.

É uma questão de fazer a lista de todos os divisores desses números: por exemplo, qual é o MDC de 20 e 36?

  • 20 tem como divisores: 1, 2, 4, 5, 10, 20,
  • 36 tem como divisores: 1, 2, 3, 4, 6, 9, 12, 18, 36.

O MDC de 20 e 36 é, portanto, 4, o maior valor entre os encontrados que vale para todos os envolvidos.

Outro exemplo: os divisores comuns de 36, 48 e 60 são 1, 2, 3, 4, 6 e 12. Assim, escrevemos: MDC (36, 48, 60) = 12.

Dois outros métodos podem ser usados: o método das subtrações sucessivas e a divisão euclidiana (sim, ela mesma).

Para calcular o MDC de 116 e 78, por exemplo:

  • Por subtrações sucessivas: 116 – 78 = 38, 78 – 38 = 40, 40 – 38 = 2, 2-2 = 0. MDC (116; 78) = 2,
  • Pelo método de Euclides: 116 = 78 x 1 + 38, 78 = 38 x 2 + 2, 38 = 19 x 2 + 0. MDC (116; 78) = 2.

O princípio é o mesmo para os dois métodos: subtraímos um número do outro tantas vezes quantas pudermos e olhamos qual é o resto.

Que tal você também refrescar seus conhecimentos sobre o que é álgebra?!

Você sabia que muitos dos sofisticados cálculos de programação avançada se baseiam no algorítmo da divisão euclidiana?

Breve história sobre o desenvolvimento da divisão euclidiana

Como já comentamos, o algoritmo de Euclides é um dos mais antigos algoritmos ainda em uso até hoje. Mais especificamente nos Livros VII (proposições 1-2) e X (proposições 2-3) de sua obra Os Elementos, Euclides discursa as proposições desse algoritmo da divisão que ficaria conhecida como divisão euclidiana.

No Livro VII, o algoritmo é formulado para números inteiros. Já no Livro X, é concebido para comprimentos de segmentos lineares, ou seja, nos termos de hoje, podemos dizer que formulado para números reais.

Observe que comprimentos, áreas e volumes não são medidos nas mesmas unidades – mesmo que representados por números reais hoje em dia. Não existe uma unidade natural de comprimento, área ou volume. Lembre também que o conceito de número real era ainda desconhecido à época de Euclides. Portanto, o último algoritmo é geométrico.

O MDC de dois comprimentos/áreas/volumes  e  b corresponde ao maior comprimento/área/volume g que mede apropriadamente a e b. Em outras palavras, essas unidades de medidas – comprimentos/áreas/volumes, por exemplo, a e b são o resultado da multiplicação da unidade de medida g por números inteiros.

No entanto, ainda em relação ao algoritmo, muitos estudiosos afirmam que – provavelmente – esse algoritmo não foi concebido por Euclides, que compila resultados de matemáticos importantes que lhe antecederam em sua obra.

Ainda nessa linha, o matemático e historiador Bartel van der Waerden, que revolucionou a álgebra no período entre-guerras, teoriza que o Livro VII origina-se de um texto sobre teoria dos números redigido por matemáticos da escola de Pitágoras, o filósofo e notório matemático grego jônico fundador do Pitagorismo.

Além disso, segundo o Wikipedia, o algoritmo era já provavelmente conhecido por Eudoxo de Cnido, atrônomo, matemático e filósofo grego. O algoritmo poderia ser ainda anterior a esse pensador, caso levemos em consideração o uso do termo técnico grego anthyphairesis, que significa subtração recíproca, em trabalhos do próprio Euclides e do notório Aristóteles, filósofo grego, discípulo de Platão e professor de Alexandre, o Grande.

Vários séculos mais tarde, podemos dizer que o algoritmo euclidiano teria sido reinventado, de forma independente, na Índia e na China, a fim de elucidar, sobretudo, as equações diofantinas que surgiram no campo da Astronomia, em busca de calendários mais precisos.

Lembre que, na matemática, uma equação diofantina é uma equação polinomial que permite a duas ou mais variáveis assumam somente valores inteiros. Ou seja, uma equação linear diofantina é uma equação entre duas adições de monômios de zero grau ou grau um.

A ideia principal no algoritmo euclidiano é que o MDC pode ser calculado usando o resto da divisão com entrada para o próximo passo. Você já notou isso?

No final do século V, o astrônomo e matemático indiano Aryabhata classificou o algoritmo euclidiano como “pulverizador”, devido à sua eficiência em resolver equações diofantinas. Ademais ao fato de que um caso especial do teorema chinês do resto já tivesse sido descrito pelo astrônomo e matemático chinês Sun Tzu, a fórmula da solução geral foi publicada por outro chinês, Ch’in Chiu-Sao, durante a Idade Média, no ano de 1247, na obra traduzida como Tratado Matemático em Nove Partes.

O algoritmo de Euclides foi primeiramente descrito no Ocidente na segunda edição de uma obra de Bachet de Méziriac, teólogo, poeta, latinista, tradutor e matemático francês. A obra era Problèmes plaisants et délectables/Problemas aprazíveis e deleitáveis, de 1624.

Nas terras europeias, o algoritmo euclidiano era usado para resolver as já mencionadas equações diofantinas e para o desenvolvimento das frações contínuas. O algoritmo de Euclides estendido, ainda, foi publicado pelo matemático inglês Nicholas Saunderson, que o atribuiu como método para calcular frações contínuas de forma muito eficiente. Procurando por um curso de matematica online de qualidade?

Definição do algoritmo euclidiano

A  ideia básica no algoritmo euclidiano é que o MDC pode ser calculado recursivamente, usando o resto da divisão como entrada para o próximo passo, que é baseado na propriedade do MDC:

MDC (a,b) = MDC (b, r)

onde r é o resto da divisão de a por b.

Isso significa que o resto da divisão em uma chamada anterior do algoritmo será empregado como entrada para a chamada seguinte.

E, como nós já sabemos, o resto pode ser calculado pela equação: r = a – bq, onde q = a/b, que é uma divisão inteira.

Nesse sentido, podemos substituir as variáveis para obtermos uma sequência lógica, usando a = r k-1, b = rk e r = r k+1, temos a seguinte sequência:

r k+1 = rk-1 – r kq

Bom, chega de fórmulas por enquanto! Esperamos que tenha ficado um pouco mais claro a origem da evolução do algoritmo de Euclides.

Você sabia que o algoritmo euclidiano não exige qualquer fatoração e que é um dos algoritmos mais antigos em uso até hoje?

As aplicações contemporâneas da divisão euclidiana e seu algoritmo

Já dissemos que o algoritmo euclidiano foi descrito tendo em mente apenas números naturais e comprimentos geométricos. No entanto, foi generalizado, durante o século XIX, para outras classes de números, como os inteiros, os gaussianos e polinômios de uma variável. O resultado disso foram várias noções de álgebra moderna abstrata, tais como os domínios euclidianos.

Perceba que o algoritmo de Euclides foi, ainda, generalizado para outras estruturas da matemática, como os nós e polinômios multivariados.

Esse algoritmo, portanto, possui muitas aplicações teóricas e práticas importantes. Ele pode ser usado para gerar quase que todas as significativas aplicações tradicionais utilizadas em diferentes culturas em todo o mundo.

O algoritmo é um elemento-chave dos algoritmos tipo RSA, isto é, um método de criptografia de chave pública empregado no comércio eletrônico. Ele é aplicado para resolver equações diofantinas, como já mencionamos, tão bem como na descoberta de números que sejam satisfatórios em múltiplas congruêcias (como o também já citado teorema chinês do resto) ou o inverso multiplicativo de um número finito.

Além de ser usado para construir frações contínuas, como já observamos, o algoritmo também pode descobrir raízes reais em um polinômio ou em vários algoritmos modernos em processos de fatoração de inteiros. E, finalmente, ele é uma excelente ferramenta, bem básica, para obter na teoria dos números modernos, tal como o teorema de Fermat-Lagrange e no teorema fundamental da aritmética.

tente resolver problemas sem ajuda de ferramentas Sabendo como fazer as operações, você pode dispensar a calculadora e não depender de nada mais para se virar nas contas!

Reforce seu aprendizado de divisão euclidiana

Mesmo depois de tantas aulas, o cérebro ainda tem que entender como encontrar a solução no dia a dia.

Você pode pesquisar por vídeos em que professores explicam com diferentes métodos como fazer uma divisão e resolvê-la, isso existe aos montes pela internet. E dê preferência por cursos com conteúdo de qualidade, não saia por aí assistindo a qualquer um. A qualidade tanto do conteúdo quanto da metodologia do professor são pontos importantes que você deve sempre considerar e prezar por.

Busque conteúdos que façam testes entre o método de uma divisão simples com um único divisor e um com um divisor com dois dígitos.

E assim você pode também demonstrar de maneira ainda mais educativa de aprender a representar uma divisão. E para isso, você pode fazer listas de exercícios, muitos e muitos exercícios para reforçar o conteúdo e reforçar também a sua memória e raciocínio.

Lembre que é matemática, depois que aprendemos e dominamos o raciocínio, o passo seguinte é fazermos dezenas e dezenas de exercícios diversos que abordem o mesmo conteúdo ou raciocínio. É assim que, de fato, aprendemos e introjetamos o aprendizado em nossa mente e vivência cotidiana.

Recapitulando: para conseguir realizar um divisão como a formalizada por Euclides, devemos saber:

  • As tabelas de multiplicação,
  • O método de subtração,
  • Aplicar a metodologia.

Não esqueça de verificar o quociente obtido e escrever o resultado com detalhes (no formato “dividendo = divisor x quociente + resto”).

Não hesite em reler aulas e refazer exercícios se os bloqueios permanecerem na sua mente e manifeste suas dificuldades, podendo inclusive recorrer a as aulas com um professor particular de matemática!

Em resumo, o algoritmo euclidiano é fundamental em muitas das operações da aritmética por ser um método simples e eficiente de encontrar o máximo divisor comum entre quaisquer dois números inteiros diferentes de zero. Ele permeia quase que toda a história da matemática, desde a aritmética clássica, passando pela moderna e também pela álgebra abstrata.

Foi o somatório de suas aplicações que tornaram esse algoritmo um dos mais relevantes no campo em que atua. Muito provavelmente quando Euclides o descreveu em sua seminal obra, talvez ele nunca imaginaria que essa seria uma ferramenta utilizada em criptografia pelo comércio eletrônio nos dias atuais. Ou tampouco que auxiliaria na autenticação de procedimentos e na encriptação de dados entre o usuário internauta e qualquer sistema criptográfico que utilize criptografia assimétrica.

E é isso! Estamos prontos para realizar qualquer divisão entre números inteiros diferentes de zero! Parece ser algo tão simples, não é? Mas foi assim que essa ferramenta deu-se início, com a simplicidade de conceitos e de aplicação!

Gostou do conteúdo? Deu para refrescar um pouco a sua memória sobre o tema? Que tal você partir também para revisitar ou descobrir o que é uma função decimal?

Compartilhar

Nossos leitores adoram esse artigo
Este artigo te trouxe as informações que procurava?

Nenhuma informação ? Sério ?Ok, trabalharemos o tema num próximoNa média, ufa !Obrigado. Deixe suas dúvidas nos comentários.Estamos muito felizes em te ajudar ! :) (média de5,00 sob 5 de 3 votos)
Loading...
avatar