Introdução à Teoria dos Números - UEPA

Marlia Brasil Xavier REITORA

Prof. M. Sc. Rubens Vilhena Fonseca COORDENADOR GERAL DOS CURSOS DE MATEMTICA

MATERIAL DIDTICO

COLABORAOMaria da Glria Costa Lima Cleyton Isamu Muto

EDITORAO ELETRONICAOdivaldo Teixeira Lopes

ARTE FINAL DA CAPAOdivaldo Teixeira Lopes

REALIZAO

BELM PAR BRASIL - 2011 -

SUMRIOCaptulo 1:...............................................................................................................................................9 NMEROS INTEIROS NOES FUNDAMENTAIS ...................................................................................91.1 NMEROS INTEIROS ....................................................................................................................................... 10 1.2 PROPRIEDADES DOS INTEIROS ........................................................................................................................ 11 1.3 VALOR ABSOLUTO DE UM INTEIRO ................................................................................................................ 12 1.4 REPRESENTAO DOS INTEIROS EM OUTRAS BASES ...................................................................................... 14 1.5 FATORIAL E PRINCPIO FUNDAMENTAL DA CONTAGEM .................................................................................. 15 1.6 PRINCPIO FUNDAMENTAL DA CONTAGEM - PFC ............................................................................................ 16 1.7 NMERO BINOMIAL ........................................................................................................................................ 17 1.8 NMEROS BINOMIAIS COMPLEMENTARES...................................................................................................... 18 1.9 NMEROS BINOMIAIS CONSECUTIVOS ............................................................................................................ 18 1. 10 PISO, TETO E NINT DE UM NMERO REAL. ................................................................................................ 20 1.11 O PRINCPIO DA CASA DOS POMBOS (PRINCPIO DAS GAVETAS DE DIRICHLET) .............................................. 24 1.12 CAOS FATORIAL: !N. ..................................................................................................................................... 25 1.13 LEFT FATORIAL: L!N ..................................................................................................................................... 26 EXERCCIOS............................................................................................................................................................ 27

Captulo 2:.............................................................................................................................................30 INDUO MATEMTICA ........................................................................................................................302.1 ELEMENTO MNIMO DE UM CONJUNTO DE INTEIROS ...................................................................................... 30 2.2 PRINCPIO DA BOA ORDENAO .................................................................................................................... 31 2.3 PRINCPIO DE INDUO FINITA. ...................................................................................................................... 32 2.4 INDUO MATEMTICA ................................................................................................................................ 33 2.5. EXEMPLOS DE DEMONSTRAO POR INDUO MATEMTICA .......................................................................... 35 2.6 . OUTRAS FORMAS DA INDUO MATEMTICA ................................................................................................ 37 EXERCCIOS............................................................................................................................................................ 42

Captulo 3:.............................................................................................................................................43 SOMATRIOS E PRODUTRIOS .............................................................................................................433.1 . SOMATRIOS ................................................................................................................................................. 43 3.2. PROPRIEDADES DOS SOMATRIOS................................................................................................................... 44 3.3. PRODUTRIOS................................................................................................................................................. 45 3.4. PROPRIEDADES DOS PRODUTRIOS ................................................................................................................. 46

Captulo 4 ..............................................................................................................................................48 DIVISIBILIDADE .....................................................................................................................................484.1. RELAO DE DIVISIBILIDADE EM Z ................................................................................................................. 48 4.2. CONJUNTO DOS DIVISORES DE UM INTEIRO ..................................................................................................... 50 4.3. DIVISORES COMUNS DE DOIS INTEIROS ........................................................................................................... 50 4.4. TEOREMA DA DIVISO ................................................................................................................................... 51 4.5. PARIDADE DE UM INTEIRO .............................................................................................................................. 54 EXERCCIOS............................................................................................................................................................ 56

Captulo 5 ..............................................................................................................................................58 MXIMO DIVISOR COMUM ...................................................................................................................585.1. MXIMO DIVISOR COMUM DE DOIS INTEIROS .................................................................................................. 58 5.2. EXISTNCIA E UNICIDADE DO MDC. ................................................................................................................ 59 5.3. INTEIROS RELATIVAMENTE PRIMOS (COPRIMOS OU PRIMOS ENTRE SI) ............................................................ 61 5.4. CARACTERIZAO DO MDC DE DOIS INTEIROS ................................................................................................ 64 5.5. MDC DE VRIOS INTEIROS .............................................................................................................................. 64 EXERCCIOS............................................................................................................................................................ 65

Captulo 6 ............................................................................................................................................. 67 ALGORITMO DE EUCLIDES MNIMO MLTIPLO COMUM................................................................. 676.1. ALGORITMO DE EUCLIDES .............................................................................................................................. 67 6.2 . MLTIPLOS COMUNS DE DOIS INTEIROS ......................................................................................................... 74 6.3. MNIMO MLTIPLO COMUM DE DOIS INTEIROS ................................................................................................ 75 6.5. MMC DE VRIOS INTEIROS .............................................................................................................................. 76 EXERCCIOS ............................................................................................................................................................ 78

Captulo 7 ............................................................................................................................................. 79 NMEROS PRIMOS ................................................................................................................................ 797.1. INTRODUO .................................................................................................................................................. 79 7.2. NMEROS PRIMOS (DO LAT. PRIMUS, PRINCIPAL. PRIME EM INGLS) .............................................................. 81 7. 3. TEOREMA FUNDAMENTAL DA ARITMTICA. ................................................................................................... 82 7.4. A SEQNCIA DOS NMEROS PRIMOS .............................................................................................................. 84 7.5. O CRIVO DE ERATSTENES. .............................................................................................................................. 86 7.6. SEQNCIA DE INTEIROS CONSECUTIVOS COMPOSTOS .................................................................................... 94 7.7 . CONJECTURAS ................................................................................................................................................ 96 7.8. FRMULAS QUE GERAM ALGUNS NMEROS PRIMOS........................................................................................ 98 7.9. DECOMPOSIO DO FATORIAL EM FATORES PRIMOS ..................................................................................... 101 7.10. MTODO DA FATORAO DE FERMAT .......................................................................................................... 105 7. 11 ALGORITMO DE FERMAT ............................................................................................................................ 105 EXERCCIOS .......................................................................................................................................................... 107

Captulo 8: .......................................................................................................................................... 110 EQUAES DIOFANTINAS LINEARES ................................................................................................. 1103.1. GENERALIDADES ........................................................................................................................................... 111 3.2. CONDIO DE EXISTNCIA DE SOLUO ........................................................................................................ 112 3.3. SOLUES DA EQUAO AX + BY = C. ........................................................................................................... 113 EXERCCIOS .......................................................................................................................................................... 115

Captulo 9 ........................................................................................................................................... 117 CONGRUNCIAS .................................................................................................................................. 1179.1. CONGRUNCIAS ............................................................................................................................................ 117 9.2. CARACTERIZAO DE INTEIROS CONGRUENTES ............................................................................................ 117 9.3. PROPRIEDADES DAS CONGRUNCIAS ............................................................................................................. 118 9.4. SISTEMAS COMPLETOS DE RESTOS................................................................................................................ 121 9.5 ARITMTICA MDULO M .............................................................................................................................. 122 9.6. ADIO E MULTIPLICAO EM m .............................................................................................................. 124 9.7. SUBTRAO EM 9.8. DIVISO EM

m ...................................................................................................................................... 130

m ............................................................................................................................................ 131 9.9. POTENCIAO EM m .................................................................................................................................. 135EXERCCIOS .......................................................................................................................................................... 139

Captulo 10 ......................................................................................................................................... 141 TEOREMAS DE FERMAT, WILSON E EULER .......................................................................... 14110.1. PEQUENO TEOREMA DE FERMAT ....................................................................................................... 141 EXERCCIOS .......................................................................................................................................................... 145 10.2. TEOREMA DE WILSON .................................................................................................................................. 146EXERCCIOS ............................................................................................................................................................................. 149

10.3. TEOREMA DE EULER .................................................................................................................................... 150 10.4. FUNO TOTIENT (N) ................................................................................................................................. 151 10.5 CLCULO DE (N) ...................................................................................................................................... 152 10.6. RESOLUO DE CONGRUNCIAS LINEARES PELO TEOREMA DE EULER ......................................................... 155 10. 7. RESOLUO DA EQUAO (N).................................................................................................................. 156

10.8 VALNCIA DA FUNO TOTIENTE: N (m) . ............................................................................................ 159 EXERCCIOS.......................................................................................................................................................... 160 10.9. TEOREMA CHINS DO RESTO (TCR) .............................................................................................................. 161 10.10. POTENCIAO: UMA APLICAO DO TEOREMA DE EULER ......................................................................... 165 10.11 POTENCIAO: UMA APLICAO DO TEOREMA CHINS DO RESTO (TCR) .................................................. 165

Captulo 11 ..........................................................................................................................................171 CIFRA DE CSAR ..................................................................................................................................17111.1. FUNES POLINOMIAIS DE CODIFICAO .................................................................................................... 174

Captulo 12 ..........................................................................................................................................179 CIFRA DE VIGENRE ...........................................................................................................................179 Captulo 13 ..........................................................................................................................................182 CIFRA DE HILL.....................................................................................................................................182 Captulo 14 ..........................................................................................................................................190 RSA .......................................................................................................................................................19014. 1. PR-CODIFICAO ...................................................................................................................................... 190 14.2 CODIFICANDO E DECODIFICANDO ............................................................................................................... 191 14. 3. ASSINATURA DIGITAL UTILIZANDO A CRIPTOGRAFIA RSA .......................................................................... 195

Captulo 15 ..........................................................................................................................................201 PARTILHA DE SENHAS .........................................................................................................................201

CAPTULO 1 NMEROS INTEIROS NOES FUNDAMENTAIS

Captulo 1:

NMEROS INTEIROS NOES FUNDAMENTAISINTRODUO

Teoria dos Nmeros nasceu cerca de 600 anos antes de Cristo quando Pitgoras e os seus discpulos comearam a estudar as propriedades dos nmeros inteiros. Os pitagricos rendiam verdadeiro culto mstico ao conceito de nmero, considerando-o como essncia das coisas. Acreditavam que tudo no universo estava relacionado com nmeros inteiros ou razes de nmeros inteiros (em linguagem atual, nmeros racionais). Alis, na antiguidade a designao nmero aplicava-se s aos inteiros maiores do que um. http://nonio.fc.ul.pt/analise1/cap1/hnum.htm O conceito de nmero tomou forma num longo desenvolvimento histrico. A origem e formulao deste conceito ocorreu simultaneamente com o despontar, entenda-se nascimento, e desenvolvimento da Matemtica. As atividades prticas do homem, por um lado, e as exigncias internas da Matemtica por outro determinaram o desenvolvimento do conceito de nmero. A necessidade de contar objetos levou ao aparecimento do conceito de nmero Natural. Todas as naes que desenvolveram formas de escrita introduziram o conceito de nmero Natural e desenvolveram um sistema de contagem. O desenvolvimento subsequente do conceito de nmero prosseguiu principalmente devido ao prprio desenvolvimento da Matemtica. Os nmeros negativos aparecem pela primeira vez na China antiga. Os chineses estavam acostumados a calcular com duas colees de barras - vermelha para os nmeros positivos e preta para os nmeros negativos.No entanto, no aceitavam a idia de um nmero negativo poder ser soluo de uma equao. Os Matemticos indianos descobriram os nmeros negativos quando tentavam formular um algoritmo para a resoluo de equaes quadrticas. So exemplo disso as contribuies de Bramaghupta, pois a aritmtica sistematizada dos nmeros negativos encontra-se pela primeira vez na sua obra. As regras sobre grandezas eram j conhecidas atravs dos teoremas gregos sobre subtrao, como por exemplo (a - b)(c - d) = ac + bd - ad - bc, mas os hindus converteram-nas em regras numricas sobre nmeros negativos e positivos. Diofanto (Sc. III) operou facilmente com os nmeros negativos. Eles apareciam constantemente em clculos intermdios em muitos problemas do seu "Aritmetika", no entanto havia certos problemas para o qual as solues eram valores inteiros negativos como por exemplo: 4x + 20 = 4 ou 3x 18 = 5x2 Nestas situaes Diofanto limitava-se a classificar o problema de absurdo. Nos sculos XVI e XVII, muitos matemticos europeus no apreciavam os nmeros negativos e, se esses

