TEORIA DOS NÚMEROS - EXERCÍCIOS DE EQUAÇÕES MODULARES

01 – Resolver as equações modulares:

Obs. Uma equação modular do tipo ax ≡ b (mod. m) é resolvida fazendo:
(1) ax = km + r   e  b = k’m + r.  ⇒  r = ax – km = b – km  ⇒ ax – (k – k’)m = b  ou ax – my = b. Se b  for múltiplo do mdc(a, m) a equação terá solução. Caso contrário, não é possível encontrar x , tal que ax ≡ b (mod. m).

(a) 2x ≡ 1 (mod. 17)
Solução: Equação correspondente: 2x – 17y = 1 . Solução particular: x = 9 e y = 1.
Outras soluções: x = 9 + (-17/1)t  = 9 – 17t ⇒ x ≡ 9 (mod. 17).

(b) 3x≡1 (mod. 17)
Solução: Equação correspondente: 3x – 17y = 1 (1 solução) . Solução particular x = 6 e y = 1
Outras soluções: x = 6 + (-17/1)t = 6 – 17t ⇒ x ≡ 6 (mod. 17).
Resposta: x ≡ 6 (mod.17)

(c) 3x ≡ 6 (mod. 18) 
Solução: Equação correspondente: 3x –  18y = 6. Mdc(3, 18) = 3 (3 soluções)
Solução particular  x = 8  e y = 1.
Outras soluções:
x = 8 + (-18/3)t = 8 – 6t = 2 + 6 – 6t = 2 + 6(1 – t) ⇒ x ≡ 2 (mod. 6) ⇒ x ≡ 2 (mod.18)  x ≡ 2 + 6 = 8 (mod.18) e x ≡ 8 + 6 = 14 (mod.18). Resposta: x ≡ 2, 8 ou 14 (mod.18)

(d) 25x ≡ 15 (mod. 29)
Solução: Equação correspondente: 25x – 29y = 15. mdc(29, 25) = 1 (1 solução)
29 = 25.1 + 4
25 = 4.6 + 1
1 = 25 – 4.6 = 25 – (29 – 25.1).6 = 25.7 – 29.6  ⇒ x = 7 e y = 6
Outras soluções x = 7 – (29/1)t = 7 – 29t ⇒ x ≡ 7 (mod.29). Resposta: x ≡ 7 (mod. 29)

(e) 5x ≡ 2 (mod. 26)
Solução: Equação correspondente: 5x – 26y = 2. mdc(5, 26) = 1 (1 solução)
Solução particular  x = -10 e y = -2. Outras soluções x = - 10 + (-26/1)t = -10 – 26t ⇒ x ≡ - 10 ≡ -10 + 26 = 16. Resposta:- x ≡ 16 (mod.26).

(f) 6x ≡ 15 (mod.21)
Solução: Equação correspondente: 6x – 21y = 15. mdc(6, 21) = 3  (3 soluções)
Solução particular  x = -1 e y = -1. Outras soluções: x = -1 + (-21/3)t = -1 – 7t ⇒ x ≡ -1 (mod.7)  ⇒ x ≡ - 1 ≡ -1 + 7 = 6,  x ≡ 6 + 7 = 13 e x ≡ 13 + 7 = 20  (mod.21) Observe que foram somados 7 unidades a cada uma dos valores para x até atingir o maior inteiro possível, menor que 21. Resposta:- x ≡ 6, 13 e 20 (mod.21).

(g) 36x ≡ 8 (mod.102)
Solução: Equação correspondente: 36x – 102y = 8
mdc(36, 102) = 6. Como 8 não é múltiplo de 6, a equação não tem solução.

(h) 34x ≡ 60 (mod.98)
Solução: Equação correspondente: 34x – 98y = 60 . mdc(34, 98) = 2 (2 soluções)
Como não foi possível encontrar uma solução imediata, utilizemos o processo comum.
98 = 34.2 + 30; 34 = 30.1 + 4; 30 = 4.7 + 2               
2 = 30 – 4.7 = 30 – (34 – 30.1).7 = 30.8 – 34.7 = (98 – 34.2).8 – 34.7 = 98.8 – 34(23) = 34(-23) – 98(-8)
60 = 30.2 = 34(-23.30) – 98(-8.30) = 34(-690) – 98(-180)
Solução particular:   x = -690 + (-98/2)t = -690 – 49t.

O menor valor positivo de x é  x = -690 + 735 = 45  => x ≡ 45 (mod.49) => x ≡ 45 e x≡45 + 49 = 94 (mod.98). Resposta: x ≡ 45 e 94 mod(98)

(i) 8x ≡ 16 (mod.12)
Solução: Equação correspondente: 8x – 12y = 16. mdc(8, 12) = 4 (4 soluções) . Solução particular x = -1 e y = -2. Demais soluções x = -1 + (-12/4)t = -1 – 3t => x ≡ -1 ≡ -1 + 3 = 2 (mod.3) => x ≡ 2,  x ≡ 2 + 3 = 5,   x ≡ 5 + 3 = 8 e x ≡ 8 + 3 = 11 (mod. 12). Resposta; x ≡ 2, 5, 8, e 11 (mod. 12).

