Teoria dos Números - Sistema de Congruência Linear

Prévia do material em texto

UNIVERSIDADE DO ESTADO DO PARÁ 
CENTRO DE CIENCIAS SOCIAIS E EDUCAÇÃO – CCSE 
NUCLEO DE SÃO MIGUEL DO GUAMÁ – CAMPUS XI 
CURSO DE LICENCIATURA PLENA EM MATEMATICA 
DISCIPLINA: TEORIA DOS NÚMEROS 
DOCENTE: BRUNO COSTA 
SISTEMA DE CONGRUÊNCIA 
LINEAR 
DISCENTES: 
ANTONIO BORGES SAMPAIO 
ANTONIO CLEBSON DA SILVA MOTA 
MARIA MARCELA DE ANDRADE LIMA 
SILVANA DO SOCORRO DA VERA CRUZ ALMEIDA 
THAYS STEFHANY SILVA CLETO 
 
São Miguel do Guamá – PA 
Dezembro / 2017 
Introdução 
Congruência. 
 Definição: Sejam a e b inteiros quaisquer e seja m>1 um inteiro 
positivo fixo. Diz-se que a é congruente a b módulo m se, e somente 
se, m divide a diferença a – b. Em outros termos a é congruente a b 
módulo m se, e somente se, existe um inteiro k tal que a – b = km 
Simbolicamente: 
 
 
 
 Definição 9.2 Se m não divide a diferença a – b, então diz-se que a é 
incongruente a b módulo m . 
a ≢ b (mod m) 
a ≡ b (mod m) ⇔ m | ( a – b ) ⇔ a - b = km ⇔ a = km + b 
 
 Teorema: Sejam 𝑛1, 𝑛2, 𝑛3, … , 𝑛𝑘 números inteiros 
positivos tais que MDC (𝑛𝑖 , 𝑛𝑗) = 1, para 𝑖 ≠ 𝑗. Então 
o sistema de congruência lineares 
𝑥 ≡ 𝑎1 𝑚𝑜𝑑 𝑛1 
𝑥 ≡ 𝑎2 𝑚𝑜𝑑 𝑛2 
𝑥 ≡ 𝑎3(𝑚𝑜𝑑 𝑛3 ) 
⁞ 
𝑥 ≡ 𝑎𝑘 𝑚𝑜𝑑 𝑛𝑘 
admite uma solução simultânea, que é única módulo o 
inteiro 𝑛 = 𝑛1, 𝑛2 , 𝑛3, … , 𝑛𝑘. 
 
O TEOREMA DO RESTO CHINÊS 
 Teorema: Uma congruência linear em uma variável 
𝑎𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) admite solução inteira se e somente se 
𝑚𝑑𝑐 (𝑎,𝑚)| 𝑏. No caso de haver solução, se 𝑥0 ∈
*0, 1, … ,𝑚 − 1+ é solução então, 
 
𝑥0 +
𝑚
𝑚𝑑𝑐(𝑎,𝑚)
𝑡: 𝑡 ∈ ℤ 
 
 São todas soluções e 
 
𝑥0 +
𝑚
𝑚𝑑𝑐(𝑎,𝑚)
𝑡: 𝑡 ∈ 0,1,…𝑚𝑑𝑐 𝑎,𝑚 − 1 
 
 São todas as soluções módulo 𝑚 da congruência. 
 
SISTEMA DE CONGRUÊNCIA LINEAR 
 Exemplo 1: Qual o menor natural que dividido por 7 
deixa resto 3 e quando dividido por 6 deixa resto 5? 
 
Exercícios Resolvidos 
Solução: Equacionando o problema, teremos o seguinte sistema 
de congruência. 
 
x ≡ 3 (mod7) 
x ≡ 5 (mod6) 
 
Sejam x1, x2 inteiros tais que x = x1 + x2, onde 
𝑥1 ≡ 3 (𝑚𝑜𝑑 7) 
e 
𝑥2 ≡ 0 (𝑚𝑜𝑑7) 
𝑥1 ≡ 0 𝑚𝑜𝑑 6 𝑥2 ≡ 5 (𝑚𝑜𝑑 6) 
 Assim 𝑥1 = 6 𝑡1 𝑒 𝑥2 = 7𝑡2. Logo a solução é dada por 