A

9


nmeros apareciam nos seus clculos, eles consideravam-nos falsos ou impossveis. Exemplo deste fato seria Michael Stifel (1487- 1567) que se recusou a admitir nmeros negativos como razes de uma equao, chamando-lhes de "numeri absurdi". Cardano usou os nmeros negativos embora chamando-os de "numeri ficti". A situao mudou a partir do (Sc.XVIII) quando foi descoberta uma interpretao geomtrica dos nmeros positivos e negativos como sendo segmentos de direes opostas. http://www.somatematica.com.br/historia.php

1.1 Nmeros InteirosOs nmeros inteiros ou apenas os inteiros so: ..., -3, -2, -1, 0, 1, 2, 3,... cujo conjunto representa-se pela letra Z, isto : Z = {..., -3, -2, -1, 0, 1, 2, 3,...} Neste conjunto Z destacam-se os seguintes subconjuntos: 1) Conjunto Z* dos inteiros no nulos ( 0 ): Z* = {x Z | x0} { 1, 2, 3,...}

2) Conjunto Z dos inteiros no negativos ( 0 ):

Z

{x Z | x 0} = {0, 1, 2, 3,...}

3) Conjunto Z dos inteiros no positivos ( 0 ):

Z

{x Z | x 0} = {0, -1, -2, -3,...}

4) Conjunto Z* dos inteiros positivos (> 0):Z* {x Z | x 0} = {1, 2, 3,...}

5) Conjunto Z* dos inteiros negativos (< 0):Z* {x Z | x 0} = {-1, -2, -3,...}

Os inteiros positivos so tambm denominados inteiros naturais e por isso o conjunto dos inteiros positivos habitualmente designado pela letra N (N = Z* ).

10


1.2 Propriedades dos InteirosO conjunto Z dos inteiros munido das operaes de adio (+) e multiplicao ( . ) possui as propriedades fundamentais que a seguir enumeramos, onde a, b e c so inteiros quaisquer, isto , elementos de Z: 1) a + b = b + a e ab = ba; e (ab) c = a (bc);

2) (a + b) + c = a + (b + c) 3) 0 + a = a e 1.a = a; 4) a = (-1) a e

a a = a + (-a) = 0;

5) a (b + c) = ab + ac; 6) 0.a = 0, e se ab = 0, ento a = 0 ou b = 0. Tambm existe uma relao de ordem entre os inteiros, representada pelo sinal < (menor que), que possui as seguintes propriedades: 7) Se a 0 , ento a > 0 ou a < 0; 8) Se a < b e b < c, ento a < c; 9) Se a < b, ento a + c < b + c; 10) Se a < b e 0 < c, ento ac < bc; 11) Se a < b e c < 0, ento bc < ac. Destas propriedades podem ser deduzidas muitas outras propriedades dos inteiros. Exemplo 1.1: Demonstrar: -(a + b) = (-a) + (-b). Com efeito, temos sucessivamente: -(a + b) = (-1) (a + b) = = (-1) a + (-1) b = = (-a) + (-b) (Propriedade 4) (Propriedade 5) (Propriedade 4)x2 .

Exemplo 1.2: Demonstrar que , se x 0 , ento 0 Com efeito: 1) Se x 0 , ento 2) Se x 0 , ento 3) Se 0x 0 ou 0 0.x x.x 0 x2 x , ento 0.x x.x 0 x2 x

(Propriedade 7) (Propriedade 11) (Propriedade 6) (Propriedade 10) (Propriedade 6)

11


Nota: Com o mesmo significado de a < b, escreve-se b > a. Indica-se, de modo abreviado, que a < b ou a = b por a b . Por exemplo, temos 2 3 , porque 2 < 3, e 2 2 , porque 2 - 2. Com o mesmo significado de a b , escreve-se b a . Em lugar de a b e b c tambm se escreve a b c .

1.3 Valor absoluto de um InteiroDefinio 1.1: Chama-se valor absoluto de um inteiro a, o inteiro que se indica por | a | , e tal que:

|a|

a, se a 0 a, se a < 0

Assim, por exemplo:| 3| 3

e

| 5|

( 5)

5

Consoante a definio de | a | , para todo inteiro a, temos:|a| 0, |a| a , | a | | a | , a | a |

O valor absoluto | a | de um inteiro a tambm pode ser definido pelas igualdades:|a| a , | a | = mx [-a, a]

onde a denota a raiz quadrada no negativa de a e mx [-a, a] indica o maior dos dois inteiros a e a.

Assim, por exemplo:| 4| ( 4) 16 4

| 6 | = mx [-6, 6] = 6

Teorema 1.1: Se a e b so dois inteiros, ento:| ab | | a | .| b |

12


Demonstrao: Com efeito:| ab | (ab) ab a. b | a | . | b |

Teorema 1.2: Se a e b so dois inteiros, ento:|a b| |a | |b|

Demonstrao: Com efeito, pela definio de | a | , temos:| a | a | a |, | b| b | b|

Somando ordenadamente estas desigualdades, obtemos:(| a | | b |) a b | a | | b |

*

o que implica:|a b| |a | |b|

* Usou se o fato de que x

a

a

x

a.

Corolrio 1.1: Se a e b so dois inteiros, ento:| a b| |a | | b|

Demonstrao: Com efeito:|a b | | a ( b) | | a | | b| |a | | b|

13


1.4 Representao dos Inteiros em outras BasesTeorema 1.3: Dado um inteiro qualquer b representao da forma: 2, todo inteiro positivo n admite uma nica

n ambm am 1bm 1 a2b2 a1b a0onde os ai so tais que 0 ai < b , i = 0, 1, ... , m

Demonstrao: Assim, dado um inteiro qualquer b 2 , todo inteiro positivo n pode ser representado por um polinmio inteiro em b do grau m (porque am 0 ), ordenado segundo as potencias decrescentes de b, e cujos coeficientes ai so inteiros que satisfaam as condies:

0 ai

b(i 0,1, 2,, m) , sendo am

0

Este polinmio representa-se, de modo abreviado, pela notao:

n (amam 1 a2a1a0 )bem que os coeficientes ai so indicados pela ordem respectiva, figurando o inteiro b como um ndice. O inteiro b chama-se base e costume dizer que n est escrito no sistema de base b.

Exemplos:a) Escrever 105 no sistema binrio 105 = 1.26 + 1.25 + 0.24 + 1.23 + 0.22 + 0.2 + 1 = (1101001)2 Por outro lado, (100111)2 = 1.25 + 0.24 + 0.23 + 1.22 + 1.2 + 1 = 39 b) Escrever 31415 no sistema de base 8 Temos, sucessivamente: 31415 3926 490 61 7 Portanto 31415 = 7.84 + 5.83 + 2.82 + 6.8 + 7 = 8.3926 = 8.490 = 8.61 = 8.7 = 8.0 = (75267)8 + + + + + 7 6 2 5 7

14


c) Escrever (3531)6 no sistema de base 10 Temos, (3531)6 = 3.63 + 5.62 + 3.6 + 1 = 847 d) Escrever (6165)7 no sistema de base 12 Temos, (6165)7 = 6.73 + 1.72 + 6.7 + 5 = 2154 Vamos escrever 2154 (base 10) na base 12: 2154 179 14 1 = 12.179 = 12.14 = 12.1 = 12.0 +6 + 11 +2 +1

No sistema de base 12 hbito designar 10 e 11 por a e b, respectivamente, de modo que os algarismos deste sistema so: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b. Portanto, 2154 = 1.123 + 2.122 + b.12 + 6 = (12b6)12 Assim, no sistema de numerao decimal, dado um inteiro n, temos que, n = am. 10m + am-1. 10m-1 + ... + a1. 10 + a0, 0 ak 10 a representao no sistema decimal do inteiro positivo n. Podemos tambm dizer que todo inteiro positivo n pode ser expresso sob a forma: n = 10k + a0 Onde a0 o algarismo das unidades de n

1.5 Fatorial e Princpio Fundamental da ContagemFoi a necessidade de calcular o nmero de possibilidades existentes nos chamados jogos de azar que levou ao desenvolvimento da Anlise Combinatria, parte da Matemtica que estuda os mtodos de contagem. Esses estudos foram iniciados j no sculo XVI, pelo matemtico italiano Niccollo Fontana (1500-1557), conhecido como Tartaglia. Depois vieram os franceses Pierre de Fermat (1601-1665) e Blaise Pascal (1623-1662). A Anlise Combinatria visa desenvolver mtodos que permitam contar - de uma forma indireta - o nmero de elementos de um conjunto, estando esses elementos agrupados sob certas condies. Definio 1.2: Chama-se fatorial de um inteiro no negativo n ( n 0 ), o inteiro que se indica por n!, e tal que:1, se n = 0 ou n = 1 n(n 1)(n 2)...3.2.1 se n 2

n!

Assim, por exemplo:

15


7! = 7.6.5.4.3.2.1 = 5040 Observe-se que n! = n.(n-1)!.

Exemplo 1.4: Escrever, usando o smbolo de fatorial, o produto dos n primeiros inteiros positivos pares e o produto dos n primeiros inteiros positivos mpares. Os n primeiros inteiros positivos pares so: 2,4,6, ..., 2n 2, 2n Isto : 2.1,2.2,2.3, ..., 2 . (n 1), 2n Portanto: 2,4,6, ..., 2n 2, 2n = 2n (1.2.3... (n -1).n) = 2n . n! Os n primeiros inteiros positivos mpares so: 1,3,5, ..., 2n 3, 2n - 1 Portanto:1.3.5...(2n 3).(2n 1) 1.2.3.4...(2n 2).(2n 1).2n 2.4.6...(2n 2).2n (2n )! 2n.n !

Exemplo 1.5: Calcular a soma: 1.1! + 2.2 ! + 3.3! + ... + n.n! Tomemos a igualdade: k.k! = (k + 1)! k! e nela faamos sucessivamente k = 1, 2, 3,..., n, o que d: 1.1! = 2! 1 2.2! = 3! 2! 3.3! = 4! 3! n.n! = (n + 1)! n! Somando ordenadamente todas essas n igualdades e simplificando, obtemos: 1.1! + 2.2! + 3.3! +...+ n.n! = (n + 1)! 1

1.6 Princpio fundamental da contagem - PFC 16


Se determinado acontecimento ocorre em n etapas diferentes, e se a primeira etapa pode ocorrer de k1 maneiras diferentes, a segunda de k2 maneiras diferentes, e assim sucessivamente , ento o nmero total T de maneiras de ocorrer o acontecimento dado por: T = k1. k2 . k3 . ... . kn

1.7 Nmero BinomialDefinio 1.3: Sejam n > 0 e k dois inteiros tais que 0 k n . Chama-se nmero binomial de numerador n e classe k, o inteiro que se indica por

n k

, e tal que:

n k

n! k!(n k)!

Obviamente, tambm podemos escrever:

n k

n(n 1)...(k 1) (n k)!

n(n 1)...(n k 1) k!

Em particular, para k = 0 ou k = n, temos:

n 0Assim, por exemplo:

n n

1

8 3

8! 8.7.6.5.4.3.2.1 8.7.6 56 3!5! 3.2.1.5.4.3.2.1 3.2.1 7 7.6.5 7.6.5 35 4 (7 4)! 3.2.1

