Matemática do ensino médio · Grades 10–12

29Aritmética

A aritmética estuda os inteiros: divisibilidade, números primos, restos. Durante muito tempo considerada a mais pura da matemática pura, ela hoje protege cada pagamento on-line: o criptossistema RSA repousa sobre os teoremas de Bézout, Gauss e Fermat demonstrados neste capítulo.

29.1 Divisibilidade e divisão euclidiana

Definição 29.1 (Divisibilidade)

Sejam $a, b \in \Z$ . Dizemos que $b$ divide $a$ , o que se escreve $b \mid a$ , se existe $k \in \Z$ com $a = kb$ . Dizemos também que $a$ é múltiplo de $b$ .

Proposição 29.2

Se $c \mid a$ e $c \mid b$ , então $c$ divide toda combinação inteira $au + bv$ ( $u, v \in \Z$ ). Se $a \mid b$ e $b \mid a$ com $a,b \in \N$ , então $a = b$ . Se $a \mid b$ e $b \neq 0$ , então $\abs a \leq \abs b$ .

Demonstração. Escreva $a = kc$ , $b = lc$ : então $au + bv = (ku + lv)c$ . Os demais itens seguem de $\abs{a} = \abs{k}\,\abs{b}$ com $\abs k \geq 1$ quando $b = ka \neq 0$ . ∎

Teorema 29.3 (Divisão euclidiana)

Sejam $a \in \Z$ e $b \in \N^*$ . Existe um único par $(q, r) \in \Z \times \N$ tal que

a = bq + r \qquad\text{e}\qquad 0 \leq r < b .

$q$ é o quociente e $r$ é o resto.

Demonstração. Existência. O conjunto dos múltiplos de $b$ que não excedem $a$ tem um maior elemento $bq$ (ele é não vazio e limitado superiormente); ponha $r = a - bq$ . Pela maximalidade, $b(q+1) > a$ , 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$ : um múltiplo de $b$ de valor absoluto menor que $b$ só pode ser $0$ , logo $r = r'$ e $q = q'$ . ∎

29.2 Congruências

Definição 29.4 (Congruência)

Seja $n \in \N^*$ . Dois inteiros $a, b$ são congruentes módulo $n$ , o que se escreve $a \equiv b \pmod n$ , se $n \mid (a - b)$ — equivalentemente, se $a$ e $b$ têm o mesmo resto na divisão euclidiana por $n$ .

Proposição 29.5 (Compatibilidade com as operações)

Se $a \equiv b \pmod n$ e $c \equiv d \pmod n$ , então

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

Demonstração. $n$ divide $(a-b) + (c-d) = (a+c) - (b+d)$ , e $ac - bd = a(c - d) + d(a - b)$ também é múltiplo de $n$ . A regra das potências segue por indução a partir da regra do produto. ∎

Método 29.6 (Calcular potências módulo $n$ )

Para calcular $a^k \bmod n$ , reduza a base módulo $n$ , depois procure uma potência pequena de $a$ congruente a $\pm1$ e use-a para encolher o expoente. Por exemplo, $2^{100} \bmod 7$ : como $2^3 = 8 \equiv 1 \pmod 7$ e $100 = 3\times33 + 1$ ,

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 MDC, Bézout e Gauss

Definição 29.7 (MDC)

Sejam $a, b$ inteiros não ambos nulos. O máximo divisor comum $\gcd(a, b)$ é o maior inteiro que divide $a$ e $b$ . Quando $\gcd(a,b) = 1$ , diz-se que $a$ e $b$ são primos entre si.

Proposição 29.8 (Algoritmo de Euclides)

Se $a = bq + r$ ( $b \neq 0$ ), então $\gcd(a, b) = \gcd(b, r)$ . Iterar a divisão euclidiana, portanto, calcula $\gcd(a,b)$ : o mdc é o último resto não nulo.

Demonstração. Todo divisor comum de $a$ e $b$ divide $r = a - bq$ (Proposição 29.2) e é, portanto, divisor comum de $b$ e $r$ ; e reciprocamente, já que $a = bq + r$ . Os dois pares têm os mesmos divisores comuns e, portanto, o mesmo mdc. O algoritmo termina porque os restos formam uma sequência estritamente decrescente de inteiros não negativos. ∎

