TEORIA DOS NÚMEROS - EXERCÍCIOS DE MDC

01 – Verdadeiro (V) ou falso (F)
Obs: usaremos a notação ~≡ para indicar "não côngruo a"

(a) 91 ≡ 0 (mod.7) Verdadeiro pois 91 = 7.13
(b) 3 + 5 + 7 ≡ 5 (mod.10) Verdadeiro 3 + 5 + 7 = 15 = 10.1 + 5
(c) –2 ≡ 2 (mod.8) Falso. (-2 + 8) = 6 => -2 ≡ 6
(d) 112 ≡ 1 (mod.3) Verdadeiro 112  ≡ 22 ≡ 1 (11 = 3.3 + 2  portanto 11 ≡ 2)
(e) 17 ~≡  9 (mod.2) Falso 17 ≡ 9 ≡ 1 (mod.2)
(f) 42 ~≡ -8 (mod.10) Falso. 42 = 10.4 + 2 ≡ 2 e -8 = 10.(-1) + 2 ≡ 2

02 – Verdadeiro (V) ou falso (F) 

(a) x ≡ 3 (mod.5) => x ∈ { ....–7, -2, 3, 8, 13 .... } 
Verdadeiro. –7 = 5.(-2) + 3  ≡ 3. Somando 5 a –7, obtém-se os demais elementos.

(b) 5 ≡ -1 (mod.6) e -1  ≡ -7 (mod.6) => 5  ≡ -7 (mod.6) 
Verdadeiro. Transitividade da relação mod.

03 – Achar o menor inteiro positivo que represente a soma:

(a) 5 + 3 + 2 + 1 + 8 (mod. 7)
Solução: 5 + 2 ≡ 0 (mod.7), 3 + 1  ≡ 4 (mod.7)  8 ≡ 1 (mod.7).
Portanto, 5 + 3 + 2 + 1 + 8 ≡ 0 + 4 + 1  ≡ 5 (mod. 7) .  Resposta: 5

(b) 2 + 3 – 1 + 7 – 2 (mod.4)
Solução: 2 + 3 ≡ 1 (mod 4) e -1 + 7 – 2 = 4 ≡ 0 (mod. 4)
Portanto: 2 + 3 – 1 + 7 – 2  ≡ 1 + 0 ≡ 1 (mod. 4) . Resposta. 1

04 - Sabendo-se que 1066  ≡ 1766 (mod. m), achar todos os possíveis valores do módulo m.
Solução: Sejam a e b os quociente das divisões de 1066 e 1766 por m e x o resto.

Os restos são iguais pois 1066 e 1766 são côngruos (mod. m). Assim temos: 1066 = ma + x e 1776 = mb + x.

Subtraindo a primeira igualdade da segunda resulta: 1776 – 1066 = ma + x – (mb + x) = ma – mb. Portanto: 710 = m(a – b). Isto implica que m é divisor de 710, ou seja m = 2, 5, 10, 142, 355 e 710.

05 – Exprimir que “n é ímpar”  de três outras maneiras.
Solução: (1) n ≡ 1 (mod. 2) (2) n ≡ - 1 (mod. 2) (3) n = 2k + 1 (4) n = 2k – 1

06 – Achar todos os inteiros x tais que 0 < x < 15 e 3x ≡ 6 (mod. 15)

Solução: Se 3x ≡ 6 (mod.15), temos 3x  = 15.a  + 6 => 3x – 15.a = 6. Como pode ser observado, a última igualdade é uma equação diofantina. Observe que mdc(3, 15) = 3.

Uma solução particular imediata é x = 7 e a = 1. Assim,  x = 7  + (-15/3)t  = 7 – 5t  e  a = 1 – (3/3)t = 1 – t. Como 0 < x < 15, temos:
7 – 5t > 0 => -5t > - 7 => t <  7/5   e 7 – 5t < 15 => -5t < 8 => t > -8/5.
Os valores inteiros de t são 1, 0, -1. Nesses casos temos para o valor de x:  x = 7 –5.1 = 2;  x = 7 – 5.0 = 7  e x = 7 – 5(-1) = 12. Resposta: 2, 7 e 12.