17


1.8 Nmeros Binomiais ComplementaresDefinio 1.4: Chamam-se nmeros binomiais complementares dois nmeros binomiais que tm o mesmo numerador e cuja soma das suas classes respectivas igual ao numerador comum. Assim, por exemplo,

20 7

e

20 13

so nmeros binomiais complementares, pois, tm o

mesmo numerador 20 e 7 + 13 = 20. Teorema 1.4: Dois nmeros binomiais complementares so iguais.

Demonstrao: Sejam

n k

e

n h

dois nmeros binomiais complementares. Ento, k + h = n e k = n h.

Portanto:

n k

n n h

n! n! (n h)!(n (n h))! (n h)!h!

n h

1.9 Nmeros Binomiais ConsecutivosDefinio 1.5: Chamam-se nmeros binomiais consecutivos dois nmeros binomiais que tm o mesmo numerador e cujas classes respectivas so inteiros consecutivos. Assim, por exemplo,

18 9

e

18 10

so nmeros binomiais consecutivos, pois, tm o mesmo

numerador 18 e as suas classes respectivas so os inteiros consecutivos 9 e 10. Teorema 1.5: Entre dois nmeros binomiais consecutivos subsiste a relao de Stifel:

n k 1

e

n k

, com 1 k n ,

n k 1

n k

n 1 k

18


Demonstrao: Com efeito:

n k 1

n k

n! n! (k 1)!(n k 1)! k!(n k)!

n! n! (k 1)!(n k 1)(n k)! k(k 1)!(n k)! n! 1 1 (k 1)!(n k)! n k 1 k

n! n 1 (k 1)!(n k)! k(n k 1) n 1 (n 1)! k!(n 1 k)!Assim, por exemplo:

k

18 9 13 8Corolrio 1.2:

18 10 12 8

19 10 12 7 k 1 k 1

n k

n 1 k 1

n 2 k 1

...

k k 1

Demonstrao: Com efeito, mudando na relao de Stifel n sucessivamente por n 1, obtemos: n 2, n 3,..., k,

n k n 1 k n 2 k n 1 k

n 1 k 1 n 2 k 1 n 3 k 1 k k 1

n 1 k n 2 k n 3 k k k

...........................................

19


Alm disso, evidente:

k k

k 1 k 1

.

Somando ordenadamente todas essas igualdades e suprimindo os termos comuns aos dois membros acha-se a relao desejada. Substituindo, nesta relao, cada nmero binomial pelo seu complementar, obtemos:

n n k n k n 1 k

n 1 n k n 2 k 1 ...

n 2 n k 1 n k 1

...

k 1

k 1 0

Corolrio 1.3:

n k 1 0

Demonstrao: Consoante a relao de Stifel, temos:n k n 1 k 1 n 2 k 2 n k 1 1 n 1 k 1 n 2 k 2 n 3 k 3 n k 0 n 1 k n 2 k 1 n 3 k 2 n k 1

...........................................

Alm disso, temos:n k 0 n k 1 0

Somando ordenadamente todas essas igualdades e suprimindo os termos comuns aos dois membros acha-se a relao desejada.

1. 10 Piso, Teto e Nint de um nmero real. fcil perceber que qualquer nmero real est entre dois nmeros inteiros, um inteiro menor que o dado nmero real e um inteiro maior que esse nmero real. Por exemplo, o nmero real 3 , est entre os inteiros -5 e 5 , est entre os inteiros 2 e 3 ( 2 5 3 ); o nmero real 2 3 4( 5 4 ), etc.. Veremos a seguir que o inteiro esquerda ser chamado de Piso 2 (floor) e o inteiro direita ser chamado de Teto(ceiling).

20


Definio 1.6: Chamam-se partes inteiras de um nmero real r, os inteiros n e n+1 que verificam s condies:

n

r

n 1

A todo nmero real r podemos associar dois nmeros inteiros chamados piso e teto. Keneth Iverson introduziu esses nomes, assim como a notao que ser usada, no incio da dcada de 1960. Definio 1.7: Chama-se piso de um nmero real r, ao maior nmero inteiro menor ou igual a r. Definio 1.8: Chama-se teto de um nmero real r, ao menor nmero inteiro maior ou igual a r. Definio 1.9: Chama-se nint de um nmero real r, o valor inteiro mais prximo de r. Para evitar ambigidades, no caso de valores de r iguais metade de um inteiro, convenciona-se arredondar o valor de nint sempre para o inteiro par. Notao: Usaremos as seguintes notaes:r = piso de r r = teto de r r

= nint de r

Assim, o piso e o teto de um nmero real r so os inteiros definidos pelas desigualdades:r 1 r r r r 1

Em linguagem da Teoria dos Conjuntos:r max{n | n r} e r min{n | n r}

Observe que r r r se, e somente se, r um nmero inteiro, e que todo nmero real r pode ser escrito sob a forma:r r k , onde 0 k r r 1

er r 1 k , onde 0 k r r 1 1

O nmero real k chama-se parte no-inteira de r.

21


Exemplos: piso e teto de r. a)2 1 e 2 2

d)

1 3

0 e

1 3

1

b)

3 e

4

e)

1 2

1 e

1 2

0

c)

3 2

2 e

3 2

1

f)

7

7 e

7

7

Exemplos: nint de r.

a) [2,3] = 2 e [2,7] = 3

d) [3,5] = 4 e [4,5] = 4

b)

1 3

0

e

23 6

4

e)

1 2

0

e

1,5

2

c) [ ] = 3

e [e] = 3

f) [-3, 4] = -3 e [-3, 7] = -4

22


Abaixo, esto ilustrados os grficos das funes piso, teto e nint, respectivamente.

f ( x)

x

f ( x)

x

23


f ( x)

x

1.11 O Princpio da Casa dos Pombos (Princpio das Gavetas de Dirichlet)O princpio da Casa dos Pombos a afirmao de que se n pombos devem ser postos em m casas, sendo n > m ento pelo menos uma casa ir conter mais de um pombo. tambm conhecido como Princpio das Gavetas de Dirichlet, acredita-se que o primeiro relato deste principio foi feito pr Dirichlet em 1834, com o nome de Schubfachprinzip ("Princpio das Gavetas"). O princpio da casa do pombo um exemplo de um argumento de calcular que pode ser aplicado em muitos problemas formais, inclundo aqueles que envolvem um conjunto infinito. Exemplo: Quantas pessoas so necessrias para se ter certeza que haver pelo menos duas delas faam aniversrio no mesmo ms? Resposta: 13 pessoas. Pelo princpio da casa dos pombos se houver mais pessoas (13) do que meses (12) certo que pelos menos duas pessoas tero nascido no mesmo ms. Embora o princpio da casa dos pombos seja uma observao trivial, pode ser usado para demonstrar resultados possivelmente inesperados . Por exemplo, em toda grande cidade, digamos com mais de 1 milho de habitantes existem pessoas com o mesmo nmero de fios de cabelo. Demonstrao: Tipicamente uma pessoa tem cerca de 150 mil fios de cabelo. razoavel supor que ningum tem mais de 1.000.000 de fios de cabelo em sua cabea. Se h mais habitantes do que o nmero mximo de fios de cabelo, necessariamente pelo menos duas pessoas tero exatamente o mesmo nmero de fios de cabelo.

24


1.12 Caos Fatorial: !n.Suponha que queremos calcular todos os anagramas da palavra ESCOLA, de modo que nenhuma letra ocupe o seu lugar original, ou primitivo. Um deles seria SEOCAL, uma vez que nenhuma letra ocupa seu lugar inicial. Esse tipo de permutao chamada de catica ou desordenada e o caos fatorial n ( tambm chamado de subfatorial ou derangements em Ingls), simbolizado por !n , usado para calcular o nmero dessas permutaes caticas. Lembre-se que o fatorial calcula o total de permutaes de um conjunto.

Definio 1.11.: Chama-se caos fatorial de um inteiro no negativo n ( n 0 ), o inteiro que se indica por !n, e tal que:

!n n!Para n 1 , temos:

1 1 1 1 ( 1)n ... 0! 1! 2! 3! n! 1 1 ( 1)n ... 2! 3! n!n

n

n!k

( 1)n 0 k!

!n n!Pode-se provar que !nn! . e

n!k

( 1)n 2 k!

M. Hassani deu outras formas para o caos fatorial:!n n! 1 ,n 1 e

e

!nOs 10 primeiros valores !n, so: n 0 1 2 3 4 5 6 7 8 9 10

e e

1

n!

en! , n 1

n! 1 0 1 2 9 44 265 1854 14833 133496 1334961

25


Voltando ao problema comentando no incio, podemos afirmar que o nmero de permutaes caticas da palavra ESCOLA !6 = 265.

Exemplos:a) !6 6!1 1 1 2! 3! 4! 9 1 1 !6 6! 24 5! 6! 6.5.4!.9 6.5! !6 4! 5! !6 265 1 1 5! 6! 9 6! 4! 6! 270 6! 1 1 2 6 1 1 5! 6! 6!6 1

1 24

1 1 5! 6!

b) !6

6! e 6! 1 e

720 2,718... 721 2,718...

264,87...

265

c) !6

265, 241...

265

d) !6!6

2,718...2221,92

1 .720 2,718...1956,96

2,718... .720265

3,086... .720

2, 718... .720

2221 1956

1.13 Left Fatorial: L!n

Dura Kurepa , em 1971 publicou a o conceito de L!n, o left factorial, definido comon 1

L !n

0! 1! 2! ... ( n 1)!k 0

k!

Um famoso problema em aberto na Teoria dos Nmeros, uma conjectura feita por Kurepa de que o MDC (n!, L!n) = 2 para todo n maior que 1. Abaixo colocamos os 10 primeiros valores do left fatorial. Por definio, L!0 = 0.n 0 1 2 L!n 0 1 2

26


3 4 5 6 7 8 9 10

4 10 34 154 874 5914 46234 409114

O left fatorial sempre par para qualquer inteiro maior que 1. Se dividirmos o left fatorial por 2, obtemos alguns valores primos. Veja L !n n 2 3 2 4 5 5 17 8 2957 9 23117 10 204557 L !n Uma questo em aberto saber se existem infinitos primos da forma . 2

EXERCCIOS1) Sem usar P.A., calcule a soma dos n primeiros inteiros positivos. 2) Calcular o inteiro positivo n, sabendo que 3n+2 . 2n+3 = 2592. 8) Decompor o inteiro 565 numa soma de cinco inteiros mpares consecutivos. 9) Achar todas as solues inteiras e positivas da equao (x + 1)(y + 2) = 2xy. 10) Determinar todos os inteiros positivos de dois algarismos que sejam igual ao qudruplo da soma dos seus algarismos. 11) Achar o menor e o maior inteiro positivo de n algarismos. 12) Resolva a equao: (x + 2)! = 72.x! 13) Resolver a equao:

3) Calcule o inteiro positivo n, sabendo-se que: 3n + 3n+1 + 3n+2 + 3n+3 = 1080. 4) Com uma calculadora, achar os valores de n < 10 para os quais n! + 1 um quadrado perfeito. 5) Sendo m e n inteiros positivos, dizer se verdadeiro ou falso: a) (mn)! = m!. n! b) (m + n)! = m! + n! 6) Demonstrar: (n 1)! [(n + 1)! n!] = (n!)2 7) Sendo n > 2, demonstrar: (n2)! > (n!)2.

7 x2

7 x 2x 2

14) Demonstrar :

n k

n k 1 n k 1 k

27

