Congruencia

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1241 palavras )
  • Download(s) : 0
  • Publicado : 9 de abril de 2013
Ler documento completo
Amostra do texto
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 incongruentesmó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 eassim (– 1)(p – 1) = 1
Já no segundo membro temos:
(– 1).(– 1)(p – 1)/2 = (– 1)2/2.(– 1)(p – 1)/2 = (– 1)(p – 1 + 2)/2 = (– 1)(p + 1)/2, assim sendo teremos:
12.32.52...(p – 6)2.(p – 4)2.(p – 2)2 ≡ (– 1)(p + 1)/2 (mod p)
(ii) 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 ímpares sem que acongruência fique alterada
(1 – p).2.(3 – p).4.(5 – p).6...(– 6).(p – 5).(– 4).(p – 3).(– 2).(p – 1) ≡ – 1(mod p)
(– 1).(p – 1).2.(– 1).(p – 3).4.(– 1).(p – 5).6... (– 1). 6.(p – 5).(– 1).4.(p – 3).(– 1).2.(p – 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.(p – 1).2.(p – 3).4.(p – 5).6...6.(p – 5).4.(p – 3).2.(p– 1) ≡ – 1(mod p)
Como p é ímpar, agora todos os fatores são pares e aparecem duas vezes
(– 1)(p – 1)/2.22.42.62...(p – 5)2.(p – 3)2.(p – 1)2 ≡ – 1(mod p)
Multiplicando ambos os membros por (– 1)(p – 1)/2
(– 1)(p – 1).22.42.62...(p – 5)2.(p – 3)2.(p – 1)2 ≡ (– 1).(– 1)(p – 1)/2 (mod p)
Como p é ímpar, então p – 1 é par e assim (– 1)(p – 1) = 1
Já no segundo membro temos:
(– 1).(– 1)(p –1)/2 = (– 1)2/2.(– 1)(p – 1)/2 = (– 1)(p – 1 + 2)/2 = (– 1)(p + 1)/2, assim sendo teremos:
22.42.62...(p – 5)2.(p – 3)2.(p – 1)2 ≡ (– 1)(p + 1)/2 (mod p)
04 – Se p é primo e a e b são inteiros mostre que:
(a + b)p ≡ ap + bp (mod p).
R. Temos que:

Note que o fatorial varia de , considerando onde k = 1,2,...,p – 1, vemos que:

Então:

05 – Se p é primo e se h + k = p-1 com h ≥ 0 e k ≥0, prove que:
h!.k! + (-1)h ≡ 0 (mod p)
06 – Seja p primo e a, b números tais que ap ≡ bp (mod p) prove que:
ap ≡ bp (mod p2)
R. (i) Se p|a e p|b então ap ≡ 0(mod p) e bp ≡ 0(mod p) e então ap ≡ bp(mod p2).
(ii) Se p†a e p†b então (p,a) = 1 e (p,b) = 1, então valem:
ap – 1 ≡ 1(mod p) => ap ≡ a(mod p) (*)
bp – 1 ≡ 1(mod p) => bp ≡ b(mod p) (**)
Fazendo (*) – (**), teremos:
ap – bp ≡ (a...
tracking img