Matemática do ensino fundamental · Grades 1–9

64Aritmética: divisores e números primos

A aritmética estuda os números inteiros e o modo como eles se dividem uns aos outros. As personagens centrais dela são os números primos, os tijolos com que todo inteiro é montado por multiplicação. O capítulo termina com o máximo divisor comum, a ferramenta certa para simplificar frações de uma vez por todas. Essa história continua, muito mais longe, no volume do ensino médio e além.

64.1 Divisores e múltiplos

Definição 64.1 (Divisor, múltiplo)

Sejam $a$ e $b$ números inteiros positivos. Dizemos que $b$ divide $a$ (ou que $b$ é um divisor de $a$ , ou que $a$ é um múltiplo de $b$ ) quando $a = b \times k$ para algum inteiro $k$ — isto é, quando a divisão de $a$ por $b$ deixa resto $0$ .

Exemplo 64.2

Os divisores de $24$ são $1, 2, 3, 4, 6, 8, 12, 24$ — eles vêm em pares cujo produto é $24$ : $(1,24)$ , $(2,12)$ , $(3,8)$ , $(4,6)$ . Os múltiplos de $7$ são $7, 14, 21, 28, \dots$

Proposição 64.3 (Critérios de divisibilidade)

Um número inteiro é divisível:

por $2$ quando o último algarismo dele é par ( $0, 2, 4, 6, 8$ );
por $5$ quando o último algarismo é $0$ ou $5$ ;
por $10$ quando o último algarismo é $0$ ;
por $3$ (resp. $9$ ) quando a soma dos algarismos é divisível por $3$ (resp. $9$ );
por $4$ quando os dois últimos algarismos formam um número divisível por $4$ .

Demonstração. Admitido neste nível. ∎

Exemplo 64.4

$7\,215$ termina em $5$ : divisível por $5$ . A soma dos algarismos dele é $7 + 2 + 1 + 5 = 15$ , divisível por $3$ , mas não por $9$ : então $7\,215$ é divisível por $3$ e não por $9$ . De fato, $7\,215 = 3 \times 5 \times 481$ .

64.2 Números primos

Definição 64.5 (Número primo)

Um número primo é um inteiro $\geq 2$ cujos únicos divisores são $1$ e ele mesmo. Os primos abaixo de $30$ são

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

O número $1$ não é primo (por convenção), e um inteiro $\geq 2$ que não é primo se diz composto.

Teorema 64.6 (Decomposição em fatores primos)

Todo número inteiro $\geq 2$ é um produto de números primos, e essa decomposição é única, a menos da ordem dos fatores.

Demonstração. Admitido neste nível. ∎

Método 64.7 (Decompor um inteiro)

Divida pelo menor primo possível, repetidamente, até chegar a $1$ :

tente $2$ enquanto o número for par;
depois tente $3$ , depois $5$ , depois $7$ … (só primos);
pare quando o quociente for $1$ ; reúna os fatores com os expoentes.

Basta testar os primos $p$ com $p^2$ não maior que o número atual: se nenhum o divide, o próprio número é primo.

Exemplo 64.8

Decomponha $360$ , uma divisão de cada vez:

360 = 2 \times 180, \quad 180 = 2 \times 90, \quad 90 = 2 \times 45, \quad 45 = 3 \times 15, \quad 15 = 3 \times 5,

então

360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5 .

A árvore de fatores de 360: cada passo separa o menor fator primo (em vermelho). Lendo as folhas vermelhas e o 5 final: 360 = 23 × 32 × 5. — A árvore de fatores de $360$ : cada passo separa o menor fator primo (em vermelho). Lendo as folhas vermelhas e o $5$ final: $360 = 2^3 \times 3^2 \times 5$ .

Teorema 64.9 (Euclides)

Existem infinitos números primos.

Demonstração. Suponha que houvesse apenas uma quantidade finita deles, digamos $p_1, p_2, \dots, p_k$ , e considere

N = p_1 \times p_2 \times \dots \times p_k + 1 .