(j) 14x ≡ 36 (mod. 48)
Solução: Equação correspondente: 14x – 48y = 36. mdc(14, 48) = 2 (2 soluções). Solução particular  x = 6 e y = 1. Outras soluções x = 6 + (-48/2)t = 6 – 24 t => x ≡ 6 (mod.24) => x ≡ 6,  x ≡ 6 + 24 = 30  (mod. 48). Resposta: x ≡ 6 ou 30 (mod.48) .

2 – Resolver por congruência as seguintes equações diofantinas lineares; 
(a) 4x + 51y = 9
Solução: Mdc(4, 51) = 1
4x ≡ 9 (mod.51). Como 4 | 9  e 9 + 51 = 60 ≡ 9 (mod. 51) podemos fazer:
4x ≡ 60 ≡ x ≡ 15 (mod. 51)
Tomando x = 15, obtém-se 4.15 + 51y = 9 ≡ y = (9 – 60)/51 = -1.
Soluções gerais x = 15 + (51/1)t   = 15 + 51t     y = -1 – (4/1)t = -1 – 4t.
Resposta:  x = 15 + 51t    e  y = -1 – 4t. Poderíamos também tomar 51y ≡ 9 (mod.4). Como 51 = 4.12 + 3 ≡ 3 (mod. 4). Assim, 51y ≡ 3y ≡ 9 ≡ y ≡ 3 (mod. 4). Tomando y = 3, teremos 4x + 51.3 = 9 ≡ x = (9 – 51.3)/4 = -144/4 = - 36. Neste caso as soluções seriam:  x = -36 + (51/1)t = -36 + 51t   e y = 3 – (4/1)t = 3 – 4t.

(b) 12x + 25y = 331
Solução: Mdc(12, 25) = 1. 12x ≡ 331 (mod.25) . Como 331 = 25.13 + 6,   331 ≡ 6 (mod.25).
Procurando um múltiplo de 12 que seja congruente com 6 mod(25)  encontraremos 25.6 + 6 = 156. Portanto, 12x ≡ 156 (mod. 25) ⇔ x ≡ 13 (mod. 25) .
Fazendo x = 13, teremos y = (331 – 12.13)/25 = 175/25 = 7.
A solução geral será: x = 13 + (25/1)t = 13 + 25t    e y = 7 – (12/1)t = 7 – 12t.

OBS.: Todos os demais itens são resolvidos por processo semelhante. Para evitar a repetição daremos apenas as respostas dos outros itens.(c) 5x – 53y = 17   Resposta: x = 14 - 53t   y = 1 - 5t

(d) 7x + 6y = 9      Resposta: x = 3 + 6t      y = - 2 – 7t 

(e) 11x  + 27y = 4  Resposta: x = 20 + 27t  y = -8 – 11t 

(f)  75x – 131y = 6  Resposta: x = 42 - 131t  y = 24 - 75t 

(g) 39x + 26y = 104  Resposta: x = 2t   y = 37 + 61t 

(h) 61x – 11y = 81    Resposta: x = 8 - 11t    y = 37 - 61t 

(i) 65x + 77y = 200   Resposta: x = 9 + 77t     y = -5 – 65t 

(j) 51x + 85y = 1037 Resposta: x = 2 + 5t       y = 11 – 3t 

OBS.: As respostas para as equações do tipo ax – by = m apresentas no livro estão todas erradas, pois o autor  resolveu tais equações aplicando x  = x₀ + (b/d)t   e y = y_o + (a/d)t onde d = mdc(a, b). Isto não leva a uma resposta válida. A solução correta é x = x_o + (-b/d)t e y = y_o – (a/d)t.

3 – Determinar o número de soluções de cada uma das seguintes congruências lineares:  Informações: Se a equações ax ≡ b (mod.m) tiver solução, o número de soluções é igual a mdc(a, m).  Para que a equação tenha solução  b deve ser múltiplo do mdc(a, m). 

(a) 3x ≡ 6 (mod. 15)
Solução: Mdc(3, 15) = 3. Como 6 é múltiplo de 3, a equação tem duas soluções.

(b) 4x ≡ 8 (mod. 15)
Solução: Mdc(4, 15) = 1. 8 é múltiplo de 1. Portanto, a equação tem 1 solução.

(c) 5x ≡ 10 (mod.15)
Solução: mdc(5, 15) = 5. Como 10 é múltiplo de 5, a equação tem 2 soluções.  

(d) 6x = 11 (mod. 15)
Solução: mdc(6, 15) = 3. Como 11 não é múltiplo de 3, a equação não tem solução.  

4 – Determinar o número de soluções que pode ter uma congruência linear cujo módulo é 20.
Solução: Seja mdc(a, 20) = d.  O mdc de 20 é um divisor de 20. Portanto, a equação poderá ter 1, 2, 4, 5, 10 ou 20 soluções, pois estes são os divisores de 20. Resposta: {1, 2,4, 5, 10, 20}.

5 – Demonstrar que se d = mdc(a, m) e se d | b, então as congruências lineares ax ≡ b  (mod.m) e (a/d)x ≡ (b/d) (mod.m/d) têm precisamente as mesmas soluções.
Solução: Temos: ax ≡ b (mod. m) ⇔ ax – my = b  ⇔ (a/d)x – (m/d)y = (b/d) ⇔ (a/d)x≡(b/d) (mod.(m/d).  Portanto, as duas equações são equivalentes. O que leva a concluir que têm as mesmas soluções. Cqd.