MA14 - Aritmetica

Unidade 3 - Parte 2

Divisao nos Inteiros(Divisao Euclidiana)

Abramo Hefez

PROFMAT - SBM

Aviso

Este material e apenas um resumo de parte da disciplina e o seuestudo nao garante o domınio do assunto.

O material completo a ser estudado encontra-se no

Capıtulo 3 - Secao 3.2

do livro texto da disciplina:

Aritmetica, A. Hefez, Colecao PROFMAT.

Estes resumos contaram com a colaboracao de Maria Lucia T.Villela.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 2/21

Divisao Euclidiana

Mesmo quando um numero inteiro a, nao nulo, nao divide umnumero inteiro b, vale o seguinte fato:

E sempre possıvel efetuar a divisao de b por a, com resto pequeno.

Este resultado, de cuja justificativa geometrica daremos uma ideiaquando a e natural, foi utilizado por Euclides (Seculo 3 a.C), nosseus Elementos, no ambito dos numeros naturais, sem enuncia-loexplicitamente.

Essa propriedade nao so e um importante instrumento na obra deEuclides, como tambem e um resultado central da teoria elementardos numeros.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 3/21

De fato, suponhamos que a ∈ Z e consideremos a decomposicaode Z em uniao de intervalos disjuntos:

Z = . . . ∪ [−2a,−a) ∪ [−a, 0) ∪ [0, a) ∪ [a, 2a) ∪ . . .

Fica claro que qualquer numero inteiro b pertence a um e somenteum desses intervalos, digamos b ∈ [qa, qa + a).

Portanto, b = qa + r , onde q e r sao univocamente determinados,com 0 6 r < a.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 4/21

Agora enunciamos o resultado geral:

Teorema (Divisao Euclidiana)

Sejam a e b dois numeros inteiros com a 6= 0. Existem dois unicosnumeros inteiros q e r tais que

b = a · q + r , com 0 6 r < |a|.

Nas condicoes do teorema, os numeros a e b sao o divisor e odividendo, enquanto q e r sao chamados, respectivamente, dequociente e de resto da divisao de b por a.

Note que

o resto da divisao de b por a e zero se, e somente se, a divide b.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 5/21

Exemplos

Como 19 = 5 · 3 + 4, o quociente e o resto da divisao de 19por 5 sao q = 3 e r = 4.

Como −19 = 5 · (−4) + 1 o quociente e o resto da divisao de−19 por 5 sao q = −4 e r = 1.

Como 32 = (−5) · (−6) + 2 o quociente e o resto da divisaode 32 por −5 sao q = −6 e r = 2.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 6/21

Exemplos - ContinuacaoMostrar que o resto da divisao de 10n por 9 e sempre 1,qualquer que seja o numero natural n.

Solucao

Como mostrar um tal resultado?

Alguns experimentos ajudam a entender melhor o problema:

101 = 10 = 9× 1 + 1,

102 = 100 = 9× 11 + 1,

103 = 1000 = 9× 111 + 1.

Agora ja entendemos melhor a questao e o resultado nos parecetao obvio que ate podemos dizer que

10n = 9× 1 . . . 11︸ ︷︷ ︸n vezes

+1,

donde, por ser 0 ≤ 1 < 9, podemos afirmar que o resto da divisaopor 9 e sempre 1.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 7/21

Muito bem, alguem poderia ponderar: Pronto, ja mostramos!

Mas, atencao! Mostrar em matematica e sinonimo de provar!

E aı, como provar tal resultado?

Via de regra, quando temos uma assercao que envolve todos osnumeros naturais maiores do que um dado natural, a tendencia etentar inducao, a menos que tenhamos uma ideia melhor!

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 8/21

A nossa assercao se traduz matematicamente do seguinte modo:

P(n) : Existe q ∈ Z tal que 10n = 9q + 1.

Ja verificamos acima que P(1) e verdade.

Para mostrar que P(n) =⇒ P(n + 1), suponhamos que P(n) sejaverdade, ou seja que existe q ∈ Z tal que 10n = 9q + 1.

Multiplicando por 10 ambos os lados dessa ultima igualdade,temos que

