56
Programa Combinatória Aritmética Racional MATEMÁTICA DISCRETA Patrícia Ribeiro Departamento de Matemática, ESTSetúbal 2018/2019 1 / 52

MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Embed Size (px)

Citation preview

Page 1: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

MATEMÁTICA DISCRETA

Patrícia Ribeiro

Departamento de Matemática, ESTSetúbal

2018/2019

1 / 52

Page 2: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Programa

1 Combinatória2 Aritmética Racional3 Grafos

2 / 52

Page 3: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Capítulo 1

Combinatória

3 / 52

Page 4: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio da Adição

TeoremaSe A e B são conjuntos finitos e disjuntos, então o número de maneirasdistintas de escolher um elemento de A ou um elemento de B é igual a

|A∪B|= |A|+ |B|.

TeoremaSe A1,A2, ...,An são conjuntos finitos e disjuntos dois a dois, então onúmero de maneiras distintas de escolher um elemento de A1 ou umelemento de A2 ... ou de An é igual a

|A1∪A2∪ ...∪An|= |A1|+ |A2|+ ...+ |An|.

4 / 52

Page 5: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio da Adição

TeoremaSe A e B são conjuntos finitos e disjuntos, então o número de maneirasdistintas de escolher um elemento de A ou um elemento de B é igual a

|A∪B|= |A|+ |B|.

TeoremaSe A1,A2, ...,An são conjuntos finitos e disjuntos dois a dois, então onúmero de maneiras distintas de escolher um elemento de A1 ou umelemento de A2 ... ou de An é igual a

|A1∪A2∪ ...∪An|= |A1|+ |A2|+ ...+ |An|.

4 / 52

Page 6: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio do Produto

TeoremaSejam A e B conjuntos finitos. Suponhamos que se pretende realizaruma escolha múltipla de dois elementos que consiste na escolha deexatamente um elemento em cada um dos conjuntos. Admitindo queestas escolhas se combinam livremente (isto é, cada escolha múltiplacorresponde a um elemento de A×B e vice-versa), então o númerototal de diferentes escolhas múltiplas possíveis é igual a

|A×B|= |A|× |B|.

5 / 52

Page 7: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio do Produto

TeoremaSejam A1,A2, ...,An conjuntos finitos. Suponhamos que se pretenderealizar uma escolha múltipla de n elementos que consiste na escolhade exatamente um elemento em cada um dos conjuntos. Admitindoque estas escolhas se combinam livremente (isto é, cada escolhamúltipla corresponde a um elemento de A1× ...×An e vice-versa),então o número total de diferentes escolhas múltiplas possíveis éigual a

|A1× ...×An|= |A1|× ...×|An|.

6 / 52

Page 8: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Arranjos completos

DefiniçãoSeja A um conjunto com n elementos. Chamamos arranjo completo(ou com repetição) dos n elementos de A tomados k a k, a todo oelemento (a1,a2, ...,ak) do produto cartesiano Ak.

O número total de arranjos completos de n elementos tomados k a krepresenta-se por An

k .

TeoremaO número total de arranjos completos de n elementos tomados k a k édado por

Ank = nk.

7 / 52

Page 9: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Arranjos completos

DefiniçãoSeja A um conjunto com n elementos. Chamamos arranjo completo(ou com repetição) dos n elementos de A tomados k a k, a todo oelemento (a1,a2, ...,ak) do produto cartesiano Ak.

O número total de arranjos completos de n elementos tomados k a krepresenta-se por An

k .

TeoremaO número total de arranjos completos de n elementos tomados k a k édado por

Ank = nk.

7 / 52

Page 10: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Arranjos simples

DefiniçãoChamamos arranjo simples (ou sem repetição ou simplesmentearranjo) dos n elementos de A tomados k a k, a todo o elemento(a1,a2, ...,ak) do produto cartesiano Ak, em que a1,a2, ...,ak sãotodos distintos entre si.

O número total de arranjos de n elementos tomados k a krepresenta-se por An

