estamos de volta para mais um encontro o objetivo de hoje não é exatamente resolver problemas utilizando a aritmética modular mas sim tentar demonstrar o resultado famoso conhecido como pequeno teorema de fermat é esse resultado será demonstrado utilizando as nossas ferramentas de aritmética modulada então quem teorema de fermat diz que se eu tenho um primo o número p primo em um número inteiro então essa congruência que é verdadeira o módulo p é o próprio número prêmio então eu vou abrir aqui em duas possibilidades a primeira que oa é múltiplo dp vai ser a primeira hipótese a
segunda hipótese pode se contar que o ar não é múltiplo dp só podem acontecer essas duas coisas se oa for múltiplo dp então o a é congruente a 0 módulo p e aí aquilo lá fica a verdadeira porque eu vou ficar com 10 elevado à p congruente a 0 módulo p conheci eu percebo que se o a multiplus dp de fato aquele resultado ali é verdadeiro agora eu preciso demonstrar que isso funciona quando a não é múltiplo dp quando a não é múltiplo dp eo p é o número primo então posso concluir que neste caso
o mdc de ipê é um ou seja eles são primos entre si e aí aquela nossa expressão original pode ser reescrita pelo seguinte como ipê são primos entre si então essa classe ar tem classe inversa módulo p que eu vou chamar de a linha então essa classe existe eu posso escrever assim ataque à classe inversa e se há elevado a pm ou escrever como a vezes a elevada apenas um e como é multiplicar pela classe inversa no primeiro membro tem que fazer o mesmo do outro lado bom a gente já sabe que o produto da
classe inversa com a classe original tem que dar o elemento nível da multiplicação então isso aqui vai ficar a elevada pelo menos um congruente está aqui de novo produto congruente a um módulo p então como eu já provei que o enunciado do teorema funciona quando é múltiplo dp está faltando provar agora que ele funciona quando o anão é múltiplo dp e provar esse anunciado quando a não é múltiplo dp é equivalente a provar que isso aqui é verdadeira então a gente vai se concentrar agora em provar que isso aqui é verdade nessas condições aqui em
que o mdc de ipê é um bom pra fazer essa demonstração primeiro eu vou considerar essa seqüência a 2 a 3 até pelo menos um a um ea partir daqui eu vou encaminhar em quatro passos o primeiro passo é provar isso aqui que essa é uma sequência de pelo menos um múltiplo de ar na qual não há múltiplos dp então você está vendo que de fato são múltiplos de ar aqui eu tenho o primeiro múltiplo segundo o músico o terceiro músico então fica fácil ver que eu tenho pelo menos um múltiplos doha agora o que
eu quero mostrar que aqui dentro não tem nenhum que seja múltiplo dp então vamos imaginar o multiplicador que é o número que vem aqui na frente ele vai de 1 até pelo menos um e vamos supor que exista um carro nessa lista que faz o último lar seu último gp então suponho que exista cá tal que caco vezes a já múltiplo dp se o café de sá é múltiplo dp então o p dividir o produto cabeça' agora o kaká é um número que está nessa lista que vai de 1 até pelo menos 11 o pp
é maior do que todos os elementos desse conjunto então o pp é primo conca o penal dividir cá e aí esse é um resultado que a gente está acostumado a usar se o perdi vide kaviza eo pp primo conca a conclusão é que o pp de vídeo a mas essa conclusão absurda porque lá no início a gente combinou que oa que o p são prêmios entre si então isso aqui é um absurdo conclusão de fato essa suposição aqui tá errada ou seja não existe naquela lista original um número que seja um múltiplo de p neste
segundo passo o que eu quero provar é que lá naquela minha sequência original não existem dois números dois camaradas que sejam congruentes entre si o módulo p então pra isso eu vou admitir dois números k1 e k2 pertencentes a listinha que vai de 1 até pelo menos um de modo que estes dois camaradas sejam diferente mas o a fazer maior aqui o a vez de cada um seja congruente a vezes cada então veja só admitindo que existem dois números diferentes nessa lista que fazem com que esses dois múltiplos a cada um ea cada dois sejam
congruentes módulo pedro bom como a eo p são prêmios entre si essa classe a tem classe inversa módulo p eu vou chamar sacolas inversa de a linha então eu vou pegar esse a linha e vou aplicar aqui a linha vezes a cada um congruente a a linha a k2 módulo p e aí esse produto vai dar a identidade ea gente conclui que cada um é congruente a cada 2 módulo p a princípio o fato de esses dois números serem congruentes não quer dizer que eles sejam iguais mas como os dois estão dentro dessa lista que
vai de 1 até pelo menos um isso garante que se eles são congruentes estão naquela lista necessariamente eles são iguais só que isso se contrapõe à nossa hipótese inicial então isso aqui também é um absurdo por tantos eu escolho k1 e k2 diferentes esses múltiplos a k1 e k2 não podem ser concluinte módulo p isso garante que lá naquela nossa lista original não existem os números que sejam congruentes módulo p o terceiro passo é bem curtinho mas é fundamental para a nossa demonstração que é o seguinte quando eu estou trabalhando com uma classe com um
módulo p as classes de equivalência são 123 até pelo menos um é nós já demonstramos os passos anteriores que dentro dessa sequência ninguém é múltiplo dbb ou seja ninguém é congruente a 0 módulo p e também mostramos no segundo passo que não há dois números nesta sequência que sejam congruentes entre si módulo p isso quer dizer que cada uma dessas classes de equivalência está associado a um dos números da minha seqüência e há somente um a uma uma associação biunívoca entre essas classes de equivalência e os números que fazem parte da minha sequência então cada
um desses caras está associado um único número da minha sequência lá de cima isso aqui tem a ver com algo que nós já vimos em aulas anteriores quando nós fizemos aquela tabela de multiplicação módulo alguma coisa quando o nosso número módulo psp era um primo acontecia de ter das classes terem investe nessas linhas que correspondiam às classe que possuir o invest nós vimos todas essas classes aqui aparecendo lá na linha não exatamente nessa ordem aparecem ordens invertidas em outras permutações e é a mesma coisa está acontecendo aqui essa correspondência ela não se dá exatamente nessa
ordem pode ser que o esteja associado ou 3 pode ser que os três já esteja associado a um mas de fato cada um de lata associado a um único daqui o quarto e último passo da nossa demonstração é pegar os números daquela seqüência original e multiplicar esse produto será congruente a 12 vezes três até pelo menos um isso módulo p do lado de cá o aparece pelo menos uma vez e então escrever isso assim é elevado à p - um que multiplica 123 aqui eu tenho a multiplicação dos números naturais até pelo menos um então
isso fica pelo menos 11 fatorial e isso é congruente ao mesmo produto que aparece outro lado que eu represento como pelo menos um fator real tudo isso mode p mas aí vamos para uma observação aqui se eu me lembrar que o mdc entre este número primo e pelo menos um fator yao é um porque é que isso acontece porque aqui eu tenho um produto de um dois três até pelo menos 1 e aqui eu tenho p então eles são primos entre si o resultado do produto de todos esses fatores aqui não pode ser simplificado com
o pp que é primo então mdc entre eles é um isso garante além do corte nós já vimos isso antes isso só pode acontecer por causa desse fato aqui então consigo cancellara conseguiu cortar pelo menos um fator yao e concluiu que há um elevado apenas um é congruente a um módulo p era esse o resultado que a gente queria obter na nossa próxima aula utilizaremos esse resultado que nós acabamos de provar na resolução de alguns problemas interessantes até lá
