Divisibilidade

A divisibilidade é o verdadeiro ponto de partida da teoria dos números porque transforma os inteiros em um sistema com estrutura: você deixa de olhar os números como “quantidades” e passa a vê-los como peças que se encaixam ou não entre si. Com uma única estrutura, a\mid b, é possível expressar desde critérios de simplificação e fatoração até o núcleo de alguns procedimentos, como o algoritmo de Euclides, que permite calcular máximos divisores comuns em segundos, mesmo com números grandes. Além disso, ela constitui a base técnica de ideias que aparecem repetidamente na matemática aplicada e na computação: congruências, aritmética modular, validações, códigos e (mais adiante) criptografia. Dominar a divisibilidade é, em essência, aprender a detectar padrões invisíveis nos inteiros e a convertê-los em procedimentos que funcionam sempre.

Objetivos de Aprendizagem
Ao final deste apunte, o estudante será capaz de:

1. Compreender a relação de divisibilidade entre números inteiros.
2. Compreender a definição de divisibilidade e suas propriedades.
3. Desenvolver demonstrações matemáticas de resultados e teoremas relacionados à divisibilidade.

ÍNDICE DE CONTEÚDOS
Definição de divisibilidade
Propriedades fundamentais da divisibilidade
Exercícios Propostos

Definição de divisibilidade

A ideia informal de “a divide b” torna-se precisa quando a expressamos como uma relação entre inteiros. Diremos que um inteiro a divide um inteiro b se b pode ser escrito como um múltiplo exato de a. Essa definição é a base do restante do apunte, pois transforma frases do tipo “encaixa exatamente” em um critério verificável.

Definição. Sejam a,b\in\mathbb{Z} com a\neq 0. Dizemos que a divide b, e escrevemos a\mid b, se e somente se existe um inteiro k\in\mathbb{Z} tal que b=ka. Caso contrário, escrevemos a\nmid b.

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

Nessa definição, o número k é chamado de quociente (ou fator) associado à divisibilidade. Por exemplo, afirmar 6\mid 42 equivale a afirmar que existe k\in\mathbb{Z} tal que 42=6k; nesse caso, basta tomar k=7.

É importante considerar

• A condição a\neq 0 é essencial, pois, se tentássemos permitir a=0, a condição de divisibilidade exigiria que existisse k\in\mathbb{Z} tal que b=0\cdot k. Contudo, 0\cdot k=0 para todo k, de modo que a única possibilidade seria b=0. Nesse caso, não haveria um k “determinado” pela relação, já que qualquer k\in\mathbb{Z} satisfaz 0=0\cdot k. Em outras palavras, a expressão informal k=b/a torna-se k=0/0, o que não está definido. Para evitar essa degeneração (em que a noção de quociente deixa de ser significativa), exige-se a\neq 0. Por esse motivo, a relação 0\mid b não é considerada válida.
• Em contrapartida, a\mid 0 é verdadeiro para todo a\in\mathbb{Z} com a\neq 0, pois basta tomar k=0 e tem-se 0=a\cdot 0.

A partir dessa definição, decorre uma equivalência que utilizaremos de forma recorrente: dizer que a\mid b é o mesmo que dizer que b pertence ao conjunto dos múltiplos inteiros de a, isto é, b\in a\mathbb{Z}, onde a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}. Essa forma de escrita enfatiza que a divisibilidade não é um “truque”, mas uma maneira de descrever subconjuntos altamente estruturados dentro de \mathbb{Z}.

Propriedades fundamentais da divisibilidade

• Reflexividade: a\mid a.
  Demonstração:

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Neutro multiplicativo em $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Int. existencial (1)}\\ (3) &\vdash a \mid a &\text{; Def. de divisibilidade (2)} \\ &\blacksquare & \end{array}

• Transitividade: se a\mid b e b\mid c, então a\mid c.

  Demonstração:

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Def. de divisibilidade, presunção}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Def. de divisibilidade, presunção}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-compactação (1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; De (3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; De (4)}\\ &\text{Álgebra dentro do quantificador}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; De (5)}\\ &\text{Fechamento de $\mathbb{Z}$ para a multiplicação}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Def. de divisibilidade (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD (7)}\\ &\blacksquare& \end{array}