k .

TeoremaO número total de arranjos simples de n elementos tomados k a k édado por

Ank = n(n−1)(n−2)...(n− k+1).

8 / 52

Page 11: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Arranjos simples

DefiniçãoChamamos arranjo simples (ou sem repetição ou simplesmentearranjo) dos n elementos de A tomados k a k, a todo o elemento(a1,a2, ...,ak) do produto cartesiano Ak, em que a1,a2, ...,ak sãotodos distintos entre si.

O número total de arranjos de n elementos tomados k a krepresenta-se por An

k .

TeoremaO número total de arranjos simples de n elementos tomados k a k édado por

Ank = n(n−1)(n−2)...(n− k+1).

8 / 52

Page 12: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Permutações

DefiniçãoChamamos permutação dos n elementos de um conjunto A, a todo oarranjo simples dos n elementos de A tomados n a n.O número total de permutações de n elementos designa-se por Pn e éigual a

Pn = Ann = n× (n−1)× ...×2×1 = n!.

9 / 52

Page 13: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Permutações

ProposiçãoDado 0 < k ≤ n, o número de arranjos simples de n elementostomados k a k é dado por

Ank =

n!(n− k)!

.

10 / 52

Page 14: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Permutações com repetição

DefiniçãoSeja A um conjunto com k elementos, A = {a1,a2, ...,ak}. Chama-sepermutação-n com repetição dos k elementos de A, em que a1 serepete n1 vezes, a2 se repete n2 vezes,..., ak se repete nk vezes e em quen1 +n2 + ...+nk = n, a todo o n-uplo do produto cartesiano An comn1 componentes iguais a a1, n2 componentes iguais a a2,..., nk

componentes iguais a ak.

O número total de permutações-n representa-se por P(n1,n2, ...,nk).

11 / 52

Page 15: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Permutações com repetição

TeoremaO número total de permutações-n com repetição dos k elementos deA, em que a1 se repete n1 vezes, a2 se repete n2 vezes,..., ak se repetenk vezes e em que n1 +n2 + ...+nk = n, é igual a

P(n1,n2, ...,nk) =n!

n1!×n2!× ...×nk!.

12 / 52

Page 16: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações

DefiniçãoSeja A um conjunto com n elementos e k um inteiro, tal que 0≤ k ≤ n.Chama-se combinação sem repetição (ou simplesmente combinação)dos n elementos tomados k a k, a qualquer subconjunto de A com kelementos.

O número total de combinações dos n elementos tomados k a krepresenta-se por

(nk

)ou por Cn

k .

13 / 52

Page 17: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações

ProposiçãoPara todo o n ∈ N tem-se que(

n0

)=

(nn

)= 1,

(n1

)=

(n

n−1

)= n e

(nk

)= 0,k > n.

14 / 52

Page 18: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações

ProposiçãoPara n,k ∈ N0, tal que 0≤ k ≤ n, tem-se que(

nk

)=

(n

n− k

).

15 / 52

Page 19: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações

TeoremaPara n ∈ N e 0≤ k ≤ n temos que

(nk

)=

1 se k = 0 ou k = n(n−1

k−1

)+(n−1

k

)se 0 < k < n

16 / 52

Page 20: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações

TeoremaPara n ∈ N e 0≤ k ≤ n temos que(

nk

)=

n!k!(n− k)!

.

17 / 52

Page 21: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações com repetição

DefiniçãoSeja A um conjunto com n elementos e k > 0 um inteiro qualquer.Chama-se combinação com repetição dos n elementos tomados k a ka toda a amostra não ordenada de k elementos de A distintos ou não.

Representa-se por C nk o número total de combinações com repetição

dos n elementos tomados k a k.

TeoremaPara n ∈ N e k > 0 qualquer, temos que

C nk = P(k,n−1) =

(k+n−1

k

),

18 / 52

Page 22: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Combinações com repetição

