Aula 14-Equações Modulares

Prévia do material em texto

Teoremas importantes sobre congruências
Teorema 1. Se n ∈ Z e se p é um número primo positivo, então
np ≡ n( mod p)
Esse Teorema é chamado de Pequeno Teorema de Fermat.
Prova: Vamos analisar três casos: o caso em que n = 0, o caso em que n > 0 e o caso em que
n < 0.
(i) Se n = 0 e p é primo positivo, então 0p = 0. Logo, 0p ≡ 0( mod p).
(ii) Para mostrar que o resultado vale para todo n ∈ N, vamos utilizar a técnica da indução
matemática.
• Se n = 1 e p é primo positivo, então 1p = 1. Logo, 1p ≡ 1( mod p) e, portanto, a
tese é válida para n = 1.
• Suponha que a tese é válida para n = k, ou seja, que kp ≡ k( mod p).
• Vamos mostrar que a tese vale para n = k + 1. Para n = k + 1, temos
(k + 1)p = C0pk
p · 10 + C1pkp−1 · 11 + C2pkp−2 · 12 + ...+ Cp−1p k1 · 1p−1 + Cppk0 · 1p
= kp + C1pk
p−1 + C2pk
p−2 + ...+ Cp−1p k
1 + 1
Observe que Ctp =
p!
(p−t)! t! =
p·(p−1)!
(p−t)! t! . Como C
t
p ∈ N, então
p · (p− 1)!
(p− t)! t! ∈ N
e, portanto, o número (p− t)! t! divide o número p · (p− 1)!.
Se 0 < t < p, então p− t < p e t < p. Como p é primo, então mdc(p, (p− t)! t!) = 1.
Como (p− t)! t! divide o produto p · (p− 1)!, então necessariamente (p− t)! t! divide
(p− 1)!. Ou seja,
(p− 1)!
(p− t)! t! ∈ Z
Com isso, concluímos que Ctp = p · (p−1)!(p−t)! t! é um múltiplo de p para todo t tal que
0 < t < p.
Ou seja, a soma C1pk
p−1 + C2pk
p−2 + ...+ Cp−1p k
1
nada mais é que um múltiplo de p.
Logo,
(k + 1)p ≡ kp + 1( mod p)
≡ k + 1( mod p)
Logo, a tese vale para k + 1 e podemos concluir que ela vale para todo n ∈ N.
(iii) Vamos mostrar agora que o resultado vale para todo n ∈ Z∗+ (utilizando que a tese vale
para os números naturais).
Se n ∈ Z∗+, então n = (−1) ·m, onde m ∈ Z.
(1) Se p = 2, então
np = n2 = (−1)2 ·m2 = m2
1
Logo,
n2 ≡ m2( mod 2)
≡ m( mod 2)
Como existem apenas duas classes de equivalência módulo 2 (que são a classe dos
números pares e a classe dos números ímpares) e
• Se m é par, então −m = n também é par.
• Se m é ímpar, então −m = n também é ímpar.
então m ≡ n( mod 2). Portanto,
n2 ≡ m( mod 2)
≡ n( mod 2)
(2) Se p 6= 2, então p é ímpar (pois o único primo par positivo que existe é o 2). Nesse
caso,
np = (−1)p ·mp = (−1) ·mp
Logo,
np ≡ (−1) ·mp( mod p)
≡ (−1) ·m( mod p)
≡ n( mod p)
Concluímos que o resultado vale para todo inteiro negativo.
Exemplo 1. Calcule
(a) 47 mod 7
(b) 505 mod 5
(c) (−150)101 mod 101
(d) 19013 mod 13
(e) (−170)17 mod 17
(f) (−1970)19 mod 19
Resolução:
(a) Como 7 é primo, então 47 ≡ 4( mod 7). Como 4 mod 7 = 4, então 47 mod 7 = 4.
(b) Como 5 é primo, então 505 ≡ 50( mod 5). Como 50 mod 5 = 0, então 505 mod 5 = 0.
(c) Como 101 é primo, então (−150)101 ≡ −150( mod 7). Como
−150 = 101 · (−2) + 52
então −150 mod 101 = 52 e, portanto, (−150)101 mod 101 = 52.
2
(d) Como 13 é primo, então 19013 ≡ 190( mod 13). Como
190 = 13 · 14 + 8
então 190 mod 13 = 8 e, portanto, 19013 mod 13 = 8.
(e) Como 17 é primo, então (−170)17 ≡ −170( mod 17). Como −170 mod 17 = 0, então
(−170)17 mod 17 = 0.
(f) Como 19 é primo, então (−1970)19 ≡ −1970( mod 19). Como
−1970 = 19 · (−104) + 6
então −1970 mod 19 = 6 e, portanto, (−970)19 mod 19 = 6.
A recíproca do Pequeno Teorema de Fermat não é verdadeira, ou seja, se np ≡ n( mod p),
então NÃO podemos afirmar que p é primo (existem vários contra-exemplos). Entretanto,
podemos extrair um resultado muito interessante do teorema, que é utilizado na detecção de
possíveis números primos:
Corolário 1. Sejam n ∈ Z e p ∈ N. Se np��≡ n( mod p), então p não é um número primo.
Exemplo 2. Como 24 = 32, então 24 mod 4 = 0. Logo, 24 ��≡ 2( mod 4). Pelo Corolário,
podemos concluir que 4 não é um número primo.
Teorema 2. Se n ∈ Z, se p é um número primo positivo e se mdc(p, n) = 1, então
np−1 ≡ 1( mod p)
Esse Teorema é chamado de Teorema de Euler.
Prova: Suponha que n ∈ Z, que p é um número primo positivo e que mdc(p, n) = 1. Do
Pequeno Teorema de Fermat, temos que
np ≡ n( mod p)
Logo, np − n é múltiplo de p. Ou seja,
np − n = k · p
onde k ∈ Z. Mas, temos que np = n · np−1. Portanto,
n · np−1 − n = k · p
n · (np−1 − 1) = k · p
Logo, n divide k · p. Como mdc(p, n) = 1, então necessariamente n | k. Temos então que
k
n
= c ∈ Z e
np−1 − 1 = k · p
n
=
k
n
· p = c · p
Como np−1 − 1 é múltiplo de p, então
np−1 ≡ 1( mod p)
3
Exemplo 3. Calcule
(a) 46 mod 7
(b) (−150)100 mod 101
(c) 19012 mod 13
(d) (−171)16 mod 17
(e) (−1970)18 mod 19
Resolução:
(a) Como 7 é primo e mdc(4, 7) = 1, então 46 ≡ 1( mod 7) e, portanto, 46 mod 7 = 1.
(b) Como 101 é primo e mdc(−150, 101) = 1, então (−150)100 ≡ 1( mod 101) e, portanto,
(−150)100 mod 101 = 1.
(c) Como 13 é primo e mdc(190, 13) = 1, então 19012 ≡ 1( mod 13) e, portanto, 19012
mod 13 = 1.
(d) Como 17 é primo e mdc(−171, 17) = 1, então (−171)16 ≡ 1( mod 17) e, portanto,
(−171)16 mod 17 = 1.
(e) Como 19 é primo e mdc(−1970, 19) = 1, então (−1970)18 ≡ 1( mod 19) e, portanto,
(−1970)18 mod 19 = 1.
Equações modulares
Seja m ∈ N. Suponha que queremos determinar todos os números inteiros x que satisfazem
a equação
x ≡ a( mod m)
onde a ∈ Z. Como
x ≡ a( mod m) ↔ x− a = k ·m para algum k ∈ Z
então as soluções dessa equação são todos os números inteiros da forma x = a+ k ·m. Ou seja,
o conjunto solução da equação é
a = {a+ k ·m | k ∈ Z}
Exemplo 4. (a) O conjunto solução da equação x ≡ 7( mod 11) é o conjunto
7 = {7 + k · 11 | k ∈ Z} = {...,−26,−15,−4, 7, 18, 25, 32, ...}
(b) O conjunto solução da equação x ≡ 32( mod 14) é o conjunto
32 = {32 + k · 14 | k ∈ Z} = {...,−24,−10, 4, 18, 32, 46, 60, 74, ...}
(c) O conjunto solução da equação x ≡ −16( mod 10) é o conjunto
−16 = 4 = {4 + k · 10 | k ∈ Z} = {...,−26, ,−16,−6, 4, 14, 24, 34, ...}
4
Seja m ∈ N. As soluções da equação
x+ b ≡ a( mod m)
onde a, b ∈ Z são as mesmas soluções da equação
x ≡ a− b( mod m)
Ou seja, o conjunto solução da equação é
a− b = {a− b+ k ·m | k ∈ Z}
Exemplo 5. (a) O conjunto solução da equação x + 10 ≡ 7( mod 11) é o conjunto solução
da equação
x ≡ 7− 10( mod 11)
x ≡ −3( mod 11)
que é o conjunto
−3 = {−3 + k · 11 | k ∈ Z} = {...,−25,−14,−3, 8, 19, 30, 41, ...}
(b) O conjunto solução da equação x− 4 ≡ 2( mod 5) é o conjunto solução da equação
x ≡ 2 + 4( mod 11)
x ≡ 6( mod 11)
que é o conjunto
6 = {6 + k · 14 | k ∈ Z} = {...,−14,−9,−4, 1, 6, 11, 16, 24, ...}
Teorema 3. Se a, b ∈ Z, se m ∈ N e se mdc(a,m) = 1, então o conjunto solução da equação
a · x ≡ b( mod m)
é S = x0 = {x0 + k ·m | k ∈ Z}, onde
• a0 = a mod m
• b0 = b mod m
• x0 = a−10 ⊗ b0
O inteiro x0 é a única solução da equação que pertence a Zm.
Prova: Se a0 = a mod m, então
a = m · q1 + a0
Seja k = mdc(m, a0). Temos que k ≥ 1, m = k · c1 e a0 = k · c2 com c1, c2 ∈ Z. Mas então
a = k · c1 · q1 + k · c2
a = k(c1 · q1 + c2)
a
k
= c1 · q1 + c2 ∈ Z
5
e, portanto, k também é um divisor de m. Como k ∈ D(a,m), k ≥ 1 e mdc(a,m) = 1, então
k = 1. Ou seja, mdc(a0,m) = 1. Logo, a0 é invertível em Zm.
Seja b0 = b mod m e x0 = a
−1
0 ⊗ b0. Temos que a−10 · b0 mod m = x0 e, portanto,
a−10 · b0 = m · q0 + x0 → x0 = a−10 · b0 −m · q0
Temos então que
a·x0 = (m·q1+a0)·x0 = m·q1·x0+a0·x0 = m·q1·x0+a0·(a−10 ·b0−m·q0) = m·q1+a0·a−10 ·b0−a0·m·q0
Logo,
a · x0 ≡ m · q1 + a0 · a−10 · b0 − a0 ·m · q0( mod m)
≡ a0 · a−10 · b0
Como a0 ⊗ a−10 = 1, então, a0 · a−10 mod m = 1 e, portanto, a0 · a−10 = m · q2 + 1. Temos então
que
a · x0 ≡ a0 · a−10 · b0( mod m)
≡ (m · q2 + 1) · b0( mod m)
≡ m · q2 · b0 + b0( mod m)
≡ b0( mod m)
≡ b( mod m)
Ou seja, a ·x0 ≡ b( mod m) e, portanto, x0 satisfaz a equação. Além disso, x0+ k ·m também
é solução da equação para todo k ∈ Z, uma vez que x0 + k ·m ≡ x0( mod m).
Suponha que y0 ∈ Z é uma solução da equação. Então
a · y0 − a · x0 ≡ b− a · x0( mod m)
a · y0 − a · x0 ≡ b−b( mod m)
a · y0 − a · x0 ≡ 0( mod m)
a · (y0 − x0) ≡ 0( mod m)
Logo, a · (y0 − x0) é múltiplo de m. Como mdc(a,m) = 1, então necessariamente y0 − x0 é
múltiplo de m. Ou seja,
y0 − x0 = c ·m onde ∈ Z
y0 = x0 + c ·m
Concluímos que todas as soluções diferem de x0 por um múltiplo de m.
Logo, o conjunto solução da equação é S = x0
6
Exemplo 6. Resolva as equações dadas.
(a) 3x ≡ 4( mod 8)
Temos que 3 mod 8 = 3 e 4 mod 8 = 4. A equação 3x ≡ 4( mod 8) equivale a equação
3⊗ x = 4
em Z8. Como mdc(3, 8) = 1, então 3 é invertível. Temos que 3−1 = 3 (pois 3 ⊗ 3 = 3 · 3
mod 8 = 9 mod 8 = 1). Multiplicando os dois lados da equação 3⊗x = 4 por 3−1, obtemos
3−1 ⊗ 3⊗ x = 3−1 ⊗ 4
1⊗ x = 3−1 ⊗ 4
x = 3−1 ⊗ 4 = 3⊗ 4 = 3 · 4 mod 8 = 12 mod 8 = 4
O conjunto solução da equação 3x ≡ 4( mod 8) é o conjunto
4 = {4 + k · 8 | k ∈ Z} = {...,−20,−12,−4, 4, 12, 20, ...}
(b) 17x ≡ 29( mod 13)
Temos que 17 mod 13 = 4 e 29 mod 13 = 3. A equação 17x ≡ 29( mod 13) equivale
a equação
4⊗ x = 3
em Z13. Como mdc(4, 13) = 1, então 4 é invertível. Temos que 4−1 = 10 (pois 10⊗4 = 10·4
mod 13 = 40 mod 13 = 1). Multiplicando os dois lados da equação 4 ⊗ x = 3 por 4−1,
obtemos
4−1 ⊗ 4⊗ x = 4−1 ⊗ 3
1⊗ x = 4−1 ⊗ 3
x = 4−1 ⊗ 3 = 10⊗ 3 = 10 · 3 mod 13 = 30 mod 13 = 4
O conjunto solução da equação 17x ≡ 29( mod 13) é o conjunto
4 = {4 + k · 13 | k ∈ Z} = {...,−35,−22,−9, 4, 17, 30, ...}
(c) 72x ≡ 140( mod 43)
Teorema do resto chinês: Sejam a, b ∈ Z e m,n ∈ N tais que mdc(m,n) = 1. Existe um
único inteiro x0 ∈ Zmn que é solução do par de equações{
x ≡ a( mod m)
x ≡ b( mod n)
O conjunto solução da equação é a classe de equivalência de x0 em Zmn.
7