Exercícios de Teoria dos Números

Exercícios de Teoria dos Números

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 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:

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 a congruê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 – b)(mod p) => p|(ap – bp) – (a – b)

Já temos que ap ≡ bp(mod p) => p|(ap – bp) logo, p|(a – b) => a ≡ b(mod p)

Como a ≡ b(mod p) teremos:

ap – 1 ≡ bp – 1 (mod p) => ap – 1.b0 ≡ bp – 1 (mod p)

ap – 2 ≡ bp – 2 (mod p) => ap – 2.b1 ≡ bp – 1 (mod p)

ap – 3 ≡ bp – 3 (mod p) => ap – 3.b2 ≡ bp – 1 (mod p)

.

.

.

a≡ b(mod p) => a.bp – 2 ≡ bp – 1 (mod p)

a0.bp – 1 ≡ a0.bp – 1(mod p) => bp – 1 ≡ bp – 1(mod p)

Somando as p congruências membro a membro:

ap – 1 + ap – 2.b + ap – 3.b2 + … + a.bp – 2 + bp – 1 ≡ p.bp – 1(mod p)

Mas p.bp – 1 ≡ 0(mod p)

logo ap – 1 + ap – 2.b + ap – 3.b2 + … + a.bp – 2 + bp – 1 ≡ 0(mod p)

então p|(ap – 1 + ap – 2.b + ap – 3.b2 + … + a.bp – 2 + bp – 1)

Já sabemos que

ap ≡ bp(mod p) => p|(ap – bp) => p|(a – b)(ap – 1 + ap – 2.b + ap – 3.b2 + … + a.bp – 2 + bp – 1)

e já temos que p|(a – b).

Logo, existem inteiros r, s tais que a – b = r.p (I)

e ap – 1 + ap – 2.b + ap – 3.b2 + … + a.bp – 2 + bp – 1 = s.p (II)

multiplicando (I) e (II) membro a membro:

(a – b)(ap – 1 + ap – 2.b + ap – 3.b2 + … + a.bp – 2 + bp – 1) = r.p.s.p

ap – bp = (r.s).p2 => p2|(ap – bp) => ap – b2 ≡ 0(mod p2) => ap ≡ bp(mod p2)

07 – Calcule φ de :

(i) 100 (ii) 23.34.52

(iii) pa (iv) p.q

(v) pa.qb

Em (iii), (iv) e (v) p e q são primos distintos.

(i) 100 = 22.52

08 – Seja f(n) = soma dos inteiros positivos menores ou iguais a n e primos com n.

Se f(n) = f(m) então n = m.

09 – Ache todos os inteiros positivos tais que φ(n)|n.

Comentários