DefiniçãoSeja A um conjunto com n elementos e k > 0 um inteiro qualquer.Chama-se combinação com repetição dos n elementos tomados k a ka toda a amostra não ordenada de k elementos de A distintos ou não.

Representa-se por C nk o número total de combinações com repetição

dos n elementos tomados k a k.

TeoremaPara n ∈ N e k > 0 qualquer, temos que

C nk = P(k,n−1) =

(k+n−1

k

),

18 / 52

Page 23: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Teorema binomial

TeoremaDados a,b ∈ R e n ∈ N qualquer, temos que

(a+b)n =n

∑k=0

(nk

)akbn−k.

19 / 52

Page 24: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio da inclusão-exclusão

Sejam A e B conjuntos finitos. Então,

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

20 / 52

Page 25: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio da inclusão-exclusão

TeoremaSeja X um conjunto e A1,A2, ...,An ⊆ X não necessariamentedistintos. Então,

|A1∪ ...∪An|=n

∑i=1|Ai|−

n

∑1≤i<j≤n

|Ai∩Aj|+

n

∑1≤i<j<k≤n

|Ai∩Aj∩Ak|+ ...+(−1)n+1|A1∩ ...∩An|.

21 / 52

Page 26: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio da inclusão-exclusão

CorolárioSeja X um conjunto e A1, ...,An ⊆ X não necessariamente distintos.Então,

|X \ (A1∪ ...∪An) |= |X|− |A1∪ ...∪An|.

22 / 52

Page 27: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio da distribuição

Forma fraca:Sejam m,n ∈ N. Se m≥ n+1 objetos são distribuídos por n caixas,então uma das caixas terá, pelo menos, dois objetos.

Forma forte:Sejam m,n,k ∈ N. Se m≥ nk+1 objetos são distribuídos por ncaixas, então uma das caixas terá, pelo menos, k+1 objetos.

23 / 52

Page 28: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Capítulo 2

Aritmética Racional

24 / 52

Page 29: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Axiomática dos Inteiros

Sejam a e b inteiros. Designaremos por a+b a sua soma e a×b (ouab) a sua multiplicação. Admitem-se válidos os seguintes axiomas:

I1. a+b e ab pertencem a Z;

I2. a+b = b+a e ab = ba;

I3. (a+b)+ c = a+(b+ c) e (ab)c = a(bc);

I4. a+0 = a e a×1 = a;

I5. a(b+ c) = ab+ac;

I6. Para cada a ∈ Z existe um único inteiro representado por −a, talque a+(−a) = 0;

I7. Se a 6= 0 e ab = ac, então b = c.

25 / 52

Page 30: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Axiomática dos Inteiros

ProposiçãoSão válidas as seguintes propriedades:

1 O elemento neutro da adição em Z é único;2 Sendo a,b,c ∈ Z é válida a lei do corte para a adição, ou seja se

a+b = a+ c, então b = c;3 Se a ∈ Z,a×0 = 0;4 Sendo a,b ∈ Z é válida a lei do anumlamento do produto, ou

seja ab = 0 sse a = 0 ou b = 0.

26 / 52

Page 31: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Axiomática dos Inteiros

DefiniçãoA subtração de inteiros representa-se por a−b e define-se como sesegue:

a−b = a+(−b).

27 / 52

Page 32: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Axiomática dos Inteiros

Suponha-se que existe uma relação de ordem nos inteirosrepresentado pelo símbolo ≤. Sejam a,b e c inteiros. Admitem-seválidos os seguintes axiomas:

I8. a≤ a;

I9. Se a≤ b e b≤ a, então a = b;

I10. a≤ b e b≤ c, então a≤ c;

I11. a≤ b⇒ a+ c≤ b+ c;

I12. a≤ b e 0≤ c, então ac≤ bc.

ObservaçãoDe referir que se pode definir as relações ≥,< e >: a≥ b sse b≤ a;a < b sse a≤ b e a 6= b; a > b sse b≤ a e a 6= b.

28 / 52

Page 33: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Axiomática dos Inteiros

