--- title: "Aritmética dos Inteiros" book: "Matemática universitária — Graduação 1" subject: math language: pt chapter: 6 exercises: 12 source: https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros --- # Capítulo 6 — Aritmética dos Inteiros A aritmética — o estudo da [divisibilidade](#def-b1-arith-divides) em $\Z$ — foi iniciada no volume do ensino médio. Este capítulo a reconstrói inteiramente a partir da divisão euclidiana, com demonstrações completas: [máximo divisor comum](#thm-b1-arith-gcd) e [algoritmo de Euclides](#met-b1-arith-euclid), identidade de Bézout e lema de Gauss, [fatoração em primos](#thm-b1-arith-fta) e o cálculo das [congruências](#def-b1-arith-congruence) até o pequeno teorema de Fermat. Além do seu próprio encanto, este material é o modelo que o [Capítulo 8](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly) imita para os polinômios. ## 6.1 Divisibilidade e divisão euclidiana **Definição 6.1 (Divisibilidade).** Para $a, b \in \Z$, $b$ *divide* $a$ (escreve-se $b \mid a$) quando $a = bq$ para algum $q \in \Z$. Consequências básicas: se $b \mid a$ e $b \mid a'$, então $b \mid (ua + va')$ para todos $u, v \in \Z$; se $b \mid a$ e $a \neq 0$, então $\abs b \leq \abs a$; e $a \mid b$ junto com $b \mid a$ forçam $b = \pm a$. **Teorema 6.2 (Divisão euclidiana).** Para todos $a \in \Z$ e $b \in \N^*$, existe exatamente um par $(q, r) \in \Z \times \N$ com $$ a = bq + r, \qquad 0 \leq r < b . $$ **Demonstração.** *Existência.* O [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $A = \{a - bk : k \in \Z\} \cap \N$ é um subconjunto não vazio de $\N$ (tome $k = -\abs a$: $a + b\abs a \geq a + \abs a \geq 0$). Seja $r = a - bq$ o seu menor elemento. Se $r \geq b$, então $r - b = a - b(q+1)$ seria um elemento menor de $A$: contradição. Logo, $0 \leq r < b$. *Unicidade.* Se $bq + r = bq' + r'$ com $0 \leq r, r' < b$, então $b(q - q') = r' - r$ e $\abs{r' - r} < b$: o múltiplo de $b$ no lado esquerdo tem de ser $0$, de modo que $q = q'$ e $r = r'$. ∎ **Exemplo 6.3 (Numeração posicional por divisões sucessivas).** Escreva $2026$ na base $7$. Divida repetidamente por $7$, guardando os restos: $$ 2026 = 7 \times 289 + 3, \quad 289 = 7 \times 41 + 2, \quad 41 = 7 \times 5 + 6, \quad 5 = 7 \times 0 + 5 . $$ Lendo os restos do último ao primeiro: $2026 = (5\,6\,2\,3)_7$. Verificação: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$. A unicidade da divisão euclidiana é exatamente o que torna cada algarismo *forçado*: em cada passo, o resto é o único inteiro de $\intint06$ congruente ao valor corrente módulo $7$, de modo que a escrita na base $7$ é única — fato usado silenciosamente sempre que o problema de fim de semana manipula “os algarismos de $n$ na base $p$”. ## 6.2 Máximo divisor comum **Teorema 6.4 (Subgrupos de Z\ZZ; existência do mdc).** 1. Todo subgrupo de $(\Z, +)$ é da forma $n\Z = \{nk : k \in \Z\}$ para um único $n \in \N$ . 2. Para $a, b \in \Z$ não simultaneamente nulos, o [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ é um subgrupo de $\Z$ e, portanto, é igual a $d\,\Z$ para um único $d \in \N^*$ . Esse $d$ é o *máximo divisor comum* $\gcd(a, b)$ : ele [divide](#def-b1-arith-divides) $a$ e $b$ , e todo divisor comum de $a$ e $b$ [divide](#def-b1-arith-divides) $d$ . **Demonstração.** (1) Seja $H \subseteq \Z$ um subgrupo (não vazio, estável por subtração; a definição formal está no [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures), e apenas estas duas propriedades são usadas). Se $H = \{0\}$, tome $n = 0$. Caso contrário, $H$ contém um elemento não nulo e o seu oposto, logo um menor elemento estritamente positivo $n$. Então $n\Z \subseteq H$. Para $x \in H$, escreva $x = nq + r$ com $0 \leq r < n$ ([Teorema 6.2](#thm-b1-arith-division)); $r = x - nq \in H$, e a minimalidade de $n$ força $r = 0$: $x \in n\Z$. Unicidade: $n$ é o menor elemento positivo de $n\Z$. (2) $a\Z + b\Z$ contém $0$ e é estável por subtração, de modo que é $d\Z$ com $d \geq 1$ (ele contém $a$ ou $b$, não nulos). Como $a, b \in d\Z$, $d$ [divide](#def-b1-arith-divides) ambos. E, se $c$ [divide](#def-b1-arith-divides) $a$ e $b$, então $c$ [divide](#def-b1-arith-divides) todo $au + bv$ — em particular $c \mid d$, pois $d \in a\Z + b\Z$. Esta é a propriedade anunciada (e ela implica $\abs c \leq d$, de modo que $d$ merece o nome de *máximo* divisor comum). ∎ **Corolário 6.5 (Identidade de Bézout).** Para $a, b$ não simultaneamente nulos, existem $u, v \in \Z$ com $$ au + bv = \gcd(a, b) . $$ Em particular ($\gcd(a,b) = 1$, o caso dos números *primos entre si*): $a$ e $b$ são [primos entre si](#cor-b1-arith-bezout) se, e somente se, $au + bv = 1$ tem solução. **Demonstração.** $\gcd(a,b) = d \in d\Z = a\Z + b\Z$. Quanto à equivalência: se $\gcd(a,b) = 1$, Bézout fornece a solução; reciprocamente, $au + bv = 1$ força todo divisor comum de $a, b$ a dividir $1$. ∎ **Método 6.6 (Algoritmo de Euclides, estendido).** Para calcular $\gcd(a, b)$ ($a > b > 0$): divida $a = bq + r$; então $\gcd(a, b) = \gcd(b, r)$ (os divisores comuns de $(a,b)$ e os de $(b,r)$ coincidem, pois $r = a - bq$); itere até que o resto seja $0$; o último resto não nulo é o mdc. Percorrendo as divisões de trás para diante (ou mantendo os coeficientes na descida), obtém-se um par de Bézout $(u, v)$. **Exemplo 6.7.** $\gcd(120, 23)$: $120 = 5 \times 23 + 5$; $23 = 4 \times 5 + 3$; $5 = 1\times 3 + 2$; $3 = 1 \times 2 + 1$; $2 = 2 \times 1 + 0$. Logo, $\gcd = 1$. De trás para diante: $$ \begin{align*} 1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\ &= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23) = 47 \times 23 - 9 \times 120 . \end{align*} $$ Verificação: $47 \times 23 = 1081$, $9 \times 120 = 1080$. **Teorema 6.8 (Lema de Gauss e consequências).** Sejam $a, b, c \in \Z$. 1. (Lema de Gauss) Se $a \mid bc$ e $\gcd(a, b) = 1$ , então $a \mid c$ . 2. Se $a \mid c$ , $b \mid c$ e $\gcd(a,b) = 1$ , então $ab \mid c$ . 3. Se $\gcd(a, b) = \gcd(a, c) = 1$ , então $\gcd(a, bc) = 1$ . **Demonstração.** (1) Bézout: $au + bv = 1$. Multiplique por $c$: $acu + bcv = c$. Os dois termos são divisíveis por $a$ (o segundo porque $a \mid bc$), logo $a \mid c$. (2) Escreva $c = aq$; de $b \mid aq$ e $\gcd(a, b) = 1$, o ponto (1) dá $b \mid q$, de modo que $ab \mid aq = c$. (3) $au + bv = 1$ e $au' + cv' = 1$. Multiplique as duas relações: $$ 1 = (au + bv)(au' + cv') = a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') , $$ uma relação de Bézout entre $a$ e $bc$: pelo [Corolário 6.5](#cor-b1-arith-bezout), $\gcd(a, bc) = 1$. ∎ **Exemplo 6.9 (Resolvendo uma equação diofantina linear).** Encontre todos os $(x, y) \in \Z^2$ com $6x + 10y = 4$. Primeiro, o *teste de existência*: $\gcd(6, 10) = 2$ [divide](#def-b1-arith-divides) $4$, de modo que há soluções (se o mdc não dividisse o lado direito, o lado esquerdo seria sempre um múltiplo dele e não haveria nenhuma). Divida tudo: $3x + 5y = 2$. Uma solução particular está à vista: $(x_0, y_0) = (-1, 1)$. Para a geral, subtraia: $3(x + 1) = -5(y - 1)$, de modo que $3 \mid 5(y-1)$ e o lema de Gauss ($\gcd(3,5) = 1$) dá $3 \mid y - 1$: $y = 1 - 3k$, e então $x = -1 + 5k$. Reciprocamente, todo par desses serve: $$ (x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z . $$ O padrão é geral: uma solução particular mais os múltiplos inteiros de $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — a mesma estrutura “particular mais homogênea” do [Capítulo 5](https://one-course.com/books/math/3/pt/chapter/5-equacoes-diferenciais-lineares#ch-b1-diffeq), com o lema de Gauss desempenhando o papel da unicidade. **Definição 6.10 (Mínimo múltiplo comum).** $\operatorname{lcm}(a, b)$ é o gerador em $\N$ do subgrupo $a\Z \cap b\Z$: é um múltiplo comum de $a$ e $b$ que [divide](#def-b1-arith-divides) todo múltiplo comum e, para $a, b \in \N^*$, $$ \gcd(a,b) \times \operatorname{lcm}(a,b) = ab \qquad (\text{demonstração no} \text{Exercício 6.5}). $$ **Exemplo 6.11 (Problemas de alinhamento são problemas de mmc).** Duas engrenagens acopladas têm $84$ e $36$ dentes. Após quantos dentes de movimento comum elas voltam juntas à posição inicial? A configuração se repete quando o número de dentes decorridos é um múltiplo comum de $84$ e $36$; a primeira vez é em $$ \operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)} = \frac{3024}{12} = 252 $$ dentes — isto é, $3$ voltas da engrenagem grande e $7$ da pequena ($252/84$ e $252/36$). Note o caminho prático: *calcule primeiro o mdc* (Euclides: $84 = 2\times36 + 12$, $36 = 3\times12$) e depois divida — nunca construa o mmc listando múltiplos. Toda questão de coincidência periódica (engrenagens, alinhamentos planetários, dízimas que se reencontram) reduz-se a esse único cálculo. ## 6.3 Números primos **Definição 6.12.** Um inteiro $p \geq 2$ é *primo* quando os seus únicos divisores positivos são $1$ e $p$. Para $p$ primo e $a \in \Z$: ou $p \mid a$, ou $\gcd(p, a) = 1$. Consequentemente ([Teorema 6.8](#thm-b1-arith-gauss)), vale o *lema de Euclides*: se $p \mid ab$, então $p \mid a$ ou $p \mid b$. **Observação 6.13 (Testando a primalidade por divisões sucessivas).** Se $n = ab$ com $2 \leq a \leq b$, então $a^2 \leq ab = n$, de modo que $a \leq \sqrt n$: um $n$ composto tem sempre um divisor [primo](#def-b1-arith-prime) $\leq \sqrt n$. Assim, para testar se $n$ é [primo](#def-b1-arith-prime) basta tentar os [primos](#def-b1-arith-prime) até $\sqrt n$. Para $n = 271$: $\sqrt{271} < 17$, e $271$ não é divisível por nenhum de $2, 3, 5, 7, 11, 13$ (é ímpar, a soma dos algarismos é $10$, não termina em $0$ nem em $5$, $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$): [primo](#def-b1-arith-prime), após seis divisões em vez de duzentas. A barreira $\sqrt n$ é um limiar genuíno: cruzá-la eficientemente para números de cem algarismos exige os testes modernos de primalidade nascidos do [Teorema 6.23](#thm-b1-arith-fermat). **Teorema 6.14 (Euclides).** Existem infinitos [números primos](#def-b1-arith-prime). **Demonstração.** Todo inteiro $n \geq 2$ tem um divisor [primo](#def-b1-arith-prime): o seu menor divisor $\geq 2$ é [primo](#def-b1-arith-prime) (uma fatoração própria dele produziria um divisor menor de $n$). Agora suponha que $p_1, \dots, p_k$ fossem todos os [primos](#def-b1-arith-prime) e seja $N = p_1 p_2 \cdots p_k + 1 \geq 2$. Algum [primo](#def-b1-arith-prime) $p_i$ [divide](#def-b1-arith-divides) $N$; mas $p_i$ também [divide](#def-b1-arith-divides) $N - 1 = p_1\cdots p_k$, de modo que $p_i \mid 1$ — absurdo. ∎ **Teorema 6.15 (Teorema fundamental da aritmética).** Todo inteiro $n \geq 2$ é um produto de [primos](#def-b1-arith-prime), e a fatoração $$ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} \qquad (p_1 < p_2 < \dots < p_k \text{ primos},\ \alpha_i \in \N^*) $$ é única. **Demonstração.** *Existência* por indução forte ([Teorema 1.12](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#thm-b1-logic-induction)): $n = 2$ é [primo](#def-b1-arith-prime); para $n > 2$, ou $n$ é [primo](#def-b1-arith-prime), ou $n = ab$ com $2 \leq a, b < n$, e a hipótese de indução fatora $a$ e $b$. *Unicidade.* Suponha $p_1 \cdots p_r = q_1 \cdots q_s$ ([primos](#def-b1-arith-prime) listados com repetição, digamos $r \leq s$) e faça indução em $r$. Se $r = 0$, o lado esquerdo é $1$, o que força $s = 0$ (um produto não vazio de [primos](#def-b1-arith-prime) excede $1$). Para $r \geq 1$: o [primo](#def-b1-arith-prime) $p_1$ [divide](#def-b1-arith-divides) $q_1(q_2\cdots q_s)$, de modo que, pelo lema de Euclides, ou $p_1 \mid q_1$, ou $p_1 \mid q_2\cdots q_s$; iterando, $p_1$ [divide](#def-b1-arith-divides) algum $q_j$. Mas $q_j$ é [primo](#def-b1-arith-prime) e $p_1 \geq 2$: necessariamente $p_1 = q_j$. Cancele esse fator comum (legítimo: $\Z$ é um domínio de integridade) para obter $$ p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s $$ (com o chapéu marcando a omissão), uma igualdade de produtos mais curtos; a hipótese de indução diz que as duas listas $p_2, \dots, p_r$ e $q_1, \dots, \widehat{q_j}, \dots, q_s$ coincidem a menos da ordem e, portanto, as originais também coincidiam. A forma com expoentes agrupa os [primos](#def-b1-arith-prime) iguais. ∎ **Proposição 6.16 (Valorações).** Para $p$ [primo](#def-b1-arith-prime) e $n \in \N^*$, escreva $v_p(n)$ para o expoente de $p$ na fatoração de $n$ (com $v_p(n) = 0$ se $p \nmid n$). Então $$ v_p(mn) = v_p(m) + v_p(n), \qquad m \mid n \iff \forall p,\ v_p(m) \leq v_p(n), $$ $$ v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr), \qquad v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m), v_p(n)\bigr). $$ **Demonstração.** A primeira identidade vale porque as fatorações se multiplicam e a fatoração de $mn$ é única. Se $m \mid n$, escreva $n = mq$ e aplique-a. Reciprocamente, se todos os $v_p(m) \leq v_p(n)$, o inteiro $q = \prod_p p^{\,v_p(n) - v_p(m)}$ satisfaz $mq = n$. A fórmula do mdc: o inteiro $d = \prod p^{\min}$ [divide](#def-b1-arith-divides) os dois pelo critério, e todo divisor comum $c$ tem $v_p(c) \leq \min$ para todo $p$, de modo que $c \mid d$; mesmo raciocínio para o mmc com o $\max$. ∎ **Exemplo 6.17 (Quadrados e cubos por meio de valorações).** Um inteiro $n \geq 1$ é um quadrado perfeito se, e somente se, todo $v_p(n)$ é par (se $n = m^2$, então $v_p(n) = 2v_p(m)$; reciprocamente, divida ao meio cada expoente). Do mesmo modo para os cubos, com múltiplos de $3$. Assim, $21168 = 2^4 \times 3^3 \times 7^2$ não é um quadrado ($v_3 = 3$ é ímpar) nem um cubo ($v_2 = 4$); o menor inteiro positivo $m$ tal que $21168\,m$ *seja* um cubo é encontrado completando cada expoente até o próximo múltiplo de $3$: $$ m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28, \qquad 21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3 = 84^3 . $$ A ideia: questões multiplicativas (quadrados, cubos, divisores, mdc, mmc) tornam-se questões *coordenada a coordenada* sobre os vetores de expoentes $(v_2, v_3, v_5, \dots)$ — a fatoração única é a afirmação de que essas coordenadas existem e estão bem definidas. ## 6.4 Congruências **Definição 6.18.** Para $n \in \N^*$: $a \equiv b \pmod n$ quando $n \mid a - b$. Esta é uma [relação de equivalência](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-equiv) compatível com a adição e a multiplicação: se $a \equiv b$ e $a' \equiv b'$ (mód. $n$), então $a + a' \equiv b + b'$, $aa' \equiv bb'$ e $a^k \equiv b^k$ para $k \in \N$. **Exemplo 6.19 (A prova dos noves).** A compatibilidade com $+$ e $\times$ é um recurso de verificação tão antigo quanto o comércio. Como $10 \equiv 1 \pmod 9$, todo inteiro é congruente módulo $9$ à soma dos seus algarismos (demonstrado no [Exercício 6.2](#exo-b1-arith-2)). Para verificar a afirmação $1234 \times 567 = 699\,678$: as somas dos algarismos dão $1234 \equiv 1$ e $567 \equiv 18 \equiv 0 \pmod 9$, de modo que o produto deve ser $\equiv 1 \times 0 = 0$; e, de fato, $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. A verificação passa (e o produto está, de fato, correto). Se alguém tivesse relatado $699\,478$, a soma dos algarismos $43 \equiv 7 \not\equiv 0$ o condenaria instantaneamente. O teste é unilateral — ele apanha um erro a menos que o próprio erro seja um múltiplo de $9$ — o que é exatamente a lição dos pseudoprimos do [Exemplo 6.24](#ex-b1-arith-pseudoprime) em miniatura: verificações por [congruência](#def-b1-arith-congruence) refutam, não certificam. **Proposição 6.20 (Invertibilidade módulo nnn).** $a$ é *invertível módulo $n$* (isto é, $ab \equiv 1 \pmod n$ para algum $b$) se, e somente se, $\gcd(a, n) = 1$. A inversa é então única módulo $n$ e calculada pelo [algoritmo de Euclides](#met-b1-arith-euclid) estendido. **Demonstração.** $ab \equiv 1 \pmod n$ significa $ab + nk = 1$ para algum $k$: uma relação de Bézout, que existe se, e somente se, $\gcd(a,n) = 1$ ([Corolário 6.5](#cor-b1-arith-bezout)). Unicidade: se $ab \equiv ab' \equiv 1$, então $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎ **Exemplo 6.21 (Invertendo 777 módulo 262626).** Como $\gcd(7, 26) = 1$, a classe de $7$ é invertível módulo $26$. Euclides estendido: $$ 26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 , $$ e depois, de trás para diante: $$ 1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 . $$ Portanto, $7 \times (-11) \equiv 1 \pmod{26}$, isto é, $7^{-1} \equiv -11 \equiv 15 \pmod{26}$; verificação: $7 \times 15 = 105 = 4 \times 26 + 1$. Com a inversa em mãos, qualquer [congruência](#def-b1-arith-congruence) $7x \equiv c \pmod{26}$ resolve-se com uma multiplicação: $x \equiv 15c$. Essa inversão mecânica é o cavalo de batalha da aritmética modular — e dos protocolos de chave pública mencionados na [Observação 6.27](#rem-b1-arith-whereused), em que os [módulos](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) têm centenas de algarismos, mas o algoritmo é exatamente este. **Exemplo 6.22 (Quando o coeficiente não é invertível).** Resolva $12x \equiv 8 \pmod{20}$. Aqui $\gcd(12, 20) = 4$, de modo que $12$ não é invertível módulo $20$ — mas a equação ainda é tratável. A [congruência](#def-b1-arith-congruence) diz que $20 \mid 12x - 8$; dividindo a relação inteira por $4$ (divisor dos três ingredientes), ela é equivalente a $5 \mid 3x - 2$, isto é, $$ 3x \equiv 2 \pmod 5 . $$ Agora, $\gcd(3, 5) = 1$ e $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6 \equiv 1$), de modo que $x \equiv 4 \pmod 5$: as soluções são $x \equiv 4, 9, 14, 19 \pmod{20}$ — *quatro* classes módulo $20$, correspondendo ao mdc. (Se o lado direito não fosse divisível por $4$, digamos $12x \equiv 6 \pmod{20}$, não haveria solução alguma: o lado esquerdo é sempre $\equiv 0 \pmod 4$.) Forma geral: $ax \equiv b \pmod n$ tem solução se, e somente se, $\gcd(a, n) \mid b$, e nesse caso tem exatamente $\gcd(a, n)$ classes de soluções — divida tudo pelo mdc e inverta. **Teorema 6.23 (Pequeno teorema de Fermat).** Seja $p$ [primo](#def-b1-arith-prime). Para todo $a \in \Z$: $$ a^p \equiv a \pmod p, $$ e, se $p \nmid a$, então $a^{p-1} \equiv 1 \pmod p$. **Demonstração.** Primeiro, para $1 \leq k \leq p - 1$, o [coeficiente binomial](https://one-course.com/books/math/3/pt/chapter/2-contagem#def-b1-counting-objects) $\binom pk = \frac{p!}{k!(p-k)!}$ é divisível por $p$: com efeito, $k!\,(p-k)!\, \binom pk = p!$ e $p$ [divide](#def-b1-arith-divides) $p!$, mas é [primo](#def-b1-arith-prime) com $k!(p-k)!$ (todos os fatores são $< p$), de modo que o lema de Gauss dá $p \mid \binom pk$. Agora demonstremos $a^p \equiv a$ para $a \in \N$ por indução. Verdadeiro para $a = 0$. Se $a^p \equiv a$, então, pelo teorema binomial, $$ (a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \equiv a + 1 \pmod p, $$ com todos os termos intermediários se anulando módulo $p$. Para $a < 0$, aplique o resultado a $-a$ e separe $p = 2$ (em que $x \equiv -x$) do $p$ ímpar (em que $(-a)^p = -a^p$). Por fim, se $p \nmid a$, multiplique $a^p \equiv a$ por uma inversa de $a$ módulo $p$ ([Proposição 6.20](#prop-b1-arith-invmod)). ∎ **Exemplo 6.24 (A recíproca de Fermat falha: 341341341).** O pequeno teorema de Fermat dá um teste barato de *composicionalidade*: se $a^{n-1} \not\equiv 1 \pmod n$ para algum $a$ [primo](#def-b1-arith-prime) com $n$, então $n$ não é [primo](#def-b1-arith-prime). O teste poderia também certificar a primalidade? Não: tome $n = 341 = 11 \times 31$, composto, e $a = 2$. Como $2^{10} = 1024 = 3 \times 341 + 1$, $$ 2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} : $$ o composto $341$ passa no teste de Fermat na base $2$ (é o menor *pseudoprimo* desse tipo). A base $3$ o desmascara ($3^{340} \not\equiv 1$), e o teste prático de primalidade, portanto, roda o teste em várias bases, com refinamentos — as versões industriais dessa ideia são o que certifica os grandes [primos](#def-b1-arith-prime) da [Observação 6.27](#rem-b1-arith-whereused). Moral: uma implicação e a sua recíproca vivem vidas separadas ([Observação 1.10](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#rem-b1-logic-pitfalls)), mesmo para teoremas. **Exemplo 6.25 (Cálculos práticos com congruências).** Qual é o resto de $7^{2026}$ na divisão por $11$? Por Fermat, $7^{10} \equiv 1 \pmod{11}$. Como $2026 = 10 \times 202 + 6$: $$ 7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4 \pmod{11}. $$ O resto é $4$. A estratégia: reduza o expoente [módulo](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) a ordem fornecida por Fermat e depois reduza as potências intermediárias a cada passo. **Observação 6.26 (Armadilhas frequentes em aritmética).** 1. *Dividir uma [congruência](#def-b1-arith-congruence).* De $ac \equiv bc \pmod n$ *não* se pode concluir $a \equiv b$ , a menos que $\gcd(c, n) = 1$ : $6 \equiv 2 \pmod 4$ , mas $3 \not\equiv 1 \pmod 4$ . A regra geral correta [divide](#def-b1-arith-divides) também o [módulo](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) : $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ . 2. *Usar mal o lema de Euclides.* $a \mid bc$ implica $a \mid b$ ou $a \mid c$ apenas para $a$ *[primo](#def-b1-arith-prime)* (ou [primo](#def-b1-arith-prime) com um dos fatores): $6 \mid 4 \times 9$ , mas $6$ não [divide](#def-b1-arith-divides) nenhum dos fatores. 3. *“[Primos entre si](#cor-b1-arith-bezout)” é uma relação, não uma propriedade.* “ $8$ e $9$ são [primos entre si](#cor-b1-arith-bezout) ” é verdade, embora nenhum deles seja [primo](#def-b1-arith-prime) ; “dois a dois [primos entre si](#cor-b1-arith-bezout) ” é mais forte que “ [primos entre si](#cor-b1-arith-bezout) no [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) ” ( $\gcd(6, 10, 15) = 1$ , mas nenhum par é formado por [primos entre si](#cor-b1-arith-bezout) ). 4. *Os expoentes não vivem módulo $n$.* Em $a^k \bmod n$ , o expoente só pode ser reduzido [módulo](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) a *ordem* de $a$ (por exemplo, $p - 1$ quando Fermat se aplica), nunca módulo $n$ : $2^{10} \bmod 11$ vale $1$ , e não $2^{10 \bmod 11} = 2^{10}$ — a redução que funciona é a que o [Exemplo 6.25](#ex-b1-arith-congruences) executa. **Observação 6.27 (Onde este capítulo é usado).** Este capítulo é tanto um modelo quanto uma caixa de ferramentas. Toda a cadeia — divisão euclidiana, mdc, Bézout, Gauss, fatoração única — é reencenada literalmente para os polinômios no [Capítulo 8](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly), em que o “grau” faz o papel do valor absoluto; comparar os dois capítulos lado a lado é a melhor maneira de entender ambos. O cálculo das [congruências](#def-b1-arith-congruence) torna-se o anel $\Z/n\Z$ no [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures), cujos elementos invertíveis ([Proposição 6.20](#prop-b1-arith-invmod)) formam o primeiro exemplo não trivial de um grupo de unidades. As valorações voltam no problema de fim de semana abaixo (fórmula de Legendre) e alimentam as demonstrações de irracionalidade do [Capítulo 10](https://one-course.com/books/math/3/pt/chapter/10-numeros-reais#ch-b1-reals). Além deste volume, a inversão de Bézout módulo $n$ é o motor da criptografia de chave pública, e o pequeno teorema de Fermat é o avô dos testes de primalidade que certificam os grandes [primos](#def-b1-arith-prime) ali usados. **Observação 6.28 (Interlúdio: Z\ZZ como modelo).** Afaste-se dos teoremas individuais e observe a arquitetura do capítulo: uma ferramenta (a divisão euclidiana) produziu uma classificação (os subgrupos $n\Z$), que produziu um teorema de existência (mdc, Bézout), que produziu um cálculo de [divisibilidade](#def-b1-arith-divides) (Gauss), que produziu a fatoração única — cada andar apoiado apenas no de baixo. O mesmo edifício será erguido mais duas vezes neste volume, com térreos diferentes: no [Capítulo 8](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly), em que a divisão pelo grau substitui a divisão pelo tamanho e tudo acima se repete *literalmente*; e, em miniatura, dentro de cada $\Z/n\Z$ do [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures), em que questões de invertibilidade (a [Proposição 6.20](#prop-b1-arith-invmod) deste capítulo) se tornam enunciados estruturais sobre anéis e corpos. Reconhecer um argumento como “o argumento de $\Z$, transplantado” é o modo mais rápido de aprender esses capítulos — e o primeiro sabor do hábito central da álgebra: demonstrar teoremas sobre *axiomas*, e não sobre objetos. ![Linhas 0 a 7 do triângulo de Pascal com as entradas ímpares preenchidas: a linha n contém 2s_2(n) delas, em que s_2(n) é o número de uns na escrita binária de n (linhas 1, 2, 4: duas entradas ímpares; linha 7 = (111)_2: todas as oito). O padrão autossemelhante — cada “triângulo de ímpares” gera duas cópias de si mesmo — é o teorema de Kummer em forma de figura, demonstrado no problema de fim de semana abaixo.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg) *Linhas $0$ a $7$ do triângulo de Pascal com as entradas *ímpares* preenchidas: a linha $n$ contém $2^{s_2(n)}$ delas, em que $s_2(n)$ é o número de uns na escrita binária de $n$ (linhas $1, 2, 4$: duas entradas ímpares; linha $7 = (111)_2$: todas as oito). O padrão autossemelhante — cada “triângulo de ímpares” gera duas cópias de si mesmo — é o teorema de Kummer em forma de figura, demonstrado no problema de fim de semana abaixo.* ## 6.5 Exercícios **Exercício 6.1 ★.** Calcule $\gcd(1\,001, 777)$ pelo [algoritmo de Euclides](#met-b1-arith-euclid), e um par de Bézout para ele. **Solução de Exercício 6.1.** $1001 = 1 \times 777 + 224$; $777 = 3 \times 224 + 105$; $224 = 2 \times 105 + 14$; $105 = 7 \times 14 + 7$; $14 = 2 \times 7 + 0$. Logo, $\gcd(1001, 777) = 7$. De trás para diante: $$ 7 = 105 - 7 \times 14 = 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224 $$ $$ = 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224 = 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 . $$ Verificação: $67 \times 777 = 52\,059$ e $52 \times 1001 = 52\,052$; a diferença é $7$. Par de Bézout: $(u, v) = (-52, 67)$ para $1001u + 777v = 7$. **Exercício 6.2 ★.** Demonstre os critérios de [divisibilidade](#def-b1-arith-divides) na base $10$: um inteiro é congruente módulo $9$ à soma dos seus algarismos, e módulo $11$ à soma alternada dos seus algarismos. Quanto vale $123\,456\,789$ módulo $9$ e módulo $11$? **Solução de Exercício 6.2.** Como $10 \equiv 1 \pmod 9$: $10^k \equiv 1$, de modo que $\sum_k d_k 10^k \equiv \sum_k d_k \pmod 9$. Como $10 \equiv -1 \pmod{11}$: $10^k \equiv (-1)^k$, de modo que o inteiro é congruente à soma alternada $\sum_k (-1)^k d_k$ módulo $11$ (começando pelo algarismo das *unidades* com sinal $+$). $123\,456\,789$: soma dos algarismos $45 \equiv 0 \pmod 9$. Soma alternada a partir das unidades: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$, de modo que o número é $\equiv 5 \pmod{11}$. **Exercício 6.3 ★.** Resolva em $\Z$: $91x \equiv 1 \pmod{237}$ *(Euclides estendido)*. **Solução de Exercício 6.3.** Euclides: $237 = 2 \times 91 + 55$; $91 = 1 \times 55 + 36$; $55 = 1 \times 36 + 19$; $36 = 1 \times 19 + 17$; $19 = 1 \times 17 + 2$; $17 = 8 \times 2 + 1$. De trás para diante: $$ 1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19 = 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19 $$ $$ = 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55 = 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55 $$ $$ = 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237. $$ Logo, $91 \times 112 \equiv 1 \pmod{237}$: as soluções são $x \equiv 112 \pmod{237}$. (Verificação: $91 \times 112 = 10\,192 = 43 \times 237 + 1$.) **Exercício 6.4 ★.** Encontre todos os pares $(x, y) \in \Z^2$ com $17x + 39y = 1$; depois todos os pares com $17 x + 39 y = 5$. **Solução de Exercício 6.4.** $\gcd(17, 39) = 1$: Euclides dá $39 = 2\times 17 + 5$, $17 = 3\times 5 + 2$, $5 = 2\times 2 + 1$ e, de trás para diante, $$ 1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17 = 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 . $$ Solução particular $(x_0, y_0) = (-16, 7)$. Solução geral da equação homogênea $17x + 39y = 0$: $x = 39k$, $y = -17k$ (pois $17 \mid 39y$ e $\gcd(17,39) = 1$ forçam $17 \mid y$ — lema de Gauss). Portanto, $$ (x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z . $$ Para o lado direito $5$, multiplique a solução particular por $5$: $(x, y) = (-80 + 39k,\; 35 - 17k)$, $k \in \Z$. **Exercício 6.5 ★★.** Demonstre que, para $a, b \in \N^*$: $\gcd(a,b) \times \operatorname{lcm}(a,b) = ab$. *(Use as fórmulas de valoração da [Proposição 6.16](#prop-b1-arith-valuation) e $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$.)* **Solução de Exercício 6.5.** Para todo [primo](#def-b1-arith-prime) $p$, com $\alpha = v_p(a)$ e $\beta = v_p(b)$: $$ v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr) = \min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta = v_p(ab) . $$ Dois inteiros positivos com a mesma valoração em todo [primo](#def-b1-arith-prime) são iguais ([Proposição 6.16](#prop-b1-arith-valuation)), de modo que $\gcd(a,b)\operatorname{lcm}(a,b) = ab$. **Exercício 6.6 ★★.** Sejam $a = 2^{10} \times 3^4 \times 5^2$ e $b = 2^6 \times 3^7 \times 7$. Calcule $\gcd(a, b)$, $\operatorname{lcm}(a,b)$ e o número de divisores positivos de $a$. *(Demonstre a fórmula de contagem de divisores $\prod_i (\alpha_i + 1)$.)* **Solução de Exercício 6.6.** Valorações: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)} 7^{\min(0,1)} = 2^6\, 3^4 = 5184$; $\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$. Contagem de divisores: um divisor positivo de $n = \prod p_i^{\alpha_i}$ é exatamente uma escolha $\prod p_i^{\beta_i}$ com $0 \leq \beta_i \leq \alpha_i$ ([Proposição 6.16](#prop-b1-arith-valuation)); as escolhas são independentes, de modo que há $\prod_i (\alpha_i + 1)$ divisores. Para $a$: $(10+1)(4+1)(2+1) = 165$. **Exercício 6.7 ★★.** Demonstre que $\sqrt p$ é irracional para todo [primo](#def-b1-arith-prime) $p$, usando valorações: compare $v_p$ dos dois lados de $p q^2 = r^2$. **Solução de Exercício 6.7.** Suponha $\sqrt p = \frac rq$ com $r, q \in \N^*$, isto é, $p q^2 = r^2$. Aplique $v_p$: $v_p(pq^2) = 1 + 2v_p(q)$ é ímpar, ao passo que $v_p(r^2) = 2 v_p(r)$ é par. Um inteiro não pode ter ao mesmo tempo valoração $p$-ádica ímpar e par: contradição. Logo, $\sqrt p \notin \Q$. **Exercício 6.8 ★★.** (Problema chinês do resto) Encontre todos os inteiros $x$ com $$ x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}. $$ Demonstre, ao longo do caminho, que, para $m, n$ [primos entre si](#cor-b1-arith-bezout), o par de [congruências](#def-b1-arith-congruence) $x \equiv a \ (m)$, $x \equiv b\ (n)$ sempre tem solução, única módulo $mn$. **Solução de Exercício 6.8.** *Fato geral.* Com $\gcd(m,n) = 1$, Bézout dá $mu + nv = 1$. Ponha $x_0 = b\,mu + a\,nv$. Então $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a \pmod m$ e, do mesmo modo, $x_0 \equiv b \pmod n$: existência. Se $x$ e $x'$ são duas soluções, $m$ e $n$ [dividem](#def-b1-arith-divides) $x - x'$, de modo que $mn \mid x - x'$ ([Teorema 6.8](#thm-b1-arith-gauss) (2)): unicidade módulo $mn$. *Numericamente:* $m = 7$, $n = 11$: $7 \times (-3) + 11 \times 2 = 1$. Logo, $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 + 44 = -61 \equiv 16 \pmod{77}$. Verificação: $16 = 2\times 7 + 2 \equiv 2 \pmod 7$; $16 = 11 + 5 \equiv 5 \pmod{11}$. Soluções: $x \equiv 16 \pmod{77}$. **Exercício 6.9 ★★.** Calcule $3^{1000}$ módulo $7$ e os dois últimos algarismos decimais de $7^{100}$ *(módulo $100 = 4 \times 25$: use o [Exercício 6.8](#exo-b1-arith-8))*. **Solução de Exercício 6.9.** [Módulo](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) $7$: Fermat dá $3^6 \equiv 1$, e $1000 = 6 \times 166 + 4$, de modo que $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$. Últimos dois algarismos de $7^{100}$: trabalhe módulo $4$ e módulo $25$. [Módulo](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) $4$: $7 \equiv -1$, de modo que $7^{100} \equiv 1$. [Módulo](https://one-course.com/books/math/3/pt/chapter/3-numeros-complexos#def-b1-complex-field) $25$: $7^2 = 49 \equiv -1$, de modo que $7^4 \equiv 1$ e $7^{100} = (7^4)^{25} \equiv 1$. Pelo teorema chinês do resto ([Exercício 6.8](#exo-b1-arith-8)), $7^{100} \equiv 1 \pmod{100}$: os dois últimos algarismos são $01$. **Exercício 6.10 ★★★.** Para $m, n \in \N^*$, demonstre que $\gcd(2^m - 1,\, 2^n - 1) = 2^{\gcd(m,n)} - 1$. *Sugestão: mostre primeiro que o resto de $2^m - 1$ módulo $2^n - 1$ é $2^r - 1$, em que $r$ é o resto de $m$ módulo $n$; depois siga o [algoritmo de Euclides](#met-b1-arith-euclid).* **Solução de Exercício 6.10.** Escreva $m = nq + r$, $0 \leq r < n$. Então $$ 2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1, $$ e $2^n - 1$ [divide](#def-b1-arith-divides) $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$. Assim, módulo $2^n - 1$, $\;2^m - 1 \equiv 2^r - 1$ e, como $0 \leq 2^r - 1 < 2^n - 1$, este *é* o resto euclidiano. Portanto, o [algoritmo de Euclides](#met-b1-arith-euclid) sobre o par $(2^m - 1, 2^n - 1)$ espelha, expoente por expoente, o algoritmo sobre $(m, n)$: cada passo de divisão substitui $(m, n)$ por $(n, r)$ em cima e $(2^m - 1, 2^n - 1)$ por $(2^n - 1, 2^r - 1)$ embaixo. O algoritmo de cima termina em $\gcd(m,n)$, de modo que o de baixo termina em $2^{\gcd(m,n)} - 1$. **Exercício 6.11 ★★★.** (Teorema de Wilson) Seja $p$ um [primo](#def-b1-arith-prime). Demonstre que $$ (p-1)! \equiv -1 \pmod p , $$ emparelhando cada fator de $(p-1)!$ com a sua inversa módulo $p$ e identificando os fatores emparelhados consigo mesmos (resolva antes $x^2 \equiv 1 \pmod p$). Verifique a recíproca: se $n \geq 2$ não é [primo](#def-b1-arith-prime), então $(n-1)! \not\equiv -1 \pmod n$. **Solução de Exercício 6.11.** Resolva primeiro $x^2 \equiv 1 \pmod p$: $p \mid (x-1)(x+1)$, de modo que, pelo lema de Euclides, $x \equiv 1$ ou $x \equiv -1 \pmod p$. No produto $(p-1)! = 1 \times 2 \times \dots \times (p-1)$, todo fator $a$ é invertível módulo $p$, e a sua inversa $a^{-1}$ é de novo um dos fatores ([Proposição 6.20](#prop-b1-arith-invmod)). Emparelhe cada $a$ com $a^{-1}$: os pares multiplicam-se dando $1$, salvo os fatores emparelhados consigo mesmos ($a = a^{-1}$, isto é, $a^2 \equiv 1$), que ficam sozinhos — e estes são exatamente $1$ e $p - 1$. Portanto, $$ (p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p . $$ (Para $p = 2$: $1! = 1 \equiv -1 \pmod 2$; o argumento de emparelhamento degenera, mas o resultado vale.) *Recíproca.* Seja $n \geq 2$ composto, $n = ab$ com $1 < a \leq b < n$. Se $a < b$, ambos aparecem como fatores distintos de $(n-1)!$, de modo que $n \mid (n-1)!$ e $(n-1)! \equiv 0 \not\equiv -1$. Se $a = b$ (isto é, $n = a^2$): para $a \geq 3$, tanto $a$ quanto $2a$ são $< n$, logo $n = a^2 \mid a \times 2a \mid (n-1)!$, mesma conclusão; para $n = 4$, $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$. **Exercício 6.12 ★★★.** (Números de Fermat) Para $n \in \N$, seja $F_n = 2^{2^n} + 1$. 1. Demonstre que $F_0 F_1 \cdots F_{n-1} = F_n - 2$ para $n \geq 1$ (indução). 2. Deduza que os números de Fermat são dois a dois [primos entre si](#cor-b1-arith-bezout) . 3. Deduza uma segunda demonstração, independente do [Teorema 6.14](#thm-b1-arith-euclidprimes) , de que existem infinitos [primos](#def-b1-arith-prime) . **Solução de Exercício 6.12.** 1. Indução. Para $n = 1$: $F_0 = 3 = F_1 - 2 = 5 - 2$. Supondo $F_0\cdots F_{n-1} = F_n - 2$: $$F_0 \cdots F_n = (F_n - 2)F_n = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr) = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$$ 2. Sejam $m < n$ e $d = \gcd(F_m, F_n)$ . Por (1), $F_m$ [divide](#def-b1-arith-divides) $F_n - 2$ , de modo que $d$ [divide](#def-b1-arith-divides) tanto $F_n$ quanto $F_n - 2$ e, portanto, [divide](#def-b1-arith-divides) $2$ . Mas todo número de Fermat é ímpar, logo $d = 1$ . 3. Cada $F_n \geq 3$ tem um divisor [primo](#def-b1-arith-prime) $p_n$ (primeiro passo do [Teorema 6.14](#thm-b1-arith-euclidprimes) ). Se $m \neq n$ , então $p_m \neq p_n$ , pois um [primo](#def-b1-arith-prime) comum dividiria $\gcd(F_m, F_n) = 1$ . A [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) $n \mapsto p_n$ é, portanto, [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) de $\N$ nos [primos](#def-b1-arith-prime) : existem infinitos [primos](#def-b1-arith-prime) . ## 6.6 Problema: A fórmula de Legendre e os transportes de Kummer **Problema 6.1.** Quantos zeros terminam a escrita decimal de $1000!$ — e, mais a fundo, qual é a potência exata de um [primo](#def-b1-arith-prime) $p$ que [divide](#def-b1-arith-divides) $n!$ ou que [divide](#def-b1-arith-divides) um [coeficiente binomial](https://one-course.com/books/math/3/pt/chapter/2-contagem#def-b1-counting-objects)? As respostas completas são duas joias da aritmética elementar: a *fórmula de Legendre* $v_p(n!) = \sum_{k\geq1} \lfloor n/p^k \rfloor$, com o seu avatar digital $v_p(n!) = \frac{n - s_p(n)}{p-1}$, e o *teorema de Kummer*: $v_p\binom{m+n}m$ conta os *transportes* (os “vai um”) na soma de $m$ e $n$ na base $p$. Este problema demonstra os dois, confere um contra o outro numericamente e colhe as consequências clássicas — zeros finais, a paridade do triângulo de Pascal e uma primeira estimativa na direção do teorema dos [números primos](#def-b1-arith-prime). Ao longo do problema, $p$ é um [primo](#def-b1-arith-prime), $\floor{x}$ é a parte inteira e $s_p(n)$ denota a soma dos algarismos de $n$ escrito na base $p$. **Parte I — Partes inteiras, valorações e a fórmula de Legendre.** 1. Aquecimento: calcule $10!$ e leia o seu número de zeros finais; calcule $v_2(10!)$ e $v_5(10!)$ diretamente a partir da fatoração de cada fator $1, 2, \dots, 10$ . 2. Demonstre que, para $x \in \R$ e $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ . 3. Demonstre que $v_p(a + b) \geq \min\bigl(v_p(a), v_p(b)\bigr)$ para todos $a, b \in \N^*$ , com igualdade sempre que $v_p(a) \neq v_p(b)$ . 4. Mostre que o número de múltiplos de $m$ em $\intint1n$ é $\lfloor n/m \rfloor$ . 5. Demonstre a *fórmula de Legendre*: para todo $n \in \N^*$, $$v_p(n!) = \sum_{k=1}^{\infty} \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$$ (uma soma finita: os termos se anulam assim que $p^k > n$). *Conte, para cada $k$, os fatores de $\intint1n$ divisíveis por $p^k$: cada um contribui com exatamente uma unidade por nível que alcança.* **Parte II — A forma digital e os zeros finais.** 1. Calcule $v_5(1000!)$ e $v_2(1000!)$ , e conclua: quantos zeros terminam $1000!$ ? 2. Demonstre a forma digital da fórmula de Legendre: escrevendo $n = \sum_i a_i p^i$ na base $p$, $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$ 3. Duas consequências para $p = 2$ : mostre que $2^n$ nunca [divide](#def-b1-arith-divides) $n!$ , e que $2^{n-1}$ [divide](#def-b1-arith-divides) $n!$ exatamente quando $n$ é uma potência de $2$ . 4. Estime o defeito: mostre que $\frac n{p-1} - \log_p(n) - 1 \leq v_p(n!) < \frac n{p-1}$ , de modo que $\frac{v_p(n!)}{n} \to \frac1{p-1}$ : a longo prazo, acumula-se uma proporção $\frac1{p-1}$ de um fator $p$ por unidade. 5. Seja $Z(n) = v_5(n!)$ o número de zeros finais de $n!$ . Mostre que $Z(n) - Z(n-1) = v_5(n)$ , deduza que $Z$ pula inteiramente o valor $5$ (calcule $Z(24)$ e $Z(25)$ ) e demonstre que nenhum fatorial termina em exatamente cinco zeros. **Parte III — O teorema de Kummer.** 1. Demonstre que $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \in \{0, 1\}$ para todos $x, y \in \R$, e deduza da fórmula de Legendre que $$v_p\binom{m+n}m = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$$ uma soma cujos termos valem cada um $0$ ou $1$. 2. Demonstre o *teorema de Kummer* : o $k$ -ésimo termo dessa soma vale $1$ exatamente quando a soma de $m$ e $n$ na base $p$ produz um transporte para a posição $k$ ; portanto, $v_p\binom{m+n}m$ é o número total de transportes. *(Escreva $m = p^km_1 + m_0$ e $n = p^kn_1 + n_0$ com $0 \leq m_0, n_0 < p^k$ e examine $\lfloor (m_0 + n_0)/p^k \rfloor$.)* 3. Deduza que, para $0 < j < p^k$: $$v_p\binom{p^k}{j} = k - v_p(j) ,$$ contando os transportes na soma $j + (p^k - j)$. (Em particular, $p \mid \binom p j$ para $0 < j < p$: o passo-chave do [Teorema 6.23](#thm-b1-arith-fermat), recuperado.) 4. Demonstre que $v_2\binom{2n}n = s_2(n)$ . Deduza que o [coeficiente binomial](https://one-course.com/books/math/3/pt/chapter/2-contagem#def-b1-counting-objects) central é sempre par e que $\binom{2n}n \equiv 2 \pmod 4$ exatamente quando $n$ é uma potência de $2$ . 5. Mostre, usando a identidade de Vandermonde ( [Exercício 2.7](https://one-course.com/books/math/3/pt/chapter/2-contagem#exo-b1-counting-7) ) e a questão 13, que $\binom{2p}p \equiv 2 \pmod p$ para todo [primo](#def-b1-arith-prime) $p$ . 6. Calcule $v_3\binom{1000}{500}$ duas vezes: uma por Kummer (escreva $500$ na base $3$ e conte os transportes em $500 + 500$ ), outra pela forma digital de Legendre (calcule $s_3(500)$ e $s_3(1000)$ ); verifique que as duas dão o mesmo valor. **Parte IV — A paridade do triângulo de Pascal e uma estimativa de densidade dos [primos](#def-b1-arith-prime).** 1. Demonstre o critério digital: $\binom nk$ é *ímpar* se, e somente se, todo algarismo binário de $k$ é no máximo o algarismo correspondente de $n$ . Enuncie e demonstre o critério análogo para $p \nmid \binom nk$ na base $p$ . 2. Deduza que a linha $n$ do triângulo de Pascal contém exatamente $2^{s_2(n)}$ entradas ímpares; verifique nas linhas $4$ e $5$ . 3. Deduza que todas as entradas interiores $\binom nk$ ( $0 < k < n$ ) são pares se, e somente se, $n$ é uma potência de $2$ . 4. Demonstre que toda potência de [primo](#def-b1-arith-prime) que [divide](#def-b1-arith-divides) $\binom{m+n}m$ é no máximo $m + n$ : se $p^a \mid \binom{m+n}m$ , então $p^a \leq m + n$ . *(Quantos termos não nulos pode ter a soma da questão 11?)* 5. Deduza que $\binom{2n}n$ [divide](#def-b1-arith-divides) $\operatorname{lcm}(1, 2, \dots, 2n)$ e combine com a estimativa inferior $\binom{2n}n \geq \frac{4^n}{2n+1}$ (que você demonstrará: a entrada central é a maior das $2n + 1$ entradas da linha $2n$) para obter $$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$$ os múltiplos comuns dos primeiros inteiros crescem *exponencialmente* — um primeiro vislumbre quantitativo da abundância dos [primos](#def-b1-arith-prime). **Parte V — Síntese.** 1. Encontre o menor $n$ tal que $n!$ termine em pelo menos $2026$ zeros. *(Estime $Z(n) \approx n/4$ e depois ajuste usando a fórmula exata.)* 2. Uma última verificação cruzada: mostre que $7$ *não* [divide](#def-b1-arith-divides) $\binom{100}{50}$ , primeiro escrevendo $50$ na base $7$ e conferindo que a soma $50 + 50$ não tem transportes, e depois calculando $v_7(100!)$ e $v_7(50!)$ com a fórmula de Legendre. 3. Onde exatamente o problema usou: (i) a fatoração única; (ii) a decomposição pela divisão euclidiana $n = p^k n_1 + n_0$ ; (iii) um argumento de contagem do [Capítulo 2](https://one-course.com/books/math/3/pt/chapter/2-contagem#ch-b1-counting) ? Uma frase para cada. 4. Síntese, num parágrafo curto: a fórmula de Legendre transforma uma questão de [divisibilidade](#def-b1-arith-divides) em aritmética de algarismos, e o teorema de Kummer lê a resposta nos transportes de uma única soma — comente essa tradução, as verificações da questão 16 e o que a estimativa da questão 21 sugere sobre os [primos](#def-b1-arith-prime) (o enunciado completo, o teorema dos [números primos](#def-b1-arith-prime) , está muito além deste volume; o análogo polinomial do instrumental deste capítulo está no [Capítulo 8](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly) ). **Solução de Problema 6.1.** **1.** $10! = 3\,628\,800$: dois zeros finais. Valorações fator a fator: as potências de $2$ vêm de $2, 4 = 2^2, 6, 8 = 2^3, 10$, totalizando $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$; as potências de $5$ vêm de $5$ e $10$: $v_5(10!) = 2$. Zeros finais $= \min(v_2, v_5) = 2$, coerente. **2.** Escreva a divisão euclidiana $\lfloor x\rfloor = nq + r$, $0 \leq r \leq n - 1$. Então $x = nq + r + \{x\}$ com $0 \leq r + \{x\} < n$, de modo que $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor$. **3.** Seja $\alpha = v_p(a) \leq \beta = v_p(b)$ (troque se necessário) e escreva $a = p^\alpha a'$, $b = p^\beta b'$ com $p \nmid a', b'$. Então $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$, de modo que $v_p(a + b) \geq \alpha = \min$. Se $\alpha < \beta$, o parêntese vale $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$: a valoração é exatamente $\alpha$. **4.** Os múltiplos de $m$ em $\intint1n$ são $m, 2m, \dots, qm$, em que $q$ é o maior inteiro com $qm \leq n$, isto é, $q = \lfloor n/m \rfloor$. **5.** Pela fatoração única, $v_p(n!) = \sum_{j=1}^{n} v_p(j)$. Conte de outro modo: cada $j$ contribui com $v_p(j) = \#\{k \geq 1 : p^k \mid j\}$, de modo que $$ v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\} = \sum_{k\geq1} \#\{j \leq n : p^k \mid j\} = \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor $$ pela questão 4 — a fórmula de Legendre. A soma é finita: os termos com $p^k > n$ se anulam. **6.** $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (divisões por $5, 25, 125, 625$); $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994$. Zeros finais de $1000!$: cada zero consome um $2$ e um $5$, de modo que há $\min(994, 249) = 249$ deles. **7.** Com $n = \sum_i a_ip^i$, a questão 2 dá $\lfloor n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (trunque a expansão na base $p$). Somando sobre $k \geq 1$ e trocando as duas somas finitas: $$ v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k} = \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1} = \frac{n - s_p(n)}{p - 1} . $$ **8.** Para $p = 2$: $v_2(n!) = n - s_2(n)$. Como $n \geq 1$ tem $s_2(n) \geq 1$, sempre $v_2(n!) \leq n - 1 < n$: $2^n \nmid n!$. E $v_2(n!) = n - 1$ se, e somente se, $s_2(n) = 1$, se, e somente se, $n$ é potência de $2$. **9.** $n$ tem $\lfloor \log_p n \rfloor + 1$ algarismos na base $p$, cada um no máximo $p - 1$, de modo que $1 \leq s_p(n) \leq (p-1)\bigl(\log_p(n) + 1\bigr)$. Substituindo na questão 7: $$ \frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1}, $$ e, dividindo por $n$: $\frac{v_p(n!)}n \to \frac1{p-1}$. **10.** $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$: a contagem de zeros finais salta de $v_5(n)$ em cada múltiplo de $5$ e é constante entre eles. $Z(24) = \lfloor24/5\rfloor = 4$ e $Z(25) = 5 + 1 = 6$: em $n = 25$ a contagem salta de $4$ direto para $6$ ($v_5(25) = 2$) e, como $Z$ é não decrescente com $Z \leq 4$ antes e $Z \geq 6$ depois, o valor $5$ nunca é atingido: nenhum fatorial termina em exatamente cinco zeros. **11.** Escreva $x = \lfloor x\rfloor + \{x\}$: $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} + \{y\}\rfloor$, e $0 \leq \{x\} + \{y\} < 2$ faz com que o último piso valha $0$ ou $1$. Então, aplicando Legendre três vezes, $$ v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!) = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr), $$ uma soma finita de $0$s e $1$s (aplique a primeira afirmação a $x = m/p^k$, $y = n/p^k$). **12.** Fixe $k \geq 1$ e escreva $m = p^km_1 + m_0$, $n = p^kn_1 + n_0$ com $0 \leq m_0, n_0 < p^k$ (divisão euclidiana: $m_0$ é o número formado pelos $k$ algarismos baixos de $m$). Então $$ \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac m{p^k}\Bigr\rfloor - \Bigl\lfloor\frac n{p^k}\Bigr\rfloor = \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor , $$ que vale $1$ se $m_0 + n_0 \geq p^k$ e $0$ caso contrário. Mas $m_0 + n_0 \geq p^k$ diz precisamente que somar os $k$ algarismos baixos de $m$ e de $n$ transborda para a posição $k$ — um transporte para a posição $k$ no algoritmo escolar da adição. Somando sobre $k$: $v_p\binom{m+n}m$ é o número de transportes na adição $m + n$ na base $p$. (Kummer, 1852.) **13.** Aplique Kummer a $m = j$, $n = p^k - j$, cuja soma é $p^k = (1\underbrace{0\cdots0}_{k})_p$. Seja $a = v_p(j)$, de modo que os algarismos de $j$ na base $p$ nas posições $0, \dots, a-1$ são $0$ e o algarismo na posição $a$ é não nulo. Os algarismos de $p^k - j$ abaixo da posição $a$ também são $0$ ($p^k - j = p^a(p^{k-a} - j/p^a)$). Na posição $a$, os dois algarismos não nulos devem somar $p$ (algarismo resultante $0$): um transporte; em cada posição $a+1, \dots, k-1$, os algarismos mais o transporte que chega somam $p$ (de novo, algarismo resultante $0$): o transporte se propaga. Total: $k - a$ transportes, de modo que $v_p\binom{p^k}j = k - v_p(j)$. Para $k = 1$: $v_p\binom pj = 1$ para $0 < j < p$, a [divisibilidade](#def-b1-arith-divides) usada no [Teorema 6.23](#thm-b1-arith-fermat). **14.** Pela forma digital (questão 7), usando $s_2(2n) = s_2(n)$ (basta acrescentar um algarismo zero): $$ v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n - s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 : $$ $\binom{2n}n$ é sempre par, e $v_2 = 1$ (isto é, $\binom{2n}n \equiv 2 \pmod 4$) exatamente quando $s_2(n) = 1$, ou seja, quando $n$ é uma potência de $2$. **15.** Vandermonde com $m = n = k = p$: $\binom{2p}p = \sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$. Para $0 < j < p$, $p \mid \binom pj$ (questão 13), de modo que $\binom pj^2 \equiv 0 \pmod p$; os termos das pontas dão $1 + 1$: $\binom{2p}p \equiv 2 \pmod p$. **16.** Base $3$: $500 = 486 + 9 + 3 + 2$, algarismos (do menos para o mais significativo) $(2, 1, 1, 0, 0, 2)$, de modo que $s_3(500) = 6$; e $1000 = 729 + 243 + 27 + 1$, algarismos $(1, 0, 0, 1, 0, 1, 1)$, de modo que $s_3(1000) = 4$. *Kummer:* some $500 + 500$ na base $3$: posição $0$: $2 + 2 = 4$, algarismo $1$, transporte $1$; posição $1$: $1 + 1 + 1 = 3$, algarismo $0$, transporte $1$; posição $2$: $1 + 1 + 1 = 3$, algarismo $0$, transporte $1$; posição $3$: $0 + 0 + 1 = 1$, sem transporte; posição $4$: $0$; posição $5$: $2 + 2 = 4$, algarismo $1$, transporte $1$; posição $6$: o transporte cai ali: algarismo $1$. Quatro transportes: $v_3\binom{1000}{500} = 4$. *Legendre:* $v_3(1000!) = \frac{1000 - 4}2 = 498$ e $v_3(500!) = \frac{500 - 6}2 = 247$, de modo que $v_3\binom{1000}{500} = 498 - 2\times247 = 4$. Os dois cálculos concordam — e os algarismos da adição $(1, 0, 0, 1, 0, 1, 1)$ reproduzem $1000$, como devem. **17.** Por Kummer ($p = 2$, $m = k$, $n' = n - k$): $\binom nk$ é ímpar se, e somente se, a adição $k + (n - k)$ na base $2$ não tem transporte, isto é, se, e somente se, em cada posição os algarismos satisfazem $k_i + (n - k)_i = n_i$; nesse caso, $k_i \leq n_i$ para todo $i$. Reciprocamente, se $k_i \leq n_i$ para todo $i$, então o número de algarismos $n_i - k_i$ é $n - k$ e a adição não tem transportes. Mesma demonstração na base $p$: $p \nmid \binom nk$ se, e somente se, todo algarismo de $k$ na base $p$ é no máximo o algarismo correspondente de $n$. **18.** Contando os $k \in \intint0n$ cujos algarismos obedecem a $k_i \leq n_i$: cada algarismo de $k$ é escolhido independentemente entre $n_i + 1$ valores, o que dá $\prod_i (n_i + 1)$ escolhas; na base $2$ isso é $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$. Linha $4 = (100)_2$: $2^1 = 2$ entradas ímpares — de fato, $1, 4, 6, 4, 1$ tem entradas ímpares apenas nas pontas. Linha $5 = (101)_2$: $2^2 = 4$ — de fato, $1, 5, 10, 10, 5, 1$. **19.** Todas as entradas interiores são pares $\iff$ a linha tem exatamente $2$ entradas ímpares (as duas pontas são sempre ímpares) $\iff 2^{s_2(n)} = 2 \iff s_2(n) = 1 \iff n$ é uma potência de $2$. **20.** Na soma da questão 11, o $k$-ésimo termo se anula assim que $p^k > m + n$ (os três pisos são então iguais; com efeito, o primeiro vale $0$ quando $p^k > m+n$; mais simplesmente, cada termo é $0$). Portanto, no máximo $\lfloor \log_p(m+n)\rfloor$ termos são não nulos, cada um valendo $1$: $a = v_p\binom{m+n}m \leq \log_p(m+n)$, isto é, $p^a \leq m + n$. **21.** Para todo [primo](#def-b1-arith-prime) $p$, $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (a maior potência de $p$ que não excede $2n$ aparece entre $1, \dots, 2n$). A questão 20 com $m = n$ dá $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ para todo $p$: pela [Proposição 6.16](#prop-b1-arith-valuation), $\binom{2n}n \mid \operatorname{lcm}(1, \dots, 2n)$. Quanto ao tamanho: a razão $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ exatamente para $k < n$, de modo que a entrada central é a maior das $2n + 1$ entradas da linha $2n$, donde $4^n = \sum_k \binom{2n}k \leq (2n+1)\binom{2n}n$. Combinando: $$ \operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq \frac{4^n}{2n + 1} . $$ Se houvesse poucos [primos](#def-b1-arith-prime) abaixo de $2n$, o mmc não poderia ser tão grande: o crescimento exponencial do mmc é um traço quantitativo da abundância dos [primos](#def-b1-arith-prime). **22.** $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac n4$, de modo que se deve mirar perto de $n = 4 \times 2026 = 8104$: $Z(8104) = 1620 + 324 + 64 + 12 + 2 = 2022$. Suba de $5$ em $5$: $Z(8110) = 2024$, $Z(8115) = 2025$, e $$ Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 . $$ Como $Z$ é constante entre múltiplos de $5$ e $Z(8119) = Z(8115) = 2025$, o menor $n$ com pelo menos $2026$ zeros finais é $n = 8120$. **23.** Base $7$: $50 = 49 + 1$, algarismos (do menos para o mais significativo) $(1, 0, 1)$. Somando $50 + 50$: posição $0$: $1 + 1 = 2 < 7$, sem transporte; posição $1$: $0 + 0 = 0$; posição $2$: $1 + 1 = 2 < 7$, sem transporte. Sem transportes, de modo que, por Kummer, $v_7\binom{100}{50} = 0$: $7 \nmid \binom{100}{50}$. Legendre concorda: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ e $v_7(50!) = 7 + 1 = 8$, de modo que $v_7\binom{100}{50} = 16 - 2\times8 = 0$. **24.** (i) A fatoração única sustenta a própria definição de $v_p$ e a sua aditividade, logo a fórmula de Legendre e toda conclusão de [divisibilidade](#def-b1-arith-divides) ([Proposição 6.16](#prop-b1-arith-valuation)). (ii) A divisão euclidiana produziu a identidade de truncamento da questão 2 e a separação $m = p^km_1 + m_0$ que isola o transporte (questão 12). (iii) Contagem: a contagem dos múltiplos de $m$ (questão 4), o produto de escolhas de algarismos (questão 18) e a estimativa da soma de linha $4^n \leq (2n+1)\binom{2n}n$ (questão 21) são todos argumentos ao estilo do [Capítulo 2](https://one-course.com/books/math/3/pt/chapter/2-contagem#ch-b1-counting). **25.** Legendre converte “que potência de $p$ [divide](#def-b1-arith-divides) $n!$” em aritmética de algarismos na base $p$; Kummer comprime a resposta para os [coeficientes binomiais](https://one-course.com/books/math/3/pt/chapter/2-contagem#def-b1-counting-objects) nos transportes de uma única adição — a [divisibilidade](#def-b1-arith-divides), aparentemente uma propriedade global de números enormes, é lida localmente, algarismo a algarismo. A questão 16 é o paradigma: quatro transportes, calculados à mão, determinam a potência exata de $3$ num número com centenas de algarismos. E a questão 21 mostra o mesmo círculo de ideias roçando águas profundas: uma estimativa inferior exponencial para $\operatorname{lcm}(1, \dots, 2n)$ é um primeiro passo, inteiramente elementar, rumo ao teorema dos [números primos](#def-b1-arith-prime), cuja demonstração está muito além deste volume. Todo o instrumental — divisão, mdc, valorações — é reencenado para os polinômios no [Capítulo 8](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly), em que o análogo de uma expansão em algarismos é a expansão em potências de $(X - a)$.