Elementos_de_Matematica_Finita_Exercicio

Prévia do material em texto

Elementos de Matemática Finita
Exercícios Resolvidos 1 - Algoritmo de Euclides; Indução
Matemática; Teorema Fundamental da Aritmética
1. Considere os inteiros a = 2406 e b = 654.
(a) Encontre d = mdc(a, b), o máximo divisor comum entre a e b.
(b) Encontre inteiros x e y, que satisfaçam a identidade de Bézout ax+ by = d.
(c) Resolva a equação diofantina ax+ by = 102, com x, y inteiros e y > 0.
(d) É possível resolver a equação ax+ by = 184 com x, y inteiros?
Resolução: (a) Para determinar o mdc, usamos o algoritmo de Euclides, fazendo
sucessivas divisões com resto:
2406 = 3 · 654 + 444
654 = 1 · 444 + 210
444 = 2 · 210 + 24
210 = 8 · 24 + 18
24 = 1 · 18 + 6
18 = 3 · 6 + 0.
Logo
mdc(2406, 654) = mdc(654, 444) = · · · = mdc(18, 6) = 6.
(b) Vamos usar o desenvolvimento do algoritmo de Euclides na alínea (a)
para obter uma identidade da forma ax+ by = 6. Assim, escrevemos:
6 = 24 + (−1) · 18 =
= 24 + (−1) · (210 − 8 · 24) =
= (−1) · 210 + 9 · 24 =
= (−1) · 210 + 9 · (444 − 2 · 210) =
= 9 · 444 + (−19) · 210 =
= 9 · 444 + (−19) · (654 − 444) =
= (−19) · 654 + 28 · 444 =
= (−19) · 654 + 28 · (2406 − 3 · 654) =
= 28 · 2406 + (−103) · 654.
Assim, (x, y) = (28,−103) é uma solução.
(c) Para resolver a equação ax+by = 102 primeiro verificamos que 6 é divisor
1
de 102. De facto, 102 = 17 · 6. Como a, b e c = 102 são todos divisíveis por
6, a equação dada é equivalente a
2406
6
x+
654
6
y =
102
6
⇔ 401x+ 109y = 17.
A identidade da alínea (a) mostra que x′ := 28, y′ := −103 é solução da
equação 401x + 109y = 1 (pois esta última equivale a 2406x + 654y = 6).
Assim, (x0, y0) := (17·(28), 17·(−103))) = (476,−1751) é solução da equação
pedida. No entanto, a coordenada y é negativa. Para encontrar uma outra
solução com y positivo, usamos o facto de que todas as soluções de 401x +
109y = 17 (note-se que 401 e 109 são primos entre si) são dadas por
(xk, yk) = (x0 + 109k, y0 − 401k) , k ∈ Z.
Assim, basta encontrar k inteiro de modo a ter −1751−401k positivo. Temos
que ter k ≤ −5. Por exemplo, com k = −5, obtemos (xk, yk) = (−69, 254).
[Verificação: 401 · (−69) + 109 · 254 = 17.]
(d) Como 184/6 = 30 + 23 , 6 não é divisor de 184, pelo que a equação dada
não tem soluções inteiras.
2. Mostre as seguintes propriedades da relação de divisibilidade, com a, b ∈ Z:
(a) Para todos os inteiros a, k, temos a | ka;
(b) Se a | b para todo o a ∈ Z, então b = 0; Se a | b para todo o b ∈ Z, então
a = ±1;
(c) Sejam a, b ∈ Z. Se a|b e b|a então |a| = |b|;
Resolução: (a) Sejam a, k ∈ Z. Por definição a|ka ⇔ ∃q ∈ Z tal que ka = qa.
Esta afirmação é válida com q := k, pelo que a|ka verifica-se sempre.
(b) A expressão “a|b ∀a ∈ Z”, significa, por definição, que “b é um inteiro tal
que, para todo a inteiro, existe q ∈ Z, tal que b = qa”. Seja a > b > 0; Então
a|b é impossível (pois para isso teríamos q = b
a
, que não é inteiro). Seja
0 > b > a; então novamente, a|b é impossível (pela mesma razão). Assim, b
só pode ser 0. De facto, com b = 0 basta escolher q = 0 para termos 0 = 0 ·a
para todo o a ∈ Z.
A expressão “a|b ∀b ∈ Z”, significa, por definição, que “a é um inteiro tal que,
para todo b inteiro, existe q ∈ Z, tal que b = qa”. Seja a um número natural
maior que 1. Então a + 1 ∈ N e a não divide a + 1, pois o resto da divisão
de a + 1 por a é 1. Se a = 0 não há forma de encontrar q para resolver a
equação b = q · 0 com b 6= 0. Mas se a = 1, dado b ∈ Z temos sempre 1|b
pois existe q ∈ Z (de facto, q := b) tal que b = q · 1. Assim, se a ∈ N, a
única hipótese é a = 1. Do mesmo modo, se a ∈ −N, verifica-se que a única
hipótese é a = −1.
(c) Sejam a, b positivos. Então a|b e b|a implica que a ≤ b e b ≤ a respecti-
vamente. Logo a = b. Se a é positivo e b negativo, seja c = −b. Aplicando o
raciocínio anterior, temos a = −b. Os outros casos são análogos, pelo que se
sempre se conclui que |a| = |b|.
3. Mostre ou indique um contra-exemplo para as seguintes afirmações:
2
(a) Sejam a, b, c ∈ Z. Se a|bc então a|b ou a|c;
(b) Sejam a, b, q, r ∈ Z tais que a = bq + r. Então (a, b) = (b, r);
(c) Sejam m e n naturais cujas factorizações em primos não contém primos em
comum. Então mdc(m,n) = 1.
(d) Sejam a, b ∈ Z. Se mdc(a, b) = d então mdc(a
d
, b
d
) = 1.
(e) Para a, b ∈ Z, e k ∈ N, temos mdc(ka, kb) = kmdc(a, b).
Resolução: (a) A afirmação é falsa em geral. Por exemplo, se a = 6, b = 3 e
c = 4 temos que a|bc pois 6|12. No entanto, 6 não divide nem 3, nem 4. A
afirmação é verdadeira nos casos em que a é primo (visto nas aulas), ou em
que (b, c) = 1 (ver o problema seguinte).
(b) Seja d = (a, b). Então d | a e d | b. Logo, d | (a − bq) pelo que d | r.
Logo d é um divisor comum a r e a b. Seja c um outro inteiro que divide b e
r simultaneamente. Então também divide a = bq + r. Como c divide a e b,
então divide d (por definição de d = (a, b)). Assim, qualquer divisor comum
a b e r divide d. Conclui-se então que d é o mdc de b e r.
(c) Vamos supor que d|m, com d > 1. Seja p um primo que divide d. Então,
pela transitividade, p|m. Logo, se um inteiro é divisível por d > 1, então
existe pelo menos um primo que o divide. Seja d > 1 um divisor comum a
m e n. Então, há um primo p que divide m e n simultaneamente. Sejam
m = p1 · · · pr e n = q1 · · · qs as factorizações de m e n. Por hipótese, nenhum
dos p’s é igual a um dos q’s. Mas p|p1 · · · pr implica que p = pi para algum
i (estamos a considerar os pi’s podem ser iguais). Da mesma forma p|n
significa que p|q1 · · · qs implica p = qj para algum j. Isto contradiz o facto de
{p1, · · · , pr}∩{q1, · · · , qs} = ∅. Logo, apenas d = 1 divide simultaneamente
m e n.
(d) Se (a, b) = d então, pela aplicação do algoritmo de Euclides, existe solução
inteira de ax+ by = d. Mas a/d e b/d são também inteiros e aquela equação
é equivalente a
a
d
x+
b
d
y = 1.
Seja (a
d
, b
d
) = c. Então temos c|a
d
e c| b
d
, e esta equação implica c|1. Mas isto
quer dizer que c = 1.
(e) Seja d = mdc(a, b). Então kd|ka e kd|kb, porque d|a e d|b. Logo kd é
um divisor comum a ka e kb. Por outro lado, pela identidade de Bézout, é
possível resolver a equação d = ax+ by, com x, y ∈ Z, equação que equivale
a kd = kax + kby. Consideremos c ∈ Z tal que c|ka e c|kb. Pela última
equação c|kd. Assim, por definição, kd é o máximo divisor comum entre ka
e kb.
4. Seja
(
n
k
)
= n!
k!(n−k)! o coeficiente binomial, para n ≥ k ≥ 0. Por convenção,
assumimos que, para outros valores inteiros de n e k,
(
n
k
)
= 0. Mostre, por
indução, que
(
n
k
)
=
n−1
∑
j=0
(
j
k − 1
)
.
3
Resolução: Vamos fixar um k ∈ N. Seja P (n, k) a equação acima, que se pre-
tende mostrar. Seja n = k. Então, a equação fica
(
n
n
)
=
∑n−1
j=0
(
j
n−1
)
=
0 + · · · + 0 +
(
n−1
n−1
)
, (são n − 1 parcelas nulas, quando j < n − 1) que equi-
vale a 1 = 1 (pois 0! = 1). Assim, mostrámos o passo base da indução.
Assumimos agora que a fórmula é válida para n ≥ k. Temos então:
(
n+ 1
k
)
=
(n+ 1)!
k!(n + 1 − k)!
=
(n+ 1)n!
k!(n + 1 − k)!
=
(n + 1 − k)n! + k n!
k!(n + 1 − k)!
=
=
(n+ 1 − k)n!
k!(n + 1 − k)!
+
k n!
k!(n + 1 − k)!
=
=
n!
k!(n − k)!
+
n!
(k − 1)!(n + 1 − k)!
=
(
n
k
)
+
(
n
k − 1
)
=