DefiniçãoSeja X um subconjunto de Z. Diz-se que l é um minorante de X se

l≤ x,∀x ∈ X.

Se l ∈ X diz-se que l é mínimo de X.

I13. (Princípio da boa ordenação de Z) Se X é um subconjunto nãovazio de Z com um minorante, então X tem mínimo.

Princípio da boa ordenação de N: Se X é um subconjunto não vaziode N ou N0, então X tem mínimo.

29 / 52

Page 34: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio de Indução

TeoremaSeja P(n) uma afirmação na variável n ∈ N que satisfaz as seguintescondições:

i) Base de indução: P(1) é verdadeira;

ii) Passo de indução: para qualquer k ∈ N se P(k) é verdadeira,então P(k+1) é verdadeira.

Então P(n) é verdadeira para todo o n ∈ N.

30 / 52

Page 35: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio de Indução (1a variante)

TeoremaSeja a ∈ N e P(n) uma afirmação na variável n ∈ N com n≥ a quesatisfaz as seguintes condições:

i) Base de indução: P(a) é verdadeira;

ii) Passo de indução: para qualquer k ≥ a se P(k) é verdadeira,então P(k+1) é verdadeira.

Então P(n) é verdadeira para todo o n≥ a.

31 / 52

Page 36: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Princípio de Indução completa

TeoremaSejam a,r ∈ N e P(n) uma afirmação na variável n ∈ N com n≥ aque satisfaz as seguintes condições:

i) Base de indução: P(a),P(a+1), ...,P(a+ r) são verdadeiras;

ii) Passo de indução: para qualquer k ≥ a+ r seP(a),P(a+1), ...,P(a+ r), ...,P(k) são verdadeiras, entãoP(k+1) é verdadeira.

Então P(n) é verdadeira para todo o n≥ a.

32 / 52

Page 37: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Divisão Inteira

TeoremaDados a,b ∈ Z, existem inteiros q e r, tais que

a = bq+ r, 0≤ r < |b|,

onde q e r têm respetivamente o nome de quociente e resto da divisãode a por b. Além disso, q e r são únicos.

33 / 52

Page 38: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Representação de números em diferentes basesSeja b≥ 2 um inteiro. Dado a ∈ N, se utilizarmos repetidamente oteorema anterior concluímos que

a = bq0 + r0

q0 = bq1 + r1

...

qn−2 = bqn−1 + rn−1

qn−1 = bqn + rn.

Se eliminarmos por retrosubstituição os quocientes qi conseguimosrepresentar a da seguinte maneira:

a = rnbn + rn−1bn−1 + ...+ r1b+ r0,

que usualmente se representa por

a = (rnrn−1...r1r0)b.

34 / 52

Page 39: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Divisibilidade

DefiniçãoDados inteiros a e b, diz-se que a é divisor de b se b = aq para algumq ∈ Z.Denota-se por a|b. Quando a não divide b utiliza-se a notação a - b.

35 / 52

Page 40: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

DivisibilidadeProposiçãoSejam a,b,c,d ∈ Z. Então:

1 ±a|a, e 1|a;2 a|b sse (−a)|b sse a|(−b);3 se c 6= 0, então a|b sse ac|bc;4 se a|b, então a|bc;5 se ab|c, então a|c e b|c;6 se a|b e b|c, então a|c;7 se a|b e c|d, então ac|bd;8 se a|b e a|c, então a|(bx+ cy), para quaisquer x,y ∈ Z;9 se a|b e b|a, então a =±b;

10 se a|1, então a =±1;11 se a,b ∈ N e a|b, então a≤ b;12 o número de divisores de um inteiro não nulo é finito. 36 / 52

Page 41: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Máximo divisor comum

Um inteiro d é um divisor comum dos inteiros a e b se d|a e d|b.

DefiniçãoSejam a,b inteiros não ambos nulos. Ao maior dos divisores comunsde a e b dá-se o nome de máximo divisor comum de a e b.Representa-se por mdc(a,b).