10n+1 = 10(9q + 1) = 9× 10q + 10 = 9(10q + 1) + 1,

o que mostra que existe q′ = 10q + 1 tal que 10n+1 = 9q′ + 1,

provando que P(n + 1) e verdade.

Pelo Princıpio de Inducao Matematica, P(n) e verdade ∀ n ∈ N.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 9/21

Outra Solucao

Com o que temos em maos, poderıamos ter dado umademonstracao alternativa da nossa propriedade.

De fato, lembrando da propriedade

(a− b)|(an − bn),

temos que

(10− 1)|(10n − 1n),

ou seja, 9|10n − 1.

Assim, 10n − 1 = 9q, logo 10n = 9q + 1.

Como 0 ≤ 1 < 9, pela unicidade na divisao euclidiana, tem-se queo resto da divisao de 10n por 9 e sempre 1.

Recomendacao: Antes de comecar a resolver um problema,convem ler o enunciado com cuidado e tentar ver como o que sepede se relaciona com o que ja conhecemos, isto pode poupartempo e energia preciosos.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 10/21

Exemplos - Continuacao

O resto da divisao de 74n − 24n + 93 por 45 e sempre 3, paratodo n ∈ N.

Solucao

Note que

74n − 24n + 93 = 492n − 42n + 93.

Temos que 45 = 49− 4 divide 492n − 42n, para todo n ∈ N, logo74n − 24n = 45q, para algum q ∈ Z.

Por outro lado, como 93 = 45 · 2 + 3,

74n − 24n + 93 = 45q + 2 · 45 + 3 = 45(q + 2) + 3,

com 0 ≤ 3 < 45.

Da unicidade do resto na divisao euclidiana, segue que 3 e o restoda divisao de 74n − 24n + 93 por 45, para todo n ∈ N.

Tente, como exercıcio, mostrar essa propriedade por inducao.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 11/21

Parte inteira do racional ab , com b > 0

Sejam a, b ∈ Z com b > 0. Escrevamos a divisao euclidiana de apor b:

a = bq + r , com 0 ≤ r < b.

Vamos dar uma interpretacao para o quociente q dessa divisao.Como

bq ≤ bq + r︸ ︷︷ ︸a

< bq + b = b(q + 1),

temos quebq ≤ a < b(q + 1).

Entao, dividindo por b,

q ≤ ab < q + 1.

Portanto, q e o maior inteiro menor ou igual ao racional ab e e

chamado de parte inteira do numero racional ab , sendo denotado

por[ab

].

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 12/21

Exemplos de parte inteira

Aproveitando alguns calculos feitos anteriormente, temos[195

]=[5·3+4

5

]=[3 + 4

5

]= 3.

[−195

]=[5·(−4)+1

5

]=[−4 + 1

5

]= −4.

Note que −4 < −3, 8 = −195 < −3.[

−32

5

]=

[5× (−7) + 3

5

]=

[−7 +

3

5

]= −7.

Se a ∈ Z e α ∈ Q, com 0 ≤ α < 1, entao [a + α] = a.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 13/21

Aplicacao

Quantos multiplos de 9 ha entre 238 e 1247?

Entendemos que se algum dos numeros 238 ou 1247 for multiplode 9, ele deve ser contado.

Solucao

As vezes, um problema se torna mais claro, quando generalizado.

Dados 0 < a < c, vamos contar quantos multiplos de a existementre 1 e c.

Pela divisao euclidiana, temos que

c = aq + r , com 0 ≤ r < a.

Portanto, podemos escrever a lista dos multiplos de a entre 1 e ccomo segue:

a, 2a, . . . , (q − 1)a, qa.

Agora ficou facil contar esses numeros: o seu numero e q =[ca

].

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 14/21

Continuacao

Agora, dados 0 < a < b < c , se quisermos contar quantos sao osmultiplos de a entre b e c, procedemos como segue:

De[ca

], que e o numero de multiplos de a entre 1 e c ,

devemos subtrair[b−1a

], que e o numero de multiplos de a

anteriores a b.

Assim, o numero de multiplos de a entre b e c e[c

a

]−[

b − 1

a

].

