Números Primos e MDC - Matemática Discreta UFC

Numeros Primos e Maximo Divisor Comum QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Nesta apresentacao Definicao formal de numeros primos Verificacao de primalidade Aplicacoes de numeros primos fatoracao Conceitos de maximo divisor comum de mınimo multiplo comum e algumas formas de calculalos 2 Referˆencias para esta aula Secao 35 do livro Matematica Discreta e suas Aplicacoes Autor Kenneth H Rosen Sexta Edicao Secao 43 do livro Discrete Mathematics and Its Applications Author Kenneth H Rosen Seventh Edition English version 3 Introdução Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Entao dado n inteiro cada m que divide n satisfaz m 0 se n 0 entao m n se n 0 entao m n se n 0 entao m n m tambem divide n m tambem divide n 5 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Entao dado n inteiro cada m que divide n satisfaz m 0 se n 0 entao m n se n 0 entao m n se n 0 entao m n m tambem divide n m tambem divide n 5 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Exemplo Quem sao os divisores de 3 Cada m que divide 3 satisfaz m 0 se 3 0 entao m 3 como 3 0 entao m 3 m tambem divide 3 3 tambem divide m 6 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Exemplo Quem sao os divisores de 3 Cada m que divide 3 satisfaz m 0 se 3 0 entao m 3 como 3 0 entao m 3 m tambem divide 3 3 tambem divide m Ou seja 3 m 3 para todo inteiro m que divide 3 6 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Exemplo Quem sao os divisores de 3 Cada m que divide 3 satisfaz m 0 se 3 0 entao m 3 como 3 0 entao m 3 m tambem divide 3 3 tambem divide m ENTAO vamos testar cada 3 m 3 6 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Exemplo Quem sao os divisores de 3 3 3 2 3 1 3 0 3 1 3 2 3 3 3 7 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Exemplo Quem sao os divisores de 3 3 3 2 3 1 3 0 3 1 3 2 3 3 3 7 Contando divisores Definicao Divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Lembrese Dizemos que a e um divisor de b se e somente se a divide b Exemplo Quem sao os divisores de 3 3 3 2 3 1 3 0 3 1 3 2 3 3 3 Assim 3 tem quatro divisores 3 1 1 e 3 7 Contando divisores Os topicos desta aula giram em torno destas perguntas 1 Quem sao os divisores de um inteiro 2 Quantos sao os divisores de um inteiro Por simplicidade lidaremos apenas com numeros positivos 8 Números Primos Numeros Primos Definicao numero primo Um inteiro n 1 e chamado primo se e somente se n tem exatamente dois divisores positivos Definicao numero composto Um inteiro n 1 que nao e primo e chamado composto Exemplo 11 e primo pois seus divisores positivos sao 1 e 11 exatamente 2 15 e composto pois seus divisores positivos sao 135 e 15 mais que 2 10 Numeros Primos Definicao numero primo Um inteiro n 1 e chamado primo se e somente se n tem exatamente dois divisores positivos Definicao numero composto Um inteiro n 1 que nao e primo e chamado composto Exemplo 11 e primo pois seus divisores positivos sao 1 e 11 exatamente 2 15 e composto pois seus divisores positivos sao 135 e 15 mais que 2 10 Numeros Primos Definicao numero primo Um inteiro n 1 e chamado primo se e somente se n tem exatamente dois divisores positivos Definicao numero composto Um inteiro n 1 que nao e primo e chamado composto Exemplo 11 e primo pois seus divisores positivos sao 1 e 11 exatamente 2 15 e composto pois seus divisores positivos sao 135 e 15 mais que 2 10 Numeros Primos Definicao numero primo Um inteiro n 1 e chamado primo se e somente se n tem exatamente dois divisores positivos Definicao numero composto Um inteiro n 1 que nao e primo e chamado composto Note que Para todo n 0 temos 1n Para todo n 0 temos nn Portanto Todo inteiro n 1 tem no mınimo dois divisores positivos Um inteiro n 1 e primo se e somente se os unicos divisores de n sao 1 e n Um inteiro n 1 e composto se e somente se n tem trˆes ou mais divisores positivos 11 Numeros Primos Definicao numero primo Um inteiro n 1 e chamado primo se e somente se n tem exatamente dois divisores positivos Definicao numero composto Um inteiro n 1 que nao e primo e chamado composto Note que Para todo n 0 temos 1n Para todo n 0 temos nn Portanto Todo inteiro n 1 tem no mınimo dois divisores positivos Um inteiro n 1 e primo se e somente se os unicos divisores de n sao 1 e n Um inteiro n 1 e composto se e somente se n tem trˆes ou mais divisores positivos 11 Numeros Primos Definicao numero primo Um inteiro n 1 e chamado primo se e somente se n tem exatamente dois divisores positivos Definicao numero composto Um inteiro n 1 que nao e primo e chamado composto Note que Para todo n 0 temos 1n Para todo n 0 temos nn Portanto Todo inteiro n 1 tem no mınimo dois divisores positivos Um inteiro n 1 e primo se e somente se os unicos divisores de n sao 1 e n Um inteiro n 1 e composto se e somente se n tem trˆes ou mais divisores positivos 11 Primos Blocos de construcao dos inteiros positivos ① Se um inteiro n 1 nao e primo entao existe um inteiro positivo k tal que kn e 1 k n ② Como kn pela definicao de divisibilidade existe um inteiro positivo c tal que n k c Como 1 k n concluımos tambem que 1 c n ③ Logo podemos escrever n como um produto de dois inteiros positivos k e c menores que ele se um desses divisores nao e primo escrevemolo como o produto de dois inteiros menores que ele ④ Esse processo termina somente com numeros primos Fato provado ha mais de 2000 anos pelos gregos e e conhecido pelo seguinte teorema Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente 12 Primos Blocos de construcao dos inteiros positivos ① Se um inteiro n 1 nao e primo entao existe um inteiro positivo k tal que kn e 1 k n ② Como kn pela definicao de divisibilidade existe um inteiro positivo c tal que n k c Como 1 k n concluımos tambem que 1 c n ③ Logo podemos escrever n como um produto de dois inteiros positivos k e c menores que ele se um desses divisores nao e primo escrevemolo como o produto de dois inteiros menores que ele ④ Esse processo termina somente com numeros primos Fato provado ha mais de 2000 anos pelos gregos e e conhecido pelo seguinte teorema Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente 12 Primos Blocos de construcao dos inteiros positivos ① Se um inteiro n 1 nao e primo entao existe um inteiro positivo k tal que kn e 1 k n ② Como kn pela definicao de divisibilidade existe um inteiro positivo c tal que n k c Como 1 k n concluımos tambem que 1 c n ③ Logo podemos escrever n como um produto de dois inteiros positivos k e c menores que ele se um desses divisores nao e primo escrevemolo como o produto de dois inteiros menores que ele ④ Esse processo termina somente com numeros primos Fato provado ha mais de 2000 anos pelos gregos e e conhecido pelo seguinte teorema Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente 12 Primos Blocos de construcao dos inteiros positivos ① Se um inteiro n 1 nao e primo entao existe um inteiro positivo k tal que kn e 1 k n ② Como kn pela definicao de divisibilidade existe um inteiro positivo c tal que n k c Como 1 k n concluımos tambem que 1 c n ③ Logo podemos escrever n como um produto de dois inteiros positivos k e c menores que ele se um desses divisores nao e primo escrevemolo como o produto de dois inteiros menores que ele ④ Esse processo termina somente com numeros primos Fato provado ha mais de 2000 anos pelos gregos e e conhecido pelo seguinte teorema Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente 12 Primos Blocos de construcao dos inteiros positivos ① Se um inteiro n 1 nao e primo entao existe um inteiro positivo k tal que kn e 1 k n ② Como kn pela definicao de divisibilidade existe um inteiro positivo c tal que n k c Como 1 k n concluımos tambem que 1 c n ③ Logo podemos escrever n como um produto de dois inteiros positivos k e c menores que ele se um desses divisores nao e primo escrevemolo como o produto de dois inteiros menores que ele ④ Esse processo termina somente com numeros primos Fato provado ha mais de 2000 anos pelos gregos e e conhecido pelo seguinte teorema Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente 12 Primos Blocos de construcao dos inteiros positivos ① Se um inteiro n 1 nao e primo entao existe um inteiro positivo k tal que kn e 1 k n ② Como kn pela definicao de divisibilidade existe um inteiro positivo c tal que n k c Como 1 k n concluımos tambem que 1 c n ③ Logo podemos escrever n como um produto de dois inteiros positivos k e c menores que ele se um desses divisores nao e primo escrevemolo como o produto de dois inteiros menores que ele ④ Esse processo termina somente com numeros primos Fato provado ha mais de 2000 anos pelos gregos e e conhecido pelo seguinte teorema Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente 12 Teorema Fundamental da Aritmetica Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente Exemplos 2 2 15 3 5 20 2 2 5 300 2 2 3 5 5 641 641 999 3 3 3 37 Note que cada primo nestas listas e um divisor ou fator do numero reescrito um produto de primos em ordem crescente e a fatoracao de um inteiro 13 Teorema Fundamental da Aritmetica Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente Exemplos 2 2 15 3 5 20 2 2 5 300 2 2 3 5 5 641 641 999 3 3 3 37 Note que cada primo nestas listas e um divisor ou fator do numero reescrito um produto de primos em ordem crescente e a fatoracao de um inteiro 13 Teste de Primalidade Teste de Primalidade A propriedade de ser um primo e chamada primalidade Como determinar se um inteiro n 1 e primo Primeira ideia averiguar se n e divisıvel por todos os numeros primos k com 1 k n Sera mesmo preciso testar todos os primos maiores que 1 e menores que n Ou podemos nos livrar de testar alguns 15 Teste de Primalidade A propriedade de ser um primo e chamada primalidade Como determinar se um inteiro n 1 e primo Primeira ideia averiguar se n e divisıvel por todos os numeros primos k com 1 k n Sera mesmo preciso testar todos os primos maiores que 1 e menores que n Ou podemos nos livrar de testar alguns 15 Teste de Primalidade A propriedade de ser um primo e chamada primalidade Como determinar se um inteiro n 1 e primo Primeira ideia averiguar se n e divisıvel por todos os numeros primos k com 1 k n Sera mesmo preciso testar todos os primos maiores que 1 e menores que n Ou podemos nos livrar de testar alguns 15 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b n Entao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Demonstracao Seja n inteiro composto Entao n possui um fator a tal que 1 a n Logo pela definicao de um fator de um inteiro positivo temos que n ab onde ambos a e b sao inteiros positivos maiores que 1 Alegacao Temos que a n ou b n Suponha por absurdo que a n e b nEntao ab nn n o que e uma contradicao Consequentemente a n ou b n Logo n possui um divisor positivo que nao e maior que n Esse divisor ou e um primo ou pelo Teorema Fundamental da Aritmetica possui um divisor primo Em qualquer dos casos n possui um divisor primo menor ou igual a n 16 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Teste de Primalidade Segue do teorema anterior que Corolario Um inteiro n e primo se ele nao e divisıvel por nenhum primo menor ou igual a n Exemplo O 101 e primo Precisamos verificar se p101 para cada inteiro p 101 que seja primo ou seja para cada p 10 arredondando para baixo que seja primo Ha apenas quatro primos neste intervalo 2 3 5 7 2 101 pois 101 mod 2 1 3 101 pois 101 mod 3 2 5 101 pois 101 mod 5 1 7 101 pois 101 mod 7 3 Como nenhum primo p 101 divide 101 temos que 101 e primo 17 Algoritmo de Fatoração Teorema Fundamental da Aritmetica Voltando ao Teorema Fundamental da Aritmetica Teorema Fundamental da Aritmetica Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente Exemplos 2 2 15 3 5 20 2 2 5 300 2 2 3 5 5 641 641 999 3 3 3 37 Como determinar a fatoracao em numeros primos de um inteiro n 1 qualquer 19 O algoritmo de fatoracao Ideia Tentar dividir n por um primo de cada vez em ordem crescente Para cada primo visitado divida o resultado obtido ate falhar Considere que Primos e uma lista inicializada com todos os primos conhecidos em ordem crescente Algoritmo Fatoracao de n Entrada inteiro n Saıda Fatoracao de n em numeros primos 1 para k em Primos faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 20 O algoritmo de fatoracao Ideia Tentar dividir n por um primo de cada vez em ordem crescente Para cada primo visitado divida o resultado obtido ate falhar Considere que Primos e uma lista inicializada com todos os primos conhecidos em ordem crescente Algoritmo Fatoracao de n Entrada inteiro n Saıda Fatoracao de n em numeros primos 1 para k em Primos faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 20 O algoritmo de fatoracao Ideia Tentar dividir n por um primo de cada vez em ordem crescente Para cada primo visitado divida o resultado obtido ate falhar Considere que Primos e uma lista inicializada com todos os primos conhecidos em ordem crescente Algoritmo Fatoracao de n Entrada inteiro n Saıda Fatoracao de n em numeros primos 1 para k em Primos faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 20 O algoritmo de fatoracao E possıvel sermos mais eficientes Pelo Teorema n podemos parar assim que k n mesmo considerando atualizacoes de n Isso nos permitiria inicializar Primos somente com os primos ate n Nesse caso quando k n teremos n 1 ou que n e primo Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre 21 O algoritmo de fatoracao E possıvel sermos mais eficientes Pelo Teorema n podemos parar assim que k n mesmo considerando atualizacoes de n Isso nos permitiria inicializar Primos somente com os primos ate n Nesse caso quando k n teremos n 1 ou que n e primo Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre 21 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 1 Para Variaveis k 2 n 99 k n Linha 2 Como 2 99 nao entramos no enquanto 99 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 1 Para Variaveis k 2 n 99 k n Linha 2 Como 2 99 nao entramos no enquanto Linha 6 Como 99 1 continuamos 99 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 99 k n Linha 2 Como 3 99 entramos no enquanto 99 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 99 k n Linha 2 Como 3 99 entramos no enquanto Linha 3 imprimimos 3 na saıda 99 3 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 33 k n Linha 2 Como 3 99 entramos no enquanto Linha 3 imprimimos 3 na saıda Linha 4 e atualizamos n para 99 div 3 33 99 3 33 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 33 k n Linha 2 Como 3 33 continuamos no enquanto 99 3 33 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 33 k n Linha 2 Como 3 33 continuamos no enquanto Linha 3 imprimimos 3 na saıda 99 3 33 3 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 11 k n Linha 2 Como 3 33 continuamos no enquanto Linha 3 imprimimos 3 na saıda Linha 4 e atualizamos n para 33 div 3 11 99 3 33 3 11 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 11 k n Linha 2 Como 3 11 saımos do enquanto 99 3 33 3 11 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 2 Para Variaveis k 3 n 11 k n Linha 2 Como 3 11 saımos do enquanto Linha 6 Como 11 1 continuamos 99 3 33 3 11 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 3 Para Variaveis k 5 n 11 k n Linha 1 Como 5 11 saımos do para 99 3 33 3 11 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 3 Para Variaveis k 5 n 11 k n Linha 1 Como 5 11 saımos do para Linha 8 Como 11 1 imprimimos 11 na saıda 99 3 33 3 11 11 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 3 Para Variaveis k 5 n 11 k n Linha 1 Como 5 11 saımos do para Linha 8 Como 11 1 imprimimos 11 na saıda atualizamos n para 1 99 3 33 3 11 11 1 22 O algoritmo de fatoracao Algoritmo Fatoracao de n Revisado 1 para k em Primos sendo k n faca 2 enquanto n 1 e kn faca 3 imprima k na saıda 4 n n div k 5 6 se n 1 encerre 7 8 se n 1 imprima n na saıda e encerre Executaremos o algoritmo para n 99 Iteracao 3 Para Variaveis k 5 n 11 k n Linha 1 Como 5 11 saımos do para Linha 8 Como 11 1 imprimimos 11 na saıda atualizamos n para 1 e encerramos 99 3 33 3 11 11 1 32 11 22 Infinitude dos primos Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Teorema Existe uma quantidade infinita de numeros primos Demonstracao Por contradicao Suponha que existem finitos numeros primos p1 p2 pn Seja Q p1p2 pn 1 Pelo Teorema Fundamental da Aritmetica Q e primo ou pode ser escrito como o produto de dois ou mais primos Alegacao Nenhum primo pj da lista p1 p2 pn divide Q Prova da alegacao Suponha por absurdo que pj Q Entao pj divide o numero Q p1p2 pn 1 o que e uma contradicao Entao existe um primo que nao esta na lista p1p2 pn Ou este primo e o Q se ele for primo ou ele e um fator primo de Q Isso e uma contradicao porque supomos que a lista p1p2 pn contem todos os primos Consequentemente existem infinitos primos 24 Infinitude dos primos Observacoes Na prova do teorema anterior nao sabemos se Q e primo Esse e um exemplo de prova nao construtiva para um enunciado existencial Para que essa prova fosse construtiva nos deverıamos ter dado explicitamente um primo ausente na lista original de n primos 25 Encontrando primos Crivo de Eratostenes 26 O Crivo de Eratostenes Ideia Encontrar todos os primos no intervalo 1 k n Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Executaremos o algoritmo para n 100 27 O Crivo de Eratostenes Ideia Encontrar todos os primos no intervalo 1 k n Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Executaremos o algoritmo para n 100 27 O Crivo de Eratostenes Ideia Encontrar todos os primos no intervalo 1 k n Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Executaremos o algoritmo para n 100 27 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 1 k 2 nao marcado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 1 k 2 marcado com primo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 1 k 2 marcado com primo e cada multiplo de 2 identificado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 1 k 2 marcado com primo e cada multiplo de 2 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 2 k 3 nao marcado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 2 k 3 marcado com primo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 2 k 3 marcado com primo e cada multiplo de 3 identificado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 2 k 3 marcado com primo e cada multiplo de 3 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 3 k 4 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 4 k 5 nao marcado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 4 k 5 marcado com primo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 4 k 5 marcado com primo e cada multiplo de 5 identificado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Iteracao 4 k 5 marcado com primo e cada multiplo de 5 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Avancando um pouco Iteracao 6 k 7 marcado com primo e cada multiplo de 7 identificado 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Avancando um pouco Iteracao 6 k 7 marcado com primo e cada multiplo de 7 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 1 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo Avancando ate o fim Iteracao 99 k 100 marcado como naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 28 O Crivo de Eratostenes A execucao do algoritmo ja estaria completa apos a iteracao 10 pois Teorema n Se n e um inteiro composto entao n possui um divisor primo menor ou igual a n Para verificarmos se numeros de 2 a n sao primos ou compostos basta executar o Crivo de Eratostenes com testes por primos ate n 29 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 2 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo 6 para j de k ate n faca 7 se j nao marcado marque com primo Avancando um pouco Iteracao 6 k 7 marcado com primo e cada multiplo de 7 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 30 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 2 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo 6 para j de k ate n faca 7 se j nao marcado marque com primo Avancando mais um pouco Iteracao 9 k 10 marcado com naoprimo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 30 O Crivo de Eratostenes Algoritmo Crivo de Eratostenes Versao 2 1 Adicione todos os inteiros de 2 a n a uma lista 2 para k de 2 ate n faca 3 se k nao estiver marcado faca 4 marque k com primo 5 marque cada multiplo de k com naoprimo 6 para j de k ate n faca 7 se j nao marcado marque com primo E entao executamos o segundo laco Logo apos Iteracao 9 cada numero nao marcado devera ser marcado com primo 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 30 Distribuicao dos numeros primos 31 Distribuicao dos numeros primos Vimos que existe uma quantidade infinita de numeros primos A sequˆencia de primos apresenta uma certa irregularidade Vemos grandes lacunas e tambem primos que sao muito proximos Quao grande sao essas lacunas Vamos provar que essas lacunas ficam cada vez maiores quando consideramos numeros cada vez maiores Para isso precisaremos da seguinte definicao Definicao Fatorial Para todo inteiro positivo n o produto de todos os inteiros de 1 ate n e chamado de fatorial de n e e denotado por n Equivalentemente n 1 2 3 n 32 Distribuicao dos numeros primos Vimos que existe uma quantidade infinita de numeros primos A sequˆencia de primos apresenta uma certa irregularidade Vemos grandes lacunas e tambem primos que sao muito proximos Quao grande sao essas lacunas Vamos provar que essas lacunas ficam cada vez maiores quando consideramos numeros cada vez maiores Para isso precisaremos da seguinte definicao Definicao Fatorial Para todo inteiro positivo n o produto de todos os inteiros de 1 ate n e chamado de fatorial de n e e denotado por n Equivalentemente n 1 2 3 n 32 Distribuicao dos numeros primos Vimos que existe uma quantidade infinita de numeros primos A sequˆencia de primos apresenta uma certa irregularidade Vemos grandes lacunas e tambem primos que sao muito proximos Quao grande sao essas lacunas Vamos provar que essas lacunas ficam cada vez maiores quando consideramos numeros cada vez maiores Para isso precisaremos da seguinte definicao Definicao Fatorial Para todo inteiro positivo n o produto de todos os inteiros de 1 ate n e chamado de fatorial de n e e denotado por n Equivalentemente n 1 2 3 n 32 Distribuicao dos numeros primos Vimos que existe uma quantidade infinita de numeros primos A sequˆencia de primos apresenta uma certa irregularidade Vemos grandes lacunas e tambem primos que sao muito proximos Quao grande sao essas lacunas Vamos provar que essas lacunas ficam cada vez maiores quando consideramos numeros cada vez maiores Para isso precisaremos da seguinte definicao Definicao Fatorial Para todo inteiro positivo n o produto de todos os inteiros de 1 ate n e chamado de fatorial de n e e denotado por n Equivalentemente n 1 2 3 n 32 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Demonstracao Seja n um inteiro positivo Seja x n 1 2 Vamos mostrar que nenhum dos numeros x x 1 x 2 x n 1 e primo Como essa e uma sequˆencia de n inteiros positivos consecutivos isso e suficiente para provar o teorema Para ver que x nao e primo note que x n 1 2 x 1 2 3 4 n 1 2 2 1 3 4 n 1 1 Assim x pode ser escrito como o produto de dois inteiros positivos menores Entao x nao e primo 33 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Demonstracao Seja n um inteiro positivo Seja x n 1 2 Vamos mostrar que nenhum dos numeros x x 1 x 2 x n 1 e primo Como essa e uma sequˆencia de n inteiros positivos consecutivos isso e suficiente para provar o teorema Para ver que x nao e primo note que x n 1 2 x 1 2 3 4 n 1 2 2 1 3 4 n 1 1 Assim x pode ser escrito como o produto de dois inteiros positivos menores Entao x nao e primo 33 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Demonstracao Seja n um inteiro positivo Seja x n 1 2 Vamos mostrar que nenhum dos numeros x x 1 x 2 x n 1 e primo Como essa e uma sequˆencia de n inteiros positivos consecutivos isso e suficiente para provar o teorema Para ver que x nao e primo note que x n 1 2 x 1 2 3 4 n 1 2 2 1 3 4 n 1 1 Assim x pode ser escrito como o produto de dois inteiros positivos menores Entao x nao e primo 33 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Demonstracao Seja n um inteiro positivo Seja x n 1 2 Vamos mostrar que nenhum dos numeros x x 1 x 2 x n 1 e primo Como essa e uma sequˆencia de n inteiros positivos consecutivos isso e suficiente para provar o teorema Para ver que x nao e primo note que x n 1 2 x 1 2 3 4 n 1 2 2 1 3 4 n 1 1 Assim x pode ser escrito como o produto de dois inteiros positivos menores Entao x nao e primo 33 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Demonstracao Seja n um inteiro positivo Seja x n 1 2 Vamos mostrar que nenhum dos numeros x x 1 x 2 x n 1 e primo Como essa e uma sequˆencia de n inteiros positivos consecutivos isso e suficiente para provar o teorema Para ver que x nao e primo note que x n 1 2 x 1 2 3 4 n 1 2 2 1 3 4 n 1 1 Assim x pode ser escrito como o produto de dois inteiros positivos menores Entao x nao e primo 33 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Para ver que x 1 nao e primo note que x 1 n 1 3 1 2 3 4 n 1 3 3 1 3 4 n 1 1 Assim x 1 pode ser escrito como o produto de dois inteiros positivos menores Entao x 1 nao e primo Assim como fizemos para x e x 1 fazemos para os demais numeros da sequˆencia De fato esse mesmo raciocınio e naturalmente generalizado para os demais casos 34 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Para ver que x 1 nao e primo note que x 1 n 1 3 1 2 3 4 n 1 3 3 1 3 4 n 1 1 Assim x 1 pode ser escrito como o produto de dois inteiros positivos menores Entao x 1 nao e primo Assim como fizemos para x e x 1 fazemos para os demais numeros da sequˆencia De fato esse mesmo raciocınio e naturalmente generalizado para os demais casos 34 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Para ver que x 1 nao e primo note que x 1 n 1 3 1 2 3 4 n 1 3 3 1 3 4 n 1 1 Assim x 1 pode ser escrito como o produto de dois inteiros positivos menores Entao x 1 nao e primo Assim como fizemos para x e x 1 fazemos para os demais numeros da sequˆencia De fato esse mesmo raciocınio e naturalmente generalizado para os demais casos 34 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Para ver que x 1 nao e primo note que x 1 n 1 3 1 2 3 4 n 1 3 3 1 3 4 n 1 1 Assim x 1 pode ser escrito como o produto de dois inteiros positivos menores Entao x 1 nao e primo Assim como fizemos para x e x 1 fazemos para os demais numeros da sequˆencia De fato esse mesmo raciocınio e naturalmente generalizado para os demais casos 34 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Generalizando considere um numero x i com 0 i n 1 Entao x i n 1 i 2 1 2 3 4 n 1 i 2 i 2 1 2 3 i 1 i 3 n 1 1 Entao x i nao e primo para 0 i n 1 Portanto existem n inteiros compostos consecutivos 35 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Generalizando considere um numero x i com 0 i n 1 Entao x i n 1 i 2 1 2 3 4 n 1 i 2 i 2 1 2 3 i 1 i 3 n 1 1 Entao x i nao e primo para 0 i n 1 Portanto existem n inteiros compostos consecutivos 35 Distribuicao dos numeros primos Teorema Para todo inteiro positivo n existem n inteiros compostos consecutivos Continuacao da Demonstracao Generalizando considere um numero x i com 0 i n 1 Entao x i n 1 i 2 1 2 3 4 n 1 i 2 i 2 1 2 3 i 1 i 3 n 1 1 Entao x i nao e primo para 0 i n 1 Portanto existem n inteiros compostos consecutivos 35 Aplicacoes da Fatoracao de Inteiros 36 Aplicacoes da Fatoracao de Inteiros A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Exemplos 210 1024 220 1048576 230 1073741824 210 310 60466176 210 510 10000000000 310 510 576650390625 37 Aplicacoes da Fatoracao de Inteiros A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Exemplos 210 1024 220 1048576 230 1073741824 210 310 60466176 210 510 10000000000 310 510 576650390625 37 Aplicacoes da Fatoracao de Inteiros A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Todos os divisores de n podem ser obtidos pela fatoracao de n Exemplo Calculamos anteriormente que 99 32 11 Note que 1 Primos cujo expoente nao foram anotados tˆem expoente igual a 1 2 Primos que nao foram anotados tˆem expoente igual a 0 Ou seja calculamos 99 32 11 20 32 50 70 111 130 170 38 Aplicacoes da Fatoracao de Inteiros A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Todos os divisores de n podem ser obtidos pela fatoracao de n Exemplo Calculamos anteriormente que 99 32 11 Note que 1 Primos cujo expoente nao foram anotados tˆem expoente igual a 1 2 Primos que nao foram anotados tˆem expoente igual a 0 Ou seja calculamos 99 32 11 20 32 50 70 111 130 170 38 Aplicacoes da Fatoracao de Inteiros A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Todos os divisores primos de n estao na fatoracao de n Exemplo Calculamos anteriormente que 99 32 11 Do ponto de vista de que 99 32 11 20 32 50 70 111 130 170 Nao existe nenhum k multiplo de 2 tal que k 99 3 99 Nao existe nenhum k multiplo de 5 tal que k 99 Nao existe nenhum k multiplo de 7 tal que k 99 11 99 Nao existe nenhum k multiplo de 13 tal que k 99 Nao existe nenhum k multiplo de 17 tal que k 99 39 Aplicacao Encontrar Divisores A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Todos os divisores primos de n estao na fatoracao de n Exemplo Calculamos anteriormente que 99 32 11 Todos os divisores de 99 codificados na sua forma fatorada 30 110 1 30 111 11 31 110 3 31 111 33 32 110 9 32 111 99 Independente de como escrevemos 99 seus divisores serao os mesmos mas a forma fatorada revela tambem os primos que aparecem na fatoracao desses divisores 40 Aplicacao Encontrar Divisores A fatoracao de um numero determina de que numero estamos falando Numeros diferentes tˆem fatoracoes diferentes Podemos representar numeros muito grandes usando numeros relativamente pequenos Todos os divisores primos de n estao na fatoracao de n Exemplo Calculamos anteriormente que 99 32 11 Todos os divisores de 99 codificados na sua forma fatorada 30 110 1 30 111 11 31 110 3 31 111 33 32 110 9 32 111 99 Entao basta variarmos os expoentes de cada primo de 0 ate o valor de expoente que esse primo apresenta na fatoracao de n para encontrarmos todos os divisores de n 40 Aplicacao Calcular Quantidade de Divisores E se quisermos saber apenas quantos divisores um numero tem A fatoracao do numero tambem diz isso Exemplo Calculamos anteriormente que 99 32 11 E vimos que basta variarmos os expoentes de cada primo de 0 ate o valor de expoente que esse primo apresenta na fatoracao de n para encontrarmos todos os divisores de n Entao se variarmos o expoente de 3 de 0 ate 2 teremos 3 possıveis valores se variarmos o expoente de 11 de 0 ate 1 teremos 2 possıveis valores Como os expoentes sao indepententes devemos multiplicar os numeros de possıveis valores Concluımos portanto que 99 tem 3 2 6 divisores 41 Aplicacao Calcular Quantidade de Divisores E se quisermos saber apenas quantos divisores um numero tem A fatoracao do numero tambem diz isso Exemplo Calculamos anteriormente que 99 32 11 E vimos que basta variarmos os expoentes de cada primo de 0 ate o valor de expoente que esse primo apresenta na fatoracao de n para encontrarmos todos os divisores de n Entao se variarmos o expoente de 3 de 0 ate 2 teremos 3 possıveis valores se variarmos o expoente de 11 de 0 ate 1 teremos 2 possıveis valores Como os expoentes sao indepententes devemos multiplicar os numeros de possıveis valores Concluımos portanto que 99 tem 3 2 6 divisores 41 Aplicacao Calcular Quantidade de Divisores E se quisermos saber apenas quantos divisores um numero tem A fatoracao do numero tambem diz isso Exemplo Calculamos anteriormente que 99 32 11 E vimos que basta variarmos os expoentes de cada primo de 0 ate o valor de expoente que esse primo apresenta na fatoracao de n para encontrarmos todos os divisores de n Entao se variarmos o expoente de 3 de 0 ate 2 teremos 3 possıveis valores se variarmos o expoente de 11 de 0 ate 1 teremos 2 possıveis valores Como os expoentes sao indepententes devemos multiplicar os numeros de possıveis valores Concluımos portanto que 99 tem 3 2 6 divisores 41 Aplicacao Calcular Quantidade de Divisores E se quisermos saber apenas quantos divisores um numero tem A fatoracao do numero tambem diz isso Exemplo Calculamos anteriormente que 99 32 11 E vimos que basta variarmos os expoentes de cada primo de 0 ate o valor de expoente que esse primo apresenta na fatoracao de n para encontrarmos todos os divisores de n Entao se variarmos o expoente de 3 de 0 ate 2 teremos 3 possıveis valores se variarmos o expoente de 11 de 0 ate 1 teremos 2 possıveis valores Como os expoentes sao indepententes devemos multiplicar os numeros de possıveis valores Concluımos portanto que 99 tem 3 2 6 divisores 41 Aplicacao Calcular Quantidade de Divisores Exemplo Pelo Algoritmo de Fatoracao encontraremos que 120 23 31 51 Entao se variarmos o expoente de 2 de 0 ate 3 teremos 4 possıveis valores se variarmos o expoente de 3 de 0 ate 1 teremos 2 possıveis valores se variarmos o expoente de 5 de 0 ate 1 teremos 2 possıveis valores Como os expoentes sao indepententes devemos multiplicar os numeros de possıveis valores Concluımos portanto que 120 tem 4 2 2 16 divisores 42 Aplicacao Calcular Quantidade de Divisores Exemplo Pelo Algoritmo de Fatoracao encontraremos que 120 23 31 51 De fato 120 tem 16 divisores 20 30 50 1 20 30 51 5 20 31 50 3 20 31 51 15 21 30 50 2 21 30 51 10 21 31 50 6 21 31 51 30 22 30 50 4 22 30 51 20 22 31 50 12 22 31 51 60 23 30 50 8 23 30 51 40 23 31 50 24 23 31 51 120 42 Máximo Divisor Comum Maximo Divisor Comum Definicao Maximo divisor comum Sejam a e b dois inteiros pelo menos um deles diferente de zero O maximo divisor comum de a e b e o maior inteiro d tal que d a e d b O maximo divisor comum de a e b e denotado por MDCa b Denotamos por Da o conjunto dos divisores de a Exemplo Dados os inteiros 3 e 5 temos que D3 1 3 D5 1 5 e MDC5 3 1 Obs1 para quaisquer dois inteiros nao negativos a e b temos que Da Db pois 1 a e 1 b Obs2 Como ja sabemos calcular divisores de um numero por fatoracao temos como calcular os divisores comuns a dois ou mais numeros Obs3 E se sabemos encontrar divisores comuns a dois ou mais numeros podemos indentificar o maior deles 44 Maximo Divisor Comum Definicao Maximo divisor comum Sejam a e b dois inteiros pelo menos um deles diferente de zero O maximo divisor comum de a e b e o maior inteiro d tal que d a e d b O maximo divisor comum de a e b e denotado por MDCa b Denotamos por Da o conjunto dos divisores de a Exemplo Dados os inteiros 3 e 5 temos que D3 1 3 D5 1 5 e MDC5 3 1 Obs1 para quaisquer dois inteiros nao negativos a e b temos que Da Db pois 1 a e 1 b Obs2 Como ja sabemos calcular divisores de um numero por fatoracao temos como calcular os divisores comuns a dois ou mais numeros Obs3 E se sabemos encontrar divisores comuns a dois ou mais numeros podemos indentificar o maior deles 44 Maximo Divisor Comum Definicao Maximo divisor comum Sejam a e b dois inteiros pelo menos um deles diferente de zero O maximo divisor comum de a e b e o maior inteiro d tal que d a e d b O maximo divisor comum de a e b e denotado por MDCa b Denotamos por Da o conjunto dos divisores de a Exemplo Dados os inteiros 3 e 5 temos que D3 1 3 D5 1 5 e MDC5 3 1 Obs1 para quaisquer dois inteiros nao negativos a e b temos que Da Db pois 1 a e 1 b Obs2 Como ja sabemos calcular divisores de um numero por fatoracao temos como calcular os divisores comuns a dois ou mais numeros Obs3 E se sabemos encontrar divisores comuns a dois ou mais numeros podemos indentificar o maior deles 44 Maximo Divisor Comum Estrategia 1 Calcular os divisores dos dois numeros e comparalos 45 Calculo do MDC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 120 23 31 51 Entao calculamos que 1 D99 1 3 9 11 33 99 2 D120 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120 Comparando as listas os unicos divisores comuns de 99 e 120 sao 1 e 3 Portanto MDC99 120 3 46 Calculo do MDC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 120 23 31 51 Entao calculamos que 1 D99 1 3 9 11 33 99 2 D120 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120 Comparando as listas os unicos divisores comuns de 99 e 120 sao 1 e 3 Portanto MDC99 120 3 46 Calculo do MDC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 120 23 31 51 Entao calculamos que 1 D99 1 3 9 11 33 99 2 D120 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120 Comparando as listas os unicos divisores comuns de 99 e 120 sao 1 e 3 Portanto MDC99 120 3 46 Maximo Divisor Comum Obs2 Como ja sabemos calcular divisores de um numero por fatoracao temos como calcular os divisores comuns a dois ou mais numeros Obs3 E se sabemos encontrar divisores comuns a dois ou mais numeros podemos indentificar o maior deles Estrategia 2 Calcular o MDC a partir dos fatores comuns 47 Calculo do MDC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 120 23 31 51 Note que 1 Todo divisor de 99 e combinacao de 30 31 32 com 110 111 2 Todo divisor de 120 e combinacao de 20 21 22 23 com 30 31 e com 50 51 Entao os divisores comuns de 99 e 120 so podem ser combinacoes de 30 ou 31 o que nos permite construir apenas os numeros 1 e 3 Portanto MDC99 120 3 48 Calculo do MDC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 120 23 31 51 Note que 1 Todo divisor de 99 e combinacao de 30 31 32 com 110 111 2 Todo divisor de 120 e combinacao de 20 21 22 23 com 30 31 e com 50 51 Entao os divisores comuns de 99 e 120 so podem ser combinacoes de 30 ou 31 o que nos permite construir apenas os numeros 1 e 3 Portanto MDC99 120 3 48 Calculo do MDC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 120 23 31 51 Note que 1 Todo divisor de 99 e combinacao de 30 31 32 com 110 111 2 Todo divisor de 120 e combinacao de 20 21 22 23 com 30 31 e com 50 51 Entao os divisores comuns de 99 e 120 so podem ser combinacoes de 30 ou 31 o que nos permite construir apenas os numeros 1 e 3 Portanto MDC99 120 3 48 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Demonstracao A fim de provar que esta formula para MDCa b e valida devemos mostrar que o inteiro do lado direito da igualdade divide ambos a e b e que nao existe nenhum inteiro maior que tambem o faca De fato este inteiro divide a e b porque o expoente de cada primo pj na formula nao excede o expoente que pj tem tanto na fatoracao de a quanto na fatoracao de b Alem disso nenhum inteiro maior pode dividir a e b porque os expoentes dos primos nesta formula nao pode ser incrementado e nenhum outro primo pode ser incluıdo 49 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Demonstracao A fim de provar que esta formula para MDCa b e valida devemos mostrar que o inteiro do lado direito da igualdade divide ambos a e b e que nao existe nenhum inteiro maior que tambem o faca De fato este inteiro divide a e b porque o expoente de cada primo pj na formula nao excede o expoente que pj tem tanto na fatoracao de a quanto na fatoracao de b Alem disso nenhum inteiro maior pode dividir a e b porque os expoentes dos primos nesta formula nao pode ser incrementado e nenhum outro primo pode ser incluıdo 49 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Demonstracao A fim de provar que esta formula para MDCa b e valida devemos mostrar que o inteiro do lado direito da igualdade divide ambos a e b e que nao existe nenhum inteiro maior que tambem o faca De fato este inteiro divide a e b porque o expoente de cada primo pj na formula nao excede o expoente que pj tem tanto na fatoracao de a quanto na fatoracao de b Alem disso nenhum inteiro maior pode dividir a e b porque os expoentes dos primos nesta formula nao pode ser incrementado e nenhum outro primo pode ser incluıdo 49 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Demonstracao A fim de provar que esta formula para MDCa b e valida devemos mostrar que o inteiro do lado direito da igualdade divide ambos a e b e que nao existe nenhum inteiro maior que tambem o faca De fato este inteiro divide a e b porque o expoente de cada primo pj na formula nao excede o expoente que pj tem tanto na fatoracao de a quanto na fatoracao de b Alem disso nenhum inteiro maior pode dividir a e b porque os expoentes dos primos nesta formula nao pode ser incrementado e nenhum outro primo pode ser incluıdo 49 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Exemplo Pelo Algoritmo da Fatoracao encontramos que 99 32 111 e 120 23 31 51 Os primos que ocorrem com expoentes positivos nestas fatoracoes sao 2 3 5 e 11 Entao percebamos estas fatoracoes como 99 20 32 50 111 e 120 23 31 51 110 Logo MDC120 99 2min03 3min21 5min01 11min10 20 31 51 110 3 50 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Exemplo Pelo Algoritmo da Fatoracao encontramos que 99 32 111 e 120 23 31 51 Os primos que ocorrem com expoentes positivos nestas fatoracoes sao 2 3 5 e 11 Entao percebamos estas fatoracoes como 99 20 32 50 111 e 120 23 31 51 110 Logo MDC120 99 2min03 3min21 5min01 11min10 20 31 51 110 3 50 Calculo do MDC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MDCa b pmina1b1 1 pmina2b2 2 pminanbn n Exemplo Pelo Algoritmo da Fatoracao encontramos que 99 32 111 e 120 23 31 51 Os primos que ocorrem com expoentes positivos nestas fatoracoes sao 2 3 5 e 11 Entao percebamos estas fatoracoes como 99 20 32 50 111 e 120 23 31 51 110 Logo MDC120 99 2min03 3min21 5min01 11min10 20 31 51 110 3 50 Mínimo Múltiplo Comum Calculo do MMC Definicao Dados dois inteiros a e b diferentes de zero o mınimo multiplo comum de a e b e o menor inteiro positivo d tal que a d e b d Notacao A funcao MMCa b retorna o mınimo multiplo comum de a b Onde o MMC aparece Mınimo multiplo comum aparece quando queremos adicionar duas fracoes para adicionar duas fracoes com denominadores a e b iniciamos reescrevendoos com o denominador comum MMCa b Exemplo Somar 1 6 1 4 Como MMC6 4 12 temos que 2 12 3 12 5 12 52 Calculo do MMC Definicao Dados dois inteiros a e b diferentes de zero o mınimo multiplo comum de a e b e o menor inteiro positivo d tal que a d e b d Notacao A funcao MMCa b retorna o mınimo multiplo comum de a b Onde o MMC aparece Mınimo multiplo comum aparece quando queremos adicionar duas fracoes para adicionar duas fracoes com denominadores a e b iniciamos reescrevendoos com o denominador comum MMCa b Exemplo Somar 1 6 1 4 Como MMC6 4 12 temos que 2 12 3 12 5 12 52 Calculo do MMC Definicao Dados dois inteiros a e b diferentes de zero o mınimo multiplo comum de a e b e o menor inteiro positivo d tal que a d e b d Notacao A funcao MMCa b retorna o mınimo multiplo comum de a b Onde o MMC aparece Mınimo multiplo comum aparece quando queremos adicionar duas fracoes para adicionar duas fracoes com denominadores a e b iniciamos reescrevendoos com o denominador comum MMCa b Exemplo Somar 1 6 1 4 Como MMC6 4 12 temos que 2 12 3 12 5 12 52 Calculo do MMC Podemos calcular o MMC de a e b a partir de seus multiplos Para encontrar multiplos de um numero basta multiplicalo pelos inteiros positivos Mas cada inteiro tera infinitos multiplos positivos dificultando encontrarmos os numeros que se repetem nas duas listas Estrategia 1 Calcular o MMC a partir dos fatores comuns 53 Calculo do MMC Podemos calcular o MMC de a e b a partir de seus multiplos Para encontrar multiplos de um numero basta multiplicalo pelos inteiros positivos Mas cada inteiro tera infinitos multiplos positivos dificultando encontrarmos os numeros que se repetem nas duas listas Estrategia 1 Calcular o MMC a partir dos fatores comuns 53 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Note que Todo multiplo de 99 precisa reter os fatores 32 e 111 Todo multiplo de 120 precisa reter os fatores 23 31 e 51 Entao o menor multiplo comum de 99 e 120 tera estes fatores e nada mais Alem disso como 31 32 basta usarmos 32 para incluir os dois fatores de base 3 Portanto MMC99 120 23 32 51 111 3960 54 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Note que Todo multiplo de 99 precisa reter os fatores 32 e 111 Todo multiplo de 120 precisa reter os fatores 23 31 e 51 Entao o menor multiplo comum de 99 e 120 tera estes fatores e nada mais Alem disso como 31 32 basta usarmos 32 para incluir os dois fatores de base 3 Portanto MMC99 120 23 32 51 111 3960 54 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Note que Todo multiplo de 99 precisa reter os fatores 32 e 111 Todo multiplo de 120 precisa reter os fatores 23 31 e 51 Entao o menor multiplo comum de 99 e 120 tera estes fatores e nada mais Alem disso como 31 32 basta usarmos 32 para incluir os dois fatores de base 3 Portanto MMC99 120 23 32 51 111 3960 54 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Note que Todo multiplo de 99 precisa reter os fatores 32 e 111 Todo multiplo de 120 precisa reter os fatores 23 31 e 51 Entao o menor multiplo comum de 99 e 120 tera estes fatores e nada mais Alem disso como 31 32 basta usarmos 32 para incluir os dois fatores de base 3 Portanto MMC99 120 23 32 51 111 3960 54 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 MDC99 120 3960 Observe que 3960 div 99 40 3960 div 120 33 Ou seja a estrategia de calcular multiplos de cada numero para comparar as duas listas exigiria ao menos 40 multiplos de 99 e 33 multiplos de 120 o que nao e nada eficiente 55 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 MDC99 120 3960 Observe que 3960 div 99 40 3960 div 120 33 Ou seja a estrategia de calcular multiplos de cada numero para comparar as duas listas exigiria ao menos 40 multiplos de 99 e 33 multiplos de 120 o que nao e nada eficiente 55 Calculo do MMC Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 MDC99 120 3960 Observe que 3960 div 99 40 3960 div 120 33 Ou seja a estrategia de calcular multiplos de cada numero para comparar as duas listas exigiria ao menos 40 multiplos de 99 e 33 multiplos de 120 o que nao e nada eficiente 55 Calculo do MMC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MMCa b pmaxa1b1 1 pmaxa2b2 2 pmaxanbn n Demonstracao A formula dada para MMCa b e valida porque um mınimo multiplo comum de a e b tem pelo menos maxai bi fatores pi na sua fatoracao prima Alem disso o mınimo multiplo comum nao tem nenhum outro fator primo alem daqueles que estao em a e b 56 Calculo do MMC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MMCa b pmaxa1b1 1 pmaxa2b2 2 pmaxanbn n Demonstracao A formula dada para MMCa b e valida porque um mınimo multiplo comum de a e b tem pelo menos maxai bi fatores pi na sua fatoracao prima Alem disso o mınimo multiplo comum nao tem nenhum outro fator primo alem daqueles que estao em a e b 56 Calculo do MMC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MMCa b pmaxa1b1 1 pmaxa2b2 2 pmaxanbn n Demonstracao A formula dada para MMCa b e valida porque um mınimo multiplo comum de a e b tem pelo menos maxai bi fatores pi na sua fatoracao prima Alem disso o mınimo multiplo comum nao tem nenhum outro fator primo alem daqueles que estao em a e b 56 Calculo do MMC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MMCa b pmaxa1b1 1 pmaxa2b2 2 pmaxanbn n Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Os primos que ocorrem com expoentes positivos nestas fatoracoes sao 2 3 5 e 11 Entao convem entendermos estas fatoracoes como 99 20 32 50 111 e 120 23 31 51 110 Entao MMC99 120 2max03 3max21 5max01 11max10 23 32 51 111 3960 57 Calculo do MMC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MMCa b pmaxa1b1 1 pmaxa2b2 2 pmaxanbn n Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Os primos que ocorrem com expoentes positivos nestas fatoracoes sao 2 3 5 e 11 Entao convem entendermos estas fatoracoes como 99 20 32 50 111 e 120 23 31 51 110 Entao MMC99 120 2max03 3max21 5max01 11max10 23 32 51 111 3960 57 Calculo do MMC Teorema Dados a e b inteiros positivos considere que p1 p2 pn sao todos os primos que ocorrem com expoentes positivos nas fatoracoes de a ou de b Isto nos permite escrever que a pa1 1 pa2 2 pan n e b pb1 1 pb2 2 pbn n Entao MMCa b pmaxa1b1 1 pmaxa2b2 2 pmaxanbn n Exemplo Pelo Algoritmo de Fatoracao encontramos que 99 32 111 e 120 23 31 51 Os primos que ocorrem com expoentes positivos nestas fatoracoes sao 2 3 5 e 11 Entao convem entendermos estas fatoracoes como 99 20 32 50 111 e 120 23 31 51 110 Entao MMC99 120 2max03 3max21 5max01 11max10 23 32 51 111 3960 57 Calculo do MMC a partir do MDC Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Exemplo Anteriormente calculamos MMC99 120 3960 e MDC99 120 3 Note que 3960 3 11880 99 120 11880 Ou seja MMC99 120 MDC99 120 99 120 como diz o teorema 58 Calculo do MMC a partir do MDC Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Exemplo Anteriormente calculamos MMC99 120 3960 e MDC99 120 3 Note que 3960 3 11880 99 120 11880 Mas por que isso acontece Lembre que 99 20 32 50 111 e 120 23 31 51 110 59 Calculo do MMC a partir do MDC Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Exemplo Anteriormente calculamos MMC99 120 3960 e MDC99 120 3 Note que 3960 3 11880 99 120 11880 Mas por que isso acontece Lembre que 99 20 32 50 111 e 120 23 31 51 110 Daı calculamos MDC99 120 2min03 3min21 5min01 11min10 60 Calculo do MMC a partir do MDC Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Exemplo Anteriormente calculamos MMC99 120 3960 e MDC99 120 3 Note que 3960 3 11880 99 120 11880 Mas por que isso acontece Lembre que 99 20 32 50 111 e 120 23 31 51 110 Daı calculamos MDC99 120 2min03 3min21 5min01 11min10 20 31 50 110 61 Calculo do MMC a partir do MDC Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Exemplo Anteriormente calculamos MMC99 120 3960 e MDC99 120 3 Note que 3960 3 11880 99 120 11880 Mas por que isso acontece Lembre que 99 20 32 50 111 e 120 23 31 51 110 Daı calculamos MDC99 120 2min03 3min21 5min01 11min10 20 31 50 110 e MMC99 120 2max03 3max21 5max01 11max10 62 Calculo do MMC a partir do MDC Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Exemplo Anteriormente calculamos MMC99 120 3960 e MDC99 120 3 Note que 3960 3 11880 99 120 11880 Mas por que isso acontece Lembre que 99 20 32 50 111 e 120 23 31 51 110 Daı calculamos MDC99 120 2min03 3min21 5min01 11min10 20 31 50 110 e MMC99 120 2max03 3max21 5max01 11max10 23 32 51 111 63 Calculo do MMC a partir do MDC Nossos numeros sao 99 20 32 50 111 120 23 31 51 110 MDC99 120 20 31 50 110 MMC99 120 23 32 51 111 Logo 99 120 20 32 50 111 23 31 51 110 20 32 50 111 23 31 51 110 23 32 51 111 20 31 50 110 23 32 51 111 20 31 50 110 MMC99 120 MDC99 120 64 Exercıcio 1 Prove que para quaisquer dois numeros c e d temse que minc d maxc d c d Usando o enunciado do exercıcio acima prove o seguinte teorema Teorema Sejam a b inteiros positivos Entao MMCa b MDCa b a b Dica Use tambem as fatoracoes em numeros primos de a e b e as formulas para MDCa b e MMCa b vistas nesta aula em termos destas fatoracoes 65 FIM