CAPTULO 1 NMEROS INTEIROS NOES FUNDAMENTAIS 15) Achar todas as solues inteiras e positivas da equao: x2 y2 = 88.; 16) Verificar se o quadrado de um inteiro pode terminar em 2, 3, 7 ou 8. 17) Hilbert escreveu os inteiros de 1 at 1000 (inclusive), em ordem decrescente. Sem usar P.A, determine qual foi o 3330 inteiro escrito? 18) Calcular o nmero de algarismos necessrios para ser escrever os nmeros positivos de 1, 2. 3, 4, ......, n algarismos. 19) O produto de um inteiro positivo de trs algarismos por 7 termina direita por 638. Achar esse inteiro. 20) Determinar quantos algarismos se emprega para numerar todas as pginas de um livro de 2748 pginas. 21) Dois homens estavam conversando num bar quando um virou para o outro e disse: Tenho trs filhas a soma de suas idades igual ao nmero da casa em frente e o produto 36. Posso determinar as idades de suas filhas apenas com esses dados? No. Dar-lhe-ei um dado fundamental: minha filha mais velha toca piano. Determine a posio (linha e coluna) ocupada pelo nmero 107. 26) Mostrar que o produto de quatro algarismos consecutivos, aumentado de 1, um quadrado perfeito. 27) A soma dos quadrados de dois inteiros 3332 e um deles o qudruplo do outro. Achar os dois inteiros. 28) Escrever os inteiros de 1 a 1993, inclusive, quantas vezes o algarismo 1 escrito? 29) Determinar o inteiro n > 1 de modo que a soma 1! + 2! + 3! + ... + n! seja um quadrado perfeito. 30) A mdia aritmtica de dois inteiros positivos 5 e a mdia geomtrica 4. Encontre esses nmeros. 31) Achar cinco inteiros positivos consecutivos cuja soma dos quadrados igual a 2010. 32) O resto por falta da raiz quadrada de um inteiro positivo 135 e o resto por excesso 38. Achar esse inteiro. 33) Resolver a equao

-

x ! 3( x 2)! x ! 3( x 2)!

31 29

Determine as idades das filhas e o nmero da casa em frente. 22) Calcular a soma dos trs maiores nmeros inteiros de, respectivamente, trs, quatro e cinco algarismos. 23) Determinar a diferena entre o maior nmero inteiro com seis algarismos diferentes e o maior inteiro com cinco algarismos tambm diferentes.s 24) Um livro tem 1235 pginas. Determinar o nmero de vezes que o algarismo 1 aparece na numerao da pginas deste livro. 25) Os nmeros abaixo esto dispostos em linhas e colunas. 1 2 8 9 15 16 22 23 29 30

34) Achar o inteiro que deve ser somado a cada um dos inteiros 2, 6 e 14 para que, nesta ordem, formem uma proporo contnua. 35) Coloque em ordem crescente: .

260 ; 340 ; 720

36) Achar o valor mnimo de uma soma de 10 inteiros positivos distintos, cada um dos quais se escreve com trs algarismos. 37) O menor nmero natural n, diferente de zero, que torna o produto de 3888 por n um cubo perfeito : 38) Um estudante ao efetuar a multiplicao de 7432 por um certo inteiro achou o produto 1731656, tendo trocado, por engano, o algarismo das dezenas do multiplicador, tomando 3 em vez de 8. Achar o verdadeiro produto. 39) Achar o menor inteiro cujo produto por 21 um inteiro formado apenas por 4 algarismo.

28

CAPTULO 1 NMEROS INTEIROS NOES FUNDAMENTAIS 40) Escreve-se a seqncia natural dos inteiros positivos, sem separar os algarismos: 123456789101112131415... Determinar: a) o 435 algarismo Apertando um boto do bordo do retngulo, trocam de cor ele e seus vizinhos (do lado ou em diagonal). Apertando o boto do centro, trocam de cor todos os seus 8 vizinhos porm ele no. Exemplos: Apertando 1, trocam de cor 1, 2, 4 e 5. Apertando 2, trocam de cor 1, 2, 3, 4, 5 e 6. Apertando 5, trocam de cor 1, 2, 3, 4, 6, 7, 8 e 9. Inicialmente todos os botes esto verdes. possvel, apertando sucessivamente alguns botes, torn-los todos vermelhos? 50) Escrevemos abaixo os nmeros naturais de 1 a 10. 1 2 3 4 5 6 7 8 9 10.

b) o 1756 algarismo. c) o 12387 algarismo.

41) Escreve-se a seqncia natural dos inteiros positivos pares, sem separar os algarismos: 24681012141618... Determinar o 2574 algarismo que se escreve. 42) As representaes decimais dos nmeros 2 e 51999 so escritos lado a lado. O nmero de dgitos escritos igual a: 43) Mostrar que o produto de dois fatores entre 10 e 20 o dcuplo da soma do primeiro com as unidades do segundo mais o produto das unidades dos dois. 44) Achar o menor inteiro positivo que multiplicado por 33 d um produto cujos algarismos so todos 7. 45) Os inteiros a e b so tais que 4 < a < 7 e 3 < b < 4. Mostrar que 0 < a b < 4. 46) Os inteiros a e b so tais que 1 < a < 3 e 2 < b < 0. Mostrar que 1 < a b < 5. 47) Os inteiros a e b so tais que -2 < a < 2 e 2 < b < 2. Mostrar que 4 < a b < 4. 48) Em um quartel existem 100 soldados e, todas as noites, trs deles so escolhidos para trabalhar de sentinela. possvel que aps certo tempo um dos soldados tenha trabalhado com cada um dos outros exatamente uma vez? 49) Um jogo consiste de 9 botes luminosos (de cor verde ou vermelha) dispostos da seguinte forma:1 4 2 5 3 6

1999

Antes de cada um deles, coloque sinais + ou de forma que a soma de todos seja zero. 51) Escrevemos abaixo os nmeros naturais de 1 a 11. 1 2 3 4 5 6 7 8 9 10 11

Antes de cada um deles, coloque sinais + ou de forma que a soma de todos seja zero. 52) Para numerar as pginas de um livro foram utilizados 663 algarismos. Quantas pginas tinha o livro? 53) Seja Q = 1! + 2! + 3! + ... + n!. Para quantos valores de n tem-se Q quadrado perfeito? 54) Quantos so os nmeros naturais de 4 dgitos que possuem pelo menos dois dgitos iguais? 55) Quantos so os nmeros de 5 algarismos, na base 10: a) Nos quais o algarismo 2 figura? b) Nos quais o algarismo 2 no figura? 56) Permutam-se de todos os modos possveis os algarismos 1, 2, 4, 6, 7 e escrevem-se os nmeros assim formados em ordem crescente. a) Que lugar ocupa o nmero 62417? b) Qual o nmero que ocupa o 66 lugar? c) Qual o 200 algarismo escrito? d) Qual a soma dos nmeros assim formados?

7

8

9

29

Captulo 2:

INDUO MATEMTICAINTRODUO

A

s cincias naturais utilizam o mtodo chamado induo emprica para formular leis que devem reger determinados fenmenos a partir de um grande nmero de observaes particulares, selecionadas adequadamente. Esse tipo de procedimento, embora no seja uma demonstrao de que um dado fato logicamente verdadeiro, frequentemente satisfatrio. Por exemplo: ningum duvidaria de que quando um corpo liberado ao seu prprio peso, no vcuo, na superfcie da terra, ele cai segundo a vertical do local. A validade de um teorema matemtico se estabelece de forma totalmente diferente. Verificar que uma certa afirmao verdadeira num grande nmero de casos particulares no nos permitir concluir que ela vlida. Para demonstrar a verdade de uma sequncia infinita de proposies, uma para cada inteiro positivo, introduziremos o chamado mtodo de recorrncia ou induo matemtica.

2.1 Elemento mnimo de um conjunto de inteirosDefinio 2.1: Seja A um conjunto de inteiros. Chama-se elemento mnimo de A um elemento a A tal que a x para todo x A . Representa-se pela notao minA, que se l: mnimo de A. Portanto, simbolicamente: minA = a (a A e ( xA) ( ax ))

Teorema 2.1: Se a elemento mnimo de A, ento esse elemento nico. Demonstrao: Com efeito, se existisse um outro elemento mnimo b de A, teramos: i) a b , porque a = minA. ii) b a , porque b = minA..

30

CAPTULO 2 INDUO MATEMTICA

Logo, pela propriedade anti-simtrica da relao de ordem natural em Z, temos a = b. O elemento mnimo de A, se existe, denomina-se tambm primeiro elemento de A ou menor elemento de A Exemplo 2.1: O conjunto N = {1, 2, 3,...} dos inteiros positivos tem o elemento mnimo, que 1 (minN = 1), porque 1 N e 1 n para todo n N . Exemplo 2.2: O conjunto A x | x 12 13), porque 13 A e 13 x para todo x A . tem o elemento mnimo, que 13 (minA =

Exemplo 2.3: O conjunto 0, 1, 2, 3,... dos inteiros no positivos no tem o elemento mnimo, porque no existe a Z- tal que a x para todo x Z- . Exemplo 2.4: O conjunto A porque 3 A (3 divide 9) e 3

x |3divide x 2 tem o elemento mnimo 3 (min A = 3),x para todo x A (1 Ae2 A).

2.2 Princpio da boa ordenaoTodo conjunto no vazio A de inteiros no negativos possui o elemento mnimo. Em outros termos, todo subconjunto no vazio A do conjunto

Z+ ={0 ,1, 2, 3, ...}dos inteiros no negativos (

A

Z+ ) possui o elemento mnimo, isto , simbolicamente:Z ,A)min A

( A

Exemplo 2.5: O conjunto A = {1, 3, 5, 7,...} dos inteiros positivos mpares um subconjunto no vazio de

Z+ (

A

Z+ ).

Logo, pelo Princpio da boa ordenao, A possui o elemento mnimo (minA = 1). Exemplo 2.6: O conjunto P = {2,3,5,7,11, ...} dos inteiros primos um subconjunto no vazio de Z+ ( P Z+). Logo, pelo Principio da boa ordenao, P possui o elemento mnimo (minP = 2). Teorema 2.2 (de Archimedes): Se a e b so dois inteiros positivos quaisquer, ento existe um inteiro positivo n tal que na b . Demonstrao:

31


Suponhamos que a e b so dois inteiros positivos para os quais na b para todo inteiro positivo n. Ento, todos os elementos do conjunto: S = {b na | n N } so inteiros positivos e, pelo Princpio da boa ordenao, S possui o elemento mnimo,

digamos minS = b ka.E como b (k + 1)a pertence a S, porque S contm todos os inteiros positivos desta forma, temos: b (k + 1) a = (b ka) a < b ka isto , b ka no o elemento mnimo de S, o que uma contradio. Logo, a propriedade archimediana verdadeira. Assim, por exemplo: i) se a = 2 e b = 11, ento n = 6, porque 6.2 > 11; ii) se a = 9 e b = 5, ento n =1, porque 1.9 > 5.

2.3 Princpio de Induo Finita.Quando uma proposio enunciada em termos de nmeros naturais, o Princpio de induo finita constitui um eficiente instrumento para demonstrar a proposio no caso geral. Na prtica, o mtodo pode ser entendido por um artifcio muito simples. Vamos supor que temos uma srie de domins idnticos colocados em fila, que comea por um deles e prossegue indefinidamente. Nosso objetivo - empurrando apenas um domin - garantir que todos caiam. Como derrubar todos os domins? Para isso, basta nos assegurarmos de que: 1) O primeiro domin cai; 2) Os domins esto dispostos de tal modo que qualquer um deles - toda vez que cai -, automaticamente, empurra o domin seguinte e o faz cair tambm. Assim, mesmo que a fila se estenda indefinidamente, podemos afirmar que todos os domins cairo.

32