Dividir $N$ por qualquer $p_i$ deixa resto $1$ , então nenhum $p_i$ divide $N$ . Mas $N \geq 2$ tem pelo menos um divisor primo (Teorema 64.6) — um primo que não está na nossa lista. Contradição: nenhuma lista finita pode conter todos os primos. ∎

64.3 O máximo divisor comum

Definição 64.10 (MDC)

O máximo divisor comum de dois números inteiros positivos $a$ e $b$ , escrito $\gcd(a, b)$ , é o maior inteiro que divide os dois. Quando $\gcd(a, b) = 1$ , os inteiros são ditos primos entre si: não têm divisor comum além de $1$ .

Exemplo 64.11

Divisores de $18$ : $1, 2, 3, 6, 9, 18$ . Divisores de $24$ : $1, 2, 3, 4, 6, 8, 12, 24$ . Divisores comuns: $1, 2, 3, 6$ ; então $\gcd(18, 24) = 6$ . Os inteiros $15$ e $28$ são primos entre si.

Proposição 64.12 (MDC pelas decomposições)

O MDC de dois inteiros é o produto dos primos que aparecem nas duas decomposições, cada um tomado com o menor dos dois expoentes.

Demonstração. Admitido neste nível. ∎

Exemplo 64.13

$360 = 2^3 \times 3^2 \times 5$ e $84 = 2^2 \times 3 \times 7$ . Primos comuns: $2$ (expoentes $3$ e $2$ : fica $2$ ) e $3$ (expoentes $2$ e $1$ : fica $1$ ). Então

\gcd(360, 84) = 2^2 \times 3 = 12 .

Teorema 64.14 (Algoritmo de Euclides)

Se $a = bq + r$ é a divisão de $a$ por $b$ com resto $r$ , então

\gcd(a, b) = \gcd(b, r).

Repetindo as divisões até o resto ser $0$ , o MDC de $a$ e $b$ é o último resto não nulo.

Demonstração. De $a = bq + r$ : todo inteiro que divide $b$ e $r$ divide $bq + r = a$ ; e de $r = a - bq$ : todo inteiro que divide $a$ e $b$ divide $r$ . Então os pares $(a, b)$ e $(b, r)$ têm exatamente os mesmos divisores comuns — em particular, o mesmo maior deles. Como os restos diminuem estritamente, o algoritmo termina, e $\gcd(x, 0) = x$ entrega o último resto não nulo. ∎

Exemplo 64.15

Calcule $\gcd(1071, 462)$ :

\begin{align*} 1071 &= 462 \times 2 + 147, \\ 462 &= 147 \times 3 + 21, \\ 147 &= 21 \times 7 + 0 . \end{align*}

O último resto não nulo é $21$ : $\gcd(1071, 462) = 21$ .

Método 64.16 (Simplificar uma fração completamente)

Para escrever $\dfrac ab$ na forma mais simples:

calcule $d = \gcd(a, b)$ , por exemplo pelo algoritmo de Euclides;
divida numerador e denominador por $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
a fração obtida é irredutível: o numerador e o denominador dela são primos entre si.

Exemplo 64.17

$\dfrac{462}{1071} = \dfrac{462 \div 21}{1071 \div 21} = \dfrac{22}{51}$ , e $\gcd(22, 51) = 1$ : irredutível.

64.4 Exercícios

Exercício 64.1 ★

Liste todos os divisores de $36$ , de $45$ e de $17$ .

Solução

Solução de Exercício 64.1.

Divisores de $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$ . Divisores de $45$ : $1, 3, 5, 9, 15, 45$ . Divisores de $17$ : apenas $1$ e $17$ ( $17$ é primo).

Exercício 64.2 ★

Usando os critérios de divisibilidade, determine se $2\,346$ é divisível por $2$ , por $3$ , por $4$ , por $5$ , por $9$ .

Solução

Solução de Exercício 64.2.

$2\,346$ termina em $6$ : divisível por $2$ , não por $5$ . Soma dos algarismos $2 + 3 + 4 + 6 = 15$ : divisível por $3$ , não por $9$ . Os dois últimos algarismos formam $46$ , e $46 = 4 \times 11 + 2$ não é divisível por $4$ : $2\,346$ não é divisível por $4$ .

