ARITMÉTICA MODULAR DEFINIÇÃO:
dizemos que dois números inteiros, a e b, são congruentes quando na divisão, por um mesmo número (m), deixam
o mesmo resto. Denotamos isto por a ≡ b (mod m).
Exemplo:
11 ≡ 3 (mod 4), pois 11 = 4 ⋅ 2 + 3.
Veja que todos os números inteiros que geram resto 3 na divisão por 4 formam uma sequência {…, -5, -1, 3, 7, 11, …}. Veja essa sequência que varia somando-se 4, que é o divisor. Se lembrarmos das propriedades da divisão lembraremos que, ao somarmos ao dividendo o próprio divisor, não iremos alterar o resto.
PROPRIEDADES: Sejam a, b, c, d, m inteiros (m > 0).
1. a ≡ a (mod m) (re exiva).
2. Se a ≡ b (mod m), então b ≡ a (mod m) (simétrica).
3. Se a ≡ b (mod m) e b ≡ c (mod m), então a ≡ c (mod m) (transitiva).
4. Se a ≡ b (mod m), então a ± c ≡ b ± c (mod m).
5. Se a ≡ b (mod m), então ac ≡ bc (mod m).
6. Se a ≡ b (mod m) e c ≡ d (mod m), então a ± c ≡ b ± d (mod m).
7. Se a ≡ b (mod m) e c ≡ d (mod m), então ac ≡ bd (mod m).
8. Sejam a, b, k, m são números inteiros com k, m > 0 e a ≡ b (mod m), então ak ≡ bk (mod m).
Observação
Estas propriedades indicam que podemos fazer quase qualquer operação com o símbolo de congruência. Uma coisa que não podemos fazer é cortar. Por exemplo, 4 ≡ 2 (mod 2), mas 2 ≡1 mod 2 ( )!
Vejamos dois exemplos em que a aritmética modular será de grande valia:
PEQUENO TEOREMA DE FERMAT
Se p é primo e p|a/ , então: ( ) p 1 a 1 mod p − ≡
Exemplo:
( ) 7 1 6 1 mod 7 − ≡ Corolário: Se p é primo e a é um inteiro positivo, então ( ) p a a mod p ≡ .
TEOREMA DE EULER
Seja n ∈ e b ∈ com mdc (b, n) = 1 (b e n são primos entre si. Então:
(n) b 1 (mod n) ϕ ≡
Lembrando que ϕ(n) é a função phi de Euler que nos indica a quantidade de números primos com n, porém, menores que n.
Exemplo:
( ) ( ) ( ) 33 20 mdc 10,33 1 10 10 1 mod 33 φ =⇒ = ≡ .
Exemplo:
Se mdc (a,m) = 1, resolver ax ≡ b (mod m).
Pelo teorema de Euler,
( )( ) ( )( ) ( )( ) m m m a 1 mod m a b b mod m ax a b mod m φ φ φ ≡ ⇒ ⋅≡ ⇒ ≡ ⋅
Como mdc (a,m) = 1, podemos cancelar o fator a, então ( )( ) m 1 x a b mod m φ − ≡ ⋅ .
A parte inteira da metade de φ(n) representa a quantidade de espécies de polígonos regulares que se pode formar de n lados, convexos e estrelados.
A quantidade de algarismos do período de uma dízima periódica, obtidos a partir de uma fração irredutível ND, é igual a φ(D) ou um divisor positivo deste.
Exemplo:
Seja a fração 211, como φ(11) = 10, seu período pode ter 1, 2, 5 ou 10 algarismos. Como 2 18
11 99 = , o período terá 2 algarismos.
ORDEM DE A COM RESPEITO A N
Ordem de a com respeito a n é o número natural ( ) { ( )} * i ord a min i ; a 1 mod n n =∈≡ .
Se a,n ∈ , com mdc (a,n) = 1, então ordn(a) | φ(n).
TEOREMA DE WILSON
Seja p um número primo, então:
(p 1)! 1 (mod p) − ≡−
Em que n! = n ⋅ (n – 1) ⋅ (n – 2) ⋅ … ⋅ 2 ⋅ 1 e lê – se n fatorial.
SISTEMA DE CONGRUÊNCIA E TEOREMA DO RESTO CHINÊS
Se (ai , mi ) = 1, (mi ,mj ) = 1 para i ≠ j e ai um número inteiro, então o sistema
1 1 2 2
3 3
r r
x a (mod m )
x a (mod m )
x a (mod m )
…
x a (mod m )
≡
≡
≡
≡
Possui solução e é única no módulo m, em que m = m1 ⋅ m2 ⋅ m3⋅ … ⋅ mr.
Exemplo:
Encontre uma solução inteira para:
x 2 (mod 11)
x 4 (mod 12)
x 5 (mod 13)
≡
≡
≡
Resolvendo por sistema de congruência teremos:
Da primeira equação x = 11q + 2. Substituindo na 2a equação temos:
11q + 2 ≡ 4 (mod 12), como 11 ⋅ 11 = 121 ≡ 1 (mod 12) teremos:
(11q 2 11 4 11 (mod 12) 11 11q 22 44 (mod 12) q 22 8 + ⋅ ≡⋅ ⇒ ⋅ + ≡ ⇒+q + 22 ≡ 8 (mod 12), assim q + 22 = 8 + 12k ⇒
q = 12k – 14. Na 3a equação teremos, x 11(12k 14) 2 132k 154 2 132k 152 5 (mod 13) = − += − += − ≡ , assim
132k ≡ 157 (mod 13) ⇒ 2k ≡ 1 (mod 13), como 14 ≡ 1 (mod 13)
vamos multiplicar toda a equação por 7 a m de aparecer 14k.
14k ≡ 7 (mod 13) ⇒ k ≡ 7 (mod 13). Assim k = 13t + 7.
Inicialmente, x = 11q + 2 e q = 12k – 14 e k = 13t + 7, assim:
x 11q 2
11(12k 14) 2
132k 154 2
132(13t 7) 152
1716t 924 152
1716t 772
11 12 13t 772
= +
= −+
= −+
= +−
= +−
= +
=⋅⋅ +
Provando que a solução é única no (mod m1 ⋅ m2 ⋅ m3 ⋅ … ⋅ mr
).
Pelo teorema do resto chinês, teremos:
156 143 132
156 143 132
2 12 13 m 4 11 13 m 5 11 12 m 1716q
2 156m 4 143 m 5 132 m 1716q ⋅ ⋅ ⋅ +⋅ ⋅ ⋅ +⋅ ⋅ ⋅ + ⇒ ⋅ +⋅ ⋅ +⋅ ⋅ + Em que m156, m143 e m132 são determinados ao se resolver:
156
143
132
156 m 1 (mod 11)
143 m 1 (mod 12)
132 m 1 (mod 13)
156 156
156 156
143 143
143 143
132 132
132
156 m 1 (mod 11) 2 m 1 (mod 11)
12 m 6 (mod 11) m 6 (mod 11).
143 m 1 (mod 12) m 1 (mod 12)
m 1 (mod 12) m 11 (mod 12).
132 m 1 (mod 13) 2 m 1 (mod 13)
14 m 7 (mod 13) ⋅ ≡ m 7 (mod 13). 132 = 2 156 6 4 143 11 5 132 7 1716q 12784 1716q 772 1716 7 1716q x 772 (mod 1716)