Vamos estabelecer matematicamente esses procedimentos. Teorema 2.3 Seja S um subconjunto do conjunto N dos inteiros positivos ( S satisfaz as duas seguintes condies: i) 1 pertence a S ( 1 S ); ii) para todo inteiro positivo k, se k S , ento (k 1) S . Nestas condies, S o conjunto N dos inteiros positivo: S = N. Demonstrao: Suponhamos, por absurdo, que S no o conjunto N dos inteiros positivos ( S conjunto de todos os inteiros positivos que no pertencem a S, isto : X = {x | x N e x S } = N S Ento, X um subconjunto no vazio de N ( X N ) e, pelo Princpio da boa ordenao, existe o elemento mnimo x0 de X (minX = x0 ). Pela primeira condio, 1 S , de modo que x0 > 1 e, portanto, x0 - 1 um inteiro positivo que no pertence a X. Logo, (x0 - 1) S e, pela segunda condio, segue-se que ( x0 - 1) + 1 = x0S , o que uma contradio, pois, x0N ) e seja X o N ) que

X

N S , isto , x0

S . Assim sendo, X

eS

= N. Consoante este Princpio de induo finita, o nico subconjunto de N que satisfaz s duas condies o prprio N.

2.4 Induo MatemticaEm matemtica, concluses como as que se obtm a seguir so inadmissveis. Por qu? Em que pecam os raciocnios utilizados? Vamos examin-los... 1) Suponha que desejemos obter uma frmula que d o valor da soma Sn = 1 + 3 + 5 + 7 + ... + (2n - 1), para qualquer inteiro positivo de n. fcil ver que: n=1 n=2 n=3 n=4 S1 = 1 = 12; S 2 = 1 + 3 = 4 = 22 ; S 3 = 1 + 3 + 5 = 9 = 32 S4 = 1 + 3 + 5 + 7 = 16 = 42

33


Por meio de um raciocnio indutivo, os resultados obtidos nos levam a afirmar que para todo inteiro positivo n tem-se Sn = n2. 2) Consideremos o trinmio P(n) = n2 + n + 41. Considerando n = 0, obtemos P(0) = 41, que um nmero primo. Substituindo n por 1, chegamos a outro nmero primo, o 43. Substituindo sucessivamente n por 2, 3, 4, 5, 6, 7, 8, 9 e 10, conseguimos como resultados outros nmeros primos (47, 53, 61, 71, 83, 97, 113, 131 e 151, respectivamente). Ento, os resultados obtidos nos induzem a afirmar que, para todo n natural, o trinmio P(n) = n2 + n + 41, sempre produz como resultado um nmero primo. Nos dois exemplos, props-se um resultado geral, supostamente vlido para todo n, com base no fato de que ele correto para alguns valores particulares de n: tal procedimento, entretanto, pode conduzir a concluses falsas. Assim, ainda que em no primeiro caso a proposio geral enunciada resulte correta - por mero acaso! -, a proposio geral do segundo exemplo falsa. De fato, P(n) gera nmeros primos para n= 0, 1, 2, 3, ..., 39, mas para n = 40, ele vale 412, que no um nmero primo. Portanto, no exemplo 2), encontramos uma proposio que - apesar de vlida em 40 casos particulares - no vlida em geral. Note bem: Uma proposio pode ser vlida em uma srie de casos particulares, mas, mesmo assim, no o ser de maneira geral. Coloca-se, ento, o seguinte problema: temos uma proposio que se mostrou correta em muitos casos particulares. No entanto, impossvel verificar todos os casos particulares. Assim sendo, como podemos saber se a proposio correta de modo geral? O Teorema abaixo, esclarece essa questo. Teorema 2.4: Seja P(n) uma proposio associada a cada inteiro positivo n e que satisfaz s duas seguintes condies: i) P(1) verdadeira;

ii) para todo inteiro positivo k, se P(k) verdadeira, ento P(k + 1) tambm verdadeira. Nestas condies, a proposio P(n) verdadeira para todo inteiro positivo n.

Demonstrao: Seja S o conjunto de todos os inteiros positivos n para os quais a proposio P(n) verdadeira, isto : S = { n N | P(n) verdadeira} Pela primeira condio, P(1) verdadeira e, portanto, 1 S . Pela segunda condio, para todo inteiro positivo k, se k S , ento (k 1) S . Logo, o conjunto S satisfaz s duas condies do Princpio de induo finita e, portanto, S = N, isto , a proposio P(n) verdadeira para todo inteiro positivo n.

34


Nota: O teorema 2.4 geralmente denominado Teorema da induo matemtica ou Princpio de induo matemtica, e a demonstrao de uma proposio usando-se este teorema chama-se demonstrao por induo matemtica ou demonstrao por induo sobre n. Na demonstrao por induo matemtica de uma dada proposio P(n) obrigatrio verificar que as condies i e ii so ambas satisfeitas. A verificao da condio i geralmente muito fcil, mas a verificao da condio ii implica em demonstrar o teorema auxiliar cuja hiptese : H: proposio P(k) verdadeira, k N . denominada hiptese de induo, e cuja tese ou concluso : T: proposio P(k + 1) verdadeira.

2.5. Exemplos de demonstrao por Induo MatemticaExemplo 2.7: Demonstrar a proposio: P(n): 1 + 3 + 5 + ... + (2n 1) = n, Demonstrao: i) P(1) verdadeira, visto que 1 = 1.n N

ii) A hiptese de induo que a proposio: P(k): 1 + 3 + 5 + ... + (2k 1) = k, k N verdadeira. Adicionando (2k + 1) a ambos os membros desta igualdade, obtemos: 1 + 3 + 5 + ... + (2k 1) + (2k + 1) = k + (2k + 1) = (k + 1) e isto significa que a proposio P(k + 1) verdadeira. Logo, pelo Teorema da induo matemtica, a proposio P(n) verdadeira para todo inteiro positivo n.

35


Exemplo 2.8: Demonstrar a proposio:

P(n) :

1 1.2

1 1 1 ... 2.3 3.4 n(n 1)

n n 1

, n N

Demonstrao:

1 1 1.2 1 1 2) A hiptese de induo que a proposio:1) P(1) verdadeira, visto que

P(k) :

1 1.2

1 1 1 ... 2.3 3.4 k(k 1)

k k 1

,k

N

verdadeira. Adicionando

1 k 1 k 2

a ambos os membros desta igualdade, obtemos:

1 1.2 k

1 1 1 ... 2.3 3.4 k(k 1) 1 k 1 k 2

1 k 1 k 2 k 1 k 2

k 1

k 2 2k 1 (k 1) k 2

e isto significa que a proposio P k 1 verdadeira. Logo, pelo Teorema da induo matemtica, a proposio P n verdadeira para todo inteiro positivo n. Exemplo 2.9: Demonstrar a proposio:

P(n) : 3| 22n 1 ,Demonstrao: 1) P (1) verdadeira, visto que 3 | 22 1 . 2) A hiptese de induo que a proposio: P k : 3 | 22k 1 , k N verdadeira. Portanto: 22k 1 = 3q, com q Z

n N

36


o que implica:

22 k 1

1 22.22k 1 4.22k 1 4.22k 4 4 1 4 22k 1 4.3q 3 3(4q 1) 3

isto , a proposio P k 1 verdadeira. Logo, pelo teorema da induo matemtica, a proposio P n verdadeira para todo inteiro positivo n. Exemplo 2.10: Demonstrar a proposio:

P(n) : 2n n,Demonstrao: 1) P(1) verdadeira, visto que 2 = 2 > 1. 2) A hiptese de induo que a proposio: P(k): 2k

n N

k, k

N

verdadeira. Portanto: 2.2k > 2k ou 2k+1 > k + k k+1

o que implica: 2k 1 k 1 , isto , a proposio P(k+1) verdadeira. Logo, pelo Teorema da induo matemtica, a proposio P(n) verdadeira para todo inteiro positivo n.

2.6 . Outras formas da induo matemticaTeorema 2.5 Seja r um inteiro positivo fixo e seja P(n) uma proposio associada a cada inteiro n r e que satisfaz s duas seguintes condies: i) P(r) verdadeira; ii) para todo inteiro k

r, se P(k) verdadeira, ento P(k + 1) tambm verdadeira. r..

Nestas condies, P(n) verdadeira para todo inteiro n

37


Demonstrao: Seja S o conjunto de todos os inteiros positivos n para os quais a proposio P(r + n 1) verdadeira, isto : S = {n N | P(r + n 1) verdadeira} S. E, pela segunda

Pela primeira condio, P(r) = P(r + 1 1) verdadeira, isto , 1 condio, se P(r + k 1) verdadeira, ento: P((r + k 1) + 1) = P(r + (k + 1) 1)

tambm verdadeira, isto , se k S, ento (k + 1) S. Logo, pelo Princpio da induo finita, S o conjunto dos inteiros positivos: S = N, isto , a proposio P(r + n 1) verdadeira para todo n N , ou seja, o que a mesma coisa, a proposio P(n) verdadeira para todo inteiro n r . Exemplo 2.11: Demonstrar a proposio: P(n): 2n Demonstrao: 1) P(4) verdadeira, visto que 24 16 4! 24 . 2) Suponhamos, agora, que verdadeira a proposio: P(k): 2k Ento, por ser 2 < k + 1 para k multiplicando termo a termo ( I ) e ( II ):4 ( II ),

n!,

n

4

k !, k

4 (I)

2k

1

k !.(k 1) ou 2k

1

(k 1)!

isto , a proposio P(k + 1) verdadeira. Logo, pelo teorema 2.5, a proposio P(n) verdadeira para todo inteiro n 4 .

Observe-se que a proposio P(n) falsa para n = 1, 2, 3, pois, temos: 2 > 1! , 2 > 2! , 2 > 3! Exemplo 2.12: Demonstrar a proposio:

38


P(n) : n2 > 2n + 1, Demonstrao: 1) P (3) verdadeira, visto que 32 = 9 > 2. 3 + 1= 7. 2) Suponhamos, agora, que verdadeira a proposio:

n

3

P(k) : k2 > 2k + 1, k Ento, temos:

3

k2 + (2k+ 1) > (2k+1) + (2k+1) ou (k +1)2 > 2 (k + 1) + 2k > 2 (k + 1) + 2 > 2 (k +1) + 1, k e, portanto: (k +1)2 > 2 (k +1) + 1, k 3. 3

Isto , a proposio P k 1 verdadeira. Logo, pelo teorema 2.5, a proposio P n verdadeira para todo inteiro n 3 . Observa-se que a proposio P n falsa para n = 1 e n = 2, pois, temos: 12 < 2.1+1 e 22 < 2.2 + 1 Teorema 2.6 Seja P(n) uma proposio associada a cada inteiro positivo n e que satisfaz s duas seguintes condies: i) P(1) verdadeira; ii) para todo inteiro positivo k, se P(1), P(2),..., P(k) so todas verdadeiras, ento P(k + 1) tambm verdadeira. Nestas condies, a proposio P(n) verdadeira para todo inteiro positivo n.

39


Demonstrao: Seja S o conjunto de todos os inteiros positivos n para os quais a proposio P(n) verdadeira, isto : S = { n N | P(n) verdadeira} Suponhamos por absurdo, que S N e seja X o conjunto de todos os inteiros positivos que na pertencem a S, isto : X = {x | x N e x S } = N S Ento, X um subconjunto no vazio de N e, pelo Princpio da boa ordenao, existe o elemento mnimo j de X (minX = j). Pela primeira condio, 1 S , de modo que j > 1, e como j o menor inteiro positivo que no pertence a S, segue-se que as proposies P(1), P(2),..., P(j 1) so todas verdadeiras. Ento, pela segunda condio, a proposio P(j) verdadeira e j S , o que uma contradio, pois j X , isto , j S . Assim sendo, S = N e a proposio P(n) verdadeira para todo inteiro positivo n. Teorema 2.7 Seja r um inteiro positivo fixo e seja P(n) uma proposio associada a cada inteiro n r e que satisfaz s duas seguintes condies: 1) P(r) verdadeira; 2) para todo inteiro k > r, se P(m) verdadeira para todo inteiro m tal que r P(k) verdadeira. Nestas condies, a proposio P(n) verdadeira para todo inteiro n r .m k , ento

