1

1

Divisibilidade

Sumário

1.1 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . 7

Unidade 1 Divisibilidade

Como a divisão de um número inteiro por outro nem sempre é possível,

expressa-se esta possibilidade através da relação de divisibilidade.

Quando não existir uma relação de divisibilidade entre dois números inteiros,

veremos que, ainda assim, será possível efetuar uma �divisão com resto pe-

queno�, chamada de divisão euclidiana. O fato de sempre ser possível efetuar tal

divisão é responsável por inúmeras propriedades dos inteiros que exploraremos

neste e nos próximos capítulos.

1.1 Divisibilidade

Dados dois números inteiros a e b, diremos que a divide b, escrevendo a|b,quando existir c ∈ Z tal que b = c · a. Neste caso, diremos também que a é

um divisor ou um fator de b ou, ainda, que b é um múltiplo de a.

Observe que a notação a|b não representa nenhuma operação em Z, nemrepresenta uma fração. Trata-se de uma sentença que diz ser verdade que existe

c tal que b = ca. A negação dessa sentença é representada por a 6 | b, sigi�candoque não existe nenhum número inteiro c tal que b = ca. Portanto, temos que

0 6 | a, se a 6= 0.

Exemplo 1 1|0, −1|0, 2|0, −2|0; 1|6, −1|6, 1|− 6, −1|− 6, 2|6, −2|6, 2|− 6,

−2| − 6, 3|6, −3|6, 3| − 6, −3| − 6, 6|6, −6|6, 6| − 6, −6| − 6; 3 6 | 4;2 6 | 5.

Suponha que a|b e seja c ∈ Z tal que b = ca. O número inteiro c é chamado

de quociente de b por a e denotado por c =b

a.

Por exemplo,

0

1= 0,

0

2= 0,

6

1= 6,

6

2= 3,

6

−3= −2, 6

3= 2,

6

6= 1.

Note ainda que, se a|b, então ±a| ± b (veri�que).

Estabeleceremos a seguir algumas propriedades da divisibilidade.

2

Unidade 1Divisibilidade

Proposição 1Sejam a, b, c ∈ Z. Tem-se que

i) 1|a, a|a e a|0.ii) se a|b e b|c, então a|c.

Demonstração(i) Isto decorre das igualdades a = a · 1, a = 1 · a e 0 = 0 · a.(ii) a|b e b|c implica que existem f, g ∈ Z, tais que b = f · a e c = g · b.Substituindo o valor de b da primeira equação na outra, obtemos

c = g · b = g · (f · a) = (g · f) · a,

o que nos mostra que a|c.

O item (i) da proposição acima nos diz que todo número inteiro é divisível

por 1 e por si mesmo.

Proposição 2Se a, b, c, d ∈ Z, então

a|b e c|d =⇒ a · c|b · d.

DemonstraçãoSe a|b e c|d, então ∃ f, g ∈ Z, b = f · a e d = g · c. Portanto,

b · d = (f · g)(a · c), logo, a · c|b · d.

Em particular, se a|b, então a · c|b · c, para todo c ∈ Z.

Proposição 3Sejam a, b, c ∈ Z, tais que a|(b± c). Então

a|b ⇐⇒ a|c.

DemonstraçãoSuponhamos que a|(b+ c). Logo, existe f ∈ Z tal que b+ c = f · a.Agora, se a|b, temos que existe g ∈ Z tal que b = g · a. Juntando as duas

igualdades acima, temos

g · a+ c = f · a,

donde segue-se que c = (f − g)a, logo a|c.

3

Unidade 1 Divisibilidade

A prova da implicação contrária é totalmente análoga.

Por outro lado, se a|(b − c) e a|b, pelo caso anterior, temos a| − c, o que

implica que a|c.

Proposição 4 Se a, b, c ∈ Z são tais que a|b e a|c, então a|(xb+yc), para todo x, y ∈ Z.

Demonstração a|b e a|c implicam que existem f, g ∈ Z tais que b = fa e c = ga.

Logo,

xb+ yc = x(fa) + y(ga) = (xf + yg)a,

o que prova o resultado.

Uma propriedade caracterítica dos números inteiros é a de ser vazio o con-

junto {x ∈ Z; 0 < x < 1}. Isto implica que se c ∈ Z é tal que c > 0, então

c > 1.

Da propriedade acima decorre a Propriedade Arquimediana de Z, ou seja,

se a, b ∈ Z, com b 6= 0, então existe n ∈ Z tal que nb > a.

De fato, como |b| > 0, temos que |b| > 1, logo

(|a|+ 1) |b| > |a|+ 1 > |a| > a.

O resultado segue se na desigualdade acima tomarmos n = |a|+ 1, se b > 0 e

n = −(|a|+ 1), se b < 0.

Proposição 5 Dados a, b ∈ N, temos que

a|b =⇒ a 6 b.

Demonstração De fato, se a|b, existe c ∈ Z tal que b = ca. Como a, b > 0, segue-se que

c ∈ N. Como 1 6 c, segue-se que a 6 ac = b.

Em particular, se a ∈ N e a|1, então 0 < a 6 1 e, portanto, a = 1.

Claramente, a recíproca da Proposição 5 não é válida, pois, por exemplo,

3 > 2; e, no entanto, 2 não divide 3.

4

Unidade 1Divisibilidade

Note que a relação de divisibilidade em N é uma relação de ordem, pois

