DIVISIBILIDADE E O ALGORÍTMO DA DIVISÃO EM Z

Prévia do material em texto

3
Divisibilidade e o algoritmo da
divis~ao em Z
3.1 Divisibilidade
Em nossa educa»c~ao b¶asica, aprendemos que quando um n¶umero inteiro ¶e dividido por
um n¶umero inteiro n~ao nulo, o quociente pode ou n~ao ser um n¶umero inteiro. Esta
observa»c~ao nos leva µa seguinte de¯ni»c~ao.
De¯ni»c~ao 3.1 Um inteiro a divide um inteiro b quando existe um n¶umero inteiro m tal
que b = a ¢m. Quando a6= 0 (e somente neste caso), dizemos tamb¶em que b ¶e divis¶³vel
por a. Neste caso, o inteiro m ¶e chamado quociente de b por a e ¶e indicado por m =
b
a
.
Quando a divide b denotamos a j b e dizemos tamb¶em que
a ¶e um divisor de b
ou que
a ¶e um fator de b
ou ainda que
b ¶e um m¶ultiplo de a.
No caso em que a6= 0, dizemos ainda que b ¶e divis¶³vel por a. Quando a n~ao divide
b escrevemos a6j b.
N~ao escreva a= b e nem an b para denotar que a divide b. A nota»c~ao correta ¶e
a j b.
Exemplo 3.1 7 divide 161 j¶a que existe um inteiro, 23, tal que 161 = 7 ¢ 23.
Os divisores de 12 s~ao 1, 2, 3, 4, 6, 12, ¡1, ¡2, ¡3 ¡4, ¡6, e ¡12.
J¶a os divisores de 23 s~ao 1, 23, ¡1 e ¡23.
20
Divisibilidade e o algoritmo da divis~ao em Z 21
Proposi»c~ao 3.1 Se a, b e c s~ao inteiros, tais que a j b e b j c, ent~ao a j c.
Demonstra»c~ao. Como a j b e b j c, existem inteiros m e n tais que b = am e c = bn.
Logo, c = (am)n = a(mn), e portanto a j c.
Proposi»c~ao 3.2 Se a, b, c, m e n s~ao inteiros, tais que a j b e a j c, ent~ao a j (mb+nc).
Demonstra»c~ao. Como a j b e a j c existem inteiros e e f tais que b = ae e c = af . Logo
mb+ nc = m(ae) + n(af) = (me+ nf)a. Portanto, a j (mb+ nc).
Para exempli¯car a proposi»c~ao acima, note que 3 j 21, 3 j 33 e, conseqÄuentemente,
3 j (5 ¢ 21¡ 3 ¢ 33), isto ¶e, 3 j 6.
3.2 O algoritmo da divis~ao em Z
Teorema 3.1 (Teorema do algoritmo da divis~ao em Z) Se a e b s~ao inteiros, e
b6= 0, ent~ao existem inteiros q e r tais que a = bq+ r, e 0 · r < jbj. Os inteiros q e r,
nas condi»c~oes acima, s~ao ¶unicos. Os inteiros q e r s~ao chamados, respectivamente, de
quociente e resto da divis~ao euclidiana de a por b.
Demonstra»c~ao. Demonstraremos o teorema supondo b > 0 e deixaremos o caso b < 0
para ser completado pelo leitor.
Pelo teorema 2.4, do algoritmo da divis~ao em N, cap¶³tulo 2, se a ¸ 0, existem
n¶umeros naturais q e r satisfazendo a = bq + r e 0 · r < b.
Se a < 0, ent~ao jaj > 0. Aplicando o teorema 2.4, existem naturais q e r
satisfazendo
jaj = bq + r; e 0 · r < b
Como jaj = ¡a, temos ent~ao ¡a = bq+ r, ou seja, a = b(¡q)+ (¡r). Se r = 0,
temos a = b(¡q) + 0, sendo ent~ao ¡q e 0 o quociente e o resto da divis~ao de a por b,
respectivamente.
Se r > 0, temos
a = b(¡q) + (¡r)
= b(¡q)¡ b+ b¡ r, logo
= b(¡q ¡ 1) + (b¡ r)
Como 0 < r < b, temos ¡b < ¡r < 0 e ent~ao, somando b aos tre^s membros desta
¶ultima desigualdade, 0 < b ¡ r < b. Fazendo q0 = ¡q ¡ 1, e r0 = b ¡ r, temos
a = bq0 + r0, com 0 < r0 < b.
No caso em que b < 0, fazendo a divis~ao euclidiana de a por jbj, obtemos quociente
e resto da divis~ao de a por b.
Divisibilidade e o algoritmo da divis~ao em Z 22
Para demonstrar a unicidade do quociente q e do resto r, suponhamos que seja
poss¶³vel fazer
a = bq1 + r1 = bq2 + r2
com q1; q2; r1 e r2 inteiros, 0 · r1 < b e 0 · r2 < b. Mostraremos que necessariamente
q1 = q2 e r1 = r2.
A partir da igualdade bq1 + r1 = bq2 + r2, obtemos 0 = b(q1 ¡ q2) + (r1 ¡ r2) ou,
equivalentemente, (r2 ¡ r1) = b(q1 ¡ q2).
Logo b divide r2 ¡ r1. Por outro lado, como 0 · r1 < b e 0 · r2 < b segue
que ¡b < r2 ¡ r1 < b, e portanto jr2 ¡ r1j < b. Como b divide jr2 ¡ r1j < b (pois
divide r2 ¡ r1), temos necessariamente (justi¯que) r2 ¡ r1 = 0 e, conseqÄuentemente,
q1 ¡ q2 = 0. Segue portanto a unicidade q1 = q2 e r1 = r2.
Observa»c~ao 3.1 Fixado um inteiro positivo d, em v¶arias insta^ncias, na teoria do n¶umeros,
classi¯camos os n¶umeros inteiros pelos restos da divis~ao por d.
Por exemplo, se d = 2 ent~ao o resto da divis~ao de qualquer inteiro n por 2 satisfaz
0 · r < 2, isto ¶e, r = 0 ou r = 1.
No primeiro caso, n = 2q, dizemos que n ¶e um inteiro par, e no segundo caso,
n = 2q + 1, dizemos que n ¶e um inteiro ¶³mpar.
De forma an¶aloga, se d = 4 temos 0 · r < 4. Conclu¶³mos ent~ao que cada inteiro
n tem uma e apenas uma das formas:
n = 4q, n = 4q + 1, n = 4q + 2, n = 4q + 3 (com q 2 Z)
Assim, o conjunto Z, dos n¶umeros inteiros, ¯ca subdividido em quatro classes de
inteiros, cada uma das classes contendo todos os inteiros que deixam um mesmo resto
quando divididos por 4.
3.3 Divis~ao euclidiana na calculadora
Nesta se»c~ao, assumiremos familiaridade com os n¶umeros reais, e exploraremos um m¶etodo
simples para obter quociente e resto, de uma divis~ao euclidiana em Z, usando uma cal-
culadora comum.
De¯ni»c~ao 3.2 (Fun»c~ao maior inteiro) Para cada x 2 R, de¯ne-se o maior inteiro
contido em x, como sendo o n¶umero [x] 2 Z tal que x = [x] + ¸, sendo ¸ real,
0 · ¸ < 1.
Exemplo 3.2 [8=3] = 2, pois 8=3 = 2 + 2=3;
[¼] = 3, pois ¼ = 3 + ®, sendo ® ¼ 0; 14.
[¡1;5] = ¡2, pois ¡1;5 = ¡2 + 0;5.
Divisibilidade e o algoritmo da divis~ao em Z 23
Lema 3.1 Para cada x 2 R, x¡ 1 < [x] · x.
Demonstra»c~ao. Seja x um n¶umero real. Ent~ao x = [x] + ®, com [x] 2 Z e 0 · ® < 1.
Da¶³ temos [x] · [x] + ® = x.
Agora, x¡ 1 = [x] + (®¡ 1).
Como 0 · ® < 1, temos ¡1 · ®¡ 1 < 0 e ent~ao [x] + (®¡ 1) < [x].
Portanto, x¡ 1 < [x].
Assim, x¡ 1 < [x] · x.
Proposi»c~ao 3.3 (Obtendo quociente e resto em uma calculadora) Sejam a e b
inteiros, com b > 0. Consideremos o n¶umero racional
a
b
. Ent~ao o quociente q e o
resto r, da divis~ao euclidiana de a por b, s~ao dados por
q =
ha
b
i
e r = b ¢
³a
b
¡
ha
b
i´
Demonstra»c~ao. Tomemos q =
ha
b
i
e r = b ¢
³a
b
¡
ha
b
i´
.
Temos ent~ao a = bq + r, sendo q = [a
b
] e r = a¡ b[a
b
] = a¡ bq ambos inteiros.
Basta veri¯car agora que 0 · r < b.
Pelo lema 3.1 temos a
b
¡ 1 <
£
a
b
¤
· a
b
, isto ¶e, a
b
¡ 1 < q · a
b
.
Sendo b > 0, temos ent~ao a¡ b < bq · a, de onde ¡a · ¡bq < b¡ a, e ent~ao
0 · a¡ bq < b.
Exemplo 3.3 Como exemplo, ao dividir 26795 por 125, em uma calculadora obtemos
26795=125 = 214;36, portanto q = [214;36] = 214 e r = (214;36 ¡ 214) ¢ 125 =
0;36 ¢ 125 = 45.
Se a = 536 e b = 18 ent~ao q = [536=18] = 29 e r = 536 ¡ [536=18] ¢ 18 =
536¡ 29 ¢ 18 = 14.
Se a = ¡380 e b = 75 ent~ao q = [¡380=75] = ¡6 e r = ¡380¡ [¡380=75] ¢75 =
¡380¡ (¡6) ¢ 75 = 70.
Este algoritmo funciona bem em calculadoras eletro^nicas, desde que os inteiros
envolvidos n~ao sejam muito grandes, por causa de limita»c~oes de mem¶oria.
Sabemos que r = (a
b
¡[a
b
])¢b ¶e um inteiro. Se aparecer, no visor de sua calculadora,
um resultado para r tal como 6; 9999998, simplesmente arredonde-o para 7.
Divisibilidade e o algoritmo da divis~ao em Z 24
3.4 Exerc¶³cios
1. De acordo com a de¯ni»c~ao 3.1, podemos dizer que 0 divide 0? (N~ao se apresse
em dar a resposta. Pense: 0 ¶e fator de 0?) Podemos dizer que 0 ¶e divis¶³vel por 0?
2. Mostre que 1260 ¶e divis¶³vel por 7, por 5 e por 9.
3. Encontre o quociente e o resto da divis~ao por 17, sendo o dividendo
(a) 100 (b) 289 (c) ¡44 (d) ¡100
Respostas. (a) q = 5, r = 15. (b) q = 17, r = 0. (c) q = ¡3, r = 7. (d)
q = ¡6, r = 2.
4. Use uma calculadora, para obter quociente e resto da divis~ao, por 2135, sendo o
dividendo
(a) 823 546 (b) 256 459 568
Respostas. (a) q = 385, r = 1571. (b) q = 120 121, r = 1233.
5. Sendo a e b inteiros, demonstre que a j b e b j a , a = §b.
6. Mostre que sendo a, b, c e d inteiros, se a j b e c j d ent~ao ac j bd.
7. Existem inteiros a, b e c tais que a j bc mas a6j b e a6j c ?
8. Mostre que a soma de dois inteiros pares ¶e sempre par, que a soma de dois inteiros
¶³mpares ¶e sempre par, e que a soma de um inteiro par com um inteiro ¶³mpar ¶e
sempre ¶³mpar.
9. Mostreque se a ¶e um inteiro ent~ao a3 ¡ a ¶e divis¶³vel por 6.
Sugest~ao. Pelo teorema 3.1, a = 6q + r, com r 2 f0; 1; 2; 3; 4; 5g.
10. Mostre que o quadrado de um inteiro ¶³mpar ¶e da forma 8k + 1, com k inteiro.
11. Mostre que o produto de dois inteiros da forma 6k + 5 ¶e um inteiro da forma
6k + 1.
Sugest~ao. Os dois inteiros tem a forma 6k1 + 5 e 6k2 + 5, para certos inteiros k1
e k2.
12. Mostre que o cubo de um inteiro ¶e de uma das formas: 9k, 9k ¡ 1, 9k + 1, com
k inteiro.
Sugest~ao. Pelo algoritmo da divis~ao por 3, todo inteiro n tem a forma 3q + r,
sendo r 2 f0; 1; 2g.
13. Seja fn o n-¶esimo n¶umero de Fibonacci. Recorde-se de que f1 = f2 = 1, e
fn = fn¡1 + fn¡2 para cada n ¸ 3.
(a) Mostre que fn ¶e par , n ¶e divis¶³vel por 3.
Sugest~ao. Mostre, por indu»c~ao sobre k, que para cada inteiro k ¸ 0, f3k ¶e
par, enquanto que f3k+1 e f3k+2 s~ao ¶³mpares (podemos considerar f0 = 0).
Divisibilidade e o algoritmo da divis~ao em Z 25
(b) Mostre que fn ¶e divis¶³vel por 3 , n ¶e divis¶³vel por 4.
(c) Mostre que fn+m = fnfm¡1 + fn+1fm se m ¸ 2 e n ¸ 1.
Sugest~ao. Mostre que, para cada n ¸ 1, a igualdade ¶e valida para m = 2 e
para m = 3. Demonstre ent~ao a igualdade, para cada n, por indu»c~ao sobre
m, pelo 2o princ¶³pio de indu»c~ao.
(d) Usando o resultado do item anterior, mostre que se n j m ent~ao fn j fm.
Sugest~ao. Mostre, por indu»c~ao sobre k, k ¸ 1, que fkn ¶e divis¶³vel por fn.
14. Sejam a; b; c; d quatro inteiros com a e c n~ao nulos. Mostre que se a j b e c j d
ent~ao ac j bd.
15. Existem inteiros a; b; c tais que a j bc mas a6j b e a6j c ?
16. Sejam a; b; c tre^s inteiros com c6= 0. Mostre que a j b se e somente se ac j bc.
17. Sejam a e b dois inteiros tais que a j b. Mostre que a · jbj.
18. Complete a demonstra»c~ao do teorema 3.1, com o caso em que b < 0.
19. Demonstre que
(a) Se x e y s~ao dois n¶umeros reais ent~ao [x+ y] ¸ [x] + [y].
Sugest~ao. Considere que [x] = a , x = a + ®, sendo a inteiro e ® um
n¶umero real satisfazendo 0 < ® < 1.
(b) Se x ¶e um n¶umero real, e x6= n+ 1
2
para todo inteiro n, ent~ao
£
x+ 1
2
¤
¶e o
inteiro mais pr¶oximo de x.
Sugest~ao. Quando x6= n+ 1
2
para todo inteiro n, o inteiro m mais pr¶oximo
de x ¶e aquele satisfazendo x = m+ ®, com ¡1
2
< ® < 1
2
.
(c) Se x = n+ 1
2
, para algum inteiro n, ent~ao n e n+ 1 s~ao eqÄuidistantes de x,
sendo os inteiros mais pr¶oximos de x.
20. (a) Mostre que, se x e d s~ao inteiros positivos, o n¶umero de inteiros positivos,
menores do que ou iguais a x, que s~ao divis¶³veis por d, ¶e calculado por
£
x
d
¤
.
Sugest~ao. Os inteiros positivos m¶ultiplos de d s~ao d, 2d, 3d, etc. Existe um
¶unico inteiro positivo n satisfazendo nd · x e (n+ 1)d > x.
(b) Calcule o n¶umero de inteiros positivos que n~ao excedem 1000 e que s~ao
divis¶³veis por 5, por 25, por 125 e por 625.
(c) Quantos inteiros entre 100 e 1000 s~ao divis¶³veis por 7 ? E por 49 ?
21. Seja T (n) uma fun»c~ao com dom¶³nio nos inteiros positivos de¯nida por
T (n) =
(
n
2
se n ¶e par
3n+1
2
se n ¶e ¶³mpar
Divisibilidade e o algoritmo da divis~ao em Z 26
Iterando a fun»c~ao T podemos construir, a partir de um inteiro positivo n ¯xado,
uma seqÄue^ncia de inteiros conforme mostra o quadro abaixo:
n n; T (n); T (T (n)); T (T (T (n))); T 4(n); T 5(n); : : :
1 1; 2; 1; 2; 1; 2; 1; : : :
2 2; 1; 2; 1; 2; 1; 2; 1; : : :
3 3; 5; 8; 4; 2; 1; 2; 1; : : :
4 4; 2; 1; 2; 1; 2; 1; : : :
5 5; 8; 4; 2; 1; 2; 1; : : :
6 6; 3; 5; 8; 4; 2; 1; 2; 1; : : :
7 7; 11; 17; 26; 13; 20; 10; 5; 8; 4; 2; 1; 2; 1; : : :
...
...
Uma conjectura muito conhecida, as vezes chamada de Conjectura de Collatz,
a¯rma que a seqÄue^ncia obtida pelas itera»c~oes de T sempre recaem na repeti»c~ao
1; 2; 1; 2; 1; : : : , independentemente do valor do inteiro inicial n.
(a) Encontre a seqÄue^ncia obtida pelas itera»c~oes de T , come»cando com n = 29.
(b) Mostre que se k ¸ 2 ¶e um inteiro, (22k ¡ 1)=3 ¶e sempre um inteiro ¶³mpar.
(c) Mostre que a seqÄue^ncia obtida pelas itera»c~oes de T , come»cando com n =
(22k ¡ 1)=3, sendo k ¸ 2 um inteiro, sempre recai em 1, 2, 1, 2, 1, : : : .