---
title: "Aritmética"
book: "Matemática do ensino médio"
subject: math
language: pt
chapter: 29
exercises: 10
source: https://one-course.com/books/math/2/pt/chapter/29-aritmetica
---

# Capítulo 29 — Aritmética

A aritmética estuda os inteiros: [divisibilidade](#def-g12-arith-divides), [números primos](#def-g12-arith-prime), 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](#def-g12-arith-divides) 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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-bounded) 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](#thm-g12-arith-euclid) 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](#def-g12-arith-divides) $(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 nnn).**

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](#def-g12-arith-divides) $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](#thm-g12-arith-euclid), portanto, calcula $\gcd(a,b)$: o [mdc](#def-g12-arith-gcd) é o último resto não nulo.

**Demonstração.** Todo divisor comum de $a$ e $b$ [divide](#def-g12-arith-divides) $r = a - bq$ ([Proposição 29.2](#prop-g12-arith-divprops)) 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](#def-g12-arith-gcd). O algoritmo termina porque os restos formam uma [sequência](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) estritamente [decrescente](https://one-course.com/books/math/2/pt/chapter/3-funcoes#def-g10-functions-variations) 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](#def-g12-arith-gcd) se, e somente se, $au + bv = 1$ para alguns inteiros $u, v$.

**Demonstração.** Percorra o [algoritmo de Euclides](#prop-g12-arith-euclidalgo) 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](#ex-g12-arith-euclidalgo): $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](#def-g12-arith-divides) $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](#def-g12-arith-prime); se $n$ não é [primo](#def-g12-arith-prime), ele tem um divisor [primo](#def-g12-arith-prime) $\leq \sqrt n$. Se um [primo](#def-g12-arith-prime) $p$ [divide](#def-g12-arith-divides) 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](#def-g12-arith-prime) (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](#def-g12-arith-prime).

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

**Teorema 29.16 (Teorema fundamental da aritmética).**

Todo inteiro $n \geq 2$ é produto de [primos](#def-g12-arith-prime), 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](#def-g12-arith-prime), 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](#def-g12-arith-prime), com repetições permitidas). Pelo lema de Euclides, $p_1$ [divide](#def-g12-arith-divides) algum $q_j$ e, sendo [primo](#def-g12-arith-prime), $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](#def-g12-arith-prime) 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](#def-g12-arith-congruence):

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

Como $p$ não [divide](#def-g12-arith-divides) 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](#def-g12-arith-prime) 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](https://one-course.com/books/math/2/pt/chapter/2-algebra-equacoes-e-inequacoes#def-g10-algebra-expand) 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](#thm-g12-arith-euclid) de $2026$ por $17$ e de $-2026$ por $17$.

**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 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](#prop-g12-arith-euclidalgo), calcule $\gcd(1071, 462)$ e encontre inteiros $u, v$ com $1071u + 462v = \gcd(1071, 462)$.

**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 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 de Exercício 29.5.**

[Divisibilidade](#def-g12-arith-divides) por $2$: entre $n$ e $n + 1$, um é par. [Divisibilidade](#def-g12-arith-divides) 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](#def-g12-arith-divides) o produto. Como $\gcd(2,3) = 1$, o [Corolário 29.12](#cor-g12-arith-coprimeprod) 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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#exo-g12-seq-1), é um inteiro.)

**Exercício 29.6 ★★.**

Resolva em $\Z$ a [congruência](#def-g12-arith-congruence) $5x \equiv 3 \pmod{11}$. (Sugestão: encontre o inverso de $5$ módulo $11$.)

**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](#def-g12-arith-congruence) 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](https://one-course.com/books/math/2/pt/chapter/2-algebra-equacoes-e-inequacoes#def-g10-algebra-equation) diofantina

$$
17x - 40y = 1,
$$

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

**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](#def-g12-arith-prime) (compare o expoente de $2$ nos dois lados de $a^2 = 2b^2$).

**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](#def-g12-arith-prime) 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](#thm-g12-arith-fta). Logo não existe fração assim: $\sqrt2 \notin \Q$.

**Exercício 29.9 ★★★.**

Seja $p$ um [primo](#def-g12-arith-prime).

1. Mostre que, para $1 \leq k \leq p - 1$ , $p$ [divide](#def-g12-arith-divides) $\dbinom{p}{k}$ . (Sugestão: use $k\binom pk = p\binom{p-1}{k-1}$ , [Exercício 27.7](https://one-course.com/books/math/2/pt/chapter/27-analise-combinatoria-e-contagem#exo-g12-comb-7) , e o lema de Gauss.)
2. 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 de Exercício 29.9.**

*1.* De $k\binom pk = p \binom{p-1}{k-1}$, $p$ [divide](#def-g12-arith-divides) $k\binom pk$. Para $1 \leq k \leq p-1$, $p \nmid k$ e $p$ [primo](#def-g12-arith-prime) 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 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](#def-g12-arith-congruence) ([Proposição 29.5](#prop-g12-arith-congops)), inversos de Bézout ([Teorema 29.10](#thm-g12-arith-bezout)) e o pequeno teorema de Fermat ([Exercício 29.9](#exo-g12-arith-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](#def-g12-arith-congruence).**

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

**Parte II — Dígitos verificadores.**

6. 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$ .
7. 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](#thm-g12-arith-gauss) )?
8. 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$ ?
9. 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}$ ?)
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$ .
11. 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.**

12. 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?
13. 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).
14. Cifre a mensagem $m = 4$ : calcule $c = m^3 \bmod 33$ .
15. Decifre: calcule $c^d \bmod 33$ (use $c \equiv -2 \pmod{33}$ ) e recupere a mensagem.
16. 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](#thm-g12-arith-gauss) cola as duas [congruências](#def-g12-arith-congruence) ). Onde entrou a forma especial $1 + 20k$ de $21 = ed$ ?
17. 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](https://one-course.com/books/math/2/pt/chapter/2-algebra-equacoes-e-inequacoes#def-g10-algebra-expand) .)

**Parte IV — Clássicos.**

18. A antiga contagem chinesa de soldados (compare com o [Exercício 29.10](#exo-g12-arith-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$ .
19. 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.)
20. Final — Hardy contra o código de barras: recapitule a caixa de ferramentas do capítulo (aritmética das [congruências](#def-g12-arith-congruence) , 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 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](#def-g12-arith-gcd) 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](#def-g12-arith-prime) e não [divide](#def-g12-arith-divides) nenhum dos fatores, ele não pode dividir o produto ([Teorema 29.11](#thm-g12-arith-gauss) e [Proposição 29.14](#prop-g12-arith-primedivides)): 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](#def-g12-arith-prime). Moral: a [congruência](#def-g12-arith-congruence) 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](#def-g12-arith-gcd), o produto $33$ também [divide](#def-g12-arith-divides) (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](#def-g12-arith-prime) 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](#def-g12-arith-gcd), 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](#def-g12-arith-congruence) transformaram restos em uma aritmética (Parte I); Bézout cunhou os inversos que resolvem [congruências](#def-g12-arith-congruence) 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.