Demonstrao: Seja S o conjunto de todos os inteiros n r para os quais a proposio P(n) falsa, isto : S = { n N | n r e P(n) falsa} Suponhamos, por absurdo, que S no vazio ( S ). Ento, pelo Princpio da boa ordenao, existe o elemento mnimo j de S (minS = j). Pela primeira condio, r S , de modo que j > r, e, por conseguinte P(m) verdadeira para todo inteiro m tal que r m j . Assim sendo, pela segunda condio, P(j) verdadeira e ), e a j S , o que uma contradio, pois, j S . Logo, o conjunto S vazio ( S proposio P(n) verdadeira para todo inteiro n r .

40


Nota Histrica

Era ideia assente na comunidade matemtica do sculo XIX, que a induo era obra do matemtico francs Blaise Pascal , tendo em conta diversas demonstraes que apresenta no seu Trait du Triangle Arithmtique. Essa situao seria integralmente modificada, vinte anos aps a formulao moderna de induo matemtica fixada por Giuseppe Peano , quando Giovanni Vacca , em 1909, num artigo de trs pginas publicado no Bulletin of American Mathematical Society, vem defender que o italiano Francesco Maurolico , pelos trabalhos que desenvolveu no primeiro livro de aritmtica includo na sua Opuscula Mathematica, escrita em 1557 e publicado em Veneza no ano de 1575, como "the first discoverer of the principle of mathematical induction". O artigo de Vacca encontrou eco, ainda que eventualmente sem verificao posterior, em autores importantes como Moritz Cantor ou Siegmund Gnther . M. Cantor, por exemplo, que atribuiu inicialmente a Pascal a principal origem do mtodo de induo completa (em Vorlesungen uber Geschichte der Mathematik, vol. 2, p. 749), viria a transferir esse atributo para Maurolico (em Zeichrift fur Mathematischen und Naturwissenschaftlichen Unterricht, vol 33, 1902, p. 536), segundo conta devido a uma informao oral que lhe foi prestada pelo prprio Vacca. Passar-se-iam mais de quarenta anos sem que o artigo de Vacca fosse alvo de qualquer crtica. At que Hans Freudenthal (em Zur Geschichte der vollstndigen Induktion, Archive Internationale d'Histoire des Sciences 6 (1953) 17-37) depois de um exame detalhado dos trabalhos de Maurolico, vem sustentar que em apenas trs pontos conseguiu reconhecer uma certa forma de induo matemtica: uma forma arcaica, contudo, ao contrrio do que observou em Pascal, onde a induo formulada pela primeira vez de uma maneira abstrata.

41


EXERCCIOS1) Demonstrar por "induo matemtica": c) 5 | (8n 3n) n n n n N N. N

n (n 1)(2n 1) a) 1 + 2 + 3 + ... + n = 62 2 2 2

d) 24 | (52n 1) e) 7 | (2 1) 8 | 32n + 7,3n

n3

N2 23 3 3

f) n

b)

n (n 1) 1 + 2 + 3 + ... + n = 4N 12 + 32 + 52 + ... + (2n 1)2 =

4) Demonstrar que 10n + 1 9n 10 um mltiplo de 81 para todo inteiro positivo n

c)

n ( 4n 3

2

1)

5) Demonstrar que n N

n3 3

n5 5N

7n um inteiro 15

positivo para todo n

d) 13 + 33 + 53 + ... + (2n 1)3 = n2(2n2 1) 6) Prove que, para todo inteiro n e) 1.2 + 2.3 + 3.4 + ... + n(n + 1) =

1 , o nmero

n (n 1)( n 3f)

2)1 2 1 1 3 ... 1 1 n n 1

an

4

n

1

3

inteiro e mpar.n

1 1 1, n N

7) Para n

1, mostre que S nk 1

k ! um

inteiro mpar. g) a + aq + aq2 + ...+aqn =

a (q n 1 1) ,q 1 q 1

8) Para n 0 , mostre que an 11n um inteiro divisvel por 133.

2

122n

1

2) Demonstrar por "induo matemtica" a) 2n < 2n+1 nn 2

N 5 5

9)

Para n a) b)

3 , mostre quen

b) 2 > n c)

n

n 1 n!2

nn nn . .

1

4n > n4 nn 3 2

d) 2 > n e) f) g)

n n n

10 4 6 10) Mostre que sempre possvel pagar, sem receber troco, qualquer quantia inteira de $, maior que $7, com notas de $3 e $5. N

n!>n

n! > n3

1

1 4

1 9

...

1 n2

2

1 , n n

3) Demonstrar por "induo matemtica" a) 2 | (3n 1) n N N

b) 6 | (n3 n) n

42

Captulo 3:

SOMATRIOS E PRODUTRIOS3.1 . SomatriosSejam os n > 1 inteiros a1,a 2 ,...,a n . Para indicar, de modo abreviado, a soma a1 a 2 ... a n desses n inteiros usa-se a notao:n

aii 1

que se l: somatrio de a i de 1 a n. Em particular, para n = 2, 3,..., temos:2 3

aii 1

a1 a 2 ,i 1

ai

a1 a 2

a 3 , ...

A letra i chama-se o ndice do somatrio e pode ser substituda por qualquer outra diferente de a e de n um ndice mudo. E os inteiros 1 e n que figuram abaixo e acima da letra grega maiscula (sigma) chamam-se respectivamente limite inferior e limite superior do ndice i. O nmero de parcelas de um somatrio sempre igual diferena entre os limites superior e inferior do seu ndice mais uma unidade. Se m e n so dois inteiros, com m n , ento, por definio:n

aii m

am am

1

am

2

...a n

Exemplo 3.1: Temos:7

5ii 1

5.1 5.2 5.3 5.4 5.5 5.6 5.7 5 10 15 20 25 30 35 140

43

CAPTULO 3 SOMATRIOS E PRODUTRIOS4

8j 3j 1

8.1 3

8.2 3 68

8.3 3

8.4 3

5 13 21 298

k .2kk 3

3.23

4.44

5.25

6.26

7.27

8.28

24 64 160 384 896 2048 3576


2 4 8 16 32 64i 1

2i

15

1 3 5 ... 29j 1

2j 1

3.2. Propriedades dos somatriosn n n

Teorema 3.1:i 1

(a i

bi )i 1

aii 1

bi

Demonstrao: Com efeito, desenvolvendo-se o primeiro membro, temos:n

(a i bi ) (a1 b1 ) (a 2 b 2 ) ... (a n b n )i 1 n n

(a1 a 2 ... a n ) (b1 b 2 ... b n )i 1

aii 1

bi

n

Teorema 3.2i 1

a

na

Demonstrao: Seja ai

a para i = 1, 2,..., n. Ento, temos:n n

ai 1 i 1

ai

a1 a 2 ... a n

a a ... a

na

n

n

Teorema 3.3i 1

(a i

a)i 1

ai

na

Demonstrao:

44

CAPTULO 3 SOMATRIOS E PRODUTRIOS

Consoante os dois teoremas anteriores, temos:n n n n

(a ii 1

a)i 1

aii 1

ai 1

ai

na

n

n

Teorema 3.4i 1

ka i

ki 1

ai

Demonstrao: Com efeito, desenvolvendo o primeiro membro, temos:n n

ka ii 1

ka1

ka 2 ... ka n

k(a1 a 2 ... a n )

ki 1

ai

20

Exemplo 3.3: Calculari 1

(5i 2)

Consoante os teoremas anteriores temos, sucessivamente:20 20 20 20

(5i 2)i 1 i 1

5ii 1

2

5i 1

i 20.2

5(1 2 ... 20) 40

1 5. (1 20)20 40 2

5.210 40 1090

3.3. ProdutriosSejam os n > 1 inteiros a1,a 2 ,...,a n . Para indicar, de modo abreviado, o produto a1a 2 ...a n desses n inteiros usa-se a notao:n

aii 1

que se l: produtrio de a i de 1 a n. Em particular, para n = 2, 3,..., temos:2 3

aii 1

a 1a 2 ,i 1

ai

a1a 2 a 3 , ...

45

CAPTULO 3 SOMATRIOS E PRODUTRIOS

A letra i chama-se o ndice do produtrio e pode ser substituda por qualquer outra diferente de a e de n um ndice mudo. E os inteiros 1 e n que figuram abaixo e acima da letra grega maiscula (pi) chamam-se respectivamente limite inferior e limite superior do ndice i. O nmero de fatores de um produtrio sempre igual diferena entre os limites superior e inferior do seu ndice mais uma unidade. Se m e n so dois inteiros, m n , ento, por definio:n

aii m

a m .a m 1.a m 2 ...a n


3ii 1

3.1 3.2 3.3 3.4 3.5 3.6

=3.6.9.12.15.18=5248804

5j 3j 1

5.1 3 5.2 3 5.3 3 5.4 3 =2.7.12.17 2856


3.9.27.81.243.729i 1

3i

16

1.3.5.7....31j 1

2j 1n

1.2.3... n 1 n

n!=i=1

i

3.4. Propriedades dos Produtriosn n n

Teorema 3.5i 1

a i bii 1

ai.i 1

bi

Demonstrao: Com efeito, desenvolvendo o primeiro membro, temos:n n n

a i bii 1

(a1b1 )(a 2 b 2 )...(a n b n )

(a 1a 2 ...a n )(b1b 2 ...b n )i 1

a i.i 1

bi

46

CAPTULO 3 SOMATRIOS E PRODUTRIOSn

Teorema 3.6i 1

a

an

Demonstrao: Seja ai

a para i = 1, 2,..., n. Ento, temos:n n

ai 1 i 1

ai

a1a 2 ...a n

a.a...a

an

n

n

Teorema 3.7i 1

ka i

kni 1

ai

Demonstrao: Com efeito, desenvolvendo o primeiro membro, temos:n n n n i 1

ka ii 14

(ka1 )(ka 2 )...(ka n ) k (a1a 2 ...a n ) k

ai

Exemplo 3.6: Calculari 1

(2i 1)

Consoante o teorema 3.7, temos:4 4

(2i 1)i 1 i 1 n n

(2i 1) (3.5.7.9) 945 893025n

Exemplo 3.7: Demonstrari, j 1

a iji 1 j 1

a ij

Com efeito, desenvolvendo o primeiro membro, temos:n

a ij (a11a12 ...a1n )(a 21a 22 ...a 2n )...(a n1a n2 ...a nn )i, j 1 n n n n n

a1j.j 1 j 1

a 2 j...j 1

a nji 1 j 1

a ij

47

Captulo 4

DIVISIBILIDADEUm conceito chave em Teoria dos Nmeros o conceito de divisibilidade. Existem muitos aspectos interessantes referentes diviso de nmeros inteiros. Antes que possam ser analisados, necessrio que conceitos bsicos como divisor e divide estejam bem estabelecidos.

4.1. RELAO DE DIVISIBILIDADE EM ZDefinio 4.1: Sejam a e b dois inteiros, com a existe um inteiro q tal que b = aq 0. Diz-se que a divide b se, e somente se,

Se a divide b tambm se diz que a divisor de b, que b mltiplo de a, que a um fator de b ou que b divisvel por a. Notao: a | b ( a divide b) Observao: Se a | b , ento a | b Teorema 4.1: Quaisquer que sejam os inteiros a, b e c tem-se: 1) a | 0 a 0, 1|a e a|a a 1 0

2) Se a | 1 , ento a =

3) Se a | b e se c | d , ento ac | bd 4) Se a | b e se b | c , ento a | c 5) Se a | b e se b | a , ento a = 6) Se a | b com b 0 , ento | a | b |b|

7) Se a | b e se a | c , ento a |(bx + cy) para todo x e y em Z

48

CAPTULO 4 DIVISIBILIDADE