Exercício 64.3 ★

Dê a decomposição em fatores primos de $72$ , $150$ , $210$ e $121$ .

Solução

Solução de Exercício 64.3.

$72 = 2^3 \times 3^2$ ; $150 = 2 \times 3 \times 5^2$ ; $210 = 2 \times 3 \times 5 \times 7$ ; $121 = 11^2$ .

Exercício 64.4 ★

$101$ é primo? E $91$ ? E $143$ ? Justifique usando a regra de parada do Método 64.7.

Solução

Solução de Exercício 64.4.

$101$ : teste os primos $p$ com $p^2 \leq 101$ , ou seja, $2, 3, 5, 7$ . Nenhum divide $101$ (é ímpar, soma dos algarismos $2$ , não termina em $0$ nem em $5$ , $101 = 7 \times 14 + 3$ ): $101$ é primo.

$91 = 7 \times 13$ : não é primo.

$143 = 11 \times 13$ : não é primo.

Exercício 64.5 ★

Calcule $\gcd(48, 60)$ de dois jeitos: listando os divisores comuns e pelas decomposições em fatores primos.

Solução

Solução de Exercício 64.5.

Divisores comuns de $48$ e $60$ : os divisores de $48$ são $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ ; os de $60$ são $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ ; os comuns são $1, 2, 3, 4, 6, 12$ , então $\gcd(48,60) = 12$ .

Pela decomposição: $48 = 2^4 \times 3$ e $60 = 2^2 \times 3 \times 5$ ; primos comuns com os menores expoentes: $2^2 \times 3 = 12$ .

Exercício 64.6 ★★

Use o algoritmo de Euclides para calcular $\gcd(255, 154)$ e depois $\gcd(1053, 325)$ . Escreva cada linha de divisão.

Solução

Solução de Exercício 64.6.

$\gcd(255, 154)$ :

\begin{align*} 255 &= 154 \times 1 + 101, \\ 154 &= 101 \times 1 + 53, \\ 101 &= 53 \times 1 + 48, \\ 53 &= 48 \times 1 + 5, \\ 48 &= 5 \times 9 + 3, \\ 5 &= 3 \times 1 + 2, \\ 3 &= 2 \times 1 + 1, \\ 2 &= 1 \times 2 + 0 . \end{align*}

Último resto não nulo: $\gcd(255, 154) = 1$ (eles são primos entre si).

$\gcd(1053, 325)$ :

\begin{align*} 1053 &= 325 \times 3 + 78, \\ 325 &= 78 \times 4 + 13, \\ 78 &= 13 \times 6 + 0 . \end{align*}

$\gcd(1053, 325) = 13$ .

Exercício 64.7 ★★

Torne irredutível a fração $\dfrac{588}{504}$ . (Calcule o MDC pelo método que preferir e depois divida.)

Solução

Solução de Exercício 64.7.

Algoritmo de Euclides: $588 = 504 \times 1 + 84$ ; $504 = 84 \times 6 + 0$ : $\gcd(588, 504) = 84$ . Então

\frac{588}{504} = \frac{588 \div 84}{504 \div 84} = \frac{7}{6},

que é irredutível.

Exercício 64.8 ★★

Uma florista tem $84$ rosas e $126$ tulipas e quer montar buquês idênticos, usando todas as flores, com a maior quantidade possível de buquês. Quantos buquês ela consegue montar, e o que cada um contém?

Solução

Solução de Exercício 64.8.

O número de buquês tem de dividir $84$ e $126$ ; o maior possível é $\gcd(84, 126)$ . Decomposições: $84 = 2^2 \times 3 \times 7$ , $126 = 2 \times 3^2 \times 7$ , então o MDC é $2 \times 3 \times 7 = 42$ . Ela consegue montar $42$ buquês, cada um com $\frac{84}{42} = 2$ rosas e $\frac{126}{42} = 3$ tulipas.

Exercício 64.9 ★★

Duas barcas saem do mesmo cais às 8:00. Uma parte a cada $24$ minutos, a outra a cada $36$ minutos. A que horas elas saem juntas pela próxima vez? (Procure o menor múltiplo comum de $24$ e $36$ ; as decomposições ajudam.)