Exemplo 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ . Logo $\gcd(252,198) = 18$ .

Teorema 29.10 (Identidade de Bézout)

Sejam $a, b$ inteiros não ambos nulos e $d = \gcd(a,b)$ . Existem $u, v \in \Z$ tais que

au + bv = d .

Em particular, $a$ e $b$ são primos entre si se, e somente se, $au + bv = 1$ para alguns inteiros $u, v$ .

Demonstração. Percorra o algoritmo de Euclides de trás para a frente: cada resto é combinação inteira dos dois anteriores, e os dados iniciais $a, b$ são combinações de si mesmos; por substituição descendente, o último resto não nulo $d$ é combinação inteira de $a$ e $b$ . (No Exemplo 29.9: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

Para a equivalência: se $\gcd(a,b) = 1$ , Bézout fornece $u, v$ ; reciprocamente, todo divisor comum de $a$ e $b$ divide $au + bv = 1$ , o que obriga $\gcd(a,b) = 1$ . ∎

Teorema 29.11 (Lema de Gauss)

Sejam $a, b, c \in \Z$ . Se $a \mid bc$ e $\gcd(a, b) = 1$ , então $a \mid c$ .

Demonstração. Bézout dá $au + bv = 1$ ; multiplique por $c$ : $acu + bcv = c$ . Os dois termos do lado esquerdo são múltiplos de $a$ (o segundo porque $a \mid bc$ ), logo $c$ também é. ∎

Corolário 29.12

Se $a \mid c$ , $b \mid c$ e $\gcd(a,b) = 1$ , então $ab \mid c$ .

Demonstração. Escreva $c = ak$ . De $b \mid ak$ e $\gcd(a,b)=1$ , Gauss dá $b \mid k$ , digamos $k = bl$ ; então $c = abl$ . ∎

29.4 Números primos

Definição 29.13 (Primo)

Um inteiro $p \geq 2$ é primo se seus únicos divisores positivos são $1$ e $p$ .

Proposição 29.14

Todo inteiro $n \geq 2$ tem um divisor primo; se $n$ não é primo, ele tem um divisor primo $\leq \sqrt n$ . Se um primo $p$ divide um produto $ab$ , então $p \mid a$ ou $p \mid b$ (lema de Euclides).

Demonstração. O menor divisor $d \geq 2$ de $n$ é primo (qualquer divisor próprio de $d$ seria um divisor menor de $n$ ). Se $n = de$ é composto com $2 \leq d \leq e$ , então $d^2 \leq de = n$ , logo $d \leq \sqrt n$ . Para o lema de Euclides: se $p \nmid a$ , então $\gcd(p, a) = 1$ (os únicos divisores de $p$ são $1$ e $p$ ), e o lema de Gauss dá $p \mid b$ . ∎

Teorema 29.15 (Euclides)

Há infinitos números primos.

Demonstração. Dada uma lista finita qualquer $p_1, \dots, p_k$ de primos, considere $N = p_1 p_2 \cdots p_k + 1$ . Algum primo $p$ divide $N$ ; mas nenhum $p_i$ divide $N$ (o resto é $1$ ), de modo que $p$ é um primo fora da lista. Nenhuma lista finita esgota os primos. ∎

Teorema 29.16 (Teorema fundamental da aritmética)

Todo inteiro $n \geq 2$ é produto de primos, e essa fatoração é única a menos da ordem dos fatores:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ primos},\ \alpha_i \geq 1 .

Demonstração. Existência, por indução forte: se $n$ é primo, ele é sua própria fatoração; caso contrário, $n = de$ com $2 \leq d, e < n$ , e ambos se fatoram pela hipótese de indução. Unicidade: suponha $p_1\cdots p_s = q_1 \cdots q_t$ (primos, com repetições permitidas). Pelo lema de Euclides, $p_1$ divide algum $q_j$ e, sendo primo, $p_1 = q_j$ ; cancele e repita. As duas fatorações coincidem termo a termo. ∎

Teorema 29.17 (Pequeno teorema de Fermat)

Seja $p$ primo e $a \in \Z$ com $p \nmid a$ . Então

a^{p-1} \equiv 1 \pmod p .

