Matemática universitária — Graduação 1 · Bachelor Year 1

6Aritmética dos Inteiros

A aritmética — o estudo da divisibilidade 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 e algoritmo de Euclides, identidade de Bézout e lema de Gauss, fatoração em primos e o cálculo das congruências até o pequeno teorema de Fermat. Além do seu próprio encanto, este material é o modelo que o Capítulo 8 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 $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$ ; existência do mdc)

Todo subgrupo de $(\Z, +)$ é da forma $n\Z = \{nk : k \in \Z\}$ para um único $n \in \N$ .
Para $a, b \in \Z$ não simultaneamente nulos, o conjunto $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 $a$ e $b$ , e todo divisor comum de $a$ e $b$ divide $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, 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); $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 ambos. E, se $c$ divide $a$ e $b$ , então $c$ divide 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 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$ .

(Lema de Gauss) Se $a \mid bc$ e $\gcd(a, b) = 1$ , então $a \mid c$ .
Se $a \mid c$ , $b \mid c$ e $\gcd(a,b) = 1$ , então $ab \mid c$ .
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, $\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 $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, 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 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), 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 $\leq \sqrt n$ . Assim, para testar se $n$ é primo basta tentar os primos 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, 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.

Teorema 6.14 (Euclides)

Existem infinitos números primos.

Demonstração. Todo inteiro $n \geq 2$ tem um divisor primo: o seu menor divisor $\geq 2$ é primo (uma fatoração própria dele produziria um divisor menor de $n$ ). Agora suponha que $p_1, \dots, p_k$ fossem todos os primos e seja $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Algum primo $p_i$ divide $N$ ; mas $p_i$ também divide $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, 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): $n = 2$ é primo; para $n > 2$ , ou $n$ é primo, 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 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 excede $1$ ). Para $r \geq 1$ : o primo $p_1$ divide $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 algum $q_j$ . Mas $q_j$ é primo 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 iguais. ∎

Proposição 6.16 (Valorações)

Para $p$ primo 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 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 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). 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 em miniatura: verificações por congruência refutam, não certificam.

Proposição 6.20 (Invertibilidade módulo $n$ )

$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 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). Unicidade: se $ab \equiv ab' \equiv 1$ , então $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Exemplo 6.21 (Invertendo $7$ módulo $26$ )

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 $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, em que os módulos 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 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. 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 $\binom pk = \frac{p!}{k!(p-k)!}$ é divisível por $p$ : com efeito, $k!\,(p-k)!\, \binom pk = p!$ e $p$ divide $p!$ , mas é primo 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). ∎

Exemplo 6.24 (A recíproca de Fermat falha: $341$ )

O pequeno teorema de Fermat dá um teste barato de composicionalidade: se $a^{n-1} \not\equiv 1 \pmod n$ para algum $a$ primo com $n$ , então $n$ não é primo. 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 da Observação 6.27. Moral: uma implicação e a sua recíproca vivem vidas separadas (Observação 1.10), 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 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)

Dividir uma congruência. 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 também o módulo: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
Usar mal o lema de Euclides. $a \mid bc$ implica $a \mid b$ ou $a \mid c$ apenas para $a$ primo (ou primo com um dos fatores): $6 \mid 4 \times 9$ , mas $6$ não divide nenhum dos fatores.
“Primos entre si” é uma relação, não uma propriedade. “ $8$ e $9$ são primos entre si” é verdade, embora nenhum deles seja primo; “dois a dois primos entre si” é mais forte que “primos entre si no conjunto” ( $\gcd(6, 10, 15) = 1$ , mas nenhum par é formado por primos entre si).
Os expoentes não vivem módulo $n$ . Em $a^k \bmod n$ , o expoente só pode ser reduzido módulo 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 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, 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 torna-se o anel $\Z/n\Z$ no Capítulo 7, cujos elementos invertíveis (Proposição 6.20) 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. 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 ali usados.