07 – Achar todos os inteiros x tais que 1 < x < 100 e x ≡ 7 (mod. 17)

Solução: Como x ≡ 7, (mod.7) temos:  x = 17.a + 7 => x – 17a = 7 .
Uma solução particular  imediata para  a equação acima é x = -10 e a = -1.

As  demais soluções x = -10 + (-17/1)t = -10 - 17t   e  a = -1 – (1/1)t  = -1 – t
Como 0 < x < 100,  podemos tirar: -10 – 17t > 0 => t < -10/17 e -10 – 17t < 100 => t > - 110/17. De onde se conclui –5 < t < -1, pois t é um inteiro. Os valores de t são então: - 6,  -5,  -4, -3, -2, -1 e em consequência, temos x = -10 –17(-6) = 92; x = -10 – 17(-5) = 75; x = -10 – 17(-4) = 58; x = -10 – 17(-3) = 41; x = -10 –17(-2) – 24 e x = -10 –17(-1) = 7.

Resposta:- 7, 24, 41, 58, 75 e 92.

08 – Sabendo-se que k ≡ 1 (mod. 4), mostrar que 6k + 5 ≡ 3 (mod. 4)

Solução: 
Se k ≡ 1 (mod. 4) então k = 4n + 1 (deixa resto 1 na divisão por 4)
6k + 5 = 6(4n + 1) + 5 = 24n + 6 + 5 = 24 n + 8 + 3 = 4(6n + 2) + 3 => 6k + 5 deixa resto 3 na divisão por 4. Portanto: 6k + 5 ≡ 3 (mod. 4). Cqd.

9 – Mostrar, mediante um exemplo, que a2 ≡ b2  (mod.m) não implica a ≡ b (mod.m).

Solução: 362 ≡ 42 (mod. 4) pois 36 = 9.4 + 0 e 4 = 4.1 + 0. Porém 6 ~≡ 4 (mod. 4)

10 – Mostrar que todo primo (exceto 2) é congruente módulo 4 a 1 ou 3.

Solução: Todo número inteiro tem uma das formas 4n, 4n + 1, 4n + 2 ou 4n + 3.
Se k é primo, k = 4n e K = 4n + 2 são pares. Portanto, exceto k =2, são números compostos.
Assim, se k é primo (exceto 2) ele terá uma das formas 4kn+1 ou 4n + 3. Portanto, os restos das divisões por 4 serão 1 ou 3, o que implica que são congruentes com 1 ou 3. Cqd.

11 – Mostrar que todo primo (exceto 2 ou 3) é congruente módulo 6 a 1 ou 5.

Solução: Todo número inteiro é expresso por uma das formas 6n, 6n + 1, 6n + 2, 6n + 3, 6n + 4 e 6n + 5. As formas 6n, 6n + 2, 6n + 4 são características de números pares, inclusive o 2 (para 6n + 2, com n = 0). Portanto, todos, exceto 2, são compostos.
A forma 6n + 3, caracteriza os múltiplos de 3.  Para n = 0, 6n + 3 = 3  que é primo. Para os demais, 6n + 3 são compostos. Assim, as formas 6n + 1 e 6n + 5 podem constituir números primos, exceto o 2 e o 3 conforme acima. Deste modo, os restos das divisões dos primos, exceto 2 ou 3, por 6, são 1 ou 5.  Disto se conclui que os primos, exceto 2 e 3, são congruentes com 1 ou 5. Cqd.

12 – Mostrar que 1110  ≡ 1 (mod. 100).

Solução: 112 = 121  ≡ 21 (mod.100)
112 . 112 = 104 ≡ 21 x 21 = 441 ≡ 41 (mod.100)
114.114 ≡ 41.41 = 1681  ≡ 81 (mod. 100)
118.112 = 1110 ≡ 81x21 = 1701 ≡ 1 (mod. 100)