• Compatibilidade com soma e subtração: se a\mid b e a\mid c, então a\mid (b+c) e a\mid (b-c).
  Demonstração:

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Def. de divisibilidade, presunção}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Def. de divisibilidade, presunção}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-compactação (1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; De (3)}\\ &\text{Álgebra dentro do quantificador.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; De (4)}\\ &\text{Fechamento de $\mathbb{Z}$ para a soma.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Def. de divisibilidade (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD (6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; De (3)}\\ &\text{Álgebra dentro do quantificador.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; De (8)}\\ &\text{Fechamento de $\mathbb{Z}$ para a subtração.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Def. de divisibilidade (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD (10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{; $\wedge$-int. no consequente (7,11) }\\ &\blacksquare& \end{array}

• Compatibilidade com produtos: se a\mid b, então a\mid (bc) para todo c\in\mathbb{Z}.
  Demonstração:

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Def. de divisibilidade, presunção}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; De (1), $\forall$-int. (c arbitrário)}\\ &\text{Álgebra em }\mathbb{Z}\text{ dentro do quantificador existencial.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; De (2), fechamento: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Def. de divisibilidade (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD (4)}\\ &\blacksquare& \end{array}

Teorema: cota do divisor

Se b\neq 0 e a\mid b, então |a|\le |b|.

Demonstração:

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Presunção} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Def. de divisibilidade, presunção} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Prop. do valor absoluto, De (2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; De (1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; De (4), se }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; De (5)} \\ &\blacksquare& \end{array}

Exercícios Propostos

1. Mostre que o teorema “cota do divisor” não é necessariamente verdadeiro se b=0
2. Consideremos um conjunto A e uma relação \rho sobre esse conjunto. Se os elementos x,y\in A forem tais que x está relacionado com y por meio de \rho, então escreve-se x\rho y. Diz-se que a relação \rho é de ordem parcial sobre A se:

   a)(\forall x\in A) (x\rho x),
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).

   Demonstre que a relação de divisibilidade é uma relação de ordem parcial sobre os números inteiros.

3. Prove por indução que, se a\mid b_1, a\mid b_2, \cdots, a\mid b_n, então a\mid \sum_{i=1}^n b_i x_i para qualquer conjunto \{x_i\}_{i=1}^n \subset \mathbb{Z}. Além disso, prove que, se a\mid b_i, com i\in \{1,2,3,\cdots, n\} e c pode ser escrito como uma combinação linear desses b_i, então a\mid c.
4. Se a\neq 0, mostre que o conjunto \{x\;:\; d\mid a\} é um conjunto finito.
5. Considere um n\in\mathbb{Z}^+ fixo, e seja

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   Prove:

   1. d\in S \leftrightarrow n/d\in S
   2. Se os elementos de S forem colocados em ordem crescente: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n, então os elementos correspondentes n\mid d_i com i \in \{1,2,\cdots, t\} estão em ordem decrescente.
6. Suponha que a,b\in\mathbb{Z}^+ e ab=c. Demonstre que \min\{a,b\}\le \sqrt{c}.
7. Um inteiro n diz-se par se 2\mid n, e ímpar se 2\nmid n. Demonstre que a soma e a diferença de:
   1. dois pares é um número par.
   2. dois ímpares é um número par.
   3. de um par e um ímpar é um número ímpar.
8. Se n é um ímpar distinto de \pm 1, prove que n não pode dividir dois pares consecutivos.
9. Sejam a,b,n\in\mathbb{Z} tais que |a-b|\lt |n|. Prove que n não pode dividir nem a nem b.
10. Suponha que a\in\mathbb{Z}. Prove que:
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. Sejam a,b,c\in\mathbb{Z} e suponhamos que c\neq 0. Mostre que ac\mid bc implica que a\mid b