Solução

Solução de Exercício 64.9.

Precisamos do menor múltiplo comum. $24 = 2^3 \times 3$ e $36 = 2^2 \times 3^2$ ; tomando cada primo com o maior expoente: $\lcm = 2^3 \times 3^2 = 72$ . As barcas voltam a sair juntas $72$ minutos depois das 8:00, às 9:12.

Exercício 64.10 ★★★

Seja $n$ um número inteiro positivo.

Mostre que $\gcd(n, n+1) = 1$ (inteiros consecutivos são sempre primos entre si).
Deduza que a fração $\dfrac{n}{n+1}$ é sempre irredutível.

Solução

Solução de Exercício 64.10.

1. Todo divisor comum $d$ de $n$ e $n+1$ divide também a diferença deles, $(n+1) - n = 1$ , então $d = 1$ : $\gcd(n, n+1) = 1$ .

2. Uma fração é irredutível exatamente quando o numerador e o denominador dela são primos entre si, o que é o caso de $n$ e $n + 1$ pela parte 1.

64.5 Problema: jarros de água, cigarras e cem armários

Problema 64.1

Problema de fim de semana — o MDC decide que quantidades dois jarros conseguem medir; os primos protegem as cigarras; e os armários que ficam abertos são os quadrados perfeitos

Três quebra-cabeças que parecem adivinhações e são, na verdade, aritmética: medir água com jarros sem marcação (o MDC disfarçado), ciclos de vida de insetos que evoluíram para números primos e um famoso corredor de cem armários cujo estado final é decidido pela contagem dos divisores. Tudo funciona com a maquinaria deste capítulo: divisibilidade, decomposição em fatores primos (Teorema 64.6) e algoritmo de Euclides (Teorema 64.14).

Parte I — Os jarros de água. Você está diante de uma fonte com dois jarros sem marcação, de $5$ L e $3$ L. Movimentos permitidos: encher um jarro até a borda, esvaziar completamente um jarro, despejar um jarro no outro até a origem ficar vazia ou o destino ficar cheio.

Meça exatamente $1$ L. (Descreva a sua sequência de movimentos e o conteúdo dos dois jarros depois de cada um.)
Meça exatamente $4$ L — o quebra-cabeça de um famoso filme de ação. (Dá para fazer em seis movimentos.)
Que números inteiros de litros de $1$ a $8$ você consegue exibir (num jarro, ou repartidos entre os dois)? Complete a lista, reaproveitando as suas sequências.
Jarros novos: $6$ L e $4$ L. Tente medir $1$ L — e depois explique por que é impossível: verifique que cada um dos três movimentos permitidos mantém o conteúdo de todo jarro múltiplo de $2$ , então toda quantidade alcançável é par.
O argumento da questão 4 vale em geral: com jarros de $a$ e $b$ litros, toda quantidade alcançável é múltipla de $\gcd(a, b)$ . Calcule $\gcd(6, 4)$ e $\gcd(5, 3)$ e diga o que a lei prevê para cada par de jarros.

Parte II — Euclides na fonte.

Calcule com o algoritmo de Euclides: $\gcd(91, 65)$ e $\gcd(2\,026, 46)$ .
Explique, com as suas palavras, por que as quantidades que aparecem nos jarros são os restos de Euclides disfarçados: com jarros de $13$ L e $5$ L, encha repetidamente o jarro pequeno e despeje-o no grande (esvaziando o grande sempre que ele encher). Que quantidades novas aparecem primeiro — e compare com os restos do algoritmo de Euclides para $(13, 5)$ .
Deduza a resposta de campeão: com jarros de $13$ e $5$ litros, dá para medir exatamente $1$ L? Justifique em uma linha, com a questão 5 e $\gcd(13, 5)$ .
Uma demonstraçãozinha de “primos entre si” no estilo do Exercício 64.10: mostre que $\gcd(n, 2n + 1) = 1$ para todo inteiro positivo $n$ . (O que um divisor comum de $n$ e $2n + 1$ tem de dividir?)
Dois ônibus saem juntos do terminal às 7:00; um parte a cada $12$ minutos, o outro a cada $18$ . Liste os horários seguintes de partida de cada um e encontre o primeiro momento em que eles saem juntos de novo. Verifique nesse exemplo a lei bonita: (primeiro múltiplo comum) $\times$ MDC $=$ produto dos dois números — e teste-a de novo com $5$ e $3$ .