37 / 52

Page 42: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Máximo divisor comum

Lema (Algoritmo de Euclides)Se a = bq+ r, então mdc(a,b) = mdc(b,r).

38 / 52

Page 43: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Máximo divisor comum

TeoremaSejam a e b inteiros não ambos nulos e d = mdc(a,b). Então, existeminteiros x e y, tais que

d = ax+by.

39 / 52

Page 44: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Máximo divisor comum

TeoremaSejam a e b inteiros não ambos nulos. Então d = mdc(a,b) sse

i) d > 0;

ii) d|a e d|b;

iii) se c|a e c|b, então c|b.

40 / 52

Page 45: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Números primos entre si

DefiniçãoSejam a,b ∈ Z. Diz-se que a e b são primos entre si (ou primosrelativos) se mdc(a,b) = 1.

ProposiçãoDois inteiros a e b são primos entre si sse existem inteiros x e y, taisque

1 = ax+by.

41 / 52

Page 46: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Números primos entre si

ProposiçãoSejam a,b,c ∈ Z. Se mdc(a,b) = 1, a|c e b|c, então ab|c.

Proposição (Lema de Euclides)Sejam a,b,c ∈ Z. Se a|bc e mdc(a,b) = 1, então a|c.

42 / 52

Page 47: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Menor múltiplo comum

DefiniçãoSejam a e b inteiros não nulos. Ao menor dos múltiplos comuns de a eb dá-se o nome de menor múltiplo comum de a e b. Representa-se pormmc(a,b).

43 / 52

Page 48: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Menor múltiplo comum

TeoremaSejam a e b inteiros não ambos nulos. Então m = mmc(a,b) sse:

1 m > 0;2 a|m e b|m;3 sendo c 6= 0, se a|c e b|c, então m|c.

44 / 52

Page 49: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Relação entre mdc e mmc

TeoremaSe a e b são inteiros não nulos, então

mmc(a,b) =|ab|

mdc(a,b).

45 / 52

Page 50: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Equação linear diofantina a 2 incógnitas

TeoremaSejam a,b,c ∈ Z,a,b 6= 0 e d = mdc(a,b).

1 a equação ax+by = c tem soluções inteiras sse d|c;2 suponhamos que d|c. Então, se (x0,y0) é uma solução inteira da

equação ax+by = c, qualquer outro par (x,y) é solução sse forda forma

x = x0 +bd t

y = y0− ad t, t ∈ Z.

46 / 52

Page 51: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Números primos

DefiniçãoUm número natural maior do que 1 diz-se primo se não tem outrosdivisores positivos além dele próprio e do 1.Um número que não é primo diz-se composto.

47 / 52

Page 52: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Números primos

TeoremaQualquer número natural maior do que 1 é produto de númerosprimos, isto é pode ser decomposto em fatores primos.

48 / 52

Page 53: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Trial division

CorolárioSeja n > 1 um número natural. Se n não é primo, então existe umprimo p, tal que p|n e p≤

√n.

49 / 52

Page 54: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Números primos

TeoremaExiste um número infinito de primos.

50 / 52

Page 55: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Decomposição em fatores primos

TeoremaSejam a e b números inteiros e p um número primo. Se p divide ab,então p divide a ou p divide b.

CorolárioSe p é um número primo e x1,x2, ...,xn são inteiros, tais que

p|x1× x2× ...× xn,

então p|xi, para algum i = 1,2, ...,n.

51 / 52

Page 56: MATEMÁTICA DISCRETA Patrícia Ribeiro - ltodi.est.ips.ptltodi.est.ips.pt/MatDisc/Acetatos/slides_aulasMD.pdf · ProgramaCombinatória Aritmética Racional Princípio do Produto Teorema

Programa Combinatória Aritmética Racional

Decomposição em fatores primos

Teorema (Teorema fundamental da aritmética)A decomposição em fatores primos de um número maior do que 1 éúnica, a menos da ordem dos fatores.

52 / 52