13 - Mostrar que 41 divide 220 – 1.

Solução: Se 41 | 220 – 1, então 220 – 1 ≡ 0 => 220 ≡ 1 (mod.41).
Portanto, devemos provar que 220 é congruente com 1 mod. 41.
Temos: 27 = 128 ≡ 5 mod.41 pois 128 = 3.41 + 5.
26 = 64 ≡ 23 (mod. 41), pois 64 = 41.1 + 23
220 = 27 x 27 x 26 ≡ 5 x 5 x 23 = 575 = 41.24 + 1 ≡ 1 (mod. 41)

14 – Achar os restos das divisões de 250 e 4165 por 7.
Solução:
(1) 250 = 23.16 + 2 = (23)16.22  ≡ (1)16 .4 ≡ 1.4   ≡ 4. Portanto, o resto da divisão de 250 por 7 é 4.
Obs. Note que 23 = 8 = 7.1 + 1  ≡ 1 (mod. 7).

(2) 41 ≡ -1 mod (7) pois 41 = 7.6 – 1.
4165 ≡ (-1)65 = -1. Portanto –1 é o resto. O resto positivo será –1 + 7 = 6.

15 – Mostrar que

(a) 89 | 244 – 1.
Solução: Se 89 | 244 – 1 então, 244  - 1 = 89.m   244 = 89m + 1. Portanto, devemos provar que 244 ≡ 1 (mod. 89).
A potencia inteira de dois imediatamente maior que 89 é 128 = 27  e 128 = 89.1 + 39  ≡ 39 (mod.89)
27 x 27  = 214 ≡ 39 x 39  = 1521 = 17.89 + 8  ≡ 8
244 = 214 x 214 x 214 x22  ≡ 8 x 8 x 8 x 4 = 128 x 16  ≡ 39 x 16  = 624 = 89.7 + 1 ≡ 1 (mod. 89). Portanto, 244  ≡ 1 (mod.89)

(b) 97 | (248 – 1)
Solução: Conforme item anterior, devemos provar que 248 ≡1 (mod. 97)
Tomemos  a potência 29 = 512 = 5.97 + 27  ≡ 27 (mod. 97)
218 = 29 x 29  ≡ 27 x 27 = 729 =  7 x 97  + 50  ≡ 50 (mod. 97)
236 = 218 x 218 ≡ 50 x 50 = 2500 = 25.97 + 75  ≡ 75 (mod. 97)
248 = 236 x 29 x 23 ≡ 75 x 27 x 8  ≡ 75 x 216  ≡ 75 x ( 97.2 + 22)  ≡ 75 x 22 = 1650 = 97.17 + 1 ≡ 1 (mod. 97). Portanto, 248 ≡ 1 (mod. 97) ou 97 | 248 - 1 .

16 – Demonstrar que, se a ≡ b (mod. m) então mdc(a, m) = mdc(b, m).

Solução: Se a ≡ b (mod. m) então a = xm + r e b = ym + r.
Para r = 0, m é um divisor de a => mdc(a, m) = m. Da mesma forma, m é um divisor de b => mdc(b, m) = m. Assim, concluímos que mdc(a, m) = m = mdc(b, m).
Para r  0, mdc(a, m) = mdc(m, r) e mdc(b, m) = mdc(m, r) de acordo com o algoritmo de Euclides ou processo das divisões sucessivas. Assim, mdc(a, m) = mdc(m, r ) = mdc(b, m).

17 – Mostrar, mediante um exemplo, que ak  ≡ bk (mod. m) e k ≡ j não implica aj  ≡ bj.

Solução: 82 ≡ 62 (mod. 7) pois 82 = 64 = 7.9 + 1  e 62 = 36 = 5.7 + 1   e 2 ≡ 9 (mod. 7)
89 = 82. 82. 82. 82.8 ≡ 1.1.1.(7.1 + 1) ≡ 1.1.1.1 ≡ 1
69 = 62.62.62.62.6 ≡ 1.1.1.6 ≡ 6 que não congruente com 89.

