KTH Matematik

5B1118 Diskret Matematik Kontrollskrivning 1 Måndagen den 15 Mars, 2004 Lösning

(1) (3p) Betrakta följande delmängderna av ℤ^{+}:

A = {n ∈ ℤ^{+}|n ≤ 1000 och n = k^{2}, där k ∈ ℤ^{+}}
B = {n ∈ ℤ^{+}|n ≤ 1000 och n = h^{3}, där h ∈ ℤ^{+}}

Beräkna |A ∪ B|.

A = {1^{2}, 2^{2}, ..., 31^{2}} och {1^{3}, 2^{3}, ..., 10^{3}}. Så |A| = 31 och |B| = 10. Enligt inklusion-exklusionsprincipen är:

|A ∪ B| = |A| + |B| − |A ∩ B|

Vi ska beräkna kardinalitaten av A ∩ B = {n ∈ ℤ^{+}|n ≤ 1000 och n = k^{2} = h^{3}, där k, h ∈ ℤ^{+}}. Men om k^{2} = h^{3} så k = m^{3} och h = i^{2} där i, m ∈ ℤ^{+}. Vi ska hitta vilka elemnt in B är på formen i^{6}. Del finns bara 1, 64, 729 så |A ∩ B| = 3 och |A ∪ B| = 31 + 10 − 3 = 38.

Svaret är 38.

(2) (3p) Låt m ∈ ℤ^{+}. Visa, med hjälp av induktion, att

Om a ≡_{m} b då a^{n} ≡_{m} b^{n} för n ≥ 1

Detta är sant för n = 1. Antag att a^{n} ≡_{m} b^{n} gäller för n ≤ k. Vi ska visa att a^{k+1} ≡_{m} b^{k+1}.

a^{k+1} = a · a^{k} ≡_{m} b · b^{k} = b^{k+1}

eller:

a ≡_{m} b betyder att a = mt+b, där t ∈ ℤ, och a^{k} ≡_{m} b^{k} betyder att a^{k} = hm+b^{k}, där h ∈ ℤ.

a^{k+1} = a^{k} · a = (hm + b^{k})(mt + b) = m(mht + hb + tb^{k}) + b^{k+1}

Så a^{k+1} ≡_{m} b^{k+1}.

(3) (3p) Lös följande diofantiska eknation:

10x + 36y = 8
36 = 10 · 3 + 6
10 = 6  + 4
6 = 4  + 2
4 = 2 · 2

Så sgd(36, 10) = 2 och:

2 = 6 − 4 = 6 − (10 − 6) = 2 · (36 − 3 · 10) − 10 = 2 · 26 − 7 · 10

Par (−7, 2) är EN lösning till 10x + 36y = 2 så par (−28, 8) är EN lösning till 10x + 36y = 8. Nu ska man hitta den allmänna lösning med hjälp av lcd. Vi vet att:

lsd(10, 36) = 2^{2} · 3^{2} · 5 = 10 · 18 = 36 · 5

Så vi har att:

10 · (−28) + 36 · 8 + (10 · 18 − 36 · 5)k = (−28 + 18k) · 10 + (8 − 5k) · 36 = 8

Del almänna lösning är x = −28 + 18k, y = 8 − 5k.