Ir ao conteúdo principal

Seção 2.2 O Algoritmo de Divisão

Uma aplicação do Princípio da Bem-Ordem que usaremos frequentemente é o algoritmo de divisão.

Este é um exemplo perfeito de uma demonstração de existência e unicidade. Devemos primeiro demonstrar que os números \(q\) e \(r\) realmente existem. Depois devemos mostrar que se \(q'\) e \(r'\) também são tais números, então \(q = q'\) e \(r = r'\text{.}\)

Existência de \(q\) e \(r\text{.}\) Seja

\begin{equation*} S = \{ a - bk : k \in {\mathbb Z} \text{ e } a - bk \geq 0 \}. \end{equation*}

Se \(0 \in S\text{,}\) então \(b\) divide a \(a\text{,}\) e podemos tomar \(q = a/b\) e \(r = 0\text{.}\) Se \(0 \notin S\text{,}\) podemos usar o Princípio da Bem-Ordem. Devemos primeiro mostrar que \(S\) é não vazio. Se \(a \gt 0\text{,}\) então \(a - b \cdot 0 \in S\text{.}\) Se \(a \lt 0\text{,}\) então \(a - b(2a) = a(1 - 2b) \in S\text{.}\) Em qualquer caso \(S \neq \emptyset\text{.}\) Pelo Princípio da Bem-Ordem, \(S\) tem um elemento mínimo, digamos \(r = a - bq\text{.}\) Portanto, \(a = bq + r\text{,}\) \(r \geq 0\text{.}\) Mostremos agora que \(r \lt b\text{.}\) Suponhamos que \(r \gt b\text{.}\) Então

\begin{equation*} a - b(q + 1)= a - bq - b = r - b \gt 0. \end{equation*}

Neste caso teríamos \(a - b(q + 1)\) no conjunto \(S\text{.}\) Mas então \(a - b(q + 1) \lt a - bq\text{,}\) o que nos levaria a uma contradição do fato que \(r = a - bq\) é o menor elemento de \(S\text{.}\) Assim \(r \leq b\text{.}\) Como \(0 \notin S\text{,}\) \(r \neq b\) e assim \(r \lt b\text{.}\)

Unicidade de \(q\) e \(r\text{.}\) Suponhamos que existem inteiros \(r\text{,}\) \(r'\text{,}\) \(q\text{,}\) e \(q'\) tais que

\begin{equation*} a = bq + r, 0 \leq r \lt b \quad \text{e}\quad a = bq' + r', 0 \leq r' \lt b. \end{equation*}