Parte III — Cigarras, divisores e armários.

Certas cigarras norte-americanas emergem apenas a cada $17$ anos; suponha que a população de um predador atinja o pico a cada $4$ anos. Se as duas coisas acontecem neste ano, em quantos anos uma emergência voltará a coincidir com um pico? Mesma pergunta se o ciclo das cigarras fosse de $16$ anos — com que frequência elas seriam massacradas? Explique numa frase por que a evolução empurrou o ciclo para um comprimento primo.
Usando a decomposição $360 = 2^3 \times 3^2 \times 5$ , conte os divisores de $360$ sem listá-los: um divisor escolhe um expoente para o $2$ (quatro escolhas: $0, 1, 2, 3$ ), um para o $3$ e um para o $5$ . Quantos divisores no total?
Mostre que, na decomposição de um quadrado perfeito $n = m^2$ , todo primo carrega um expoente par. Deduza, sem calcular raiz quadrada nenhuma, que $360$ não é um quadrado perfeito.
Emparelhe cada divisor $d$ de $n$ com o parceiro $\frac{n}{d}$ dele (para $n = 36$ : $1 \leftrightarrow 36$ , $2 \leftrightarrow 18$ , $3 \leftrightarrow 12$ , $4 \leftrightarrow 9$ , $6 \leftrightarrow 6$ ). Quando um divisor é o próprio parceiro? Deduza o critério: $n$ tem um número ímpar de divisores exatamente quando $n$ é um quadrado perfeito. Confira em $36$ e em $360$ .
Os cem armários. Os armários $1$ a $100$ começam fechados. O aluno $1$ inverte o estado de todos os armários; o aluno $2$ inverte os armários $2, 4, 6, \dots$ ; o aluno $k$ inverte os múltiplos de $k$ ; e assim por diante, até o aluno $100$ . Explique que alunos tocam o armário $n$ , quantas vezes ele é invertido e — usando a questão 14 — exatamente que armários terminam abertos. Quantos ficam abertos?

Solução

Solução de Problema 64.1.

1. Encha o de $3$ e despeje-o no de $5$ (conteúdos: $0/3 \to 3$ no grande). Encha o de $3$ de novo e despeje no de $5$ até ele encher: o jarro grande só aceita mais $2$ , deixando

3 - 2 = 1 \text{ L no jarro pequeno.}

Movimentos: encher o $3$ ; despejar $3 \to 5$ ; encher o $3$ ; despejar $3 \to 5$ .

2. Encha o de $5$ ; despeje no de $3$ (sobram $2$ no grande); esvazie o de $3$ ; despeje os $2$ no de $3$ ; encha o de $5$ ; despeje no de $3$ até encher — ele aceita $1$ , deixando $\mathbf{4}$ L no jarro grande. Seis movimentos.

3. Todos: $1$ (questão 1), $2$ (depois de dois movimentos da questão 2), $3$ e $5$ (enchimentos simples), $4$ (questão 2), $6 = 3 + 3$ (um jarro pequeno cheio mais $3$ despejados no grande), $7 = 5 + 2$ , $8 = 5 + 3$ (os dois cheios). Toda quantidade inteira de $1$ a $8$ L é mensurável com o $5$ e o $3$ .

4. Início: os dois jarros contêm $0$ , múltiplo de $2$ . Encher põe um conteúdo em $6$ ou $4$ : par. Esvaziar põe em $0$ : par. Despejar move água entre jarros cujos conteúdos eram pares, e a quantidade despejada é uma diferença de números pares (o espaço que sobra, ou a quantidade disponível): todos os conteúdos permanecem pares para sempre. Um alvo ímpar como $1$ L é inalcançável.

