Baixe o app para aproveitar ainda mais
Prévia do material em texto
Disciplina: Aritmética e Teoria dos Números Docente: Luiz Carlos Pitzer Unidade 2: Algoritmo de Euclides e Números Primos Esta unidade está dividida em quatro tópicos: Tópico 1 – Mdc e mmc Tópico 2 – Aplicação de mdc Tópico 3 – Números primos Tópico 4 – Números especiais Unidade 2: Algoritmo de Euclides e Números Primos OBJETIVOS DA APRENDIZAGEM A partir do estudo desta unidade, você deverá ser capaz de: conhecer as definições e propriedades de mdc e mmc; reconhecer a aplicação de mdc e mmc na resolução de problemas; desenvolver a partir do conhecimento de mdc, a resolução de problemas envolvendo equações diofantinas; identificar os números primos, suas propriedades, fatoração e principais resultados; compreender o teorema fundamental da aritmética; aplicar os conceitos de números primos para os números especiais (Números de Mersene, Números de Fermat e Números perfeitos). Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc Neste tópico, veremos dois importantes conceitos da aritmética: o Máximo Divisor Comum (mdc) e Mínimo Múltiplo Comum (mmc). No primeiro deles, o mdc, veremos sua definição e desenvolveremos o Algoritmo de Euclides, que trará contribuições significativas e, posteriormente, no próximo tópico, aplicações importantíssimas na matemática, como nos números de Mersene, Fermat e na resolução de Equações Diofantinas. Sem muita ênfase, o mmc será abordado mais superficialmente, porém, assim como mdc, mostraremos sua aplicação em situações problema, definição e formas de determiná-lo. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM Um divisor comum de dois números inteiros a e b, não simultaneamente nulos, é um número inteiro tal que e . Por exemplo, os números 1, 2, 3 e 6 são os divisores comuns de 12 e 18. A definição a seguir foi essencialmente dada por Euclides nos Elementos e se constitui em um dos pilares da sua aritmética. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM Definição: diremos que é um máximo divisor comum de e , se possuir as seguintes propriedades: é um divisor comum de e de ; é divisível por todo divisor comum de e . A condição (ii) anterior pode ser reescrita como se segue: ) Se é um divisor comum de e , então . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM Caro acadêmico e, provavelmente, futuro professor, o processo de ensino de matemática não é uma missão simples, logo, por esse motivo, desenvolveremos uma estratégia simples de ensino. Traremos inicialmente problemas contextualizados que abordem de forma natural o conceito de Máximo Divisor Comum e definiremos e mostraremos estratégias de como calculá-lo. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM Exemplo: É comum as pessoas se solidarizarem em momentos festivos como o Natal. Um grupo de pessoas juntaram uma certa quantia em dinheiro, com a finalidade de confeccionar pacotes de presente, contendo chocolates e balas. Com o valor arrecadado, conseguiram comprar um total de 210 balas e 378 chocolates sortidos. Qual o número máximo de pacotes que poderão confeccionar, sabendo que todos devem ter a mesma quantidade de chocolates e balas? Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM Resolução: perceba que podemos apresentar algumas formas de resolver o problema. Poderíamos montar 6 pacotes, e, com isso, ter: 210/6 = 35 balas por pacote; 378/6 = 63 chocolates por pacote. Outra possibilidade é montar 14 pacotes, com: 210/14 = 15 balas por pacote; 378/14 = 27 chocolates por pacote. Entre outras formas! Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM A procura por tentativa ou chute pode ser algo complicado e ineficaz. Apesar disso, é possível encontrar a resposta por esse método. Será que há uma resposta melhor? Só podemos resolver o problema com números inteiros, ou seja, a divisão deve ser exata. Se admitirmos apenas divisores naturais, estes devem ser comuns entre os números. Pois bem, vejamos os divisores de cada um destes números: D(378) = {1, 2, 3, 6, 7, 9, 14, 18, 21, 27, 42, 54, 63, 126, 189, 378}; D(210) = {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM D(378) = {1, 2, 3, 6, 7, 9, 14, 18, 21, 27, 42, 54, 63, 126, 189, 378}; D(210) = {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}. Note que os divisores comuns aos números são: 1, 2, 3, 6, 7, 14, 21 e 42. Não tínhamos feito o caso do maior divisor 42. Este sendo o Máximo Divisor Comum apresentará a resposta procurada: 210/42 = 5 balas por pacote; 378/42 = 9 chocolates por pacote. Portanto, cada um dos 42 pacotes terá um total de 14 itens, sendo, 5 balas e 9 chocolates. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÁXIMO DIVISOR COMUM Acompanhe algumas consequências e casos particulares que não realizaremos a demonstração. Para todo , temos que: ; (a ordem não interfere, isto é, vale a comutatividade); ; ; para todo ; (não importa o sinal). Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc CÁLCULO DO MDC Para determinar o de dois ou mais números, há alguns métodos que podem ser utilizados, porém cada método possui sua particularidade, importância e aplicação na solução de problemas. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc FATORAÇÃO MÚLTIPLA Para a aplicação do método da Fatoração Múltipla, temos que definir com antecipação o que são Números Relativamente Primos. Definição: dois números chamam-se relativamente primos (ou primos entre si) se . Exemplo: , isto é, 10 e 21 são primos entre si, apensar de não serem primos individualmente. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc FATORAÇÃO MÚLTIPLA Sabemos que o conceito de números primos não foi abortado ainda, entretanto, gostaríamos de mostrar este método, que, de modo geral, é aprendido nos estudos da escola básica. O método consiste em dividir de forma simultânea os dois números, por números primos. Coloca-se os dois números um ao lado do outro, no lado direito é feito uma barra vertical, o qual será colocado, os números primos que os dividem. Acompanhe um exemplo! Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc FATORAÇÃO MÚLTIPLA Exemplo: calcule o Resolução: primeiramente, colocaremos os números um ao lado do outro com a barra vertical à direita. 120, 100 Agora, basta encontrar os números primos, que simultaneamente dividem os números, colocando o seu resultado, na parte de baixo. Quando não for mais possível dividir por algum número primo, estará concluída a tabela. 120, 100 2 60, 50 2 30, 25 5 6, 5 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc FATORAÇÃO MÚLTIPLA Exemplo: calcule o Resolução: primeiramente, colocaremos os números um ao lado do outro com a barra vertical à direita. 120, 100 Note que 6 e 5 são primos entre si, desta forma o processo é interrompido. Para determinar o , basta multiplicar os primos que são divisores simultâneos dos números: 120, 100 2 60, 50 2 30, 25 5 6, 5 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc FATORAÇÃO MÚLTIPLA Duas observações importantes sobre este método: Não é necessário seguir a ordem crescente dos números primos para realizar as divisões sucessivas. Não é necessário dividir por um número primo, é possível chegar na mesma resposta, dividindo por algum número composto. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES O Algoritmo proposto por ele traz uma singularidade muitogrande por não ser necessário fazer qualquer fatoração. Inicialmente, acompanharemos a seguinte propriedade. Propriedade: se e são números naturais com , então . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Exemplo: calcule o . Resolução: utilizando da propriedade vista anteriormente, podemos estabelecer que: Note que, na parte final, poderíamos aplicar mais uma ou duas vezes a propriedade, obtendo: Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Apesar da simplicidade da resolução e, novamente, sem a necessidade de fatorar em números primos, tivemos bastante trabalho algébrico para realizar. O lema a seguir proporcionará um melhoramento neste processo, nos ajudando na agilidade dos cálculos do entre dois números. Lema: (Lema de Euclides) sejam com . Se existe , então existe e . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Perceba como podemos acelerar o processo do mdc. Ao invés de aplicarmos por duas, três vezes o mesmo valor a ser diminuído, podemos, rapidamente, aplicar um múltiplo deste número. Veremos a seguir um teorema fundamental do algoritmo de Euclides. Teorema: seja e o resto da divisão do inteiro pelo inteiro (positivo) . Então . Podemos calcular o mdc entre dois inteiros aplicando recursivamente o teorema anterior, obtendo o chamado método das divisões sucessivas ou Algoritmo de Euclides. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Há uma forma de organizar o procedimento do algoritmo, que além de fornecer a resposta, apresenta a cronologia dos eventos de forma harmoniosa. Exemplo: determine o . Resolução: utilizando o algoritmo de Euclides, teremos, inicialmente: pois, 6 3887 637 65 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Aplicando novamente, agora para os números 637 e 65, teremos 6 3887 637 65 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Aplicando novamente, agora para os números 637 e 65, teremos visto que . Repetindo o processo até que o resto seja zero, o diagrama fica assim preenchido. 6 9 3887 637 65 65 52 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES Aplicando novamente, agora para os números 637 e 65, teremos visto que . Repetindo o processo até que o resto seja zero, o diagrama fica assim preenchido. Isso mostra que . 6 9 1 4 3887 637 65 52 13 65 52 13 0 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES O algoritmo de Euclides nos fornece que é possível escrever os restos como: Então, substituindo cada informação, uma em seguida da outra, obtemos a seguinte relação: Temos então que Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc ALGORITMO DE EUCLIDES O Algoritmo de Euclides nos fornece, portanto, um meio prático de escrever o mdc de dois números como soma de dois múltiplos dos números em questão. Teorema: (Teorema de Bézout) dados os inteiros e , existem inteiros e tais que . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÍNIMO MÚLTIPLO COMUM Assim como fizemos no mdc, realizaremos, neste novo assunto, a abordagem de dois exemplos, em que este conceito aparece naturalmente. Exemplo: em uma pequena pista de atletismo de 150 metros, duas pessoas, estão realizando seus exercícios diários, partindo simultaneamente de um mesmo ponto. Uma dessas pessoas consegue realizar cada volta em 25 segundos. A outra, correndo mais devagar, leva 30 segundos para completar a volta. Depois de quantos segundos as duas pessoas voltarão a se encontrar no mesmo ponto de partida? Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÍNIMO MÚLTIPLO COMUM Resolução: note que o atleta mais veloz passará cada volta em múltiplos de 25, ou seja, após terminar a primeira volta terá passado 25 segundo, ao término da segunda volta 50 segundos e assim por diante. Podemos então estabelecer que os múltiplos de 25, determinaram a passagem do atleta mais veloz pelo ponto inicial. De mesmo modo, o outro atleta, apresentará múltiplos de 30. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÍNIMO MÚLTIPLO COMUM Comparando os múltiplos do 25 e 30, podemos notar que há momentos que ambos passam pela linha de partida simultaneamente. Como queremos o menor múltiplo comum, então, isso ocorrerá após 150 segundos. Esse valor nos mostra que o atleta mais rápido consegue dar 6 voltas, enquanto atleta mais lento apenas 5 voltas. Outro fato importante e curioso é que, a partir do resultado obtido, podemos prever que os próximos encontros acontecerão a cada 150 segundos, caso se mantenha sempre o ritmo. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc MÍNIMO MÚLTIPLO COMUM Definição: diremos que um número é um mínimo múltiplo comum () de e se e somente se, possuir as seguintes propriedades: é um múltiplo comum de e ; se é um múltiplo comum de e , então . Se é um múltiplo comum de e , então, do item (ii) da definição anterior, temos que , e, portanto, , o que nos diz que o mínimo múltiplo comum, se existe, é único e é o menor dos múltiplos comuns de e . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc CÁLCULO DO MMC Uma proposta para determinar o entre dois ou mais números é pela fatoração simultânea. Exemplo: determine . Resolução: O processo será parecido com o mdc, porém, sempre que for possível, devemos dividir os dois números e finalizar quando ambos chegarem a 1. 12, 30 2 Ambos são divisíveis por 2; 6, 15 2 O 6 é divisível pelo 2 e o 15 não, logo, apenas copiar o 15; 3, 15 3 Ambos são divisíveis pelo 3; 1, 5 5 Por fim, dividir o 5 por ele mesmo. 1, 1 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc CÁLCULO DO MMC Para então determinar o , basta multiplicarmos todos os números primos encontrados no lado direito da barra, . 12, 30 2 Ambos são divisíveis por 2; 6, 15 2 O 6 é divisível pelo 2 e o 15 não, logo, apenas copiar o 15; 3, 15 3 Ambos são divisíveis pelo 3; 1, 5 5 Por fim, dividir o 5 por ele mesmo. 1, 1 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc CÁLCULO DO MMC Veremos, a seguir, outra forma de determinar o , usando o e o Algoritmo de Euclides. Proposição: dados dois números naturais e não nulos, temos que existe e Essa proposição pode ser entendida que, para determinar o de dois inteiros, podemos dividir o produto dos dois números pelo seu . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 1 – Mdc e mmc CÁLCULO DO MMC Exemplo: encontre o . Resolução: utilizando o algoritmo de Euclides, teremos Portanto, . Usando da proposição anterior, 1 4 60 48 12 12 0 Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES A resolução de vários problemas de aritmética recai na resolução, em números inteiros, de equações do tipo com Tais equações são chamadas equações diofantinas lineares em homenagem a Diofanto de Alexandria (aprox. 300 d.C.). Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Nem sempre estas equações possuem solução. Por exemplo, a equação não possui nenhuma solução em números inteiros. Pois, caso contrario, teríamos par e, portanto, nunca igual a 3. (ímpar) Então, é natural perguntar-se em que condições tal equação possui soluções e, caso as tenha, como determina-las? Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Proposição:sejam . A equação admite solução em números inteiros se, e somente se, . A conclusão sobre essa proposição é bem simples! Para que uma equação diofantina linear de segunda ordem tenha solução, há a necessidade que o entre os coeficientes divida o termo independente na equação. Sabendo dessa informação, apresentaremos agora, outra proposição que nos mostra como determinar as soluções de uma equação diofantina, a partir de uma solução particular , e mostrará, como deve ser dada a sua solução geral. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Proposição: seja , uma solução da equação em que . Então, as soluções em da equação são Usando o algoritmo euclidiano, é possível determinar tais que o que já sabíamos pelo Teorema de Bézout. Multiplicando ambos os membros da igualdade anterior por , obtemos Logo, e é uma solução particular da equação. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Exemplo: resolva a equação . Resolução: o , ou seja , portanto, a equação tem solução. Dividindo ambos os termos da equação pelo , obtemos a equação equivalente Pelo algoritmo de Euclides, encontraremos Para igualar ao nosso problema, em que o lado direito corresponde ao 12, vamos multiplicando por 12 todos os termos, obtendo: Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Exemplo: resolva a equação . Resolução: Logo, conseguimos encontrar uma solução particular, em que e . Portando, usando da proposição anterior, as soluções são dadas por e Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Apesar de ser possível verificar a possibilidade de solução natural, por meio da análise de sistemas de inequações, apresentaremos um teorema que dá fundamento para realizar essa análise, sem a necessidade de explorar o uso de inequações. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 2 – Aplicação de mdc EQUAÇÕES DIOFANTINAS LINEARES Teorema: a equação , onde , tem solução em se, e somente se, Note também que o conjunto é finito e seu maior elemento é Portanto, se a equação admite solução nos naturais. Se , ela não admite solução. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 3 – Números Primos INTRODUÇÃO Os números primos é um dos estudos mais intrigantes e maravilhosos da matemática. Desde a época dos filósofos gregos, há mais de 2.000 anos, este já é um assunto que era um dos mais misteriosos. Carl Friedrich Gauss (1777–1855), matemático alemão, acreditava que a teoria dos números é ramo mais importante da matemática. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 3 – Números Primos Definição (número primo): todo número natural, maior que 1, que só tem como divisores positivos, o próprio 1 e ele mesmo é dito número primo. Deste modo, conhecendo essa definição e definindo e , como dois números primos, e um número , inteiro qualquer, podemos estender a definição para os seguintes lemas: Lema: se , então ; Lema: se , temos que . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 3 – Números Primos A partir disso, definimos também os números maiores que 1, que não são primos, de números compostos. Verifique que, por exemplo, os números 2 (único par e primo), 3, 5, 11, 13, são primos, e 4, 8, 9, 16, 25 são compostos. Note que os números compostos podem ser sempre gerados pela multiplicação de números primos. Como 4 = 2 x 2 ou 18 = 2 x 3 x 3. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 3 – Números Primos Agora, vamos ao importante Teorema: Teorema (teorema fundamental da aritmética): todo número que é maior que 1 é primo ou composto, ou seja, escreve-se de maneira única como um produto de fatores primos. Vamos a alguns exemplos do resultado: A fatoração de 72 é: 72 = 2 · 2 · 2 · 3 · 3 = 2³ · 3² A fatoração de −20 é: −20 = −2 · 2 · 5 = −2² · 5 A fatoração de 36 é: 36 = 2 · 2 · 3 · 3 = 2² · 3² Unidade 2: Algoritmo de Euclides e Números Primos Tópico 3 – Números Primos Uma aplicação importante dos números primos e compostos é a determinação da quantidade de divisores positivos de um número natural . Definição: nomeando a quantidade de divisores positivos de , em que: , sendo primos e naturais, temos que: Exemplo: determine a quantidade de divisores positivos do número 360. Resolução: sabemos que a decomposição do número 360 é: . Logo, . Portanto, 360 tem 24 divisores positivos. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais PRIMOS DE FERMAT Antes de definir o que é um número primo de Fermat, precisaremos de um resultado, que será enunciado e provado a seguir. Proposição: dados e , dois números naturais maiores que 1. Se é primo, então temos que é par e , com . Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais PRIMOS DE FERMAT Definição (números de Fermat): os números de Fermat são da forma: Exemplos: Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais PRIMOS DE FERMAT São os 4 primeiros números de Fermat, e, de fato, são primos. Fermat acreditava, sem comprovações, que os números deste formato eram primos. Porém, anos mais tarde, Euler mostrou que: , que é composto, negando os pensamentos de Fermat. Deste modo, apenas os números de Fermat, que são primos, são ditos PRIMOS DE FERMAT. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais NÚMEROS PERFEITOS Os números como 6 e 28, com a propriedade de serem iguais a metade da soma de seus divisores, tiveram o poder de fascinar os gregos antigos, que os chamaram de números perfeitos. Até a Idade Média, conheciam-se apenas os seguintes números perfeitos: 6, 28, 496, 8 128 e 33 550 336. Atualmente, conhecem-se mais alguns números perfeitos. Um fato curioso é que todos os números perfeitos conhecidos são pares. Não se sabe nada sobre a existência ou não de números perfeitos Ímpares. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais NÚMEROS PERFEITOS Definição: para todo , temos: a soma dos divisores naturais de . Exemplos: Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais NÚMEROS PERFEITOS Agora, analisaremos os números naturais, sob o aspecto da comparação de com Definição: chamaremos um número de: Deficiente, se Abundante, se Perfeito, se Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais NÚMEROS PERFEITOS Exemplos: mas . Portanto, 15 é um número deficiente. as . Portanto, 12 é um número abundante. as . Portanto, 6 é um número perfeito. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais PRIMOS DE MERSENNE Os números de Mersenne são os números da forma; onde e um numero primo. No intervalo os números de Mersenne que são primos, chamados de primos de Mersenne, correspondem aos seguintes valores de : 2, 3, 5, 7, 13, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253 e 4423. Até o presente momento, o maior primo de Mersenne conhecido e , descoberto em agosto de 2008 e que possui no sistema decimal 12.978.189 dígitos. Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais FATORAÇÃO DO FATORIAL EM PRIMOS Verificaremos como determinar a fatoração de um número Antes de dar início aos estudos, apresentaremos a notação como sendo a parte inteira de uma divisão. Por exemplo: Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais FATORAÇÃO DO FATORIAL EM PRIMOS Dados um número primo e um número natural m, definimos por o expoente da maior potência de que divide , em outras palavras, é o expoente da potência de p que aparece na fatoração de em fatores primos. Particularmente,representará a potência de que aparece na fatoração de em fatores primos. Teorema: (Legendre) sejam m um número natural e um número primo. Então: Unidade 2: Algoritmo de Euclides e Números Primos Tópico 4 – Números Especiais FATORAÇÃO DO FATORIAL EM PRIMOS Exemplo: determinaremos a decomposição de 10! Em fatores primos. Devemos achar para todo primo . Então: Segue que . Bons estudos! “
Compartilhar