Então \(bq + r = bq' + r'\text{.}\) Suponhamos que \(r' \geq r\text{.}\) Da última equação temos \(b(q - q') = r' - r\text{;}\) portanto, \(b\) deve dividir a \(r' - r\) e \(0 \leq r'- r \leq r' \lt b\text{.}\) Isso é possível só se \(r' - r = 0\text{.}\) Logo, \(r = r'\) e \(q = q'\text{.}\)

Sejam \(a\) e \(b\) inteiros. Se \(b = ak\) para algum inteiro \(k\text{,}\) escreveremos \(a \mid b\text{.}\) Um inteiro \(d\) se chama divisor comum de \(a\) e \(b\) se \(d \mid a\) e \(d \mid b\text{.}\) O máximo divisor comum dos inteiros \(a\) e \(b\) é um inteiro positivo \(d\) tal que \(d\) é um divisor comum de \(a\) e \(b\) e se \(d'\) é qualquer outro divisor comum de \(a\) e \(b\text{,}\) então \(d' \mid d\text{.}\) Escreveremos \(d = \gcd(a, b)\text{;}\) por exemplo, \(\gcd( 24, 36) = 12\) e \(\gcd(120, 102) = 6\text{.}\) Dizemos que dois inteiros \(a\) e \(b\) são relativamente primos se \(\gcd( a, b ) = 1\text{.}\)

Seja

\begin{equation*} S = \{ am + bn : m, n \in {\mathbb Z} \text{ e } am + bn \gt 0 \}. \end{equation*}

Claramente, o conjunto \(S\) não é vazio; logo, pelo Princípio da Bem-Ordem \(S\) tem um elemento mínimo, digamos \(d = ar + bs\text{.}\) Afirmamos que \(d = \gcd( a, b)\text{.}\) Escreve \(a = dq + r'\) com \(0 \leq r' \lt d\text{.}\) Se \(r' \gt 0\text{,}\) então

\begin{align*} r'& = a - dq\\ & = a - (ar + bs)q\\ & = a - arq - bsq\\ & = a( 1 - rq ) + b( -sq ), \end{align*}

que está em \(S\text{.}\) Mas isso estaria em contradição com o fato de que \(d\) é o menor membro de \(S\text{.}\) Logo, \(r' = 0\) e \(d\) divide a \(a\text{.}\) Um argumento similar mostra que \(d\) divide a \(b\text{.}\) Portanto, \(d\) é um divisor comum de \(a\) e \(b\text{.}\)

Suponhamos que \(d'\) é outro divisor comum de \(a\) e \(b\text{,}\) e queremos mostrar que \(d' \mid d\text{.}\) Se \(a = d'h\) e \(b = d'k\text{,}\) então

\begin{equation*} d = ar + bs = d'hr + d'ks = d'(hr + ks). \end{equation*}

Ou seja \(d'\) divide a \(d\text{.}\) Logo, \(d\) é o único máximo divisor comum de \(a\) e \(b\text{.}\)

Subseção 2.2.1 O Algoritmo de Euclides

Entre outras coisas, o Teorema 2.2.2 nos permite calcular o máximo divisor comum de dois inteiros.

Calculemos o máximo divisor comum de \(945\) e \(2415\text{.}\) Primeiro observemos que

\begin{align*} 2415 & = 945 \cdot 2 + 525\\ 945 & = 525 \cdot 1 + 420\\ 525 & = 420 \cdot 1 + 105\\ 420 & = 105 \cdot 4 + 0. \end{align*}

Usando os passos de trás para frente, 105 divide a 420, 105 divide a 525, 105 divide a 945, e 105 divide a 2415. Logo, 105 divide tanto a 945 como a 2415. Se \(d\) foi outro divisor comum de 945 e 2415, então \(d\) também dividiria a 105. Portanto, \(\gcd( 945, 2415 ) = 105\text{.}\)

Recorrendo as equações anteriores de baixo para cima, podemos obter números inteiros \(r\) e \(s\) tais que \(945 r + 2415 s = 105\text{.}\) Note que

\begin{align*} 105 & = 525 + (-1) \cdot 420\\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\ & = 2 \cdot 525 + (-1) \cdot 945\\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\ & = 2 \cdot 2415 + (-5) \cdot 945. \end{align*}

Assim \(r = -5\) e \(s= 2\text{.}\) Note que \(r\) e \(s\) não são únicos, pois por exemplo \(r = 41\) e \(s = -16\) também funcionariam.

Para calcular \(\gcd(a,b) = d\text{,}\) estamos usando sucessivas divisões para obter uma sucessão decrescente de inteiros positivos \(r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}\) ou seja,

\begin{align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ & \vdots \\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\ r_{n - 1} & = r_n q_{n + 1}. \end{align*}

Para encontrar \(r\) e \(s\) tais que \(ar + bs = d\text{,}\) começamos com a última equação e substituímos os resultados obtidos das equações anteriores:

\begin{align*} d & = r_n\\ & = r_{n - 2} - r_{n - 1} q_n\\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2} \\ & \vdots \\ & = ra + sb. \end{align*}

O algoritmo que acabamos de usar para encontrar o máximo divisor comum \(d\) de dois inteiros \(a\) e \(b\) e escrever \(d\) como combinação linear de \(a\) e \(b\) se conhece como o algoritmo de Euclides.

Subseção 2.2.2 Números Primos

Seja \(p\) um inteiro tal que \(p \gt 1\text{.}\) Dizemos que \(p\) é um número primo, ou simplesmente \(p\) é primo, se e só se os únicos números inteiros positivos que dividem a \(p\) são 1 e o mesmo \(p\text{.}\) Um inteiro \(n \gt 1\) que não é primo se chama composto.

Suponhamos que \(p\) não divide a \(a\text{.}\) Devemos mostrar que \(p \mid b\text{.}\) Como \(\gcd( a, p ) = 1\text{,}\) existem inteiros \(r\) e \(s\) tais que \(ar + ps = 1\text{.}\) Assim

\begin{equation*} b = b(ar + ps) = (ab)r + p(bs). \end{equation*}

Como \(p\) divide tanto \(ab\) como si mesmo, \(p\) divide \(b = (ab)r + p(bs)\text{.}\)

Demonstraremos este teorema por contradição. Suponhamos que existe só uma quantidade finita de primos, digamos \(p_1, p_2, \ldots, p_n\text{.}\) Seja \(P = p_1 p_2 \cdots p_n + 1\text{.}\) Então \(P\) deve ser divisível por algum \(p_i\) com \(1 \leq i \leq n\text{.}\) Neste caso, \(p_i\) deve dividir \(P - p_1 p_2 \cdots p_n = 1\text{,}\) o que é uma contradição. Logo, já seja \(P\) é primo ou existe um primo adicional \(p \neq p_i\) que divide \(P\text{.}\)

Unicidade. Para demonstrar a unicidade procederemos por indução em \(n\text{.}\) O teorema é claramente verdadeiro para \(n = 2\) pois neste caso \(n\) é primo. Agora suponhamos que o resultado se cumpre para todos os inteiros \(m\) tais que \(1 \leq m \lt n\text{,}\) e

\begin{equation*} n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l, \end{equation*}

com \(p_1 \leq p_2 \leq \cdots \leq p_k\) e \(q_1 \leq q_2 \leq \cdots \leq q_l\text{.}\) Pelo Lema 2.2.5, \(p_1 \mid q_i\) para certos \(i = 1, \ldots, l\) e \(q_1 \mid p_j\) para certos \(j = 1, \ldots, k\text{.}\) Como todos os \(p_i\) e os \(q_i\) são primos, \(p_1 = q_i\) e \(q_1 = p_j\text{.}\) Logo, \(p_1 = q_1\) pois \(p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}\) Por a hipótese de indução,

\begin{equation*} n' = p_2 \cdots p_k = q_2 \cdots q_l \end{equation*}

tem uma fatoração única. Logo, \(k = l\) e \(q_i = p_i\) para \(i = 1, \ldots, k\text{.}\)

Existência. Para demonstrar a existência, suponhamos que existe algum inteiro que não pode ser escrito como produto de primos. Seja \(S\) o conjunto de tais números. Pelo Princípio da Bem-Ordem, \(S\) contém um elemento mínimo, digamos \(a\text{.}\) Se os únicos fatores positivos de \(a\) são \(a\) e 1, então \(a\) é primo, o que é uma contradição. Logo, \(a = a_1 a_2\) com \(1 \lt a_1 \lt a\) e \(1 \lt a_2 \lt a\text{.}\) Nem \(a_1\in S\) nem \(a_2 \in S\text{,}\) pois \(a\) é o menor elemento de \(S\text{.}\) Assim

\begin{align*} a_1 & = p_1 \cdots p_r\\ a_2 & = q_1 \cdots q_s. \end{align*}

Portanto,

\begin{equation*} a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s. \end{equation*}

Assim \(a \notin S\text{,}\) o que é uma contradição.

Subseção 2.2.3 Nota Histórica

Os números primos já foram estudados pelos antigos Gregos. Dos resultados importantes da Antiguidade são a demonstração de Euclides de que existe uma infinidade de primos e a crivo de Eratóstenes, um método para calcular todos os números primos menores do que um inteiro positivo dado. Um problema em teoria de números é encontrar uma função \(f\) tal que \(f(n)\) é primo para cada inteiro \(n\text{.}\) Pierre Fermat (1601?–1665) conjeturou que \(2^{2^n} + 1\) era primo para todo \(n\text{,}\) mas posteriormente Leonhard Euler (1707–1783) demonstrou que

\begin{equation*} 2^{2^5} + 1 = \text{4,294,967,297} \end{equation*}

é um número composto. Uma das muitas conjeturas não demonstradas sobre números primos é a conjetura de Goldbach. Numa carta ao Euler em 1742, Christian Goldbach enunciou a conjetura que todo inteiro positivo com a exceção de 2 parecia ser uma soma de dois primos: \(4 = 2 + 2\text{,}\) \(6 = 3 + 3\text{,}\) \(8 =3 + 5\text{,}\) \(\ldots\text{.}\) Enquanto a conjetura foi verificada para todos os números até \(4 \times 10^{18}\text{,}\) ainda não foi demonstrada em geral. Como os números primos têm um papel importante na criptografia de chave pública, há atualmente grande interesse em determinar se um número grande é primo ou não.

Sage.

El objetivo inicial de Sage fue de apoyar la investigación en teoría de números, de manera que funciona muy bien para los tipos de cálculos con enteros que tenemos en este capítulo.