Observação 6.28 (Interlúdio: $\Z$ 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 (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, 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, em que questões de invertibilidade (a Proposição 6.20 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. — 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, e um par de Bézout para ele.

Solução

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 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

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

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

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 e $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Solução

Solução de Exercício 6.5.

Para todo primo $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 são iguais (Proposição 6.16), 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

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); 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 $p$ , usando valorações: compare $v_p$ dos dois lados de $p q^2 = r^2$ .

Solução

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, o par de congruências $x \equiv a \ (m)$ , $x \equiv b\ (n)$ sempre tem solução, única módulo $mn$ .

Solução

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 $x - x'$ , de modo que $mn \mid x - x'$ (Teorema 6.8 (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).

Solução

Solução de Exercício 6.9.

Módulo $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 $4$ : $7 \equiv -1$ , de modo que $7^{100} \equiv 1$ . Módulo $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), $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.

Solução

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 $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 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. 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, então $(n-1)! \not\equiv -1 \pmod n$ .

Solução

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). 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$ .

Demonstre que $F_0 F_1 \cdots F_{n-1} = F_n - 2$ para $n \geq 1$ (indução).
Deduza que os números de Fermat são dois a dois primos entre si.
Deduza uma segunda demonstração, independente do Teorema 6.14, de que existem infinitos primos.

Solução

Solução de Exercício 6.12.

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 .$
Sejam $m < n$ e $d = \gcd(F_m, F_n)$ . Por (1), $F_m$ divide $F_n - 2$ , de modo que $d$ divide tanto $F_n$ quanto $F_n - 2$ e, portanto, divide $2$ . Mas todo número de Fermat é ímpar, logo $d = 1$ .
Cada $F_n \geq 3$ tem um divisor primo $p_n$ (primeiro passo do Teorema 6.14). Se $m \neq n$ , então $p_m \neq p_n$ , pois um primo comum dividiria $\gcd(F_m, F_n) = 1$ . A aplicação $n \mapsto p_n$ é, portanto, injetiva de $\N$ nos primos: existem infinitos primos.

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 $p$ que divide $n!$ ou que divide um coeficiente binomial? 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. Ao longo do problema, $p$ é um primo, $\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.

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$ .
Demonstre que, para $x \in \R$ e $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
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)$ .
Mostre que o número de múltiplos de $m$ em $\intint1n$ é $\lfloor n/m \rfloor$ .
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.

Calcule $v_5(1000!)$ e $v_2(1000!)$ , e conclua: quantos zeros terminam $1000!$ ?
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} .$
Duas consequências para $p = 2$ : mostre que $2^n$ nunca divide $n!$ , e que $2^{n-1}$ divide $n!$ exatamente quando $n$ é uma potência de $2$ .
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.
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.

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$ .
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$ .)
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, recuperado.)
Demonstre que $v_2\binom{2n}n = s_2(n)$ . Deduza que o coeficiente binomial central é sempre par e que $\binom{2n}n \equiv 2 \pmod 4$ exatamente quando $n$ é uma potência de $2$ .
Mostre, usando a identidade de Vandermonde (Exercício 2.7) e a questão 13, que $\binom{2p}p \equiv 2 \pmod p$ para todo primo $p$ .
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.

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$ .
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$ .
Deduza que todas as entradas interiores $\binom nk$ ( $0 < k < n$ ) são pares se, e somente se, $n$ é uma potência de $2$ .
Demonstre que toda potência de primo que divide $\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?)
Deduza que $\binom{2n}n$ divide $\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.

Parte V — Síntese.

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.)
Uma última verificação cruzada: mostre que $7$ não divide $\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.
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? Uma frase para cada.
Síntese, num parágrafo curto: a fórmula de Legendre transforma uma questão de divisibilidade 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 (o enunciado completo, o teorema dos números primos, está muito além deste volume; o análogo polinomial do instrumental deste capítulo está no Capítulo 8).

Solução

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 usada no Teorema 6.23.

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 $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, $\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 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.

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 (Proposição 6.16). (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.

25. Legendre converte “que potência de $p$ divide $n!$ ” em aritmética de algarismos na base $p$ ; Kummer comprime a resposta para os coeficientes binomiais nos transportes de uma única adição — a divisibilidade, 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, 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, em que o análogo de uma expansão em algarismos é a expansão em potências de $(X - a)$ .

Termos definidos neste capítulo

Ver todos os 395 termos do glossário