Aritmética Modular - Teoria dos Números (Resumo)

Prévia do material em texto

UNIVERSIDADE FEDERAL DO MARANHÃO 
DEPARTAMENTO DE MATEMÁTICA 
ALUNO: SAMUEL CANTOARIA FERREIRA 
 
 
ARITIMÉTICA MODULAR – CAPÍTULO 3 
 
1. Definição e propriedades 
Sejam 𝑎 e 𝑏 inteiros, dizemos que 𝑎 é congruente a 𝑏 módulo 𝑛, se 𝑎 − 𝑏 é um múltiplo de 
𝑛. Em símbolos 
𝑎 ≡ 𝑏 (mod 𝑛) 
Exemplos: 
3 ≡ 8 (mod 5) 
12 ≡ 3 (mod 4) 
A congruência modular tem algumas propriedades básicas como: 
a) Reflexiva: 𝑎 ≡ 𝑎 (mod 𝑛) 
b) Simétrica: Se 𝑎 ≡ 𝑏 (mod 𝑛) então 𝑏 ≡ 𝑎 (mod 𝑛) 
c) Transitiva: Se 𝑎 ≡ 𝑏 (mod 𝑛) e 𝑏 ≡ 𝑐 (mod 𝑛) então 𝑎 ≡ 𝑐 (mod 𝑛) 
Mostremos a validade das propriedades. 
(a) 𝑎 ≡ 𝑎 (mod 𝑛) ⟹ 𝑎 − 𝑎 = 0 é divisível por 𝑛, e de fato 0 é divisível por todos os números. 
(b) 𝑎 ≡ 𝑏 (mod 𝑛) implica 𝑎 − 𝑏 = 𝑛𝑘 para algum 𝑘 inteiro, basta multiplicar (−1) a ambos os 
lados que obtemos 𝑏 − 𝑎 = (−𝑘)𝑛 o que implica 𝑏 ≡ 𝑎 (mod 𝑛) 
(c) 𝑎 ≡ 𝑏 (mod 𝑛) ⟹ 𝑎 − 𝑏 = 𝑘𝑛 e 𝑏 ≡ 𝑐 (mod 𝑛) ⟹ 𝑐 − 𝑏 = 𝑞𝑛 somando as duas igualdes 
temos: 
(𝑎 − 𝑏) − (𝑐 − 𝑏) = 𝑘𝑛 − 𝑞𝑛 
𝑎 − 𝑐 = (𝑘 − 𝑞)𝑛 ⟹ 𝑎 ≡ 𝑐 (mod 𝑛) 
 
2. Resíduos 
Digamos que 𝑎 é um inteiro positivo. Dividindo 𝑎 por 𝑛 temos 
𝑎 = 𝑛. 𝑞 + 𝑟 e 0 ≤ 𝑟 < 𝑛 
Assim, 
𝑎 − 𝑟 = 𝑛. 𝑞 
o que equivale a dizer que 
𝑎 ≡ 𝑟 (mod 𝑛) 
Em geral, se 𝑎 ≡ 𝑟 (mod 𝑛) e 0 ≤ 𝑟 < 𝑛 dizemos que 𝑟 é o resido de 𝑎. Vamos agora mostrar 
que o resido de 𝑎 é único. Suponha que exista dos resíduos de 𝑎, 𝑟 e 𝑟′então 
𝑎 ≡ 𝑟 (mod 𝑛) 
𝑎 ≡ 𝑟′ (mod 𝑛) 
Pelas propriedades reflexiva e transitiva temos que 𝑟 ≡ 𝑟′ (mod 𝑛). Digamos que 𝑟 > 𝑟′, por 
tanto 𝑟 como 𝑟’ serem menores que 𝑛, vamos ter que 0 ≤ 𝑟 − 𝑟′ < 𝑛. Isso significa que 𝑟 − 𝑟′ 
só é múltiplo de 𝑛 se o cofator for zero; o que nos mostra que 𝑟 = 𝑟′. 
Note que acima encontramos o resíduo de 𝑎 positivo, caso 𝑎 for negativo qual é o resíduo de 𝑎? 
Supondo 𝑎 negativo, −𝑎 é positivo, então 
−𝑎 = 𝑛. 𝑞 + 𝑟 𝑒 0 ≤ 𝑟 < 𝑛; 
Multiplicando (−1), a ambos os lados, obtemos: 
𝑎 = 𝑛. (−𝑞) − 𝑟 𝑒 0 ≤ 𝑟 < 𝑛; 
ou seja, 
𝑎 ≡ −𝑟 (mod 𝑛) 
Se 𝑟 = 0, então 𝑎 ≡ 0 (mod 𝑛) e já achamos o resíduo. Caso 𝑟 ≠ 0, então (𝑛 − 𝑟) − (−𝑟) = 𝑛 
o que implica 
−𝑟 ≡ 𝑛 − 𝑟 (mod 𝑛) 
Então pela transitividade encontramos 
𝑎 ≡ 𝑛 − 𝑟 (mod 𝑛) 
Observe que −𝑟 não poderia ser resíduo, pois não está entre 0 e 𝑛, por isso consideramos 𝑛 −
𝑟, pois esse sim cumpre nossas exigências para o “cargo” de resíduo. 
A partir dos resultados acima, podemos enunciar a seguinte proposição: 
 