𝑥 = 𝑥1 + 𝑥2 = 6 𝑡1 + 7𝑡2. Resta agora encontrar os 
valores de 𝑡1 𝑒 𝑡2. Como 𝑥1 ≡ 3 (𝑚𝑜𝑑 7), então segue-
se que: 6𝑡1 ≡ 3 𝑚𝑜𝑑 7 ⇒ 36𝑡1 ≡ 18 𝑚𝑜𝑑 7 ⇒ 𝑡1 ≡
 4 𝑚𝑜𝑑 7 . Logo 𝑡1 = 4 + 7𝑘1. Analogamente, como 
𝑥2 ≡ 5 (𝑚𝑜𝑑 6) então: 7𝑡2 ≡ 5 𝑚𝑜𝑑 6 ⇒ 𝑡2 ≡
 5 𝑚𝑜𝑑 6. Logo 𝑡2 = 5 + 6 𝑘2. 
 Achados 𝑡1 = 4 + 7𝑘1 e 𝑡2 = 5 + 6𝑘 2, substituindo 
na equação, 𝑥 = 6 𝑡1 + 7𝑡2 ⇒ 𝑥 = 6 4 + 7 𝑘1 =
 7 5 + 6𝑘2 = 59 + 42 𝑘1 + 𝑘2 = 17 + 42𝑘. 
 
 Logo, a solução deste sistema será 𝑥 = 17 + 42𝑘. 
Então o menor inteiro que dividido por 6 deixa resto 5 e 
quando dividido por 7 deixa resto 3 é o 17. 
 
 Exemplo 2: Determinar qual o número deixa restos 2, 
3 e 2 quando dividido, respectivamente, por 3, 5 e 7. 
 Solução: Inicialmente , observamos que o problema é 
equivalente ao sistema 
 
𝑥 ≡ 2 𝑚𝑜𝑑 3
𝑥 ≡ 3 𝑚𝑜𝑑 5
𝑥 ≡ 2 𝑚𝑜𝑑 7
 
 
 Temos que M=3x5x7=105 
 
 M1=35, M2=21 e M3=15; 
 
Exercícios Resolvidos 
 Por outro lado as soluções das congruências 
 
35 ≡ 1 𝑚𝑜𝑑 3 
21 ≡ 1 𝑚𝑜𝑑 5 𝑒 
15 ≡ 1 𝑚𝑜𝑑 7 
 
São respectivamente, y1=2, y2=1 e y3=1 
 Portanto, uma solução módulo M=105 é dada por 
X=𝑀1𝑦1𝑐1 + 𝑀2𝑦2𝑐2 + 𝑀3𝑦3𝑐3 = 233 
Como 233≡23 mod 105, segue que 23 é uma solução e 
qualquer outra solução é do tipo 23+105t, t ∈ ℤ. 
 Exemplo 3: Resolva o sistema: 
 
𝑥 ≡ 3 (𝑚𝑜𝑑 5)
𝑥 ≡ 4 (𝑚𝑜𝑑 7)
 
 
 Solução: A primeira congruência nos permite concluir que 
𝑥 = 5𝑞 + 3. Daí, 
 5𝑞 + 3 ≡ 4 (𝑚𝑜𝑑 7) 
 5𝑞 ≡ 1 (𝑚𝑜𝑑 7) 
 15𝑞 ≡ 3 (𝑚𝑜𝑑 7) 
 𝑞 ≡ 3 (𝑚𝑜𝑑 7). 
 Assim, 𝑞 = 3 + 7𝑘 e 
 𝑥 = 5𝑞 + 3 
 = 5(3 + 7𝑘) + 3 
 = 35𝑘 + 18, 
 para algum inteiro k. 
 
 FONSECA, Rubens Vilhena. Teoria dos números – Belém: 
UEPA / Centro de Ciências Sociais e Educação, 2011. 
 
 SANTOS, José Plínio de Oliveira. Introdução à teoria dos 
números - Rio de Janeiro: IMPA, 2005. 
 
REFERÊNCIAS