MAT1310_Lista2_R (1)
3 pág.

MAT1310_Lista2_R (1)


DisciplinaMatemática Discreta3.520 materiais76.461 seguidores
Pré-visualização1 página
DEPARTAMENTO DE MATEMA´TICA PUC-RIO
MAT1310 \u2013 MATEMA´TICA DISCRETA \u2013 2012.1
Algumas respostas e soluc¸o\u2dces da Lista de Exerc´\u131cios II
3) Temos que encontrar as soluc¸o\u2dces da equac¸a\u2dco 19x+ 33y = 1000 com x, y inteiros na\u2dco-
negativos. Primeiro encontramos uma soluc¸a\u2dco particular. Comec¸amos calculando mdc(33, 19)
pelo algoritmo de Euclides:
1 1 2 1
33 19 14 5 4 1
Usando isso, temos
1 = 5 \u2212 4 = 5 \u2212
(
14 \u2212 2× 5
)
= 3× 5 \u2212 14
= 3×
(
19 \u2212 14
)
\u2212 14 = 3× 19 \u2212 4× 14
= 3× 19 \u2212 4×
(
33 \u2212 19
)
= 7× 19 \u2212 4× 33
Multiplicando por 1000, achamos uma soluc¸a\u2dco particular da equac¸a\u2dco 19x + 33y = 1000, a
saber, x0 = 7000, y0 = \u22124000. Como mdc(19, 33) = 1, a soluc¸a\u2dco geral e´ x = 7000 \u2212 33t,
y = \u22124000 + 19t, onde t e´ um inteiro qualquer. Temos x \u2265 0 \u21d4 t \u2264 7000/33 ' 212.1 e
y \u2265 0 \u21d4 t \u2265 4000/19 ' 210.5. Logo as u´nicas possibilidades sa\u2dco t = 211 e t = 212, o que
da´ (x, y) = (37, 9) e (x, y) = (4, 28), respectivamente. Portanto as possibilidades de compra
sa\u2dco 37 embalagens de 19g e 9 embalagens de 33g, ou 4 embalagens de 19g e 28 embalagens de
33g.
4) 10 selos de 5 reais.
5 selos de 3 reais e 7 selos de 5 reais.
10 selos de 3 reais e 4 selos de 5 reais.
15 selos de 3 reais e um selo de 5 reais.
5)
(a) Como mdc(14, 91) = 7 e 7 - 3, a equac¸a\u2dco na\u2dco tem soluc¸a\u2dco em Z2.
(b) (x, y) = (18\u2212 35 k,\u22122 + 4 k) com k \u2208 Z.
7) 29 de novembro.
10) (a) Escreva (n + 1)! + k = k ·
(
(n+ 1)!
k
+ 1
)
e observe que se k \u2264 n + 1, enta\u2dco
(n+ 1)!
k
\u2208 N.
11) Observe que 641 e´ um nu´mero primo e na\u2dco divide 3355. Enta\u2dco usando o Pequeno
Teorema de Fermat, 641 divide 3355641\u22121 \u2212 1 e o resto da divisa\u2dco de 3355640 por 641 e´ 1.
12) 1
13) 5
14) 1
15 Temos que encontrar 2x mod 10. As pote\u2c6ncias de 2 mo´dulo 10 sa\u2dco 21 \u2261 2, 22 \u2261 4,
23 \u2261 8, 24 \u2261 6, 25 \u2261 2, 4, 8, 6, . . . , repetindo com per´\u131odo 4. Portanto temos que simplificar
32010 mod 4. As pote\u2c6ncias de 3 mo´dulo 4 sa\u2dco 31 \u2261 3, 32 \u2261 1, 33 \u2261 3, . . . , repetindo com
per´\u131odo 2. Como 2010 e´ par, temos x = 32010 \u2261 1 mod 4. Portanto 2x \u2261 21 \u2261 2 mod 10. A
resposta e´ 2.
16) 719
1002 \u2261 7 (mod 10).
17) 1
18) 177219
2011 \u2261 3 (mod 10).
19) (a) V (b) F
20)
(a) Falso. Contra-exemplo: m = 4, a = b = 2.
(b) Falso.
(c) Falso.
(d) Falso. Contra-exemplo: a = b = 1, m = 4. A\u131´ (a+ b)m \u2261 0 6\u2261 2 \u2261 am + bm mod m.
Obs: Esta fo´rmula vale se m e´ primo. Isso sugere procurar um contra-exemplo com
m = 4.
21) 103 e´ primo, enta\u2dco por Fermat, 4102 \u2261 1 (mod 103) e 6102 \u2261 1 (mod 103). Assim
62420 = (6102)23 · 674 \u2261 674 (mod 103) \u2261 38 (mod 103),
4128 = 4102 · 426 \u2261 426 (mod 103) \u2261 2 (mod 103) e
62420 + 4128 \u2261 40 (mod 103).
Temos, pelo algoritmo de Euclides, mdc(40, 103) = 1 = 40·(\u221218)+103·7 = 1, logo 40·(\u221218) \u2261
1 (mod 103). Como (\u221218) \u2261 85 (mod 103), a resposta e´ 85.
22)
(a) Tre\u2c6s sa\u2dco imediatos: 0 na\u2dco tem inverso e os inversos de 1 e 10 \u2261 \u22121 sa\u2dco eles pro´prios.
Para os outros, fatoramos nu´meros que sa\u2dco \u2261 1. Temos 1 \u2261 12 = 2 × 6 = 3 × 4
(logo 2\u22121 \u2261 6 etc), 1 \u2261 23 (primo), 1 \u2261 34 = 2 × 17 (na\u2dco adianta), 1 \u2261 45 = 5 × 9,
1 \u2261 56 = 7× 8. Resposta:
x 0 1 2 3 4 5 6 7 8 9 10
x\u22121 6 \u2203 1 6 4 3 9 2 8 7 5 10
(b) A tabela do item anterior e´ u´til aqui. Multiplicando a primeira equac¸a\u2dco por 2\u22121 \u2261 6,
temos x + 7 y \u2261 6. Subtraindo esta equac¸a\u2dco da segunda, temos 3y \u2261 2. Multiplicando
por 3\u22121 \u2261 4, temos y \u2261 8. Da segunda equac¸a\u2dco, x \u2261 4\u2212 4y \u2261 5.
24) Como 10 \u2261 1 mod 9, todas as pote\u2c6ncias de 10 sa\u2dco congruentes a 1 mo´dulo 9. Portanto
qualquer inteiro positivo e´ congruente mo´dulo 9 a` soma dos seus d´\u131gitos (em decimal). Por
exemplo,
2012 = 2 · 103 + 0 · 102 + 1 · 101 + 2 · 100 \u2261 2 + 0 + 1 + 2 \u2261 5 mod 9.
No caso em questa\u2dco, x \u2261 50(1 + 2 + 3 + 4 + 5) mod 9. Simplificando, x \u2261 5 · 6 \u2261 3. O
resto da divisa\u2dco de x por 9 e´ 3.
25) {0, 1, 3, 4, 5, 9}
28) (a) 23 + 30 k, com k \u2208 Z
(b) (c) 55 + 60 k, com k \u2208 Z
30) x = 37 (52 k \u2212 42) + 9 = 52 (37 k \u2212 30) + 15
{379, 2303}
31) Mostre que a diferenc¸a entre os inteiros e´ mu´ltiplo de 10.
32) (a) 25 (b) 82
32) 43
34) (a) 13 (b) 47 (c) 78
35) (a) 35 (b) 82 e 41 (c) 51 e 85
36)
(a) (37\u2212 1) (41\u2212 1) = 36 · 40 = 1440
c deve satisfazer mdc(c, 1440) = 1, logo c = 131.
(b) 500131 \u2261 607 mod 1517
(c) d e´ o inverso multiplicativo de 131 mo´dulo 1440:
131 · 11 + 1440 · (\u22121) = 1
1 \u2261 131 · 11 mod 1440 e d = 11
(d) 511 \u2261 446 mod 1517
37) (a) A=10, B=11, . . .
(b) c = 7
(c) 64\u2212 119\u2212 6\u2212 119\u2212 · · ·
38) 2510271029349914992118231310
39) PUC