Proposição 1. Sejam 𝑎 e 𝑛 > 1 números inteiros e 𝑟 o resto da divisão de |𝑎| por 𝑛, então o 
resíduo de 𝑎 módulo 𝑛 é: 
• 0 𝑠𝑒 𝑟 = 0; 
• 𝑟 𝑠𝑒 𝑟 ≠ 0 𝑒 𝑎 ≥ 0; 
• 𝑛 − 𝑟 𝑠𝑒 𝑟 ≠ 0 𝑒 𝑎 < 0. 
Vejamos um exemplo interessante. Quais são os resíduos possíveis módulo 6 que um primo 
𝑝 > 3 pode ter? 
Para começar os únicos resíduos possíveis módulo 6, são 0, 1, 2, 3, 4 ou 5. Como 𝑝 é primo, 
então 0 não pode ser um resíduo. Já 1 é possível, pois 7 é primo e 7 ≡ 1(mod 6). Quanto a 2, 
se 𝑝 ≡ 2(mod 6) então 𝑝 deveria ser par e isso é impossível, o mesmo argumento usamos para 
4. Caso 𝑝 ≡ 3(mod 6) então 𝑝 = 6𝑘 + 3 = 3(2𝑘 + 1) o que é impossível pois 𝑝 é primo. Já 5 é 
um valor possível, pois 5 ≡ 5(mod 6) e 5 é primo. 
 Podemos dizer de uma outra maneira que 𝑝 é congrunte a 1 ou 5 módulo 6, escrevendo 
que 𝑝 é da forma 6𝑘 + 1 ou 6𝑘 + 5. (Ver Teorema 1.19 Introdução a Teoria dos Números do 
José Plinio). 
 
3. Adição, Multiplicação e Congruência 
Agora vamos ver mais algumas propriedades da congruência modular. Se 𝑎 ≡ 𝑎′ (mod 𝑛) e 𝑏 ≡
𝑏′ (mod 𝑛), então vale: 
• 𝑎 + 𝑏 ≡ 𝑎′ + 𝑏′(mod 𝑛) 
• 𝑎𝑏 ≡ 𝑎′𝑏′(mod 𝑛) 
• 𝑎𝑘 ≡ (𝑎′)𝑘 (mod 𝑛) , para 𝑘 ≥ 0 
Prova: 
(a) Se 𝑎 ≡ 𝑎′ (mod 𝑛) e 𝑏 ≡ 𝑏′ (mod 𝑛) temos 𝑎 − 𝑎′ = 𝑝𝑛 e 𝑏 − 𝑏′ = 𝑞𝑛, somando ambos os 
lados temos: 
(𝑎 − 𝑎′) + ( 𝑏 − 𝑏′) = 𝑝𝑛 + 𝑞𝑛 
(𝑎 + 𝑏) − (𝑎′ + 𝑏′) = (𝑝 + 𝑞)𝑛 
o que implica 𝑎 + 𝑏 ≡ 𝑎′ + 𝑏′(mod 𝑛) 
(b) Se 𝑎 ≡ 𝑎′ (mod 𝑛) e 𝑏 ≡ 𝑏′ (mod 𝑛) temos 𝑎 = 𝑎′ + 𝑝𝑛 e 𝑏 = 𝑏′ + 𝑞𝑛, multiplicando 𝑎 e 𝑏: 
𝑎𝑏 = (𝑎′ + 𝑝𝑛 )(𝑏′ + 𝑞𝑛) = 𝑎′𝑏′ + 𝑎′𝑞𝑛 + 𝑏′𝑝𝑛 + 𝑝𝑞𝑛2 ⟹ 
⟹ 𝑎𝑏 − 𝑎′𝑏′ = (𝑎′𝑞 + 𝑏′𝑝 + 𝑝𝑞𝑛)𝑛 ⟹ 𝑎𝑏 ≡ 𝑎′𝑏′(mod 𝑛) 
(c) Se 𝑎 ≡ 𝑎′(mod 𝑛), então 𝑎 = 𝑎′ + 𝑝𝑛 elevando ambos os lados a 𝑘 obtemos: 
𝑎𝑘 = (𝑎′ + 𝑞𝑛)𝑘 = (𝑎′)𝑘 + (
𝑘
1
) (𝑎′)𝑘−1(𝑞𝑛) + ⋯ + (
𝑘
𝑘 − 1
) (𝑎′)1(𝑞𝑛)𝑘−1 + (𝑞𝑛)𝑘 ⟹ 
⟹ 𝑎𝑘 − (𝑎′)𝑘 = 𝑛(𝑘
1
)(𝑎′)𝑘−1(𝑞𝑛) + ⋯ + ( 𝑘
𝑘−1
)(𝑎′)1(𝑞𝑛)𝑘−1 + (𝑞𝑛)𝑘 
Como 𝑛 é fator de todas as parcelas do segundo membro, 𝑎𝑘 − (𝑎′)𝑘 é múltiplo de 𝑛, concluindo 
a prova. 
 
