Teoria dos Números

Universidade Federal do Maranhao Superintendˆencia de Tecnologias na Educacao Licenciatura em Matematica EaD Teoria dos Numeros ATIVIDADE AVALIATIVA UNIDADE 3 Exercıcio 1 20 pts Seja a 1 e m n 0 Prove que mdcam 1 an 1 amdcm n 1 Exercıcio 2 20 pts Sejam mn 0 e suponha que mn m2 n2 Prove que m n Exercıcio 3 20 pts Considere a sequˆencia infinita de numeros 10 001 100 010 001 1000 100 010 001 Mostre que nenhum dos termos dessa sequˆencia e primo Exercıcio 4 20 pts Seja n um numero inteiro positivo Dizemos que n e um numero potˆencia se em sua fatoracao em primos todos os expoentes forem estritamente maiores que 1 Prove que existem infinitos inteiros positivos distintos tais que i Nenhum dos elementos do conjunto e um numero potˆencia ii A soma de qualquer subconjunto finito de elementos tambem nao e um numero potˆencia 1 QUESTÃO 1 Seja 𝑎 1 e 𝑚 𝑛 𝑍𝟘 Desejase provar que 𝑔𝑐𝑑𝑎𝑚 1 𝑎𝑛 1 𝑎gcd𝑚𝑛 1 Primeiro estabelecese o seguinte fato fundamental uma versão exponencial do algoritmo de Euclides para inteiros 𝑢 𝑣 0 𝑔𝑐𝑑𝑎𝑢 1 𝑎𝑣 1 𝑔𝑐𝑑𝑎𝑢𝑣 1 𝑎𝑣 1 Justificase pela identidade 𝑎𝑢 1 𝑎𝑢𝑣 𝑎𝑣 1 𝑎𝑢𝑣 1 𝑎𝑣 𝑎𝑣 1 Como qualquer divisor comum de 𝑎𝑢 1 e 𝑎𝑣 1 também divide combinações lineares inteiras desses dois números o conjunto de divisores comuns de 𝑎𝑢 1 𝑎𝑣 1 coincide com o de 𝑎𝑢𝑣 1 𝑎𝑣 1 Logo seus máximos divisores comuns são iguais Aplicase agora o algoritmo de Euclides aos expoentes m e n Supondo sem perda de generalidade 𝑚 𝑛 constróise a sequência de restos 𝑟0 𝑚 𝑟1 𝑛 𝑟𝑘1 𝑟𝑘1 mod 𝑟𝑘 𝑘 1 que termina em 𝑟𝑡 gcd𝑚 𝑛 e 𝑟𝑡1 0 Repetindo a identidade acima a cada passo obtémse gcd𝑎𝑟0 1 𝑎𝑟1 1 gcd𝑎𝑟1 1 𝑎𝑟2 1 gcd𝑎𝑟𝑡 1 𝑎𝑟𝑡1 1 Como 𝑟𝑡1 0 temse 𝑎𝑟𝑡1 1 𝑎0 1 0 e por definição de máximo divisor comum gcd𝑥 0 𝑥 para todo 𝑥 𝑍𝟘 Assim gcd𝑎𝑚 1 𝑎𝑛 1 gcd𝑎𝑟𝑡 10 𝑎𝑟𝑡 1 𝑎gcd𝑚𝑛 1 A igualdade requerida está portanto demonstrada A escolha da identidade 𝑎𝑢 1 𝑎𝑢𝑣 1 𝑎𝑣 𝑎𝑣 1 é natural porque permite transportar o algoritmo de Euclides dos inteiros uv para o par 𝑎𝑢 1 𝑎𝑣 1 preservando o mesmo máximo divisor comum até chegar ao resto nulo quando o resultado se lê diretamente QUESTÃO 2 Sejam 𝑚 𝑛 𝑍𝟘 e suponhase que 𝑚𝑛 𝑚2 𝑛2 Desejase provar que 𝑚 𝑛 Escrevese 𝑑 gcd𝑚 𝑛 e decompõemse 𝑚 𝑑 𝑥 𝑛 𝑑 𝑦 com gcd𝑥 𝑦 1 Substituindo na hipótese de divisibilidade 𝑚𝑛 𝑚2 𝑛2 𝑑2 𝑥𝑦 𝑑2 𝑥2 𝑦2 𝑥𝑦 𝑥2 𝑦2 Dessa última concluise individualmente que 𝑥 𝑥2 𝑦2 e 𝑦 𝑥2 𝑦2 Como 𝑥 𝑥2 a primeira implica 𝑥 𝑦2 De modo análogo como 𝑦 𝑦2 a segunda implica 𝑦 𝑥2 Agora usase o fato aritmético se gcd𝑥 𝑦 1 e 𝑥 𝑦2 então 𝑥 1 Com efeito todo primo p que divide x dividiria 𝑦2 logo dividiria y contrariando gcd𝑥 𝑦 1 Portanto 𝑥 1 Simetricamente de 𝑦 𝑥2 e gcd𝑥 𝑦 1 segue 𝑦 1 Concluise que 𝑥 𝑦 1 Logo 𝑚 𝑑 𝑥 𝑑 e 𝑛 𝑑 𝑦 𝑑 o que fornece 𝑚 𝑛 como se queria demonstrar QUESTÃO 3 Considere a sequência cujos termos são 10001 100010001 1000100010001 Cada termo tem a forma 𝑇𝑘 1 104 108 104𝑘 k1 parcelas 104𝑖 𝑘 𝑖0 Pela soma de uma progressão geométrica 𝑇𝑘 104𝑘1 1 104 1 𝑘 1 Escrevese 𝑏 104 e 𝑐 102 observase que 𝑏 𝑐2 O objetivo é mostrar que 𝑇𝑘 é sempre composto Caso k ímpar Então k1 é par logo 𝑇𝑘 𝑏𝑘1 1 𝑏 1 𝑏 𝑘1 2 1 𝑏 𝑘1 2 1 𝑏 1 𝑏 𝑘1 2 1 𝑏 1 𝑏 𝑘1 2 1 O primeiro fator é inteiro porque 𝑥𝑟1 𝑥1 1 𝑥 𝑥𝑟1 e o segundo fator é maior que 1 Assim 𝑇𝑘 é produto de dois inteiros maiores que 1 portanto não é primo Caso k par Então k1 é ímpar Usando 𝑏 𝑐2 𝑇𝑘 𝑐2𝑘1 1 𝑐2 1 𝑐𝑘1 1𝑐𝑘1 1 𝑐 1𝑐 1 𝑐𝑘1 1 𝑐 1 𝑐𝑘1 1 𝑐 1 Ambos os quocientes são inteiros 𝑐𝑘1 1 é múltiplo de 𝑐 1 para todo k e 𝑐𝑘1 1 é múltiplo de 𝑐 1 quando 𝑘 1 é ímpar Além disso cada fator é maior que 1 Logo 𝑇𝑘 é composto também neste caso Concluise que para todo 𝑘 1 𝑇𝑘 104𝑘1 1 104 1 é composto Portanto nenhum termo da sequência é primo QUESTÃO 4 i Chamase número potência aquele cujo fatoramento em primos tem todos os expoentes estritamente maiores que 1 Desejase construir infinitos inteiros positivos distintos que não sejam números potência Considerase o conjunto 𝑆 𝑝 𝑍𝟘 𝑝 é primo Para qualquer 𝑝 𝑆 o fatoramento em primos é 𝑝 𝑝1 O único expoente presente é 1 que não é estritamente maior que 1 Logo nenhum 𝑝 𝑆 é número potência Para ilustrar têmse por exemplo 2 21 3 31 5 51 7 71 11 111 e todos são nãopotência porque o expoente é 1 Resta justificar que existem infinitos elementos em S Assumese por absurdo que os primos são finitos 𝑝1 𝑝2 𝑝𝑘 Considerase 𝑁 𝑝1 𝑝2 𝑝𝑘 1 Qualquer primo q que divide N não pode coincidir com algum 𝑝𝑖 pois se 𝑝𝑖 𝑁 e 𝑝𝑖 𝑝1 𝑝𝑘 então 𝑝𝑖 𝑁 𝑝1 𝑝𝑘 1 o que é impossível Portanto existe um primo q fora da lista 𝑝1 𝑝𝑘 contrariando a suposição de finitude Concluise que há infinitos primos consequentemente o conjunto S fornece infinitos inteiros positivos distintos e nenhum deles é número potência como se queria ii Desejase construir um conjunto infinito 𝐴 𝑍𝟘 tal que a soma de qualquer subconjunto finito não seja número potência isto é em sua fatoração em primos algum expoente seja igual a 1 Uma maneira suficiente de garantir isso é fazer com que toda soma finita seja livre de quadrados pois se 𝑎𝑖 fosse número potência então seria múltiplo de 𝑝2 para todo primo p que o divide em particular seria múltiplo de algum quadrado 𝑝2 Logo se todas as somas finitas forem livres de quadrados nenhuma delas é número potência Constróise A por indução mantendo a seguinte propriedade todas as somas de subconjuntos não vazios dos elementos já escolhidos são livres de quadrados Suponha escolhidos 𝑥1 𝑥𝑘 com a propriedade acima e denote por 𝒮𝓀 𝑥𝑖 𝑖𝐼 𝐼 1 𝑘 o conjunto finito de todas as somas já possíveis Seja 𝑃𝑘 o conjunto finito de primos que aparecem em alguma fatoração de algum 𝑠 𝒮𝓀 Definese 𝑀𝑘 𝑝2 𝑝𝑃𝑘 Para cada 𝑝 𝑃𝑘 e cada 𝑠 𝒮𝓀 evitase a congruência 𝑥 𝑠𝑚𝑜𝑑𝑝2 pois ela faria 𝑝2 𝑠 𝑥 Como para cada 𝑝2 há apenas um resíduo proibido para cada s e 𝒮𝓀 é finito existe um resíduo 𝑟𝑚𝑜𝑑 𝑀𝑘 que não pertence a nenhum desses resíduos proibidos além disso impõese também 𝑟 0𝑚𝑜𝑑 𝑝2 para todo 𝑝 𝑃𝑘 para que o novo elemento tomado módulo 𝑝2 não seja múltiplo desse quadrado Pelo Teorema de Dirichlet sobre progressões aritméticas existe um primo 𝑞 𝑟𝑚𝑜𝑑𝑀𝑘 e podese escolhêlo suficientemente grande para satisfazer 𝑞 max 𝒮𝓀 Tomase 𝑥𝑘1 𝑞 Verificase a preservação da propriedade 1 Como 𝑥𝑘1 𝑞 é primo ele é livre de quadrados e portanto não é número potência 2 Para qualquer 𝑠 𝒮𝓀 e qualquer 𝑝 𝑃𝑘 temse por construção 𝑞 𝑠𝑚𝑜𝑑 𝑝2 Logo 𝑝2 𝑠 𝑞 Ademais 0 𝑠 𝑞 2𝑞 𝑞2 de modo que 𝑞2 𝑠 𝑞 Portanto nenhuma soma nova 𝑠 𝑞 é múltipla de quadrado isto é todas as somas novas são livres de quadrados 3 As somas antigas em 𝒮𝓀 já eram livres de quadrados por hipótese de indução Concluise que após adicionar 𝑥𝑘1 todas as somas de subconjuntos não vazios dentre 𝑥1 𝑥𝑘 𝑥𝑘1 permanecem livres de quadrados logo nenhuma é número potência Como o procedimento pode ser repetido indefinidamente obtémse um conjunto infinito 𝐴 𝑥1 𝑥2 que satisfaz ii a soma de qualquer subconjunto finito de seus elementos não é um número potência QUESTÃO 1 Seja a1 e m nZ 0 Desejase provar que gcd a m1a n1a gcd m n1 Primeiro estabelecese o seguinte fato fundamental uma versão exponencial do algoritmo de Euclides para inteiros uv0 gcd a u1a v1gcd a uv1a v1 Justificase pela identidade a u1a uv a v1a uv1a va v1 Como qualquer divisor comum de a u1 e a v1 também divide combinações lineares inteiras desses dois números o conjunto de divisores comuns de a u1a v1 coincide com o de a uv1a v1 Logo seus máximos divisores comuns são iguais Aplicase agora o algoritmo de Euclides aos expoentes m e n Supondo sem perda de generalidade m n constróise a sequência de restos r0mr1nr k1r k1 mod rk k 1 que termina em rtgcd mn e rt10 Repetindo a identidade acima a cada passo obtémse gcd a r01a r11gcd a r11a r21gcda r t1a rt 11 Como rt10 temse a rt11a 010 e por definição de máximo divisor comum gcd x 0x para todo xZ 0 Assim gcd a m1a n1gcd a rt10a r t1a gcd m n1 A igualdade requerida está portanto demonstrada A escolha da identidade a u1a uv1 a va v1 é natural porque permite transportar o algoritmo de Euclides dos inteiros uv para o par a u1a v1 preservando o mesmo máximo divisor comum até chegar ao resto nulo quando o resultado se lê diretamente QUESTÃO 2 Sejam m nZ 0 e suponhase que mn m 2n 2 Desejase provar que mn Escrevese dgcd m n e decompõemse md x nd y com gcd x y 1 Substituindo na hipótese de divisibilidade mn m 2n 2d 2 xy d 2x 2 y 2 xy x 2 y 2 Dessa última concluise individualmente que x x 2 y 2e y x 2 y 2 Como x x 2 a primeira implica x y 2 De modo análogo como y y 2 a segunda implica y x 2 Agora usase o fato aritmético se gcd x y 1 e x y 2 então x1 Com efeito todo primo p que divide x dividiria y 2 logo dividiria y contrariando gcd x y 1 Portanto x1 Simetricamente de y x 2 e gcd x y 1 segue y1 Concluise que xy1 Logo md xdend yd o que fornece mn como se queria demonstrar QUESTÃO 3 Considere a sequência cujos termos são 100011000100011000100010001 Cada termo tem a forma T k110 410 810 4 k k1 parcelas i0 k 10 4 i Pela soma de uma progressão geométrica T k 10 4 k11 10 41 k 1 Escrevese b10 4 e c10 2 observase que bc 2 O objetivo é mostrar que T k é sempre composto Caso k ímpar Então k1 é par logo T kb k 11 b1 b k 1 2 1b k 1 2 1 b1 b k 1 2 1 b1 b k1 2 1 O primeiro fator é inteiro porque x r1 x1 1xx r1 e o segundo fator é maior que 1 Assim T k é produto de dois inteiros maiores que 1 portanto não é primo Caso k par Então k1 é ímpar Usando bc 2 T kc 2 k1 1 c 21 c k11 c k11 c1c1 c k 11 c1 c k 11 c1 Ambos os quocientes são inteiros c k 11 é múltiplo de c1 para todo k e c k 11 é múltiplo de c1 quando k1 é ímpar Além disso cada fator é maior que 1 Logo T k é composto também neste caso Concluise que para todo k 1 T k 10 4 k11 10 41 é composto Portanto nenhum termo da sequência é primo QUESTÃO 4 i Chamase número potência aquele cujo fatoramento em primos tem todos os expoentes estritamente maiores que 1 Desejase construir infinitos inteiros positivos distintos que não sejam números potência Considerase o conjunto SpZ 0 p é primo Para qualquer pS o fatoramento em primos é pp 1 O único expoente presente é 1 que não é estritamente maior que 1 Logo nenhum pS é número potência Para ilustrar têmse por exemplo 22 133 155 177 11111 1 e todos são nãopotência porque o expoente é 1 Resta justificar que existem infinitos elementos em S Assumese por absurdo que os primos são finitos p1 p2 pk Considerase Np1 p2 pk1 Qualquer primo q que divide N não pode coincidir com algum pi pois se piN e pi p1 pk então piNp1 pk1 o que é impossível Portanto existe um primo q fora da lista p1 pk contrariando a suposição de finitude Concluise que há infinitos primos consequentemente o conjunto S fornece infinitos inteiros positivos distintos e nenhum deles é número potência como se queria ii Desejase construir um conjunto infinito A Z 0 tal que a soma de qualquer subconjunto finito não seja número potência isto é em sua fatoração em primos algum expoente seja igual a 1 Uma maneira suficiente de garantir isso é fazer com que toda soma finita seja livre de quadrados pois se ai fosse número potência então seria múltiplo de p 2 para todo primo p que o divide em particular seria múltiplo de algum quadrado p 2 Logo se todas as somas finitas forem livres de quadrados nenhuma delas é número potência Constróise A por indução mantendo a seguinte propriedade todas as somas de subconjuntos não vazios dos elementos já escolhidos são livres de quadrados Suponha escolhidos x1 xk com a propriedade acima e denote por Sk i I xiI 1 k o conjunto finito de todas as somas já possíveis Seja Pk o conjunto finito de primos que aparecem em alguma fatoração de algum sSk Definese M k p Pk p 2 Para cada pPk e cada sSk evitase a congruência xsmod p 2 pois ela faria p 2sx Como para cada p 2 há apenas um resíduo proibido para cada s e Sk é finito existe um resíduo r mod M k que não pertence a nenhum desses resíduos proibidos além disso impõese também r 0mod p 2 para todo pPk para que o novo elemento tomado módulo p 2 não seja múltiplo desse quadrado Pelo Teorema de Dirichlet sobre progressões aritméticas existe um primo qr mod M k e podese escolhêlo suficientemente grande para satisfazer qmax Sk Tomase xk1q Verificase a preservação da propriedade 1 Como xk1q é primo ele é livre de quadrados e portanto não é número potência 2 Para qualquer sSk e qualquer pPk temse por construção qsmod p 2 Logo p 2sq Ademais 0sq2qq 2 de modo que q 2sq Portanto nenhuma soma nova sq é múltipla de quadrado isto é todas as somas novas são livres de quadrados 3 As somas antigas em Sk já eram livres de quadrados por hipótese de indução Concluise que após adicionar xk1 todas as somas de subconjuntos não vazios dentre x1 xk xk 1 permanecem livres de quadrados logo nenhuma é número potência Como o procedimento pode ser repetido indefinidamente obtémse um conjunto infinito Ax1 x2 que satisfaz ii a soma de qualquer subconjunto finito de seus elementos não é um número potência