Baixe o app para aproveitar ainda mais
Prévia do material em texto
Francisco Cordeiro Fabula Joana Augusto Victor Jorge Pilal Rodrigues Musselo Baptista Números Primos (Licenciatura em Ensino de Matemática) Universidade Rovuma Nampula 2021 2 Francisco Cordeiro Fabula Joana Augusto Victor Jorge Pilal Rodrigues Musselo Baptista Números Primos Universidade Rovuma Nampula 2021 Trabalho de carácter avaliativo orientado no Departamento de Ciências Naturais e Matemática, 2º ano de Matemática, 2º semestre, cadeira de Teoria de Numros, lecionada pelo docente: Victor Manuel Estaúpe Machado 3 Índice Introdução ................................................................................................................................... 4 1. Breve histórico sobre números primos ................................................................................ 6 1.1 Causas .............................................................................................................................. 7 2. Caracterização de números primos ..................................................................................... 8 Definiçoes Preliminares .............................................................................................................. 8 Teorema de teste de primalidade ................................................................................................ 8 Teorema fundamental da aritmética ........................................................................................... 8 Terorema de Wilson ................................................................................................................... 9 a) As fórmulas de estimação sobre os tipos de números primos especiais; ............................ 9 Primos ......................................................................................................................................... 9 Primos fatoriais ........................................................................................................................... 9 Primos de Mersenne ................................................................................................................... 9 Primos de Fermat ...................................................................................................................... 10 Primos de Wilson ..................................................................................................................... 10 Primos de Germain ................................................................................................................... 10 b) Funções que fornecem quantidades de números primos ................................................... 10 Função 𝜋 dos números primos ................................................................................................ 10 Primos de Fibonacci ................................................................................................................. 11 3. Aplicações de números primos ......................................................................................... 11 3.1 Na construção de ternos pitagóricos .............................................................................. 11 3.2 Criptografia .................................................................................................................... 11 4. Análise da abordagem dos conjuntos numéricos na Matemática escolar ......................... 12 Conclusão ................................................................................................................................. 14 Bibliografia ............................................................................................................................... 15 4 Introdução O presente trabalho aborda sobre Números primos. Os números primos são uma das mais fascinantes partes da matemática. Eles vêm intrigando os matemáticos desde a época dos antigos filósofos gregos, a mais de dois milênios atrás. A área da Matemática que estuda os números inteiros e suas propriedades é chamada Teoria dos Números. Atualmente, os números primos ocupam um papel reduzido nos primeiros capítulos dos livros de Teoria dos Números e Álgebra Moderna. Isto chega a ser uma injustiça, pelo papel fundamental que os números primos exercem hoje, em áreas aplicadas como a criptografia. Este trabalho tem o propósito de apresentar os números primos não como uma introdução às Estruturas Algébricas, mas como uma disciplina independente, capaz de despertar o interesse por suas aplicações. 5 Objetivos: Geral: Este trabalho tem como objetivo geral organizar de modo sistemático os mais destacados avanços dentro da Teoria dos Números, no que se refere aos números primos. Além disso, este trabalho possui os seguintes objetivos específicos: Elaborar uma retrospectiva histórica dos números primos; Citar teoremas, demonstrações e exemplos sobre os mesmos; Apresentar os recentes avanços na área da criptografia, auxiliada pela teoria dos números primos. Metodologia O trabalho será feito consoante pesquisa bibliográfica, internet e revistas, e depois sera compilado como resultados de discussão. 6 1. Breve histórico sobre números primos Os romanos apenas traduziram literalmente a palavra grega para primeiro que em latim é primus. Daí vem os nossos números primos. Primeiros números primos, bem como suas propriedades, foram pela primeira vez estudados intensamente pelos antigos matemáticos gregos. No papiro de Rhindi, por exemplo, há indícios de que o antigo povo egípcio tinha algum conhecimento sobre os números primos. No entanto, o registro mais antigo de um estudo explicito sobre números primos é devido aos gregos. Pitágoras de Samos foi um dos percursores desse estudo, embora seu interesse mais direcionado para o místico, chegando a criar a escola Pitagórica (500 a 300 a.c). Os grandes seguidores da época entendiam a ideia de primalidade, revelavam interesses em números perfeitos e amigáveis. A escola dava grande importância ao número “1”, que era chamado de unidade. Os outros números tinham importância reduzida, pois todos eles representavam apenas multiplicidades da unidade e por isso eram chamados de números. A partir dessas denominações, os pitagóricos começaram perceber que existiam dois tipos de números: Números primos: são números que não podem ser gerados pela multiplicação, a partir de outros números, como 2, 3, 5, 7, 11, e etc. Números compostos ou secundários: são números que podem ser gerados a partir de outros números, como o 6=2.3; 9=3.3 No livro “Os elementos”, Euclides prova que existem infinitos números primos. Esta é uma das demonstrações conhecidas a usar o método da contradição, com a obtenção de um resultado. Os elementos de Euclides (cerca de 300 a.C), contém teoremas importantíssimos sobre os números primos, incluindo a demonstração de sua infinitude e o teorema fundamental da aritmética. Euclides também mostrou como construir um número perfeito a partir de um primo de Mersenne. Ao grego Erastóstenes (nasceu em Cirene, na Grécia, por volta de 276 anos, no século III a.c), atribuiu-se um método simples para cálculo de números primos, conhecido actualmente como crivo de Erastóstenes. Por outro lado, nos tempos actuais, os grandes números primos são encontrados por computadores, através de testes de primalidade mais complexos, como por exemplo o teste de primalidade AKS. Pierre de Fermat (nasceu na França em Beaumont-de-Lomages em Agosto de 1601) no início do século XVII, provocando a conjectura e Albert Girard, cria alguns teoremas que mais tarde seriam usados como base de muitos resultados em Teoria de Números e de métodos para testes 7 deprimalidade que são utilizados até hoje. Fermat correspondeu-se com outros matemáticos do seu tempo, como Marin Mersenne, que junto com Fermat, formularam os números de Mersenne (número da forma 2𝑛 − 1). Em uma carta enviada a Mersenne (Padre, matemático, filosofo natural e teólogo francês, nascido de família camponesa) Fermat afirma ter descoberto uma formula para achar os números primos para todo n natural, 22 𝑛 + 1 que ficou conhecida como Pequeno teorema de Fermat. Embora não tivesse conseguido provar esse resultado, a formula funcionava para 𝑛 = 0, 1, 2, 3 𝑒 4. Os números dessa forma 22 𝑛 + 1 ficaram conhecidos como números de Fermat. Alguns anos depois o matemático Leonhard Euler (1707-1783) mostrou que para 𝑛 = 5 𝑜 𝑛𝑢𝑚𝑒𝑟𝑜 22 5 + 1 era divisível por 641, ou seja, que esse número não era primo. Euler demonstrou uma afirmação mais geral, que ficou conhecida como função 𝜑 de Euler. Função 𝜑(𝑛) de Euler definida como número de naturais menores que n que primos com n. Marin Mersenne dedicou-se ao estudo sobre números primos, os números da forma 2𝑛 − 1 ficaram conhecidos como números de Mersenne, que estão inteiramente ligados aos números perfeitos da forma 2𝑛−1(2𝑛 − 1). Karl Friedrich Gauss (1.777 – 1.855) foi o primeiro matemático a fazer alguns avanços neste sentido: ele estimou 𝑃(𝑥) ≅ ∫ 1 ln 𝑡 𝑑𝑡 𝑥 2 1.1 Causas 1.1.1 Místicas: Os matemáticos da escola de Pitágoras (500 a 300 A.C.) estavam interessados nos números pelas suas propriedades numerológicas e místicas (acreditavam na transmissao das almas e, portanto, que não se devia matar ou comer animal porque ele podia ser a moradia de um amigo morto). 1.1.2 Naturais: algumas propriedades de números que vem desafiando a humanidade há mais de dois milênios sendo chamados por alguns autores “átomos da aritmética”. 1.1.3 Cientificas: medição do meridiano terrestre e a circunferência da terra. 8 2. Caracterização de números primos Um número primo caracteriza-se por possuir apenas dois divisores (1 e ele próprio). Definiçoes Preliminares Definicao 1: Sejam 𝑎, 𝑏, 𝑐 ∈ 𝑍. Dizemos que 𝑎 é um divisor de 𝑐 se existe 𝑏 tal que 𝑎𝑏 = 𝑐. Notacao: a|c (le-se a divide c). Definicao 2: Um numero natural 𝑝 ≠ 1 é chamdo número primo se os seus unicos divisores não negativos são 1 e 𝑝. Teorema de teste de primalidade Se o inteiro 𝑎 < 𝑛2 não for divisível por qualquer inteiro 𝑞 < 𝑛 ,então 𝑎 é primo. Demonstração (por absurdo) Vamos supor que 𝑎 não é primo. Então 𝑎 admite um divisor efectivo, seja ele 𝑝 Assim teremos 𝑎 = 𝑝. 𝑞 Como, por hipótese ,𝑎 não admite nenhum divisor menor que 𝑛,então teremos 𝑝 ≥ 𝑛 e 𝑞 ≥ 𝑛 onde 𝑝. 𝑞 ≥ 𝑛2e consequentemente 𝑎 ≥ 𝑛2, o que contradiz a hipótese. C.q.d Teorema fundamental da aritmética HEFEZ (2006), diz que ʽʽqualquer inteiro 𝑎, diferente de 1,admite pelo menos um divisor primo”. Demonstração: Lembre-se que qualquer inteiro ou é primo ou é composto. por isso conduziremos a demonstração observando este dois casos. 1°Caso : se 𝑎 é primo, o teorema esta demonstrado, visto que qualquer número (diferente de zero) é divisor de si próprio ; 2°Caso: Se 𝑎 é composto, então admite pelo menos um divisor efectivo e se admite mais que um, então indiquemos o menor por 𝑝. 𝑝 é necessariamente primo, pois, pelo contrário 𝑝 admitiria por sua vez um divisor efectivo 𝑝1 < 𝑝, que seria também um divisor de 𝑎, o que contraria a hipótese de ser 𝑝 o menor divisor efectivo de 𝑎. C.q.d 9 Terorema de Wilson Se p é um numero primo entao (𝑝 − 1)! ≡ −1(𝑚𝑜𝑑 𝑝) Demonstracao. Como (2 − 1)! ≡ 1(𝑚𝑜𝑑 2) ≡ −1(𝑚𝑜𝑑 2), logo o resultado é valido para 𝑝 = 2. Sabemos que 𝑎𝑥 ≡ 1(𝑚𝑜𝑑 𝑝) possui uma única solucao para todo a no conjunto {1, 2, 3, … , (𝑝 − 2), (𝑝 − 1)} somente 1 e 𝑝 − 1 são seus próprios inversos modulo p, podemos agrupar os números 2, 3, 4, … , (𝑝 − 2) em (𝑝 − 3) 2 ⁄ pares cujo produto seja congruente a 1 modulo p. se multiplicarmos essas congruências, membro a membro, teremos 2 ∙ 3 ∙ 4 ∙ 5 ∙ … ∙ (𝑝 − 2) ≡ 1(𝑚𝑜𝑑 𝑝), multiplicando ambos os lados por 𝑝 − 1 teremos 2 ∙ 3 ∙ 4 ∙ 5 ∙ … ∙ (𝑝 − 2)(𝑝 − 1) ≡ (𝑝 − 1)1(𝑚𝑜𝑑 𝑝) isto é (𝑝 − 1)! ≡ −1(𝑚𝑜𝑑 𝑝) uma vez que 𝑝 − 1 ≡ −1(𝑚𝑜𝑑 𝑝). Exemplo. Número 31 é primo. 1 ∙ 2 ∙ 3 ∙ … ∙ 29 ∙ 30 ≡ 30(𝑚𝑜𝑑 31), 30! ≡ 30(𝑚𝑜𝑑 31), 30! ≡ −1(𝑚𝑜𝑑 31), (31 − 1)! ≡ −1(𝑚𝑜𝑑 31) a) As fórmulas de estimação sobre os tipos de números primos especiais; Primos Gêmeos Definição. Seja p e q números primos, consideremos 𝑝 < 𝑞, serão chamados de gêmeos se a diferença entre eles for sempre modulo 2, ou seja, 𝑃 = 𝑞 + 2. Exemplo. Pares de primos gêmeos: 3 𝑒 5, 5 𝑒 7, 11 𝑒 13, 17 𝑒 19, 29 𝑒 31, 41 𝑒 43, 59 𝑒 61, 71 𝑒 73, 101 𝑒 102, 107 𝑒 109. Primos fatoriais Definição. Um número p é chamado de fatorial se está na forma: 𝑝 = 𝑛! ± 1 para algum n, onde pode ser representado pela forma: 𝑛! = 1 ∙ 2 ∙ 3 ∙ … ∙ 𝑛 = ∏ 𝑘𝑛𝑘=1 , para todo inteiro 𝑛 ≥ 0. Os primeiros primos fatoriais são: n 1 2 3 3 4 5 6 7 11 12 p 2 3 5 7 23 719 5039 39911681 479001599 87178291199 Primos de Mersenne Definição. Um número da forma 𝑀(𝑛) = 2𝑛 − 1, com 𝑛 = 2, 3, 5, 7, … é chamado de Mersenne. Assim a sequência de números de Mersenne são: 10 𝑀(𝑛) ≥ 2 = (3, 7, 31, 63, 127, 255, 511, 1023, … , 2𝑛 − 1, … ) Primos de Fermat Definição. Um número inteiro positivo que assume a forma 22 𝑛 + 1 sendo n um inteiro não negativo. Os primeiros números primos de Fermat são: 𝐹0 = 3, 𝐹1 = 5, 𝐹2 = 7, 𝐹3 = 257, 𝐹4 = 65537 Primos de Wilson Definição. Dado p designa-se número primo de Wilson, então (𝑝 − 1)! ≡ (𝑚𝑜𝑑 𝑝). Logo, o quociente de Wilson: 𝑊(𝑝) = (𝑝 − 1)! + 1 𝑝 É um inteiro. O número p é chamado de primo de Wilson se 𝑊(𝑝) ≡ 0(𝑚𝑜𝑑 𝑝), são exemplos de primos de Wilson 5 e 13. Primos de Germain Definição. P é um primo de Germain se 2𝑝 + 1 é primo. Os primeiros números primos de Germain são: 2, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, … b) Funções que fornecem quantidades de números primos Função 𝝅 dos números primos Definição. Seja x um número real, definimos 𝜋(𝑥) como sendo a quantidade de números primos 𝑝 tais que 0 < 𝑝 ≤ 𝑥. Exemplo. 𝜋(0) = 𝜋(1) = 0 , 𝜋(2) = 1, 𝜋(3) = 𝜋(4) = 2. De forma geral, se organizarmos os primos de forma crescente, 𝑝1 = 2, 𝑝2 = 3, 𝑝3 = 7, …, teremos que 𝜋(𝑥) = 𝑛 𝑠𝑒 𝑝𝑛 ≤ 𝑥 < 𝑝𝑛+1. Um dos matemáticos famosos a se dedicar ao estudo de 𝜋(𝑥)foi matemático suíço Leonhard Euler que demonstrou os primos são menos frequentes que os quadrados de números inteiros. 11 Primos de Fibonacci Definição. Números de Fibonacci obedecem a seguinte função recorrente 𝐹(𝑛) = { 0, 𝑠𝑒 𝑛 = 0 1, 𝑠𝑒 𝑛 = 1 𝐹(𝑛 − 1) + 𝐹(𝑛 − 2), 𝑠𝑒 𝑛 > 1 Os números primos de Fibonacci são: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437. c) No século XVIII em 1.742, Goldbach (1.690 – 1.764) escreveu uma carta para Euler sugerindo que todo número par maior que dois é a soma de dois números primos. Exemplo. 6=3+3, 8=3+5, 10=3+7=5+5, 12=5+7, 14=3+11=7+7, 16=3+13=5+11, 18=5+13=7+11. 3. Aplicações de números primos 3.1 Na construção de ternos pitagóricos No século VI a.C., Pitágoras de Samos - matemático e lósofo - foi uma das figuras mais inuentes e misteriosas da Matemática. Uma de suas principais contribuições foi o desenvolvimento da lógica numérica. Segundo SINGH (2002, p.28), graças a Pitágoras, "os números deixaram de ser apenas coisas usadas meramente para contar e calcular e passaram a ser apreciados por suas próprias características.". Ele estudou aspropriedades de diversos números, buscando relacioná-los e encontrar padrões. O Teorema de Pitágoras, enunciado a seguir, é um dos seus resultados mais conhecidos: Em um triângulo retângulo qualquer, o quadrado da hipotenusa é igual à soma dos quadrados dos catetos. Ou seja, tomando um triângulo retângulo com hipotenusa de medida z e catetos medindo x e y, teríamos a igualdade: 𝑥2 + 𝑦2 = 𝑧2 Os números que pertencem a um trio pitagórico também são considerados especiais. Dados três inteiros a, b e c que satisfazem o Teorema de Pitágoras, dizemos que tais números formam um trio pitagórico. Alguns exemplos de conjuntos que formam um trio pitagórico são: {3, 4, 5}, {6, 8, 10}, {5, 12, 13} e {9, 12, 15}. 3.2 Criptografia Os numeros primos ganham relevancia em 1978, quando Ronald Rivest, Adi Shamir e Leonard Adleman, do laboratorio de ciencias de informacao do Massachusetts Institite of Tecnology (MIT), tiveram a ideia de implementar o sistema criptografico com chaves assimetricas, 12 idealizado por Driffie. O principio baseia-se na relativa facilidade de encontrar numeros primos grandes e ao mesmo tempo na dificuldade pratica em fatorar o produto dois desses numeros. O sistema criptografico (RSA) funciona da seguinte forma: Uma pessoa escolhe dois numeros primos p e q muito grandes e efectua o seu produto 𝑚 = 𝑝 ∙ 𝑞 em seguida essa pessoa escolhe um par de elementos a e b tais que: 𝑎 ∙ 𝑏 ≡ 1(𝑚𝑜𝑑 𝜑(𝑚)) Note que obrigatoriamente (𝑎, 𝜑(𝑚)) = (𝑏, 𝜑(𝑚)) = 1. A primeira pessoa pode escolher inicialmente a tal que (𝑎, 𝜑(𝑚)) = 1 e em seguida resolver a congruencia 𝑎𝑋 ≡ 1(𝑚𝑜𝑑 𝜑(𝑚)). A peimeira pessoa torna publicos os numeros a e b, que são a chave publica. A chave secreta dela serao os primos p e q, os numeros 𝜑(𝑚) = (𝑝 − 2)(𝑝 − 1) e a. Dado um numero 𝑥 < 𝑚, a codificacao feita pela segunda pessoa que conheca a chave publica da primeira pode cifrar x segue: a segunda pessoa acha o único 𝐶(𝑥) < 𝑚 tal que: 𝑥𝑏 = 𝐶(𝑥)(𝑚𝑜𝑑 𝑚) a segunda pessoa envia 𝐶(𝑥) para a primeira, a segunda ao receber 𝐶(𝑥), usa a sua chave privada a para achar o numero 𝐷(𝐶(𝑥)) < 𝑚 tal que: 𝐶(𝑥)𝑎 ≡ 𝐷(𝐶(𝑥))(𝑚𝑜𝑑 𝑚) Note que somente a primeira pessoa consegue determinar 𝐷(𝐶(𝑥)), pois so ele detem a chave a. Mas, 𝐷(𝐶(𝑥)) = 𝑥 pois existe 𝑘 ∈ 𝑁 tal que: 𝑎 ∙ 𝑏 = 1 + 𝑘𝜑(𝑚) e 𝐷(𝐶(𝑥)) = 𝐶(𝑥)𝑎 = (𝑥𝑏)𝑎 = 𝑥𝑎∙𝑏 = 𝑥1+𝑘𝜑(𝑚) ≡ 𝑥(𝑚𝑜𝑑 𝑚) 4. Análise da abordagem dos conjuntos numéricos na Matemática escolar a) Classes e Conteúdos : os conjuntos numéricos estudam-se na 8ª e 10ª classes. Na 8ª classe: teoria de conjuntos: Números naturais, números inteiros, números racionais e irracionais e números reais. Em classes anteriores deve ter estudado os números naturais. Vamos, porém, revê-los para podermos depois compreender melhor os números inteiros e os números racionais. Desde os tempos mais remotos que a actividade de contar se tornou fundamental no desenvolvimento da Humanidade. Os números naturais surgiram, assim, como uma necessidade humana de contar e ordenar objectos 13 Na 10ª classe: Relações entre conjuntos • Subconjunto. Relação de inclusão (contém e está contido) • Igualdade de conjuntos • Conjunto universal; • Operações com conjuntos; • Reunião de conjuntos; • Intersecção de conjuntos; • Diferença de conjuntos; • Complementar de conjunto; • Propriedades das operações de conjuntos; • Resolução de problemas concretos da vida real. No ensino fundamental os números primos são estudados dentro de conjunto de números naturais. Recomendações Este trabalho não pretende esgotar os assuntos abordados, tornando sua abordagem superficial. Além disso, não é possível cobrir todos os campos envolvendo números primos, pois senão o trabalho se estenderia muito além de seus objetivos. Como mencionado anteriormente, os números primos já são conhecidos e estudados a mais de 2.000 anos. Mas isto não significa que este seja um assunto velho: novos números primos e algoritmos para achá-los foram descobertos recentemente, principalmente nos últimos 50 anos, com o advento dos computadores. E ainda existem muitas questões em aberto. Este trabalho pretende fornecer uma visão geral do que foi conquistado no passado sobre o assunto e quais são as próximas metas. 14 Conclusão Feito o trabalho, concluiu-se que Gauss afirma que os problemas envolvendo números primos foram amplamente estudados e que seria inútil discuti-los detalhadamente. E Gauss está correto. Neste trabalho, que pretendia apresentar os números primos sob diferentes enfoques, foi necessário deixar muitos assuntos de fora. Como exemplo, podem ser citados: as demonstrações que existem infinitos números primos de Wilson de Euler, de Fibonacci e de Lucas, espaçamento entre primos consecutivos, primos em progressão aritmética, primos regulares, de Sophie Germain, o teste de Miller, além de resultados probabilísticos sobre números primos. Mas o próprio Gauss, na mesma citação, afirma também que a própria dignidade da ciência exige que estes e outros problemas sejam estudados. Embora de forma superficial, muito dos principais e mais interessantes resultados foram aqui expostos. Longe de esgotar o assunto, este trabalho se propõe apenas a criar o interesse pelos números primos. Espera-se ter tido sucesso neste sentido. 15 Bibliografia Domingues; H.,Iezzi, G. Álgebra Moderna. São Paulo: Atual, 1982. CALADO J.J.G. Aritmética racional. Braga, Livraria Cruz, 1967. [2] .JR. Frank Ayres. Álgebra Moderna. Colecção Schaum, Brasil, McGraw-Hill,1979. [3]. VIEIRA, Mª Teresa e outros. Matemática 12º2º Vol. Porto, Porto Editora, 1995. [4]. NEVES, Mª Augusta e outros. Matemática 12º Ano-Livro de Texto- 2º Vol.Porto, Porto Editora, 1997.
Compartilhar