n−1
∑
j=0
(
j
k − 1
)

 +
(
n
k − 1
)
=
=
n
∑
j=0
(
j
k − 1
)
,
onde a hipótese de indução foi usada na igualdade da penúltima linha.
5. Seja n um natural e sejam b1, · · · , bn números reais positivos. Mostre, por indução,
que a sua média aritmética é superior ou igual á sua média geométrica, isto é:
b1 + · · · + bn
n
≥ (b1 · · · bn)
1
n .
Resolução: Para n = 1 temos um número real b = b1. A desigualdade fica,
b
1 ≥ (b)
1 que é verdadeira. Assumimos agora que a desigualdade acima é
válida para quaisquer b1, · · · , bn reais positivos.
Consideremos então a1, · · · , an+1 reais positivos arbitrários. SejaA := (a1 · · · an+1)
1
n+1 ,
ou seja An+1 = a1 · · · an+1. Assim, existe pelo menos um par de índices dis-
tintos, i, j ∈ [n + 1] = {1, · · · , n + 1} tais que ai ≥ A ≥ aj > 0. Sem perda
de generalidade, podemos assumir que esses índicessão n e n + 1, ou seja,
an ≥ A ≥ an+1 > 0. Isto significa que
0 ≥
1
A
(an −A)(an+1 −A) =
anan+1
A
+A− (an + an+1) (1)
Seja b1 := a1,..., bn−1 := an−1, mas agora bn :=
anan+1
A
. Então, usando a
equação (1) na segunda linha:
a1 + · · · + an+1 = a1 + · · · + an−1 + an + an+1 ≥
≥ a1 + · · · + an−1 +
anan+1
A
+A =
= b1 + · · · + bn +A ≥ n(b1 · · · bn)
1
n +A =
= n(a1 · · · an−1
anan+1
A
)
1
n +A = n(An+1
1
A
)
1
n +A =
= nA+A = (n + 1)A = (n+ 1)(a1 · · · an+1)
1
n+1
como queriamos provar (o passo de indução é usado na terceira linha).
4
6. Considere a seguinte afirmação, evidentemente falsa, em geral:
P (n) :
n
∑
k=0
k =
n2 + n+ 1
2
.
Vamos assumir que a proposição é válida para um dado natural n. Então
n+1
∑
k=0
k = (n+1)+
n
∑
k=0
k = n+1+
n2 + n+ 1
2
=
n2 + 3n + 3
2
=
(n+ 1)2 + (n+ 1) + 1
2
,
que é a afirmação P (n+1). Uma vez que o princípio de indução foi correctamente
aplicado, porque é que P (n) não é verdadeira para todo o natural n?
Resolução: Porque não começámos a indução num certo P (n0) que fosse ver-
dadeiro. De facto, por exemplo P (1) significaria que
∑1
k=0 k = 0 + 1 =
12+1+1
2 =
3
2 , o que é falso. Da mesma forma, P (2) é falsa, etc, pelo que não
conseguimos encontrar o natural n0 a partir do qual aplicar a indução.
7. Seja m = pk11 · · · p
kr
r a factorização de m ∈ Z em primos distintos (todos os ki > 0),
e d > 0. Então d|m se e só a factorização de d é pl11 · · · p
lr
r com li ≥ 0, i = 1, · · · , r.
Resolução: Seja d divisor positivo de m. Seja p um primo que entra na factoriza-
ção de d. Então p|d logo, pela transitividade, p|m ou seja, p|pk11 · · · p
kr
r . Assim
p|pkii para algum i = 1, · · · , r. Mas p|p
ki
i equivale a p|pi (como se verifica
facilmente), ou seja p = pi, para algum i. Concluímos que todos os primos
que entram na factorização de d pertencem a {p1, · · · , pr}. É fácil de ver que
pl11 · · · p
lr
r |p
k1
1 · · · p
kr
r sempre que 0 ≤ li ≤ ki (pois p
k1
1 · · · p
kr
r = q · p
l1
1 · · · p
lr
r ,
para certo q ∈ Z). Reciprocamente, se li > ki então p
li
i não divide p
ki
i ,
e a conclusão segue uma vez que todos os primos nesta factorização foram
considerados distintos (ou seja pi ∤ pj para i e j índices distintos entre 1 e r).
8. Seja φ a função de Euler.
(a) Uma função f : N → N diz-se multiplicativa se f(mn) = f(m)f(n) sem-
pre que m e n sejam primos entre si. Mostre que a função φ de Euler é
multiplicativa.
(b) Prove que, se p1, · · · , pr são os inteiros que dividem um dado natural m ∈ N,
então
φ(m) = m
(
1 −
1
p1
)
· · ·
(
1 −
1
pr
)
.
Resolução: (a) Por definição, φ(n) = |Sn|, onde Sn é o conjunto de naturais ≤ n
que são primos com n. Sejam m,n dois naturais primos entre si, (m,n) = 1.
Vamos encontrar uma bijecção entre Smn e o produto cartesiano Sm × Sn, o
que basta para mostrar:
φ(mn) = |Smn| = |Sm × Sn| = |Sm| · |Sn| = φ(m)φ(n).
5
Definimos então:
ψ : Smn → Sm × Sn
a 7→ (am, an)
onde, para cada a ∈ Smn, definimos am ∈ [m] := {1, · · · ,m} e an ∈ [n] como,
respectivamente, o resto da divisão inteira de a por m, e o resto da divisão
por n. Primeiro, verificamos que ψ está bem definida. De facto, se a ∈ Smn
então (a,mn) = 1. Logo, (a,m) = 1 e (a, n) = 1 (de verificação elementar,
ou pelo teorema fundamental da aritmética). Pelo algoritmo de Euclides,
(a,m) = (m,am) = (a, n) = (n, an) = 1. Assim, ψ está bem definida pois
am ∈ Sm e an ∈ Sn. (Note-se que os casos am = 0 ou an = 0 não podem
ocorrer). Vamos agora verificar que ψ é bijectiva. Para a sobrejectividade,
seja (b, c) ∈ Sm × Sn ⊂ [m] × [n]. Temos que encontrar a ∈ Smn tal que
ψ(a) = (b, c), ou seja (b, c), são os restos da divisão de algum a ∈ Smn por m
e por n. Como m e n são primos, sabemos que a equação xm− yn = c − b
tem solução, para algum par de inteiros (x, y) ∈ Z2. Assim, seja
a′ := xm+ b = yn+ c. (2)
Podemos ver facilmente que a′ é primo commn, ou seja (a′,mn) = 1 (o que se
deixa ao leitor). Somando um múltiplo apropriado de mn, podemos garantir
que a = a′ + kmn ∈ [mn]. Assim, provámos que ψ é sobrejectiva. Suponha-
se agora que ψ(a) = ψ(a′) = (am, an). Isso corresponde a encontrar outra
solução da equação (2). Como as soluções são parametrizadas por (x, y) =
(x0 + kn, y0 + km), quaisquer duas soluções a e a′ diferem por um múltiplo
de mn, e concluimos que existe uma única solução em [mn] = {1, · · · ,mn}.
Assim, ψ é sobrejectiva e injectiva, pelo que é bijectiva, como pretendido.
(b) Vamos usar os casos simples, em que sabemos φ(pk) = pk − pk−1 quando
p é primo (no caso de pk é fácil ver que os naturais ≤ pk que não são primos
com pk são todos os múltiplos de p, de 1 até pk, e portanto são exactamente
pk−1 números). Assim, seja m = pk11 · · · p
kr
r a factorização de m em potências
de primos. Usamos agora a propriedade multiplicativa da alínea (a), dado
que (pkii , p
kj
j ) = 1 sempre que i 6= j. Temos então:
φ(nm) = φ(pk11 · · · p
kr
r ) =
= φ(pk11 ) · · · φ(p
kr
r ) =
= (pk11 − p
k1−1
1 ) · · · (p
kr
r − p
kr−1
r ) =
= pk11 · · · p
kr
r
(
1 −
1
p1
)
· · ·
(
1 −
1
pr
)
=
= m
(
1 −
1
p1
)
· · ·
(
1 −
1
pr
)
como pretendido.
6