5. $\gcd(6, 4) = 2$ : só quantidades pares — confirmado pela questão 4. $\gcd(5, 3) = 1$ : toda quantidade inteira é permitida pela lei, e a questão 3 realizou todas elas. O MDC é exatamente a unidade de medida dos jarros.

6. $91 = 1 \times 65 + 26$ ; $65 = 2 \times 26 + 13$ ; $26 = 2 \times 13 + 0$ : $\gcd(91, 65) = 13$ . E $2\,026 = 44 \times 46 + 2$ ; $46 = 23 \times 2 + 0$ : $\gcd(2\,026, 46) = 2$ .

7. Despejando o de $5$ no jarro de $13$ repetidamente: depois de dois enchimentos, o jarro grande contém $10$ ; o terceiro enchimento só cabe em $3$ , deixando $5 - 3 = 2$ no jarro pequeno — o resto de $13$ por $5$ era $3$ , e as quantidades $3$ (espaço) e $2$ (sobra) são exatamente os números de Euclides ( $13 = 2 \times 5 + 3$ , $5 = 1 \times 3 + 2$ ). Continuando, aparece $3 - 2 = 1$ : o resto seguinte do algoritmo. A fonte executa as divisões de Euclides com água.

8. $\gcd(13, 5) = 1$ , então a lei da questão 5 permite toda quantidade inteira — e a cascata da questão 7 de fato produziu $1$ L. Sim.

9. Um divisor comum de $n$ e $2n + 1$ divide $2n + 1 - 2 \times n = 1$ : ele tem de ser $1$ . Logo, $\gcd(n, 2n+1) = 1$ sempre.

10. Ônibus A: 7:12, 7:24, 7:36, 7:48, 8:00 …; ônibus B: 7:18, 7:36, 7:54 … Primeira partida em comum: 7:36, depois de $36$ minutos — o primeiro múltiplo comum de $12$ e $18$ . Lei: $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times 18$ . Para $5$ e $3$ : primeiro múltiplo comum $15$ , e $15 \times \gcd(5,3) = 15 \times 1 = 15 = 5 \times 3$ .

11. Com ciclo de $17$ anos: a próxima coincidência é o primeiro múltiplo comum de $17$ e $4$ ; como $\gcd(17, 4) = 1$ , ele é $17 \times 4 = 68$ anos — as cigarras encontram o pico uma vez a cada quatro emergências. Com ciclo de $16$ anos: $16$ é múltiplo de $4$ , então toda emergência cai num pico. Um comprimento de ciclo primo não compartilha fator nenhum com nenhum ciclo de predador mais curto, afastando ao máximo as coincidências: aritmética como camuflagem.

12. Quatro escolhas de expoente para o $2$ , três para o $3$ , duas para o $5$ : $4 \times 3 \times 2 = 24$ divisores.

13. Se $m = 2^{a} \times 3^{b} \times \cdots$ , então $m^2 = 2^{2a} \times 3^{2b} \times \cdots$ : todo expoente é dobrado, logo par. Em $360 = 2^3 \times 3^2 \times 5$ , os expoentes do $2$ e do $5$ são ímpares: $360$ não é um quadrado perfeito.

14. Um divisor é o próprio parceiro exatamente quando $d = \frac nd$ , isto é, $n = d^2$ : só os quadrados têm um divisor central assim. Para todos os outros $n$ , os divisores se repartem em pares, numa contagem par. Então: número ímpar de divisores $\Leftrightarrow$ quadrado perfeito. Conferindo: $36$ tem os divisores $1, 2, 3, 4, 6, 9, 12, 18, 36$ — nove deles, número ímpar, e $36 = 6^2$ ; já $360$ tem $24$ (questão 12), número par, e não é quadrado (questão 13).

15. O armário $n$ é invertido uma vez por cada aluno $k$ cujo número divide $n$ : ao todo, tantas vezes quantos divisores $n$ tem. Um armário termina aberto quando é invertido um número ímpar de vezes — pela questão 14, exatamente quando $n$ é um quadrado perfeito. Armários abertos: $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$ — dez deles.