Divisibilidade e Números Primos

A divisibilidade, o máximo divisor comum e os números primos formam a base da teoria dos números: cada número inteiro é construído multiplicativamente a partir de primos, e a forma como é construído governa quase todos os resultados posteriores.

Definition

Um número inteiro 'a' divide 'b' se 'b' for igual a 'a' vezes algum número inteiro; um número primo é um número inteiro maior que um cujos únicos divisores positivos são um e ele mesmo. Divisibilidade e números primos referem-se à decomposição multiplicativa de números inteiros e aos blocos de construção irredutíveis dessa decomposição.

Scope

Este tópico aborda a relação de divisibilidade nos números inteiros, o algoritmo da divisão, máximos divisores comuns e mínimos múltiplos comuns calculados através do algoritmo euclidiano, a identidade de Bezout, o lema de Euclides, o teorema fundamental da aritmética e a teoria elementar dos primos — sua infinitude, heurísticas de distribuição e primalidade.

Core questions

• Como o algoritmo euclidiano calcula os máximos divisores comuns e produz a identidade de Bezout?
• Por que o lema de Euclides força a fatoração em primos a ser única?
• Como se pode provar que existem infinitos números primos, e o que tais provas revelam?
• Como os primos são distribuídos entre os números inteiros, e como a primalidade é decidida na prática?

Key theories

Algoritmo da divisão e o algoritmo euclidiano

Qualquer número inteiro dividido por um número inteiro positivo deixa um quociente e um resto únicos; a iteração disso fornece o máximo divisor comum e, por substituição retroativa, inteiros que o expressam como uma combinação linear (identidade de Bezout).

Teorema fundamental da aritmética

Todo número inteiro acima de um é um produto de primos que é único até a ordem; o lema de Euclides (um primo que divide um produto divide um fator) é o passo chave.

Infinitude dos primos

O argumento clássico de Euclides mostra que nenhuma lista finita de primos é completa; a fórmula do produto de Euler para a função zeta fornece uma prova analítica e quantifica a densidade dos primos através da divergência da soma dos recíprocos dos primos.

Clinical relevance

A fatoração rápida e os testes de primalidade são fundamentais para a criptografia: a segurança RSA baseia-se na dificuldade de fatorar grandes produtos de dois primos, enquanto testes de primalidade eficientes (como Miller-Rabin) tornam a geração de chaves prática.

History

Os Elementos de Euclides (c. 300 a.C.) já continham o algoritmo euclidiano, o lema de Euclides e a prova de que os primos são infinitos. O crivo de Eratóstenes forneceu o primeiro método sistemático para listar primos, e o trabalho de Euler, Legendre e Gauss nos séculos XVIII e XIX reformulou a distribuição de primos como um problema quantitativo.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

Um é um número primo?

Não. Um é excluído por definição para que a fatoração prima seja única; se um fosse considerado primo, cada número teria infinitas fatorações.

Para que serve a identidade de Bezout?

Ela afirma que o máximo divisor comum de dois números inteiros é uma combinação linear inteira deles, o que é a base para calcular inversos modulares e resolver equações diofantinas lineares.