Baixe Hygino ...tmetica - hygino domingues-fundamentos de aritmetica[168-187] e outras Notas de estudo em PDF para Teoria dos Números, somente na Docsity! De fato, da hipótese segue que m + r = n, para algum r EZ,. As- sim, para todo pEZ: n+p=(m+r)+p=(m+p)+r. Donde: m+p<n+p. o; Compatibilidade com a multiplicação: m €n e O£p = mp < np. Por hipótese n=m +, onde r = (a, 0), para algum a E IN. Supondo p=(b,0), como pn =pm +pr, onde pr=(ab,0)€EZ,, então pm «pn. 2. Imersão de IN em Z Mostraremos agora, dentro da construção que fizemos, em que termos se pode considerar IN como parte de Z, Seja f: IN > Z definida por f(a) = (a, 0), para todo a E Z. Ou seja: fo) =(0,0)=0 (D=(1,0)=+1 TO)=+2 =E9 Então: e Im(f) = (Ka)la EIN) =2Z, =(0,+1,+2, +43, ...). *fa)=1b) = (3,0)- cfa+b=(+50)=(3,0)+(D,0)= f(a)+fb), va, DEIN e fab)=(35,0)= (2,0) - (b, 0) = f(a) fb), va, DE IN s Sea<b,entãob=a+c, para algum c E IN e portanto b=60)-BrcO=(,0)+0)-=ta)+(c0) b, 0) = a =b, o que mostra que f é injetora. o que significa que fa) < Hb) Assim, no que se refere aos aspectos algébricos e à ordenação, Z , é uma cópia de IN, obtida através de f. Daí porque se pode identificar IN com Z, e considerar IN € Z. Mais especificamente, nessa identificação o número natu- ral O passa a se confundir com o inteiro O = (0, 0), o natural 1 com o inteiro +1=(1,0), e assim por diante, A função f considerada costuma ser chamada de imersão de IN em Z, por razões óbvias em face das propriedades que desta- camos a seu respeito. Isso posto, se x=(a, DJEZ, então x=(a, b=(a, 0) +(0, b)= =(a,0)+[-—(b, 0)] e, em consegiuência da identificação feita, x = a — b. Logo, todo inteiro é igual à diferença (em Z) entre dois números naturais. 168 Por outro lado, se a, b € IN, levando em conta a identificação de IN com Z,: a-b=(a,0) - (b,0) = (a, 0) + (0,b) = (a,b) o que mostra que a subtração de dois números naturais é sempre possível em Z — e isso, no fundo, era o que se tinha em vista com a construção do conjunto dos números inteiros. 21 O princípio do menor inteiro A identificação que fizemos de IN com Z, torna válida a demonstração que fizemos em 3.3 do princípio do menor inteiro: o, Seja SC Z,8 +. Se S admite uma cota inferior (e portanto infinitas), então S possui mínimo, EXERCÍCIOS 352. Sea, b, c, d E Z, prove que: a) (a-b) (e — d)= (ac + bd) — (ad + bo) b) (a + b) (c — d) = (ac + bo) — (ad + ba) 353, Sejam x e y inteiros tais que xy = 1. Prove que x=y=1 ou x=y=-1. 354. Prove queia<b+c es a-b<c. 355. Sep >0, prove quea — p< a, para todo a E Z. 356. Proveque:x'=x = x=0 ou x=1. 357. Para todo a E Z, mostre que a-l=máxix EZ|x<a) 358. Sea<be c<d,mosrequea-d<b-c. 359. Proveque:a<bec<d = bc +ad< ac + bd. 360. Mostre que, para todo n E Z, o conjunto (x €EZ|n<x<n+1) é vazio. 169 APÊNDICE II ARITMÉTICA MÓDULO m Sejam > 1 um inteiro e indiquemos por Z,, 0 sistema completo de restos mínimos positivos, módulo m: Z,, = (0,1,2,...,m-— 1). Sex,y €Z,, en- tendemos por soma módulo m de x com y o resto da divisão euclidiana de x + y por m. Usaremos a notação x z y para indicar a soma módulo m de x com y. Por exemplo 6f7=5 pois na divisão de 13 por 8 o resto é 5. Como o resto da divisão euclidiana de um inteiro qualquer por m está sempre em Z,,, então a correspondência (9) +x?y é uma lei de composição interna em Z,, (ou uma operação sobre Z,,) à qual chamamos adição módulo m. Para essa operação valem as propriedades: mm mom o a(xtytfz=x+(y+z) (associativa) m m . agxty=y+x (comutativa) a; Existe elemento neutro: é o número 0. a, Todo a E Z, tem simétrico aditivo em Z,,: é o elemento m — a, poiso res- to da divisão de a + (m — a) = m por m é 0. Provaremos apenas a,, já que a demonstração das demais propriedades é imediata. Vamos supor x + y=nt+y=mg+r,04r<me gPyfr=rPr=n(rHz=mg+r,0<€r,<m). Daí resulta (x +y)+ (ri +2)= (mg +ri)+ (mg + ro) 170 e então: x+y+z=m(g+g)+r (0<r,<m) Portanto r; = (x É y) + z é o resto da divisão euclidiana de x + y + 2 porm. De maneira análoga, mostra-se que x + (y + z) é, também, o resto da divi- são euclidiana de x + y + z por m. Dessas conclusões resulta a igualdade desejada. Para cada par de elementos x, y E Z,,, indicaremos por x * y o produto módulo m de x por y, assim definido: m scg a x” y = resto da divisão euclidiana de xy por m Obviamente a correspondência m Gy) +xºy define também uma lei de composição interna em Z,,: é a chamada multiplica- ão módulo m. Para esta operação valem as seguintes propriedades: m (x"yrz=x"(y"2) (associativa) mx" y=y"x (comutativa) ms Existe elemento neutro: obviamente o número 1. E, envolvendo adição e multiplicação, vale mom mom o dxlytzgn=xytxez ou seja, a multiplicação módulo m é distributiva em relação à adição mó- dulo m. As propriedades apontadas até aqui indicam que Z é, em relação à adi- ção e à multiplicação módulo m, um modelo do que se chama em álgebra de anel comutativo (a qualificação “comutativo”” decorre do fato de se verificar mo)”. Observemos que o próprio Z, em relação à adição e à multiplicação usuais, também é um anel comutativo. Vamos nos referir a Z,, como anel dos inteiros módulo m e a Z como anel dos inteiros, simplesmente. A seguir focalizare- mos algumas diferenças estruturais entre os anéis Z,, (m > 1)e Z. Mas antes vejamos como se podem visualizar as operações num anel Z,,, por meio de tá- buas. Para Z,, por exemplo: + + 4 0 1 2 3 0 1 2 3 o1o 1 2 3 c|jo 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 o 3 2 1 (*) Ver exercício 364. 171 364. 176 Fixado um elemento a E Z,, (a é a chave do código — de transmissão e 27 de recepção), a aplicação x fe x + a permuta os elementos de Z, e, consegiientemente, os elementos do conjunto formado pelo símbolo do espaço e as 26 letras. Dessa forma cada mensagem se transforma em có- digo; o fato de f ser bijetora garante que mensagens diferentes são codifi- cadas de maneira diferente e, ainda, a possibilidade da decodificação. Vejamos, por exemplo, como codificar a frase “eu vou”, usando como chavea = 15. 7 - 5 > 5f15=2 + T 27 - 21 > 2+15=9 > IT 0» 0f15=15 > O 2 > 22 > 22+15=10 > J > 15 5f15=3+ I O<ceam 4 U>2M>mnfs=o- Portanto o código para a frase dada é “TIOJCI”. Para decodificar, por exemplo, G X A, considerando que o simétrico aditivo de 15 é 12 (mantendo, portanto, a chave a = 15), procede-se assim: G> 7>9fwr=19>5s x >> xnfir=-9 > 1 A d1->afn=3s>-M Logo, a mensagem era “sim”. Isto posto: a) Codifique “Teoria dos números" usando a = 5 como chave. b) Se a chave usada foi a = 12, decodifique a mensagem: OMYAUDLZFYQCUOUD Como já foi esboçado neste Apêndice, um anel comutativo é constituído de um conjunto A * Z, uma “adição” (x,y) —» x + y e uma “multi- plicação” (x, y) -» xy sobre A, de modo que: a, (a+b)+c= =a+(b+c), va,b,cEA;agatb=b+a, va, DbEA; as existe elemento neutro para a adição, ou seja, um elemento 0 E A tal que a+0=a, va € A;a,paratodoa E Aexistea' E Atalquea+a' =e (a” é o oposto ou simétrico aditivo de a) m, a(bc) = (ab)c, va,b, cE A; m, existe elemento neutro para a multiplicação, ou seja, um elemento 1 E Atalquea: 1=a,va€A;m,ab=ba, Va, DE A; da(b+c)=ab+ac, Ya,b,cEA. São exemplos de anéis, como já vimos, Z e Z, (vm > 1). Num anel comutativo À a soma € o produto de n elementos a,, à, ..., a, € A(n > 2), bem como a potência enésima de a E A (n > 1) se defi- nem generalizando os conceitos respectivos em Z. Assim, são definidos por recorrência do seguinte modo: za - (E ajeo 7 a - (x sa 4 i=1 i=l e aa= ria (n>1) Isso posto, provemos a chamada fórmula do binômio de Newton para um anel comutativo A qualquer: “Se x e y são elementos não nulos de um anel comutativo (ou seja, x e y são diferentes do elemento neutro da adição de A) então, para todo n >, vale a relação = jn e+m= > (Gero p=0 ! » (o) "mm 0<r<m Observemos que, por definição, a? = 1 (elemento neutro da multiplica- ção) para todoa £ 0e 0! =1. onde Resolução: i Provemos primeiro a relação de Sifel para os coeficientes binomiais que figuram na fórmula do binômio, ou seja (º)- (27!) + (274) (L<ran-1) De fato: (oe (E) E + SE n- 1)! n=1) Prr-D)in-r= ED =gnSroiy é (ny (E +)- =t-Dit-r-Dlrta-r)/” + o n=18 nono fm “(€-Dt-r-D ra-) de-n -(2) 177 178 it A fórmula do binômio será provada por indução sobre n. n=1: (etyl=x+y Eles p= 10 pyl=x+y Logo, a fórmula vale para n = 1. Seja n > 2 e suponhamos: alin-1 serio E (remo Ge +y) > p y p=0 Multiplicando por x + y a relação anterior: sl in-1 sd mt care Ee a E (PT cego Z, Pp Y 2, p Y Ora, se r é um inteiro tal que 0 < r <n, então no segundo membro da relação anterior há dois termos cuja parte literal é x"-"y": o pri- meiro se obtém para p = r no primeiro somatório, sendo seu coefi- : K n—1 ciente o número | r | + € O outro se obtém para p= — 1 no segundo somatório, sendo seu coeficiente o número (2 ” i ) -. Logoo r-— coeficiente de x"-*y* em (x + yJ" é: o ()+(20)-(:) ceme(ts eee E (Eee (121)er- (od-lo e li)-(i) CAPÍTULO IV OS NÚMEROS RACIONAIS 1. Introdução Sempre que a divisão de um inteiro por outro não era exata, Os egípcios antigos, já por volta do ano 2000 a.G., usavam frações para exprimir o resul- tado. E usavam também frações para operar com seu sistema de pesos e me- didas. Contudo, por razões difíceis de explicar, com exceção das frações > e z às vezes, os egípcios usavam apenas frações unitárias, ou seja, frações cujo numerador é 1. Por exemplo, no problema 24 do papiro Rhind (cerca de 1700 a.C.) no qual o escriba pede que se efetue a divisão de 19 por 8, a respos- ta é dada, usando a nossa notação, por: 2+ + À 8 aj Embora os egípcios não adotassem sempre o mesmo procedimento, pode-se mostrar que toda fração entre O e 1 é soma de frações unitárias, o que representa uma garantia teórica para essa opção. Aliás, o uso das frações unitárias, além de não ficar confinado ao Egito an- tigo, se estendeu por vários séculos. Basta dizer que Fibonacci, no seu já citado Laber abaci, escrito no século XIII d.C. (cap. II, item 11), não só as usava como fornecia tabelas de conversão das frações comuns para unitárias. É que, embo- ra uma das finalidades dessa obra fosse divulgar os numerais indo-arábicos e a notação decimal posicional, Fibonacci não chegou a perceber a grande vanta- gem deste sistema: sua aplicabilidade para exprimir frações. Por exemplo: + = 0,95. Mas convém registrar que os babilônios, 2 000 anos antes de Cristo, apesar de algumas ambigúidades, decorrentes de não contarem com um sím- 179 bolo para o zero e outro para a separairiz, conseguiram estender o princípio posicional às frações no seu sistema de base 60. Por exemplo, o numeral que, como já vimos no capítulo I, poderia representar o inteiro 1+ 1 - 60= 61, também poderia ser uma representação de 1 1+ 5 Na verdade o uso da forma decimal para representar frações, tal como em À = 0,25, somente começaria a vingar após a publicação, em 1585, de um pequeno texto de Simon Stevin (1548-1620) intitulado De thiende (O décimo). Embora a essa altura a forma decimal já não constituísse uma novidade para os especialistas, esse trabalho de Stevin alcançou grande popularidade e conse- guiu seu intento, que era ensinar a “'como efetuar, com facilidade nunca vista, todos os cálculos necessários entre os homens, por meio de inteiros sem fra- ções”!. A notação inicialmente usada por Stevin acabou sendo melhorada com o emprego da virgula ou do ponto como separatriz decimal, conforme suges- tão de John Napier (1550-1617), feita em 1617. 2. A divisão em Z Sejama, bEZ,b + 0. Sea é múltiplo de b, então existe um único c Ez de maneira que a = be. Este elemento c é chamado quociente de a por b e costu- ma ser indicado por: c=>-ouc=a!b a b A operação que a cada par (a, b), nas condições expostas, associac = a : béa divisão em Z.. Portanto a divisão em Z só está definida em (a, bDEZxZ:b&0cbla) Mas certas questões corriqueiras ao homem há milênios, como a citada no item anterior de dividir 19 por 8, embora envolvendo só números intei- ros, não admitem uma resposta no âmbito de Z. É coerente indicar essa resposta por 2 , uma vez que se o primeiro número iosse 16 ela se expri- miria por 2 = b. Gumpre então ampliar Z, convenientemente de mancira 180 a poder abarcar todos os quocientes + (a, b EZ, b + 0) que possam surgir de questões da mesma natureza da que acabamos de lembrar. Essa ampliação, tal como no caso de IN para Z, pode ser feita de duas maneiras: elementarmente, agregando-se a Z os novos quocientes e definindo no conjunto resultante as operações e a relação de ordem convenientes; ou for- malmente, construindo a partir de Z um novo conjunto, com os requisitos de- sejados, mas de tal modo que uma de suas partes possa ser identificada plena- mente com Z. É claro que historicamente o caminho seguido foi o primeiro. Optamos por fazer a construção formal do conjunto dos números racio- nais (a ampliação pretendida de Z.) já no corpo do capítulo porque, além de um pouco menos penosa que a de Z, é mais difundida, mesmo em nível ele- meniar, e portanto trata-se de algo certamente mais familiar ao leitor. 3. Números racionais: construção, operação e relação de ordem Seja Z' = (m €Z|m + 0) e consideremos sobre Z x Z* = ((m, n)Jjm EZ, n€Z*) a relação “ definida por (m, n) M (p, q) se, e somente se, mq = np Para “V valem as três propriedades que caracterizam uma relação de equivalência, ou seja: É (m, n)N (tm, n), para todo (m, n) EZ x Z* (reflexiva) ii (mn) (p,q) = (p, 9) (m, n) (simétrica) ii(mn)CV(p Det q) (r,s) = (m,n)d(r,s) (transitiva) Verifiquemos iii já que i e ii decorrem diretamente da definição de N. Por hipótese: mq = np e ps = qr. Multiplicando a primeira dessas igualdades por s e a segunda por n, resulta: mgs = nps e nps = ngr. Daí, mgs = ngr e portanto, cancelando q, o que é possível pois q E Z*, obtém-se ms = nr. Donde (m, n) * (r, 5). Logo a relação “V determina sobre Z x Z* uma partição em classes de equivalência. Para cada par (m, n) E Z x Z*, a classe de equivalência à qual esse elemento pertence será indicada por = . Ou seja: D=(y)Ezxz']e, 9) “Gm nh= (x,y) EZxZ']nx= my) Por exemplo: T =) EZXZ=s = (0,1 =D (AL A) 181