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′.

Existência de q e r. Seja

S={a−bk:k∈Z e a−bk≥0}.

Se 0∈S, então b divide a a, e podemos tomar q=a/b e r=0. Se 0∉S, podemos usar o Princípio da Bem-Ordem. Devemos primeiro mostrar que S é não vazio. Se a>0, então a−b⋅0∈S. Se a<0, então a−b(2a)=a(1−2b)∈S. Em qualquer caso S≠∅. Pelo Princípio da Bem-Ordem, S tem um elemento mínimo, digamos r=a−bq. Portanto, a=bq+r, r≥0. Mostremos agora que r<b. Suponhamos que r>b. Então

a−b(q+1)=a−bq−b=r−b>0.

Neste caso teríamos a−b(q+1) no conjunto S. Mas então a−b(q+1)<a−bq, o que nos levaria a uma contradição do fato que r=a−bq é o menor elemento de S. Assim r≤b. Como 0∉S, r≠b e assim r<b.

Unicidade de q e r. Suponhamos que existem inteiros r, r′, q, e q′ tais que

a=bq+r,0≤r<bea=bq′+r′,0≤r′<b.

Então bq+r=bq′+r′. Suponhamos que r′≥r. Da última equação temos b(q−q′)=r′−r; portanto, b deve dividir a r′−r e 0≤r′−r≤r′<b. Isso é possível só se r′−r=0. Logo, r=r′ e q=q′.

🔗
Sejam a e b inteiros. Se b=ak para algum inteiro k, escreveremos a∣b. Um inteiro d se chama divisor comum de a e b se d∣a e d∣b. 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, então d′∣d. Escreveremos d=mdc(a,b); por exemplo, mdc(24,36)=12 e mdc(120,102)=6. Dizemos que dois inteiros a e b são relativamente primos se mdc(a,b)=1.

Seja

S={am+bn:m,n∈Z e am+bn>0}.

Claramente, o conjunto S não é vazio; logo, pelo Princípio da Bem-Ordem S tem um elemento mínimo, digamos d=ar+bs. Afirmamos que d=mdc(a,b). Escreve a=dq+r′ com 0≤r′<d. Se r′>0, então

r′=a−dq=a−(ar+bs)q=a−arq−bsq=a(1−rq)+b(−sq),

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

Suponhamos que d′ é outro divisor comum de a e b, e queremos mostrar que d′∣d. Se a=d′h e b=d′k, então

d=ar+bs=d′hr+d′ks=d′(hr+ks).

Ou seja d′ divide a d. Logo, d é o único máximo divisor comum de a e b.

🔗

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. Primeiro observemos que

2415=945⋅2+525945=525⋅1+420525=420⋅1+105420=105⋅4+0.

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, mdc(945,2415)=105.

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

105=525+(−1)⋅420=525+(−1)⋅[945+(−1)⋅525]=2⋅525+(−1)⋅945=2⋅[2415+(−2)⋅945]+(−1)⋅945=2⋅2415+(−5)⋅945.

Assim r=−5 e s=2. Note que r e s não são únicos, pois por exemplo r=41 e s=−16 também funcionariam.

🔗
Para calcular mdc(a,b)=d, estamos usando sucessivas divisões para obter uma sucessão decrescente de inteiros positivos r1>r2>⋯>rn=d; ou seja,

b=aq1+r1a=r1q2+r2r1=r2q3+r3⋮rn−2=rn−1qn+rnrn−1=rnqn+1.

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

d=rn=rn−2−rn−1qn=rn−2−qn(rn−3−qn−1rn−2)=−qnrn−3+(1+qnqn−1)rn−2⋮=ra+sb.

🔗
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>1. 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. Um inteiro n>1 que não é primo se chama composto.

Suponhamos que p não divide a a. Devemos mostrar que p∣b. Como mdc(a,p)=1, existem inteiros r e s tais que ar+ps=1. Assim

b=b(ar+ps)=(ab)r+p(bs).

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

Demonstraremos este teorema por contradição. Suponhamos que existe só uma quantidade finita de primos, digamos p1,p2,…,pn. Seja P=p1p2⋯pn+1. Então P deve ser divisível por algum pi com 1≤i≤n. Neste caso, pi deve dividir P−p1p2⋯pn=1, o que é uma contradição. Logo, já seja P é primo ou existe um primo adicional p≠pi que divide P.

Unicidade. Para demonstrar a unicidade procederemos por indução em n. 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≤m<n, e

n=p1p2⋯pk=q1q2⋯ql,

com p1≤p2≤⋯≤pk e q1≤q2≤⋯≤ql. Pelo Lema 2.2.5, p1∣qi para certos i=1,…,l e q1∣pj para certos j=1,…,k. Como todos os pi e os qi são primos, p1=qi e q1=pj. Logo, p1=q1 pois p1≤pj=q1≤qi=p1. Por a hipótese de indução,

n′=p2⋯pk=q2⋯ql

tem uma fatoração única. Logo, k=l e qi=pi para i=1,…,k.

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. Se os únicos fatores positivos de a são a e 1, então a é primo, o que é uma contradição. Logo, a=a1a2 com 1<a1<a e 1<a2<a. Nem a1∈S nem a2∈S, pois a é o menor elemento de S. Assim

a1=p1⋯pra2=q1⋯qs.

Portanto,

a=a1a2=p1⋯prq1⋯qs.

Assim a∉S, 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. Pierre Fermat (1601?–1665) conjeturou que 22n+1 era primo para todo n, mas posteriormente Leonhard Euler (1707–1783) demonstrou que

225+1=4,294,967,297

🔗
é 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, 6=3+3, 8=3+5, …. Enquanto a conjetura foi verificada para todos os números até 4×1018, 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.