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 a 6
= 0 (e somente neste caso), dizemos tamb¶em que b ¶e divis¶³vel
b
por a. Neste caso, o inteiro m ¶e chamado quociente de b por a e ¶e indicado por m = .
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 a 6
= 0, dizemos ainda que b ¶e divis¶³vel por a. Quando a n~ao divide
b escrevemos a 6
j b.
a j b.
N~ao escreva a= b e nem an b para denotar que a divide b. A nota»c~ao correta ¶e
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
~o em Z
Divisibilidade e o algoritmo da divisa
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»co~es 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 tr^es membros desta
u¶ltima desigualdade, 0 < b ¡ r < b. Fazendo q 0 = ¡q ¡ 1, e r0 = b ¡ r, temos
a = bq 0 + 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.
~o em Z
Divisibilidade e o algoritmo da divisa
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 ¡ r1 j < b. Como b divide jr2 ¡ r1 j < 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 inst^ancias, 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 calculadora 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.
~o em Z
Divisibilidade e o algoritmo da divisa
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
a
inteiros, com b > 0. Consideremos o n¶umero racional . Ent~ao o quociente q e o
b
resto r, da divis~ao euclidiana de a por b, s~ao dados por
³ a h a i´
hai
e r =b¢
¡
q=
b
b
b
Demonstra»c~ao. Tomemos q =
hai
e r =b¢
³a
¡
h a i´
.
b
b
b
Temos ent~ao a = bq + r, sendo q = [ ab ] e r = a ¡ b[ ab ] = a ¡ bq ambos inteiros.
Basta veri¯car agora que 0 · r < b.
£ ¤
Pelo lema 3.1 temos ab ¡ 1 < ab · ab , isto ¶e,
a
b
¡ 1 < q · ab .
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 eletr^onicas, desde que os inteiros
envolvidos n~ao sejam muito grandes, por causa de limita»co~es de mem¶oria.
Sabemos que r = ( ab ¡[ ab ])¢b ¶e um inteiro. Se aparecer, no visor de sua calculadora,
um resultado para r tal como 6; 9999998, simplesmente arredonde-o para 7.
~o em Z
Divisibilidade e o algoritmo da divisa
3.4
24
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 a 6
j b e a6
j 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. Mostre que 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).
~o em Z
Divisibilidade e o algoritmo da divisa
25
(b) Mostre que fn ¶e divis¶³vel por 3 , n ¶e divis¶³vel por 4.
(c) Mostre que fn+m = fn fm¡1 + fn+1 fm 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 a 6
j b e a6
jc?
16. Sejam a; b; c tr^es inteiros com c 6
= 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 x 6
= n + 21 para todo inteiro n, ent~ao x + 12 ¶e o
inteiro mais pr¶oximo de x.
Sugest~ao. Quando x 6
= n + 12 para todo inteiro n, o inteiro m mais pr¶oximo
de x ¶e aquele satisfazendo x = m + ®, com ¡ 12 < ® < 12 .
uidistantes de x,
(c) Se x = n + 12 , para algum inteiro n, ent~ao n e n + 1 s~ao eqÄ
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 xd .
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
(
n
se n ¶e par
2
T (n) =
3n+1
se n ¶e ¶³mpar
2
~o em Z
Divisibilidade e o algoritmo da divisa
26
Iterando a fun»c~ao T podemos construir, a partir de um inteiro positivo n ¯xado,
uma seqÄu^encia 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
2
3
4
5
6
7
..
.
1; 2; 1; 2; 1; 2; 1; : : :
2; 1; 2; 1; 2; 1; 2; 1; : : :
3; 5; 8; 4; 2; 1; 2; 1; : : :
4; 2; 1; 2; 1; 2; 1; : : :
5; 8; 4; 2; 1; 2; 1; : : :
6; 3; 5; 8; 4; 2; 1; 2; 1; : : :
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Äu^encia 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Ä
u^encia 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Äu^encia obtida pelas itera»co~es de T , come»cando com n =
(22k ¡ 1)=3, sendo k ¸ 2 um inteiro, sempre recai em 1, 2, 1, 2, 1, : : : .