18 – Demonstrar as seguintes proposições:

(a) Se a é um inteiro ímpar então a2  ≡ 1 (mod. 8)
Solução: Todos os inteiros são de uma das formas, 4k, 4k + 1, 4k + 2  ou 4k + 3.  Serão ímpares as formas 4k + 1 e 4k + 3.
Assim, a2 = (4k + 1)2 = 16k2 + 8k + 1 = 8(2k2 + k) + 1 = 8n + 1  ≡ 1 (mod. 8)
a2 = (4k + 3)2 = 16k2 + 24k + 9 = 16k2 + 24k + 8 + 1 = 8(2k2 + 3k + 1) + 1  ≡ 1 (mod. 8)

(b) Se a é um inteiro qualquer, então a3  ≡ 0, 1 ou 8 (mod. 9).
Solução: Todo número inteiro tem a forma: 3n, 3n + 1 ou 3n + 2.  Para os seus cubos, temos:
(3n)3 = 27n3 = 9(3n3) + 0  ≡ 0 (mod.9)
(3n + 1)3 = (3n)3 + 3.(3n)2.1 + 3(3n).12 + 13 = 27n3 + 27n2 + 9n + 1 = 9(3n3 + 3n2 + n) + 1  ≡ 1 (mod. 9)
(3n + 2)3 = (3n)3 + 3.(3n)2.2 + 3(3n).22 + 23 = 27n3 + 54n2 + 36n + 1 = 9(3n3 + 6n2 + 4n) + 8  ≡ 8 (mod. 9).

(c) Se a é um inteiro qualquer, então a3   ≡ a (mod. 6).
Solução: Qualquer inteiro é de uma das formas: 6k ≡ 0 , 6k + 1 ≡ 1, 6k + 2 ≡ 2, 6k + 3 ≡ 3, 6k + 4 ≡ 4, 6k + 5 ≡ 5. Elevando ao cubos estas formas temos: (6k)3 = 6(6k3) ≡ 0  ≡ 6k (mod. 6)
(6k + 1)3 = (6k)3 + 3(6k)2 + 3(6k) + 1 = 216k3 + 108k2 + 18k + 1 = 6(36k3 + 18k2 + 3k) + 1  ≡ 1 ≡ 6k + 1 (mod. 6)
(6k + 2)3 = (6k)3 + 3(6k)2.2 + 3(6k).22 + 23  = 216k3 + 216k2 + 72k + 8 = 6(36k3 + 36k2 + 12k + 1) + 2 ≡ 2 ≡ 6k + 2 (mod. 6)
(6k + 3)3 = (6k)3 + 3(6k)2.3 + 3(6k).32 + 9 = 216k3 + 324k2 + 162k + 9 = 6(36k3 + 54k2 + 27k + 1) + 3 ≡ 3 ≡ 6k + 3 (mod. 6)
(6k + 4)3 = (6k)3 + 3(6k)2.4 + 3(6k).42 + 27 = 216k3 + 432k2 + 432k + 64 = 6(36k3 + 72k2 + 72k + 10) + 4 ≡ 4 ≡ 6k + 4 (mod. 6)
(6k + 5)3 = (6k)3 + 3(6k)2.5 + 3(6k).52 + 1 = 216k3 + 540k2 + 450k + 125 = 6(36k3 + 54k2 + 27k + 20) + 5 ≡ 5 ≡ 6k + 5 (mod. 6).

19 – Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 4.

Solução: Um conjunto é um sistema completo de restos módulo 4, se os elementos desse conjunto forem côngruos com 0, 1, 2 e 3.