Para todo $a \in \Z$ (sem hipótese de coprimalidade), $a^p \equiv a \pmod p$ .

Demonstração. Considere os $p - 1$ inteiros $a, 2a, 3a, \dots, (p-1)a$ módulo $p$ . Nenhum é $\equiv 0$ (se $p \mid ka$ com $1 \leq k \leq p-1$ , o lema de Euclides obriga $p \mid k$ , o que é impossível), e eles são dois a dois distintos módulo $p$ (se $ka \equiv la$ , então $p \mid (k - l)a$ , logo $p \mid k - l$ , logo $k = l$ ). Assim, módulo $p$ , eles são os números $1, 2, \dots, p-1$ em alguma ordem. Multiplicando todas as congruências:

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

Como $p$ não divide nenhum entre $1, \dots, p-1$ , usar repetidamente o lema de Euclides permite cancelar $(p-1)!$ , restando $a^{p-1} \equiv 1$ . A segunda forma segue multiplicando por $a$ (e é trivial quando $p \mid a$ ). ∎

Exemplo 29.18 (Aplicação à criptografia)

O teorema de Fermat torna reversível a exponenciação módulo $n$ quando os expoentes são bem escolhidos — o coração do criptossistema RSA. Com $p, q$ primos grandes e $n = pq$ , publicam-se $n$ e um expoente $e$ ; a cifragem é $x \mapsto x^e \bmod n$ . Decifrar exige um expoente $d$ com $ed \equiv 1 \pmod{(p-1)(q-1)}$ , que só quem conhece $p$ e $q$ consegue calcular — e recuperar $p, q$ a partir de $n$ significa fatorar um número de centenas de algarismos, o que nenhum algoritmo conhecido faz em tempo razoável.

29.5 Exercícios

Exercício 29.1 ★

Calcule o quociente e o resto da divisão euclidiana de $2026$ por $17$ e de $-2026$ por $17$ .

Solução

Solução de Exercício 29.1.

$17 \times 119 = 2023$ , logo $2026 = 17 \times 119 + 3$ : quociente $119$ , resto $3$ . Para $-2026$ : $-2026 = 17\times(-120) + 14$ (de fato, $17 \times 120 = 2040$ e $2040 - 2026 = 14$ ): quociente $-120$ , resto $14$ (o resto tem de estar em $\intco{0}{17}$ , de modo que não é $-3$ ).

Exercício 29.2 ★

Qual é o resto de $7^{100}$ módulo $10$ ? (Qual é o último algarismo de $7^{100}$ ?)

Solução

Solução de Exercício 29.2.

Módulo $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . Logo $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : o último algarismo de $7^{100}$ é $1$ .

Exercício 29.3 ★

Usando o algoritmo de Euclides, calcule $\gcd(1071, 462)$ e encontre inteiros $u, v$ com $1071u + 462v = \gcd(1071, 462)$ .

Solução

Solução de Exercício 29.3.

Euclides: $1071 = 2\times462 + 147$ ; $462 = 3\times147 + 21$ ; $147 = 7\times21 + 0$ . Logo $\gcd = 21$ .

Substituindo de volta: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ . Assim, $u = -3$ , $v = 7$ : $1071\times(-3) + 462\times7 = 21$ .

Exercício 29.4 ★

Mostre que, para todo $n \in \Z$ , $n^2$ é congruente a $0$ ou $1$ módulo $4$ . Deduza que um inteiro $\equiv 3 \pmod 4$ nunca é soma de dois quadrados.

Solução

Solução de Exercício 29.4.

Todo inteiro é $\equiv 0, 1, 2$ ou $3 \pmod 4$ e, ao quadrado: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . Assim, $n^2 \equiv 0$ ou $1 \pmod 4$ . Uma soma de dois quadrados é, então, congruente a $0 + 0$ , $0 + 1$ ou $1 + 1$ , isto é, a $0$ , $1$ ou $2 \pmod 4$ — nunca a $3$ .

Exercício 29.5 ★★

Mostre que, para todo $n \in \N$ , $n(n+1)(2n+1)$ é divisível por $6$ .

Solução

Solução de Exercício 29.5.