Demonstrao: Em todas as demonstraes estaremos aplicando a Definio 1 e considerando aceitas todas as propriedades operatrias dentro do conjunto . 1) De fato: 0 = a.0; a = 1.a; a = a.1

2) De fato, se a|1, ento 1 = a.q, o que implica a = 1 e q = 1 ou a = -1 e q = -1, ou seja: a = 1. 3) De fato,a|b b a.q

c|dPortanto:

d

c.q1

bd4) De fato:

ac.(q.q1 )

ac | bd

a|b

b

a.q

b|cLogo, c a.(q.q1 ) 5) De fato:a|b

c b.q1

a|c.

b

a.q

b|aLogo:a a(qq1 ) qq1 1

a b.q1

q1 |1

q1

1

a

b

6) De fato, nas condies da proprieade, temos:a|b b a.q, ou seja | b | | a | .| q |

Como q 0 , temos que | q | 1 , desse modo temos | b | | a | . 7) De fato:a|b b a.q

a|c

c a.q1

49


Logo, quaisquer que sejam os inteiros x e y:bx cy aqx aq1 y a(qx q1 y) a | (bx cy)

Esta propriedade (7) pode ser generalizada; ou seja, se

a | bk , k 1,2,3,..., nento, quaisquer que sejam os inteiros

x1, x2 ,..., xntemos:

a | (bx1 bx2 ... bxn )

De acordo com as propriedades (1) e (4), a relao de divisibilidade em reflexiva e transitiva, mas no simtrica.

4.2. Conjunto dos divisores de um inteiroO conjunto de todos os divisores de um inteiro qualquer a indica-se por D(a) = {x Z* | x | a }

imediato que, para todo inteiro a, se tem D(a) = D(-a). Qualquer que seja o inteiro a 0 , se x | a , ento:a x a D(a) [ | a |,| a |]

significando que qualquer inteiro a 0 tem um nmero finito de divisores.

4.3. Divisores comuns de dois inteirosDefinio 4.2 Chama-se divisor comum de dois inteiros a e b todo inteiro d d | a e d | b. 0 tal que

50


Notao: D(a,b) = { x Obs.: D(a,b)

| x | a e x | b} ou seja, D(a,b) = D(a)

*

D(b)

; D(0,0) = *

Exemplo 4.1: Sejam os inteiros a = 12 e b = -15. temos:

D 12 D 15Portanto:D 12, 15

1, 2, 3, 4, 6, 12 1, 3, 5, 15

D 12

D

15

1, 3

4.4. Teorema da DivisoO Teorema da diviso, que veremos a seguir, usado por Euclides no seu livro Elementos, estabelece uma diviso com resto. um teorema que foi "provado" uma vez atravs de um algoritmo que explica como se processa a diviso, por esse motivo ficou conhecido como Algoritmo de Euclides. Teorema 4.2 Se a e b so dois inteiros, com b > 0, ento existem e so nicos os inteiros q e r que satisfazem s condies: a = bq + r e 0 r < b Demonstrao:

Existncia Seja S o conjunto de todos os inteiros no-negativos que so da forma a bx, com x , isto : S = {a bx ; x , a bx 0 }

Este conjunto S no vazio, porque, sendo b > 0, temos b resulta: a bx = a + b |a | a+|a| 0

1 e, portanto, para x = - | a |,

Assim sendo, pelo Princpio da boa ordenao, existe o elemento mnimo r de S tal que 0 r e r = a bq ou a = bq + r, com q

51


Alm disso, temos r < b, pois, se fosse r b, teramos: 0 r b = a bq b = a b( q+1 ) < r

isto , r no seria o elemento mnimo de S. Unicidade Para demonstrar a unicidade de q e r, suponhamos que existem dois outros inteiros q 1 e r1 tais que a = bq1 + r1 e 0 Ento, teremos: bq1 + r1 = bq + r por outro lado, temos: -b 0, nada h que demonstrar, e se b < 0, ento | b | > 0, e por conseguinte existem e so nicos os inteiros q1 e r tais que a = | b |q1 + r e 0 ou seja, por ser | b | = - b: a = b(- q1 ) + r e 0 r< |b| r 0, bq a < b(q+1) e, para b < 0, bq a < b(q-1). Exemplo 4.2: Achar o quociente q e o resto r na diviso de a = 59 por b = -14 que satisfazem as condies do algoritmo da diviso. Efetuamos a diviso usual dos valores absolutos de a e b, obtemos:

59 14.4 3o que implica:59 14 4 3

e

0

3

14

Logo, o quociente q

4 e o resto r

3.

Exemplo 4.3: Achar o quociente q e o resto r na diviso de a = -79 por b = 11 que satisfazem as condies do algoritmo da diviso. Efetuamos a diviso usual dos valores absolutos de a e b, obtemos: 79 = 11.7 + 2 o que implica: -79 = 117 2

53


Como o termo r = 2 < 0 no satisfaz a condio 0 r 11 , somando e subtraindo o valor 11 de b ao segundo membro da igualdade anterior, obtemos:79 11 7 11 11 2 11 8 9

com 0 9 11 . Logo, o quociente q = -8 e o r = 9. Exemplo 4.4: Sejam os inteiros a = 1, -2, 61, -59 e b = -7. Temos:1 2 7 .0 1 e 7 .1 5 0 1 7 q 0 e r =1

e0 5 7 q 1 e r=5 61 7 8 5 e 0 5 7 q 8 e r=5 59 7 .9 4 e 0 4 7 q 9 e r=4

4.5. Paridade de um InteiroNa diviso de um inteiro qualquer a por 2 os possveis restos so r = 1 e r = 0. Se r = 0 , ento o inteiro a = 2q denominado par; e se r = 1, ento o inteiro a = 2q + 1 denominado mpar, q . Dois inteiros que so ambos pares ou ambos mpares dizem-se de mesma paridade, a dois inteiros tais que um par e o outro mpar, dizemos que tem paridades diferentes. De modo geral, dado um inteiro a 2 , pode-se sempre escrever um inteiro qualquer n, de modo nico, na forma n aq r , onde k , r e r a . Teorema 4.3 1) A soma ou a diferena de dois nmeros pares par. 2) A soma ou a diferena de dois nmeros mpares par. 3) A soma ou a diferena de um nmero par com um nmero mpar mpar.

Demonstrao: 1) Sejam a = 2k1 e b = 2k2, ento a k2). 3) Sejam a = 2k1 e b = 2k2 +1, ento a b = 2k1 (2k2 +1) = 2(k1 k2) +1. b = 2k1 2k2 = 2(k1 k2). (2k2 +1) = 2(k1 + k2 + 1) ou 2(k1-

2) Sejam a = 2k1 +1 e b = 2k2 +1, ento a

b = (2k1 +1)

54


Exemplo 4.5: Mostrar que o quadrado de qualquer inteiro mpar da forma 8k+1. Com efeito, pelo algoritmo da diviso, qualquer inteiro de uma das seguintes formas:4q, 4q 1, 4q 2, 4q 3

Nesta classificao, somente os inteiros das formas 4q +1 e 4q +3 so mpares e , portanto, os seus quadrados so da forma:4q 1 4q 32

8 2q 2 q 8 2q 2

1 8k 1 3q 1 1 8k 1

2

Assim, por exemplo, 7 e 13 so inteiros mpares, e temos:

72 49 8.6 1 132 169 8.21 1

55


EXERCCIOS1) Mostrar que se a | b, ento (-a) | b, a | (-b) e (-a) | (-b). 2) Sejam a, b e c inteiros. Mostrar que: a ) se a | b, ento a | bc. b ) se a | b e se a | c, ento a2 | bc. c ) a | b se e somente se ac | bc (c 3) Verdadeiro ou falso: se a | (b + c), ento a | b ou a | c. 4) Mostrar que, se a um nmero inteiro qualquer, ento um dos inteiros a, a + 2, a + 4 divisvel por 3. 5) Sendo a um inteiro qualquer, mostrar: a ) 2 | a(a + 1). b ) 3 | a(a + 1)(a + 2) . 6) Mostrar que um inteiro qualquer da forma 6k + 5 tambm da forma 3t + 2. 7) Mostrar que todo inteiro mpar da forma 4k + 1 ou 4k + 3. 8) Mostrar que o quadrado de um inteiro qualquer da forma 3k ou 3k + 1. 9) Mostrar que o cubo de um inteiro qualquer de uma das formas 9k, 9k + 1 ou 9k + 8. 10) Mostrar que: a) n(n + 1)(2n + 1)/6 um inteiro, qualquer que seja o inteiro positivo n. 0). 14) Demonstrar que: Se a e b so inteiros mpares, ento 8 | a2 b2. 15) Determinar os inteiros positivos que divididos por 17 deixam um resto igual ao quadrado do quociente. 16) Verdadeiro ou falso: se a | c e se b | c, ento a | b. 17) Mostrar que a diferena entre os cubos de dois inteiros consecutivos nunca divisvel por 2. 18) Na diviso do inteiro a = 427 por um inteiro positivo b, o quociente 12 e o resto r. Achar o divisor b e o resto r. 19) Na diviso do inteiro 525 por um inteiro positivo o resto 27. Achar os inteiros que podem ser o divisor e o quociente. 20) Na diviso de dois inteiros positivos o quociente 16 e o resto o maior possvel. Achar os dois inteiros, sabendo-se que sua soma 341. 21) Achar os inteiros positivos menores que 150 e que divididos por 39 deixam um resto igual ao quociente. 22) Seja d um divisor de n (d | n). Mostrar que cd | n se e somente se c | (n/d). 23) Sejam n, r e s inteiros tais que 0 < r < n e 0 < s < n. Mostrar que se n | (r s) ento r = s. 24) Mostrar que o produto de dois inteiros mpares um inteiro mpar. 25) Demonstrar que se m e n so inteiros mpares, ento 8 | (m4 + n4 2). 26) Demonstrar que 30 | (n5 n) 27) Mostrar que, para todo inteiro n, existem inteiros k e r tais que n = 3k + r e r = -1, 0, 1. 13) Sendo m e n dois inteiros quaisquer, mostrar que os inteiros m + n e m n tm sempre a mesma paridade.

b) Se a um inteiro mpar, ento 24 | a (a2 1). 11) Mostrar que se a | (2x 3y) e se a | (4x 5y), ento a | y. 12) Sendo a e b dois inteiros quaisquer, mostrar que os inteiros a e a + 2b tm sempre a mesma paridade.

56

CAPTULO 4 DIVISIBILIDADE 28) Mostrar que (1 + 2 + . . . + n) | 3(1 2 + 22 + . . . + n2) para todo n > 1. 29) Mostre que todo inteiro mpar, quadrado perfeito, da forma 4n + 1. 30) Na diviso de 392 por 45, determinar: a) o maior inteiro que se pode somar ao dividendo sem alterar o quociente.

b) o maior inteiro que se pode subtrair ao dividendo sem alterar o quociente. 31) Numa diviso de dois inteiros, o quociente 16 e o resto 167. Determinar o maior inteiro que se pode somar ao dividendo e ao divisor sem alterar o quociente. 32) Achar o maior inteiro de quatro algarismos divisvel por 13 e o menor inteiro de cinco algarismos divisvel por 15. 33) Achar um inteiro de quatro algarismos, quadrado perfeito, divisvel por 27 e terminado em 6. 34) Mostre que se a, b e c so inteiros mpares, a equao ax racional.2

bx

c

0 no tem raiz

35) Um tabuleiro 6 6 est coberto com domins 2 1. Mostre que existe uma reta que separa as peas do tabuleiro sem cortar nenhum domin. 36) Dividindo-se o nmero 245 por um nmero natural b, obtm-se quociente 5 e resto r. Determine o valor da soma dos valores possveis para b. 37) A diviso de um certo nmero inteiro N por 1994 deixa resto 148. Calcule o resto da diviso de N + 2000 pelo mesmo nmero 1994. 38) Considere quatro nmeros inteiros a, b, c e d. Prove que o produto: (a-b) . (c-a) . (d-a) . (d-c). (d-b). (c-b) divisvel por 12. 39) Prove que a mpar.n

