Congruencia

Lista de Exercícios de Teoria dos Números
01 – Qual o último dígito da representação decimal de 3400 ?
R. O último dígito da representação decimal de um número é o resto da divisão do número por 10.
Temos que (3,10) = 1.
Usando o Teorema de Euler temos:
3φ(10) ≡ 1(mod 10) φ(10) = φ(2.5) = φ(2) φ(5) = (2 – 1)(5 – 1) = 4
34 ≡ 1(mod 10) => (34)100 ≡ 1100(mod 10) => 3400 ≡ 1(mod 10)
Logo, o último dígito da representação decimal de 3400 é 1.
02 – a) Mostrar que 2, 4, 6, ..., 2m é um S.C.R. módulo m se m é impar.
R. Basta dividirmos todos os elementos por 2 e teremos:
1, 2, 3, ... , m que é um sistema completo de resíduos módulo m.
b) Mostrar que 12, 22, 32, ..., m2 não é um S.C.R. módulo m se m > 2.
R. Temos que mostrar que os números tomados dois a dois não são incongruentes módulo m. Basta tomarmos dois números a e b, a > b, tais que a + b = m
Tomando a2 – b2 = (a + b)(a – b) = m.(a – b) ≡ 0(mod m) => a2 – b2 ≡ 0(mod m) =>
=> a2 ≡ b2(mod m)
03 – Se p é um primo ímpar, prove que:
12.32.55.....(p-2)2 ≡ (-1)(p+1)/2(mod p) e 22.42.65.....(p-1)2 ≡ (-1)(p+1)/2(mod p)
R. (i) Pelo Teorema de Wilson:
(p – 1)! ≡ – 1(mod p)
1.2.3.4.5.6...(p – 6).(p – 5).(p – 4).(p – 3).(p – 2).(p – 1) ≡ – 1(mod p) podemos subtrair p dos termos pares sem que a congruência fique alterada
1.(2 – p).3.(4 – p).5.(6 – p)...(p – 6).(– 5).(p – 4).(– 3).(p – 2).(– 1) ≡ – 1(mod p)
1.(– 1)(p – 2).3.(– 1)(p – 4).5.(– 1)(6 – p)...(p – 6).(–1).5.(p – 4).(–1).3.(p – 2).(– 1).1 ≡ – 1(mod p)
Como temos (p – 1)/2 fatores pares, então teremos (– 1)(p – 1)/2, que iremos colocar em evidência.
(– 1)(p – 1)/2.1.(p – 2).3.(p – 4).5.(6 – p)...(p – 6).5.(p – 4).3.(p – 2).1 ≡ – 1(mod p)
Como p é ímpar, agora todos os fatores são ímpares e aparecem duas vezes
(– 1)(p – 1)/2.12.32.52...(p – 6)2.(p – 4)2.(p – 2)2 ≡ – 1(mod p)
Multiplicando ambos os membros por (– 1)(p – 1)/2
(– 1)(p – 1).12.32.52...(p – 6)2.(p – 4)2.(p – 2)2 ≡ (– 1).(– 1)(p – 1)/2 (mod p)
Como p é ímpar, então p – 1 é par e