i) é re�exiva: ∀ a ∈ N, a|a. (Proposição 1(i)),

ii) é transitiva: se a|b e b|c, então a|c. (Proposição 1(ii)),

iii) é anti-simétrica: se a|b e b|a, então a = b. (Segue da Proposição 5).

As proposições a seguir serão de grande utilidade.

Proposição 6Sejam a, b ∈ Z e n ∈ N. Temos que a− b divide an − bn.

DemonstraçãoVamos provar isto por indução sobre n.

É óbvio que a a�rmação é verdade para n = 1, pois a− b divide a1 − b1 =

a− b.

Suponhamos, agora, que a− b|an − bn. Escrevamos

an+1 − bn+1 = aan − ban + ban − bbn = (a− b)an + b(an − bn).

Como a− b|a− b e, por hipótese, a− b|an− bn, decorre da igualdade acima

e da Proposição 4 que a− b|an+1− bn+1. Estabelecendo o resultado para todo

n ∈ N.

Proposição 7Sejam a, b ∈ Z e n ∈ N. Temos que a+ b divide a2n+1 + b2n+1.

DemonstraçãoVamos provar isto também por indução sobre n.

A a�rmação é, obviamente, verdade para n = 0, pois a+ b divide a1+ b1 =

a+ b.

Suponhamos, agora, que a+ b|a2n+1 + b2n+1. Escrevamos

a2(n+1)+1 + b2(n+1)+1 = a2a2n+1 − b2a2n+1 + b2a2n+1 + b2b2n+1 =

(a2 − b2)a2n+1 + b2(a2n+1 + b2n+1).

Como a+b divide a2−b2 = (a+b)(a−b) e, por hipótese, a+b|a2n+1+b2n+1,

decorre das igualdades acima e da Proposição 4 que a+ b|a2(n+1)+1+ b2(n+1)+1.

Estabelecendo, assim, o resultado para todo n ∈ N.

5

Unidade 1 Divisibilidade

Proposição 8 Sejam a, b ∈ Z e n ∈ N. Temos que a+ b divide a2n − b2n.

Demonstração Novamente usaremos indução sobre n.

A a�rmação é verdadeira para n = 1, pois claramente

a+ b divide a2 − b2 = (a+ b)(a− b).

Suponhamos, agora, que a+ b|a2n − b2n. Escrevamos

a2(n+1) − b2(n+1) = a2a2n − b2a2n + b2a2n − b2b2n =

(a2 − b2)a2n + b2(a2n − b2n).

Como a+ b|a2− b2 e, por hipótese, a+ b|a2n− b2n, decorre das igualdades

acima e da Proposição 4 que a + b|a2(n+1) + b2(n+1). Estabelecendo, desse

modo, o resultado para todo n ∈ N.

6

Unidade 1Divisibilidade

1.2 Problemas

1. Sejam a, b, c ∈ Z e c 6= 0. Mostre que

ac|bc⇐⇒ a|b.

2. (ENC-98)1 A soma de todos os múltiplos positivos de 6 que se escrevem

(no sistema decimal) com dois algarismos é:

(A) 612 (B) 648 (C) 756 (D) 810 (E) 864

3. Com quanto zeros termina o número 100!?

4. (a) Mostre que o produto de i números naturais consecutivos é divisível

por i!.

(b) Mostre que 6|n(n+ 1)(2n+ 1), para todo n ∈ N.

5. Mostre, por indução matemática, que, para todo n ∈ N,

(a) 8|32n + 7

(b) 9|10n + 3.4n+2 + 5

(c) 9|n4n+1 − (n+ 1)4n + 1

(d) 169|33n+3 − 26n− 27

6. Mostre que 13|270 + 370.

7. Mostre que, para todo n,

(a) 9|10n − 1

(b) 8|32n − 1

(c) 53|74n − 24n

(d) 3|10n − 7n

(e) 13|92n − 24n

(f) 6|52n+1 + 1

(g) 19|32n+1 + 44n+2

(h) 17|102n+1+72n+1

(i) 14|34n+2 + 52n+1

8. Sejam a, b ∈ Z.

a) Se a 6= b, mostre que, para todo n ∈ N, n > 2,

an − bn

a− b= an−1 + an−2 · b+ · · ·+ a · bn−2 + bn−1.

1Exame Nacional de Cursos, MEC/INEP.

7

Unidade 1 Problemas

b) Se a+ b 6= 0, mostre que, para todo n ∈ N,

a2n+1 + b2n+1

a+ b= a2n − a2n−1 · b+ · · · − a · b2n−1 + b2n.

c) Mostre que, para todo n ∈ N,

a2n − b2n

a+ b= a2n−1 − a2n−2 · b+ · · ·+ a · b2n−2 − b2n−1.

9. Para quais valores de a ∈ N

a) a− 2|a3 + 4?

b) a+ 3|a3 − 3?

c) a+ 2|a4 + 2?

d) a+ 2|a4 + 2a3 + a2 + 1?

10. Mostre que, para todos a,m, n ∈ Z,

m > n > 0 =⇒ a2n

+ 1|a2m − 1.

11. Mostre, para todo n ∈ N, que n2|(n+ 1)n − 1.

12. Mostre, para todo a ∈ Z, que

a) 2|a2 − a b) 3|a3 − a c) 5|a5 − a d) 7|a7 − a

13. Mostre que existem in�nitos valores de n em N para os quais 8n2 + 5 é

divisível por 7 e por 11.

8