Portanto, a resposta para o nosso problema e:[1247

9

]−[

238− 1

9

]= 112.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 15/21

Par ou ımpar?

Desde os tempos de Pitagoras, os numeros inteiros saoclassificados em pares e ımpares. Essa classificacao pode serjustificada pela divisao euclidiana.

Dado um numero inteiro n ∈ Z qualquer, temos duaspossibilidades:

i) n e par: o resto da divisao de n por 2 e 0, isto e, existe q ∈ N talque n = 2q; ou

ii) n e ımpar: o resto da divisao de n por 2 e 1, ou seja, existeq ∈ N tal que n = 2q + 1.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 16/21

Generalizacao: divisao por m ≥ 3

Mais geralmente, fixado um numero natural m > 2, pode-sesempre escrever um numero qualquer n, de modo unico, na forman = mk + r , onde k , r ∈ Z e 0 6 r < m.

Por exemplo,

todo numero inteiro n pode ser escrito em uma, e somenteuma, das seguintes formas: 3k , 3k + 1, ou 3k + 2.

Ou ainda,

todo numero inteiro n pode ser escrito em uma, e somenteuma, das seguintes formas: 4k , 4k + 1, 4k + 2, ou 4k + 3.

Este ultimo fato, permite mostrar o resultado a seguir.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 17/21

Exercıcio

Nenhum quadrado de um numero inteiro e da forma 4k + 3.

Solucao

De fato, seja a ∈ Z.

Se a = 4k, entao a2 = 16k2 = 4k ′, onde k ′ = 4k2.

Se a = 4k + 1, entao a2 = 16k2 + 8k + 1 = 4k ′ + 1,onde k ′ = 4k2 + 2k.

Se a = 4k + 2, entao a2 = 16k2 + 16k + 4 = 4k ′,onde k ′ = 4k2 + 4k + 1.

Se a = 4k + 3, entao a2 = 16k2 + 24k + 9 = 4k ′ + 1,onde k ′ = 4k2 + 6k + 2.

Vamos aplicar este resultado para mostrar algo interessante.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 18/21

Exercıcio

Nenhum numero da forma a = 11 . . . 1 (n algarismos iguais a 1,com n > 1) e um quadrado.

Solucao

De fato, podemos escrever

a = b · 100 + 11 = 4(25 · b + 2) + 3,

onde b = 11 . . . 1 (n− 2 algarismos iguais a 1). Logo, a e da forma4k + 3 e, portanto, nao pode ser um quadrado.

Com esta tecnica pode-se mostrar que nenhum numero da forma11 . . . 1 e soma de dois quadrados. Deixamos isto como exercıcio.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 19/21

Exercıcio

a) Quais sao os numeros que, quando divididos por 7, deixam restoigual a metade do quociente?

Solucao

Seja a o numero com a propriedade descrita acima. Pela divisaoeuclidiana de a por 7 temos que existem inteiros q e r , tais quea = 7q + r , com 0 ≤ r < 7. Como 0 ≤ r = q

2 ≤ 6, entao q e par,com 0 ≤ q ≤ 12.

Os valores possıveis de q, r e a estao na seguinte tabela:

q 0 2 4 6 8 10 12

r 0 1 2 3 4 5 6

a = 7q + r 0 15 30 45 60 75 90

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 20/21

Exercıcio

b) (ENC: 2011) Seja N um numero natural. Mostre que a divisaode N2 por 6 nunca deixa resto 2.

Solucao

Pela divisao euclidiana de N por 6, existem inteiros q e r tais queN = 6q + r , com 0 ≤ r ≤ 5.Portanto, N2 = 36q2 + 12qr + r2 = 6(6q2 + 2qr) + r2.Assim, o resto que N2 deixa na divisao por 6 e o mesmo resto der2.Analisaremos os valores de r2, na seguinte tabela:

r 0 1 2 3 4 5

r2 0 1 4 9 = 6 · 1 + 3 16 = 6 · 2 + 4 25 = 6 · 4 + 1

Logo, os restos possıveis sao 0, 1, 3 e 4.

PROFMAT - SBM Aritmetica - Unidade 3 - Parte 2 - Divisao Euclidiana slide 21/21