Lista p3

Prévia do material em texto

MAT034 - A´lgebra A - Lista de problemas 3
Bhalchandra D. Thatte, Departamento de Matema´tica, UFMG
bhalchandra@mat.ufmg.br
October 9, 2013
Congrueˆncias
1. Define a ≡ b (mod n) para a, b, n ∈ Z, n > 0.
2. Verifique que ≡ e´ uma relac¸a˜o equivaleˆncia.
3. Prova da Teorema 4.2 em Burton.
4. Prove que 41 | 220 − 1, 89 | 244 − 1 e 97 | 248 − 1.
5. Prove que 39 | 53103 + 10353 e 7 | 111333 + 333111.
6. Expressar 877 em base 2, 5, 7, 11.
7. Calcule 7141 (mod 123), 5168 (mod 81), 3211 (mod 97) usando o algoritmo exponencial
binomial.
8. Prove que para todos n ≥ 1, 27 | 25n+1 + 5n+2 e 43 | 6n+2 + 72n+1.
9. Mostre que se p e´ primo e n < p < 2n enta˜o
(
2n
n
) ≡ 0 (mod p).
10. Prove que se a na˜o e´ par enta˜o para todos n ≥ 1, a2n ≡ 1 (mod 2n+2).
11. Resolva as equac¸o˜es seguintes em inteiros
(a) 3x + 7y = 11,
(b) 2x + y = 3,
(c) 231x + 217y = 76,
(d) 182x + 42 = 54.
12. Resolva as equac¸o˜es seguintes
(a) 25x ≡ 15 (mod 29)
(b) 5x ≡ 2 (mod 26)
(c) 6x ≡ 15 (mod 21)
(d) 36x ≡ 8 (mod 102)
1
(e) 140x ≡ 133 (mod 301)
13. Use o algoritmo de Euclid para calcular x, y tal que 231x + 147y = 105.
14. Procure todas soluc¸o˜es dos sistemas de equac¸o˜es seguintes. Use o teorema Chineˆs de resto
quando e´ poss´ıvel.
(a) x ≡ 3 (mod 5), x ≡ 5 (mod 7), x ≡ 7 (mod 11), x ≡ 11 (mod 5).
(b) 2x ≡ 3 (mod 5), 3x ≡ 5 (mod 7), 5x ≡ 7 (mod 11), 7x ≡ 11 (mod 5).
(c) x ≡ 3 (mod 6), x ≡ 5 (mod 15), x ≡ 7 (mod 20).
(d) 2x ≡ 1 (mod 5), 3x ≡ 9 (mod 6), 4x ≡ 1 (mod 7), 5x ≡ 9 (mod 11).
(e) 17x ≡ 3 (mod 210). (Use as soluc¸o˜es do sistema 17x ≡ 3 (mod 2), 17x ≡ 3 (mod 3),
17x ≡ 3 (mod 5), 17x ≡ 3 (mod 7).)
(f) 7x + 3y ≡ 10 (mod 16) & 2x + 5y ≡ 9 (mod 16).
(g) 8x + 3y ≡ 10 (mod 16) & 2x + 5y ≡ 9 (mod 16).
(h) 4x + 3y ≡ 7 (mod 16) & 2x + 5y ≡ 9 (mod 16).
2