bn divisvel por a+b se n

57

Captulo 5

MXIMO DIVISOR COMUM5.1. Mximo Divisor Comum de Dois InteirosDefinio 5.1 Sejam a e b dois inteiros no conjuntamente nulos (a 0 ou b 0). Chama-se mximo divisor comum de a e b o inteiro positivo d (d 0) que satisfaz s condies: 1) d | a e d | b; 2) se c | a e se c | b, ento c d.

Observe-se que, pela condio (1), d um divisor comum de a e b, e pela condio (2), d o maior dentre todos os divisores comuns de a e b.

O mximo divisor comum de a e b indica-se pela notao mdc(a,b). imediato que o mdc(a,b) = mdc(b,a). Em particular: (i) o mdc(0,0) no existe. (ii) o mdc(a,1) = 1 (iii) se a 0, ento o mdc(a,0) = | a |

(iv) se a | b, ento o mdc(a,b) = | a | Assim, por exemplo: mdc(8,1) = 1 mdc(-3,0) = | -3 | = 3 mdc(-6,12) = | -6 | = 6.

Exemplo 5.1 Sejam os inteiros a = 16 e b = 24. Os divisores comuns positivos de 16 e 24 so 1, 2, 4 e 8, e como o maior 8, segue-se que o mdc(16,24) = 8.

Observa-se que mdc(-16,24) = mdc(16,-24) = mdc(-16,-24) = 8. Exemplo 5.2 Sejam os inteiros a = -24 e b = 60. Os divisores comuns positivos de 24 e 60 so 1, 2, 3, 4, 6 e 12, e como o maior deles 12, segue-se que o mdc(-24,60) = 12.

58

CAPTULO 5 MXIMO DIVISOR COMUM

5.2. Existncia e unicidade do MDC.Teorema 5.1 (Identidade de Bzout ) Se a e b so dois inteiros no conjuntamente nulos ( a 0 ou b 0), ento existe e nico o mdc(a,b); alm disso, existem inteiros x e y tais que mdc(a,b) = ax + by Isto , o mdc(a,b) uma combinao linear de a e b.

Nota: Algumas fontes creditam este teorema ao matemtico francs Claude Gaspard Bachet de Mziriac e no ao tambm francs, Etienne Bzout.

Demonstrao: Seja S o conjunto de todos os inteiros positivos da forma au + bv, com u, v S = { au + bv | au + bv Este conjunto S no vazio (S 0 e u, v Z} 0, ento um dos dois inteiros: Z, isto :

), porque, por exemplo, se a e

a = a.1 + b.0

-a = a.(-1) + b.0

positivo e pertence a S. Logo, pelo Princpio da boa ordenao, existe e nico o elemento mnimo d de S: minS = d 0. E, consoante a definio de S, existem inteiros x e y tais que d = ax + by. Posto isto, vamos mostrar que d = mdc(a,b). Com efeito, pelo algoritmo da diviso, temos: a = dq + r, com 0 O que d: r = a dq = a (ax + by)q = a(1 qx) + d(-qy) Isto , o resto r uma combinao linear de a e b. Como 0 r d e d 0 o elemento mnimo de S, segue-se que r = 0 e a = dq, isto , d | a. Com raciocnio inteiramente anlogo se conclui que tambm d | b. Logo, d um divisor comum positivo de a e b. Finalmente, se c um divisor comum positivo qualquer de a e b ( c | b, c 0), ento: c | (ax + by) c|d c d r d

Isto , d o maior divisor comum positivo de a e b, ou seja: mdc(a,b) = d = ax + by e o teorema fica demonstrado. x, y Z

59


Nota: A demonstrao do teorema 1 deixa ver que o mdc(a,b) o menor inteiro positivo da forma ax + by, isto , que pode ser expresso como combinao linear de a e b. Mas, esta representao do mdc(a,b) como combinao linear de a e b no pe punica, pois, temos:

mdc(a,b) = d = a(x + bt) + b(y - at) qualquer que seja o inteiro t. Importa ainda notar que, se d = ar + bs. Para algum par de inteiros r e s, ento d no necessariamente o mdc(a,b). Assim, por exemplo, se: mdc(a,b) = ax + by ento t.mdc(a,b) = atx + bty Para todo inteiro t, isto : d = ar + bd onde d = t.mdc(a,b), r = tx e s = ty. Exemplo 5.3 Sejam os inteiros a = 6 e b = 27. Temos: mdc(6,27) = 3 = 6(-4 + 27t) + 27(1 6t) qualquer que seja o inteiro t. Exemplo 5.4 Sejam os inteiros a = -8 e b = -36. Temos: mdc(-8,-36) = 4 = (-8)4 + (-36)(-1) Teorema 5.2 Se a e b so dois inteiros no conjuntamente nulos (a conjunto de todos os mltiplos do mdc(a,b) = d T = { ax + by | x,y Z} 0 ou b 0), ento o

60


Demonstrao: Como d | a e d | b, segue-se que d | (ax + by), quaisquer que sejam os inteiros x e y, e por conseguinte todo elemento do conjunto T e um mltiplo de d. Por outro lado, existem inteiros x0 e y0 tais que d = ax0 + by0, de modo que todo mltiplo kd de d da forma: kd = k(ax0 + by0) = a(kz0) + b(ky0) isto , kd uma combinao linear de a e b e, portanto, kd elemento do conjunto T.

5.3. Inteiros Relativamente Primos (coprimos ou primos entre si)Definio: Sejam a e b dois inteiros no conjuntamente nulos (a so relativamente primos se, e somente se, o mdc(a,b) = 1. 0eb 0). Diz-se que a e b

Assim, por exemplo, so relativamente primos os inteiros: 2 e 5, -9 e 16, -27 e 35, pois, temos: mdc(2,5) = mdc(-9,16) = mdc(-27,-35) = 1 Dois inteiros a e b coprimos admitem como nicos divisores comuns 1 e 1. Teorema 5.3 Dois inteiros a e b, no conjuntamente nulos (a se, e somente se, existem inteiros x e y tais que ax + by = 1. Demonstrao: ( ) Se a e b so relativamente primos, ento o mdc(a,b) = 1 e por conseguinte existem inteiros x e y tais que ax + by = 1 ( ) Reciprocamente, se existem inteiros x e y tais que ax + by = 1 e se o mdc(a,b) = d, ento d | a e d | b. Logo, d | (ax + by) e d | 1, o que implica d = 1 ou mdc(a,b) =1, isto , a e b so primos entre si. Corolrio 5.1 Se o mdc(a,b) = d, ento o mdc( a/d , b/d ) = 1. Demonstrao: Preliminarmente, observa-se que a/d e b/d so inteiros, porque d um divisor comum de a e b. Posto isso, se o mdc(a,b) = d, ento existem inteiros x e y tais que ax + by = d, ou seja, dividindo ambos os membros desta igualdade por d: 0eb 0), so primos entre si

61


(a/d)x + (b/d)y = 1 Logo, pelo teorema anterior, os inteiros a/d e b/d so primos entre si, isto , o mdc (a/d ,b/d) = 1. Assim, por exemplo: mdc(-12,30) = 6 e mdc(-12/6 , 30/6) = mdc(-2,5) = 1. Corolrio 5.2 Se a | b e se o mdc(b,c) = 1, ento o mdc (a,c) = 1. Demonstrao: Com efeito: a | b b = aq, com q Z mdc(b,c) = 1 bx + cy = 1, com x, y Portanto: a(qx) + cy = 1 mdc(a,c) = 1 Z.

Corolrio 5.3 Se a | c, se b | c e se o mdc(a,b) = 1, ento ab | c. Demonstrao: Com efeito: a|c b|c mdc(a,b) = 1 c = aq1, c = bq2, ax + by = 1, acx + bcy = c com q1 com q2 Z Z Z

com x,y

Portanto: c = a(nq2)x = b(aq1)y = ab(q2x + q1y) ab | c

Observe-se que somente as condies a | c e b | c no implicam ab | c. Assim, por exemplo, 6 | 24 e 8 | 24, mas 6.8 | 24 (o mdc(6,8) = 2 1). Corolrio 5.4 Se mdc(a,b) = 1 = mdc(a,c), ento o mdc(a,bc) = 1.

62


Demonstrao: Com efeito: mdc(a,b) = 1 mdc(a,b) = 1 Portanto: 1 = ax + by(az + ct) = a(x + byz) + bc(yt) o que implica mdc(a,bc) = 1. Corolrio 5.5 Se o mdc(a,bc) = 1, ento mdc(a,b) = 1 = mdc(a,c). Demonstrao: Com efeito: mdc(a,bc) = 1 Portanto: ax + b(cy) = 1 ax + c(by) = 1 mdc(a,b) = 1 mdc(a,c) = 1 ax + (bc)y = 1, com x,y Z. ax + by = 1, com x,y az + ct = 1, com z,t Z Z

Note-se que esta proposio a recproca da anterior. Teorema 5.4 (de Euclides) Se a | bc e se o mdc(a,b) = 1, ento a | c. Demonstrao: Com efeito: a | bc bc = aq, com q Z mdc(a,b) = 1 ax + by = 1, com x, y acx + bcy = c Portanto: c = acx + aqy = a(cx + qy) Note-se que somente a condio a | bc no implica que a | c. Assim, por exemplo, 12 | 9.8, mas 12 | 9 e 12 | 8 mdc(12,9) a|c Z

1 e mdc(12,8)

1.

63


5.4. Caracterizao do MDC de Dois InteirosTeorema 5.5 Sejam a e b dois inteiros no conjuntamente nulos (a positivo d (d 0) o mdc(a,b) se e somente se satisfaz s condies: (1) d | a e d | b (2) se c | a e se c | b, ento c | d Demonstrao: ( ) Suponhamos que o mdc (a, b) = d. Ento, d | a e d | b, isto , a condio (1) satisfeita. Por outra parte, existem inteiros x e y tais que ax + by = d e, portanto, se c | a e se c | b, ento c | (ax + by) e c | d, isto , a condio (2) tambm satisfeita. ( ) Reciprocamente, seja d um inteiro positivo qualquer que satisfaz s condies (1) e (2). Ento, pela condio (2), todo divisor comum c de a e b tambm divisor de d, isto , c | d, e isto implica c d. Logo, d o mdc(a,b). 0 ou b 0). Um inteiro

5.5. MDC de vrios InteirosO conceito de mximo divisor comum, definido para dois inteiros a e b, estende-se de maneira natural a mais de dois inteiros. No caso de trs inteiros a, b e c, no todos nulos, o mdc(a,b,c) o inteiro positivo d (d 0) que satisfaz s condies: (1) d | a, d | b e d | c (2) se e | a, se e | b e se e | c, ento e Assim, por exemplo: mdc(39,42,54) = 3 e mdc(49,210,350) = 7 Importa notar que trs inteiros a, b e c podem ser primos entre si, isto , o mdc(a,b,c) = 1, sem que sejam primos entre si dois a dois, que o caso, por exemplo, dos inteiros 6, 10 e 15. Teorema 5.6 O mdc(a,b,c) = mdc(mdc(a,b),c). Demonstrao: Com efeito, seja mdc(a,b,c) = d e mdc(a,b) = e. Ento, d | a, d | b e d | c, e como existem inteiros x e y tais que ax + by = e, segue-se que d | (ax + by) ou d | e, isto , d um divisor comum de e e c (d | e e d | c). d

64


Por outro lado, se f um divisor comum qualquer de e e c (f | e e f | c), ento f |

Documents

Introdução à Teoria dos Números - UEPA