4. Critérios de Divisibilidade 
Nessa seção vamos usar congruência para criar critérios de divisibilidade, afim de economizar 
em determinar se um número é ou não divisível por outro 
4.1 Divisibilidade por 3 
Seja 𝑎 um número inteiro, tal que os algarismos de 𝑎 são, 𝑎𝑛, 𝑎𝑛, … , 𝑎𝑛, ou seja 
𝑎 = 𝑎𝑛10
𝑛 + 𝑎𝑛−110
𝑛−1 + ⋯ + 𝑎110 + 𝑎0 
Contudo 10 ≡ 1 (mod 3) então podemos calcular o módulo 3 de 10² como segue102 ≡
10.10 ≡ 1.1 ≡ 1 (mod 3). Se continuarmos o processo vamos concluir que 10𝑛 ≡ 1 (mod 3). 
Dessa forma pelas propriedades vista anteriormente 
𝑎 ≡ 𝑎𝑛. 1 + 𝑎𝑛−1. 1 + ⋯ + 𝑎1. 1 + 𝑎0 (mod 3) 
Se quisermos saber se o número 𝑎 é múltiplo de 3 𝑎 ≡ 0(mod 3) o que implica 𝑎𝑛. 1 +
𝑎𝑛−1. 1 + ⋯ + 𝑎1. 1 + 𝑎0 ≡ 0(mod 3), ou seja, acabamos de criar um critério de divisibilidade 
por 3. 
“Um número inteiro é divisível por 3 se, e somente se, a soma de seus 
 algarismo é divisível por 3”. 
Para o critério de divisibilidade por 9 e 11 usamos o mesmo processo. 
 
4.2 Divisibilidade por 7 
Vamos agora tentar encontrar um critério de divisibilidade para 7. Nesse caso se fossemos 
tentar utilizar o processo anterior iriamos cair em um processo mais complicado que dividir o 
número por 7 e ver se é divisível ou não, então tentaremos encontrar um processo melhor. Seja 
𝑎 inteiro: 
𝑎 = 𝑎𝑛10
𝑛 + 𝑎𝑛−110
𝑛−1 + ⋯ + 𝑎110 + 𝑎0 
𝑎 = (𝑎𝑛10
𝑛−1 + 𝑎𝑛−110
𝑛−2 + ⋯ + 𝑎1)10 + 𝑎0 
Chame 𝑎𝑛10
𝑛−1 + 𝑎𝑛−110
𝑛−2 + ⋯ + 𝑎1 = �̂�, então: 
𝑎 = �̂� ∙ 10 + 𝑎0 
Mas temos que 10 ≡ 3 (mod 7) então: 
𝑎 ≡ �̂� ∙ 3 + 𝑎0 (mod 7) 
Podemos ainda multiplicar por 2 ambos os lados 
2𝑎 ≡ �̂� ∙ 6 + 𝑎0 ∙ 2 (mod 7) 
Contudo 6 ≡ −1 (mod 7), logo 
2𝑎 ≡ −�̂� + 2𝑎0 (mod 7) 
Na prática temos que apenas verificar se −�̂� + 2𝑎0 é divisível por 7. A reciproca se mostra 
fazendo todos os passos inversos que fizemos para chegar nesse resultado. Vamos a um 
exemplo. 
Tome 𝑎 = 62.104 então �̂� = 6210 e 𝑎0 = 4 
−�̂� + 2𝑎0 = −6210 + 2 ∗ 4 = −6202 
Repetindo o processo �̂� = 620 e 𝑎0 = 2 
−�̂� + 2𝑎0 = −620 + 2 ∗ 2 = −616 
Repetindo o processo �̂� = 61 e 𝑎0 = 6 
−�̂� + 2𝑎0 = −61 + 2 ∗ 6 = −49 
Como 49 é divisível por 7, temos que 62.104. Note que em nossa argumentação não provamos 
a reciproca.