Inteiros e congruências

Saber que $6\mid42$ significa que existe um inteiro $q$ com $42=6q$; aqui, $q=7$. Escrever a igualdade torna o quociente disponível para as contas de uma prova. Este padrão de exibir a testemunha repete-se em Bézout e nas congruências abaixo.

Divisão e divisibilidade

Para $a,b\in\mathbb Z$ com $b\ne0$, existem inteiros únicos $q,r$ tais que:

$$a=bq+r,\qquad 0\le r<|b|.$$

O resto é não negativo, mesmo que o dividendo seja negativo. Por exemplo, $-19=(-5)\cdot4+1$. Com divisor negativo, $19=(-4)\cdot(-4)+3$.

A unicidade vem do limite do resto. Se $a=bq+r=bs+t$, então $b(q-s)=t-r$. Como $|t-r|<|b|$, esse múltiplo de $b$ só pode ser zero. Assim, $q=s$ e $r=t$.

Nesta cadeira, $b\mid a$ usa um divisor $b\ne0$ e significa que $a=bq$ para algum $q\in\mathbb Z$. Não é uma fração. Todo o inteiro não nulo divide zero, pois $0=b\cdot0$. Não usamos zero como divisor.

Se $d\mid a$ e $d\mid b$, então $d$ divide qualquer combinação linear inteira $ua+vb$. De facto, para $a=dk$ e $b=d\ell$:

$$ua+vb=d(uk+v\ell),$$

com $uk+v\ell\in\mathbb Z$. Os coeficientes podem ser negativos. Exigir coeficientes naturais seria outra condição.

Primos e fatorização

Um inteiro positivo $p>1$ é primo se os seus únicos divisores positivos são $1$ e $p$. Um inteiro maior do que 1 que não é primo é composto. O 1 não é primo nem composto.

Todo o inteiro positivo maior do que 1 tem uma fatorização em primos, única salvo a ordem dos fatores. Por exemplo:

$$180=2^2\cdot3^2\cdot5,\qquad 168=2^3\cdot3\cdot7.$$

O mdc é o maior divisor positivo comum. O mínimo múltiplo comum, mmc, é o menor inteiro positivo múltiplo de ambos. Na fatorização dos dois números, o menor expoente de cada primo dá o mdc; o maior dá o mmc:

$$\gcd(180,168)=2^2\cdot3=12, \qquad \operatorname{mmc}(180,168)=2^3\cdot3^2\cdot5\cdot7=2520.$$

Para $a,b>0$, $\gcd(a,b)\operatorname{mmc}(a,b)=ab$, porque somar o mínimo e o máximo dos dois expoentes dá a sua soma.

Há infinitos primos. Se houvesse só $p_1,\ldots,p_k$, o número $p_1\cdots p_k+1>1$ teria um divisor primo. Nenhum dos primos da lista o divide, porque deixaria resto 1. Não precisamos de afirmar que esse número é primo, apenas que tem um divisor primo fora da lista.

Máximo divisor comum e Euclides

O máximo divisor comum é o maior divisor positivo comum. Usamos a notação $\gcd(a,b)$ ou $\operatorname{mdc}(a,b)$. Para um dos valores zero, $\gcd(a,0)=|a|$ se $a\ne0$. Excluímos o par $(0,0)$ da definição como maior divisor, porque todos os inteiros positivos dividem ambos.

Se $a=bq+r$, os divisores comuns de $a,b$ são os mesmos de $b,r$:

• Quem divide $a$ e $b$ divide $r=a-bq$.
• Quem divide $b$ e $r$ divide $a=bq+r$.

Logo, $\gcd(a,b)=\gcd(b,r)$. O algoritmo de Euclides repete esta transformação até o resto ser zero. Os restos não negativos diminuem estritamente, por isso o processo termina.

Para $\gcd(252,198)$, registamos o par que fica para a divisão seguinte:

$$\begin{aligned} 252&=1\cdot198+54,\\ 198&=3\cdot54+36,\\ 54&=1\cdot36+18,\\ 36&=2\cdot18+0. \end{aligned}$$