Divisibilidade por $2$ : entre $n$ e $n + 1$ , um é par. Divisibilidade por $3$ : se $n \equiv 0$ , então $3 \mid n$ ; se $n \equiv 1 \pmod 3$ , então $2n + 1 \equiv 3 \equiv 0$ ; se $n \equiv 2$ , então $n + 1 \equiv 0$ . Em todos os casos $3$ divide o produto. Como $\gcd(2,3) = 1$ , o Corolário 29.12 dá $6 \mid n(n+1)(2n+1)$ . (Isso também redemonstra que $\frac{n(n+1)(2n+1)}{6}$ , a soma dos quadrados do Exercício 20.1, é um inteiro.)

Exercício 29.6 ★★

Resolva em $\Z$ a congruência $5x \equiv 3 \pmod{11}$ . (Sugestão: encontre o inverso de $5$ módulo $11$ .)

Solução

Solução de Exercício 29.6.

Procuramos o inverso de $5$ módulo $11$ : testando (ou por Bézout), $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ . Multiplicando a congruência por $9$ :

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

As soluções são os inteiros $x = 5 + 11k$ , $k \in \Z$ . (Verificação: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Exercício 29.7 ★★

Resolva em $\Z \times \Z$ a equação diofantina

17x - 40y = 1,

e descreva em seguida todas as soluções de $17x - 40y = 6$ .

Solução

Solução de Exercício 29.7.

$\gcd(17, 40) = 1$ , de modo que há soluções. Euclides: $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ . Substituindo de volta: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ . Logo $17\times(-7) - 40\times(-3) = 1$ : a solução particular $(x_0, y_0) = (-7, -3)$ .

Solução geral de $17x - 40y = 1$ : subtraindo a relação particular, $17(x + 7) = 40(y + 3)$ ; como $\gcd(17, 40) = 1$ , Gauss dá $40 \mid x + 7$ , logo $x = -7 + 40k$ e então $y = -3 + 17k$ , $k \in \Z$ (e todos esses valores servem).

Para $17x - 40y = 6$ , multiplique a solução particular por $6$ : $(x_1, y_1) = (-42, -18)$ , e o mesmo raciocínio dá

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(Por exemplo, $k = 2$ : $x = 38$ , $y = 16$ ; de fato, $17\times38 - 40\times16 = 646 - 640 = 6$ .)

Exercício 29.8 ★★

Mostre que $\sqrt2$ é irracional usando a unicidade da fatoração em primos (compare o expoente de $2$ nos dois lados de $a^2 = 2b^2$ ).

Solução

Solução de Exercício 29.8.

Suponha $\sqrt2 = \frac ab$ com $a, b \in \N^*$ ; então $a^2 = 2b^2$ . Na fatoração em primos de um quadrado, todo expoente é par; assim, o expoente de $2$ em $a^2$ é par, enquanto em $2b^2$ é ímpar (uma unidade a mais que um número par). Duas fatorações do mesmo inteiro com expoentes diferentes de $2$ contradizem a unicidade do Teorema 29.16. Logo não existe fração assim: $\sqrt2 \notin \Q$ .

Exercício 29.9 ★★★

Seja $p$ um primo.

Mostre que, para $1 \leq k \leq p - 1$ , $p$ divide $\dbinom{p}{k}$ . (Sugestão: use $k\binom pk = p\binom{p-1}{k-1}$ , Exercício 27.7, e o lema de Gauss.)
Deduza, por indução em $a \geq 0$ , outra demonstração do pequeno teorema de Fermat na forma $a^p \equiv a \pmod p$ .

Solução

Solução de Exercício 29.9.

1. De $k\binom pk = p \binom{p-1}{k-1}$ , $p$ divide $k\binom pk$ . Para $1 \leq k \leq p-1$ , $p \nmid k$ e $p$ primo dão $\gcd(p, k) = 1$ , de modo que o lema de Gauss dá $p \mid \binom pk$ .

2. Indução em $a$ . Para $a = 0$ : $0^p \equiv 0$ . Suponha $a^p \equiv a \pmod p$ . Pelo teorema binomial,

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

pois todos os termos do meio se anulam módulo $p$ pelo item 1. Pela hipótese de indução, $(a+1)^p \equiv a + 1 \pmod p$ . Isso demonstra $a^p \equiv a$ para todo $a \in \N$ , e o caso $a < 0$ segue escrevendo $a \equiv a + kp$ para um representante positivo adequado.

Exercício 29.10 ★★★

(Problema chinês dos restos.) Encontre todos os inteiros $n$ tais que

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(Sugestão: resolva as duas primeiras condições e incorpore a terceira; os coeficientes de Bézout ajudam.)

Solução

Solução de Exercício 29.10.

$n \equiv 2 \pmod 3$ e $n \equiv 3 \pmod 5$ : escreva $n = 2 + 3s$ ; então $2 + 3s \equiv 3 \pmod 5$ , isto é, $3s \equiv 1 \pmod 5$ . O inverso de $3$ módulo $5$ é $2$ ( $3\times2 = 6 \equiv 1$ ), logo $s \equiv 2 \pmod 5$ , digamos $s = 2 + 5t$ , e $n = 8 + 15t$ : as duas primeiras condições significam $n \equiv 8 \pmod{15}$ .

Acrescentando $n \equiv 2 \pmod 7$ : $8 + 15t \equiv 2 \pmod 7$ e $15 \equiv 1 \pmod 7$ , logo $t \equiv -6 \equiv 1 \pmod 7$ , digamos $t = 1 + 7u$ . Assim, $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(Verificação: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ .)

29.6 Problema: Códigos secretos e dígitos verificadores

Problema 29.1

Problema de fim de semana — as congruências protegem cada código de barras e cada cartão de crédito, e o pequeno teorema de Fermat opera a fechadura dos segredos do mundo

G. H. Hardy gabava-se, em 1940, de que a teoria dos números era “imaculada” por aplicações. Oitenta anos depois, cada bipe de código de barras, cada pagamento com cartão e cada mensagem cifrada o contradizem — e exatamente com as ferramentas deste capítulo: congruências (Proposição 29.5), inversos de Bézout (Teorema 29.10) e o pequeno teorema de Fermat (Exercício 29.9). Este problema confere os códigos, arromba uma versão de brinquedo da fechadura e aprende por que a fechadura verdadeira aguenta.

Parte I — Fluência com congruências.

Calcule $2026 \bmod 7$ ; depois o último algarismo de $7^{100}$ (encontre o ciclo das potências de $7$ módulo $10$ ).
Exponenciação rápida (Método 29.6): calcule $5^{117} \bmod 13$ (parta de $5^2 \equiv -1$ ).
Resolva $3x \equiv 5 \pmod 7$ .
Rode o algoritmo de Euclides em $(97, 35)$ , substitua de volta para achar inteiros $u, v$ com $97u + 35v = 1$ e deduza o inverso de $35$ módulo $97$ .
Enuncie com precisão quando $a$ é invertível módulo $n$ e qual teorema entrega o inverso.

Parte II — Dígitos verificadores.

ISBN-10: os dez algarismos $d_1 \dots d_{10}$ do código de um livro devem satisfazer $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . Verifique o ISBN real $0\,306\,40615\,2$ .
Demonstre que o esquema ISBN detecta todo erro em um único algarismo: se um algarismo muda de $d \not\equiv 0$ , a soma ponderada muda de $w d$ com $1 \leq w \leq 10$ — por que isso nunca pode ser $\equiv 0 \pmod{11}$ (Teorema 29.11)?
Demonstre que ele também detecta toda troca de dois algarismos adjacentes (distintos). Depois explique o segredo do projeto: que propriedade de $11$ fez as duas demonstrações funcionarem, e o que poderia dar errado com o módulo $10$ ?
Os códigos de barras EAN-13 ponderam os algarismos por $1, 3, 1, 3, \dots$ módulo $10$ . Calcule o dígito verificador que completa $978\,2940199\,05$ . Que trocas de algarismos adjacentes o EAN deixa de detectar? (Quando é $2(a - b) \equiv 0 \pmod{10}$ ?)
Os cartões de crédito usam o esquema de Luhn: da direita para a esquerda, dobre um algarismo sim, outro não (subtraindo $9$ quando o dobro passa de $9$ ), some tudo e exija um múltiplo de $10$ . Verifique o número de teste $4539\,1488\,0343\,6467$ .
Em uma frase: o que o módulo primo comprou para o ISBN e que o EAN e o Luhn, presos ao $10$ , não podem ter?

Parte III — A fechadura de Fermat.

Uma armadilha antes do tesouro: calcule $2^{10} \bmod 341$ , deduza $2^{340} \bmod 341$ — e depois fatore $341$ . O que esse exemplo (um pseudoprimo de Fermat) diz sobre usar o pequeno teorema de Fermat como teste de primalidade?
RSA em miniatura: tome $p = 3$ , $q = 11$ , de modo que $n = 33$ e $(p-1)(q-1) = 20$ ; o expoente público é $e = 3$ . Encontre o expoente privado $d$ com $3d \equiv 1 \pmod{20}$ (o método da questão 4).
Cifre a mensagem $m = 4$ : calcule $c = m^3 \bmod 33$ .
Decifre: calcule $c^d \bmod 33$ (use $c \equiv -2 \pmod{33}$ ) e recupere a mensagem.
Por que a decifragem sempre funciona: mostre que $m^{21} \equiv m$ tanto módulo $3$ quanto módulo $11$ (o pequeno teorema de Fermat em cada mundo) e conclua módulo $33$ (o Teorema 29.11 cola as duas congruências). Onde entrou a forma especial $1 + 20k$ de $21 = ed$ ?
A segurança da fechadura: todo mundo conhece $n$ e $e$ ; recuperar $d$ exige $(p-1)(q-1)$ e, portanto, os fatores de $n$ . Nosso $33$ se fatora à primeira vista — por que o mesmo esquema, com $n$ de seiscentos algarismos, protege os bancos do mundo? (Uma frase sobre a assimetria entre multiplicar e fatorar.)

Parte IV — Clássicos.

A antiga contagem chinesa de soldados (compare com o Exercício 29.10): um contingente deixa resto $2$ quando enfileirado de $3$ em $3$ e resto $3$ quando enfileirado de $5$ em $5$ . Encontre todos os efetivos possíveis e explique por que a resposta é única módulo $15$ .
Demonstrações de uma linha, enfim: de $10 \equiv 1 \pmod 9$ , demonstre que todo número é congruente à soma de seus algarismos módulo $9$ ; de $10 \equiv -1 \pmod{11}$ , deduza a regra da soma alternada para o $11$ . (O volume do ensino fundamental demonstrou isso com álgebra explícita — admire a compressão.)
Final — Hardy contra o código de barras: recapitule a caixa de ferramentas do capítulo (aritmética das congruências, inversos de Bézout, pequeno teorema de Fermat, colagem de módulos primos entre si) e onde cada uma se encaixou neste problema; depois dê o veredicto moderno sobre o “imaculada”.

Solução

Solução de Problema 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ . Potências de $7$ módulo $10$ : $7, 9, 3, 1$ , ciclo de comprimento $4$ ; $100 \equiv 0 \pmod 4$ : o último algarismo de $7^{100}$ é $1$ .

2. $5^2 = 25 \equiv -1 \pmod{13}$ , logo $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ e $5^{117} \equiv 5 \pmod{13}$ .

3. O inverso de $3$ módulo $7$ é $5$ ( $15 \equiv 1$ ): $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ .

4. $97 = 2 \times 35 + 27$ ; $35 = 27 + 8$ ; $27 = 3 \times 8 + 3$ ; $8 = 2 \times 3 + 2$ ; $3 = 2 + 1$ . Substituindo de volta: $1 = 97 \times 13 + 35 \times (-36)$ . Assim, $35 \times (-36) \equiv 1 \pmod{97}$ : o inverso de $35$ é $-36 \equiv 61 \pmod{97}$ .

5. $a$ é invertível módulo $n$ exatamente quando $\gcd(a, n) = 1$ : Bézout fornece $au + nv = 1$ , isto é, $au \equiv 1$ ; reciprocamente, um inverso obriga o mdc a dividir $1$ .

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : válido.

7. A soma muda de $wd$ com $1 \leq w \leq 10$ e $1 \leq \abs d \leq 9$ : como $11$ é primo e não divide nenhum dos fatores, ele não pode dividir o produto (Teorema 29.11 e Proposição 29.14): a soma alterada nunca volta a ser $\equiv 0$ : todo erro em um único algarismo dispara o alarme.

8. Trocar algarismos adjacentes $a, b$ (pesos $w + 1, w$ ) muda a soma de $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ para $a \neq b$ : detectado. O segredo é a primalidade de $11$ : módulo $10$ , produtos como $5 \times 2$ se anulam sem que nenhum fator seja nulo, de modo que um erro de peso $5$ e tamanho $\pm 2$ (ou uma troca azarada) poderia passar despercebido.

9. Soma ponderada dos doze algarismos: $119$ ; o dígito verificador tem de completá-la até um múltiplo de $10$ : $1$ (código completo $978\,2940199\,051$ ). O EAN deixa passar as trocas adjacentes com $2(a - b) \equiv 0 \pmod{10}$ , isto é, $\abs{a - b} = 5$ : trocar um $2$ por um $7$ , digamos, passa invisível — o preço do simpático módulo $10$ .

10. Dobrando um algarismo sim, outro não a partir da direita e dobrando os resultados ( $16 \to 7$ etc.), a soma dá $80 \equiv 0 \pmod{10}$ : o cartão de teste é validado.

11. Com um módulo primo todo peso é invertível, de modo que todos os erros simples e todas as trocas adjacentes são apanhados — o luxo do ISBN; os esquemas módulo $10$ mantêm algarismos amigáveis e aceitam um pequeno ponto cego.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , logo $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . E, no entanto, $341 = 11 \times 31$ é composto: ele passa no teste de Fermat na base $2$ sem ser primo. Moral: a congruência de Fermat é necessária, não suficiente — testar primalidade exige ferramentas mais afiadas (e as recebe, nos volumes de graduação).

13. $3d \equiv 1 \pmod{20}$ : $d = 7$ ( $21 = 20 + 1$ ).

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ .

15. $31 \equiv -2$ : $(-2)^7 = -128$ , e $-128 + 4 \times 33 = 4$ : o texto cifrado decifra para $m = 4$ . A fechadura gira.

16. Módulo $3$ : se $3 \nmid m$ , então $m^2 \equiv 1$ (Fermat), logo $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; se $3 \mid m$ , os dois lados são $\equiv 0$ . Módulo $11$ : $m^{10} \equiv 1$ ou $11 \mid m$ , e $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . Tanto $3$ quanto $11$ dividem $m^{21} - m$ e, sendo primos entre si, o produto $33$ também divide (Gauss): $m^{21} \equiv m \pmod{33}$ . O expoente $ed = 21 = 1 + 20k$ foi construído para que os dois expoentes de Fermat ( $2$ e $10$ , divisores de $20$ ) desaparecessem.

17. Multiplicar dois primos de $300$ algarismos leva um microssegundo; recuperá-los a partir do produto derrota todo algoritmo conhecido e todos os computadores do mundo — a fechadura é uma via de mão única. (Nosso $n = 33$ é a rua em escala de brinquedo, caminhável nos dois sentidos.)

18. Testando restos (ou construindo com Bézout): $n \equiv 8 \pmod{15}$ : os efetivos $8, 23, 38, 53, \dots$ Unicidade módulo $15$ : duas soluções diferem por um múltiplo de $3$ e de $5$ , logo de $15$ ( $3$ e $5$ primos entre si, Gauss). O general com $1000$ soldados anuncia “ $8$ ” com três enfileiramentos rápidos — o antigo truque da contagem de tropa.

19. $10 \equiv 1 \pmod 9$ dá $10^k \equiv 1$ , logo $\sum d_k 10^k \equiv \sum d_k$ : um número e a soma de seus algarismos são congruentes módulo $9$ (e módulo $3$ ). E $10 \equiv -1 \pmod{11}$ dá $\sum d_k 10^k \equiv \sum (-1)^k d_k$ : a regra alternada. Duas regras da infância, uma linha cada.

20. As congruências transformaram restos em uma aritmética (Parte I); Bézout cunhou os inversos que resolvem congruências lineares e o $d$ do RSA (questões 4 e 13); o pequeno teorema de Fermat abriu e fechou a fechadura (questões 15–16); colar módulos primos entre si contou soldados e concluiu a demonstração (questões 16 e 18). Veredicto sobre Hardy: o mais puro teorema que ele conhecia hoje protege cada compra — a pureza, dado tempo, é a coisa mais aplicável que existe.