(a) { -2, -1, 0, 1} 
Solução: Considerando o módulo 4, temos
- 2  ≡ 2 pois –2 = 4(-1) + 2
- 1  ≡ 3 pois –1 = 4(-1) + 3
Portanto, temos o conjunto equivalente (0, 1, 2, 3}. Assim, o conjunto dado é um sistema completo de restos.

(b) {0, 4, 8, 12}
Solução:  
4 = 4.1 + 0  ≡ 0
8 = 4.2 + 0 ≡ 0
12 = 12.3  + 0   ≡ 0.
Portanto o conjunto dado é equivalente ao conjunto { 0 }, de onde se conclui que não é um conjunto completo de restos.

(c) { -13, 4, 17, 18 }
Solução: 
-13 = 4(-4) + 3  ≡ 3
  4 = 4( 1) + 0  ≡ 0
17 = 4.4 + 1  ≡ 1
18 = 4.4 + 2  ≡ 2
O conjunto dado é equivalente a {0, 1, 2, 3}. Portanto é um conjunto completo de restos módulo 4.

(d) –5, 0, 6, 22
Solução:
-5 = 4(-2) + 3  ≡ 3
0  ≡  0
6 = 4.1 + 2  ≡  2
22 = 4.5 + 2
O conjunto é equivalente a {0, 2, 3}. Portanto, não é um conjunto completo.

Respostas: São conjuntos completos os das letras a e c.

20 – Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 6.

Solução: Um sistema completo de restos módulo 6 deve ser equivalente ao conjunto {0, 1, 2, 3, 4, 5}

(a) { 1, 2, 3, 4, 5} . Resposta: Não é um conjunto completo. Falta o 0 (zero)

(b) {0, 5, 10, 15, 20, 25}. Resposta: Sim pois os restos da divisão por 6 são respectivamente: 0, 5, 4, 3, 2, 1.

(c) {-4, -3, -2, -1, 0, 1}. Resposta: Sim, pois  -4  ≡ 2, -3  ≡ 3, -2  ≡ 4, -1  ≡ 5 (mod. 6) . Assim temos {0, 1, 2, 3, 4, 5}

(d) {17, -4,  6, 7, 10, 3}. Resposta: O resto da divisão de 17 por 6 é 5, portanto 17 ≡ 5.
- 4 ≡ 2 ; 6 ≡ 0 ; 7 ≡ 1 ;  10 ≡ 4 .Temos então o conjunto {0, 1, 2, 3, 4, 5}. O conjunto é um conjunto completo de restos módulo 6. Resposta: são conjuntos completos os indicados nas letras (b) e (c)

21 – Achar um sistema completo de restos {p1, p2, ... p7} módulo 7, tal que todo pi é primo.

Solução: Tomando p1 = 2, p2 = 3, p3 = 5 , p4 = 7 ≡ 0. Estes são imediatos. Faltam os primos congruentes a 4 e 6. Devemos escolher um múltiplo de 7 somado a 4 e um múltiplo de 7 somado a 6 e um múltiplo de 7 que somado a 1 que resultem em primos.
Para 4 temos: p5 = 11 ≡ 4 (mod 7)
Para 6 temos: p6 = 13 ≡ 6 (mod. 7)
Para 1 temos: p7 = 28 = 7.4 + 1 ≡ 1
Portanto, um sistema de restos módulo 7, formado por primos é {2, 3, 5, 7, 11, 13, 28}.

22 – Achar um sistema completo de restos módulo 7 formado só de múltiplos não negativos de 4.

Solução: Inicialmente devemos ter 4x = 7y + 1 => 4x – 7y = 1. Uma solução inteira para essa equação é x = 9 e y =5. Assim, basta tomar os múltiplos de 4 a partir de 36.
Temos então: P1 = 36 ≡ 1; P2 = 40 ≡ 5; P3 = 44 ≡ 2; P4 = 48 ≡ 6 ; P5 = 52 ≡ 3; P6 = 56 ≡ 0; P7 = 60  ≡ 4. Assim temos: { 36, 40, 44, 48, 52, 56, 60}