Congruências e Aritmética Modular

A aritmética modular estuda os números inteiros até a divisibilidade por um módulo fixo, transformando os inteiros no anel finito Z/nZ e fornecendo à teoria dos números sua ferramenta computacional mais flexível.

Definition

Dois inteiros são congruentes módulo n se sua diferença for divisível por n. A aritmética modular é a aritmética das classes de resíduos resultantes, que formam o anel comutativo Z/nZ.

Scope

Este tópico abrange a relação de congruência e classes de resíduos, aritmética em Z/nZ, congruências lineares e polinomiais, o teorema chinês do resto, o pequeno teorema de Fermat e o teorema de Euler, a estrutura do grupo de unidades, raízes primitivas e a ordem dos elementos. É a linguagem na qual a maior parte da teoria dos números elementar e computacional é expressa.

Core questions

• Quando uma congruência linear ax congruente a b mod n tem soluções e quantas?
• Como o teorema chinês do resto decompõe Z/nZ em um produto sobre módulos de potência prima?
• Por que o pequeno teorema de Fermat e o teorema de Euler são válidos e o que eles dizem sobre a ordem das unidades?
• Para quais módulos existe uma raiz primitiva, tornando o grupo de unidades cíclico?

Key theories

Teorema chinês do resto

Se os módulos são coprimos dois a dois, um sistema de congruências simultâneas tem uma solução única módulo o produto; equivalentemente, Z/nZ é isomorfo ao produto de Z sobre seus fatores de potência prima.

Pequeno teorema de Fermat e teorema de Euler

Para a coprimo com n, a elevado ao totiente de n é congruente a um módulo n; o caso primo (Fermat) fundamenta os testes de primalidade e o caso geral fundamenta o RSA.

Raízes primitivas e estrutura de grupo

O grupo multiplicativo de unidades mod n é cíclico exatamente quando n é um, dois, quatro, uma potência de primo ímpar ou o dobro de um; um gerador é uma raiz primitiva, fornecendo um logaritmo discreto.

Clinical relevance

A aritmética modular é o motor computacional da criptografia (RSA, Diffie-Hellman, esquemas de curva elíptica), somas de verificação e detecção de erros (ISBN, funções hash) e geração de números pseudoaleatórios, tornando-a a parte mais amplamente utilizada da teoria dos números.

History

Embora casos especiais apareçam na matemática chinesa e indiana antiga (o problema do resto nomeado para o primeiro), a teoria sistemática das congruências foi introduzida por Gauss nas Disquisitiones Arithmeticae (1801), onde ele estabeleceu a notação e provou os resultados estruturais centrais.

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

O que significa a notação a congruente a b mod n?

Significa que n divide a diferença a menos b, equivalentemente a e b deixam o mesmo resto na divisão por n.

Por que o RSA depende do teorema de Euler?

A criptografia e descriptografia RSA são exponenciações modulares cuja composição retorna a mensagem original precisamente porque o teorema de Euler garante que o expoente relevante atua como a identidade módulo a chave.