O último resto não nulo é $18$, o mdc. Dois inteiros são primos entre si quando o seu mdc é 1.

Ao chegar a $(18,0)$, aplicamos $\gcd(18,0)=18$. Os quocientes não são o resultado; servem para obter os restos e, a seguir, os coeficientes de Bézout. Cada linha acima já mostra o par seguinte: $(252,198)$ passa a $(198,54)$, depois $(54,36)$, $(36,18)$ e $(18,0)$, sempre com o mesmo mdc.

Identidade de Bézout

Para inteiros $a,b$ não ambos zero, existem $u,v\in\mathbb Z$ com:

$$\gcd(a,b)=ua+vb.$$

Podemos encontrá-los retrocedendo nas divisões de Euclides:

$$\begin{aligned} 18&=54-36\\ &=54-(198-3\cdot54)\\ &=4\cdot54-198\\ &=4(252-198)-198\\ &=4\cdot252-5\cdot198. \end{aligned}$$

Confere no fim: $1008-990=18$. Um erro de sinal num passo pode conservar o mdc e estragar os coeficientes.

Provar que dois valores são primos entre si

Considera $3k+2$ e $5k+3$, com $k\in\mathbb Z$. Qualquer divisor comum divide:

$$5(3k+2)-3(5k+3)=1.$$

Assim, o único divisor positivo comum é 1. Este argumento prova a afirmação para todos os $k$, sem calcular um mdc para cada caso.

O lema de Euclides diz que, se $p$ é primo e $p\mid ab$, então $p\mid a$ ou $p\mid b$. Se $p\nmid a$, temos $\gcd(p,a)=1$. Por Bézout, $1=up+va$; multiplicando por $b$, $b=upb+vab$, que é divisível por $p$. A hipótese “primo” é necessária: $6\mid2\cdot3$, mas $6$ não divide nenhum dos fatores.

Equações com soluções inteiras

Bézout também permite decidir se $ax+by=c$ tem soluções inteiras. Para $a,b>0$ e $d=\gcd(a,b)$, há solução se e só se $d\mid c$. A necessidade vem de $d$ dividir qualquer combinação. Para a suficiência, multiplicamos uma identidade $d=ua+vb$ por $c/d$.

Por exemplo, $\gcd(18,30)=6$ e $6=2\cdot18-30$. Logo $(x,y)=(2,-1)$ resolve $18x+30y=6$. Não há solução em naturais: com $x,y\ge0$, a soma ou é zero ou vale pelo menos 18. Solução inteira não significa solução não negativa.

Para encontrar todas as soluções inteiras, comparamos uma solução qualquer com a conhecida:

$$18(x-2)+30(y+1)=0 \quad\Longleftrightarrow\quad 3(x-2)=-5(y+1).$$

Como 3 e 5 são primos entre si, $5\mid(x-2)$. Escrevemos $x=2+5t$ e obtemos $y=-1-3t$, com $t\in\mathbb Z$. Substituir dá sempre 6, e a comparação mostra que nenhuma solução ficou de fora.

Em geral, a partir de uma solução $(x_0,y_0)$, todas as soluções são

$$x=x_0+\frac bd t,\qquad y=y_0-\frac ad t,\qquad t\in\mathbb Z.$$

Uma restrição a naturais acrescenta $x\ge0,y\ge0$ a este parâmetro. Tem de ser conferida depois de resolver em inteiros.

Congruências e operações

Para um módulo $m>0$:

$$a\equiv_m b \quad\Longleftrightarrow\quad m\mid(a-b).$$

Também se escreve $a\equiv b\pmod m$. Isto equivale a ter o mesmo resto na divisão por $m$. Por exemplo, $-1\equiv_7 6$.

Podemos somar, subtrair e multiplicar congruências do mesmo módulo. Se $a-b=mk$ e $c-d=m\ell$, então:

$$ac-bd=(a-b)c+b(c-d)=m(kc+b\ell).$$

Por isso, $a\equiv_m b$ e $c\equiv_m d$ implicam $ac\equiv_m bd$. Reduzir valores intermédios evita números grandes sem mudar o resto final.

$\mathbb Z_m$ pode representar-se por $\{0,1,\ldots,m-1\}$ com as operações seguidas da redução módulo $m$. Igualdade entre representantes e congruência entre inteiros são conceitos diferentes: $8\ne1$, mas $8\equiv_7 1$.

Cancelar e inverter

Não podemos cancelar um fator qualquer. $2\cdot2\equiv_6 2\cdot5$, mas $2\not\equiv_6 5$.

Se $\gcd(c,m)=1$, Bézout dá $uc+vm=1$, logo $uc\equiv_m1$. O valor $u$ é um inverso multiplicativo de $c$. Multiplicar por esse inverso permite cancelar $c$.

Por exemplo, $3\cdot5=15\equiv_7 1$, por isso 5 é o inverso de 3 módulo 7. De $3x\equiv_7 4$ obtemos $x\equiv_7 5\cdot4\equiv_7 6$. Confirmamos $3\cdot6=18\equiv_7 4$.

Mesmo sem inverso, podemos cancelar mudando o módulo. Se $d=\gcd(c,m)$:

$$ca\equiv_m cb\quad\Longleftrightarrow\quad a\equiv_{m/d}b.$$

De $m\mid c(a-b)$, dividimos por $d$. Como $c/d$ e $m/d$ são primos entre si, Bézout permite cancelar $c/d$ e concluir $(m/d)\mid(a-b)$. A recíproca vem de multiplicar por $c$.

No exemplo com fator 2 e módulo 6, obtemos $2\equiv_3 5$, não uma congruência módulo 6.

Um inverso existe se e só se o número e o módulo são primos entre si. Em módulo primo $p$, todos os representantes não nulos têm inverso. Para $m>1$, o zero não tem inverso.

Resolver congruências lineares

Para $ax\equiv_m b$, calcula $d=\gcd(a,m)$. A congruência tem solução se e só se $d\mid b$:

• Uma solução dá $ax-mq=b$; como $d$ divide $a$ e $m$, tem de dividir $b$.
• Se $d\mid b$, escreve Bézout como $d=ua+vm$. Multiplica por $b/d$: $b=a(u b/d)+m(v b/d)$. Os coeficientes são inteiros, logo $x=u b/d$ é uma solução.

Se há solução, dividimos $a,b,m$ por $d$. A congruência reduzida tem coeficiente invertível e uma classe de soluções módulo $m/d$. No módulo original há $d$ classes distintas.

Para $6x\equiv_{14}8$, temos $d=2$, que divide 8. Reduzimos:

$$3x\equiv_7 4\quad\Longrightarrow\quad x\equiv_7 6.$$

Em $\mathbb Z_{14}$, as soluções são $6$ e $13$. Conferindo, $36$ e $78$ deixam resto 8 módulo 14. Já $6x\equiv_{14}9$ não tem solução, porque 2 não divide 9.

Não mantenhas o módulo 14 depois de dividir os dois membros por 2. A redução também divide o módulo.

Pequeno teorema de Fermat

Se $p$ é primo e $p\nmid a$:

$$a^{p-1}\equiv_p1.$$

Multiplicar os representantes $1,\ldots,p-1$ por $a$ permuta as classes não nulas, porque $a$ é invertível. O produto dessas classes é, portanto, o mesmo. Cancelando $(p-1)!$, que também é invertível, obtemos o resultado.

Para calcular $3^{100}\bmod7$, usamos $3^6\equiv_7 1$ e $100=16\cdot6+4$. Assim:

$$3^{100}\equiv_7 3^4=81\equiv_7 4.$$

Fermat também dá $a^{-1}\equiv_p a^{p-2}$ quando $a$ não é múltiplo de $p$. Não uses a fórmula num módulo composto sem outra justificação.