Introdução à Teoria dos Números, Manuais, Projetos, Pesquisas de Matemática

Baixe Introdução à Teoria dos Números e outras Manuais, Projetos, Pesquisas em PDF para Matemática, somente na Docsity! UNIVERSIDADE DE BRASÍLIA DEPARTAMENTO DE MATEMÁTICA -IE TEORIA DOS NÚMEROS Texto de aula Professor Rudolf R. Maier Versão atualizada 2005 Estas notas são o resultado da experiência nas aulas do curso do mesmo t́ıtulo, proferido regularmente pelo autor neste Departamento de Matemática. Durante o curso e na elaboração destas notas fizemos livre uso e seguimos com modificações e complementações à linha do livro ELEMENTARY NUMBER THEORY de David M. Burton Revised Printing University of New Hampshire Allyn and Bacon, Inc. Boston·London·Sydney·Toronto c©1980 TEORIA DOS NÚMEROS Notas de aula - Versão atualizada 2005 Prof. Rudolf R. Maier § 1 Resultados Preliminares A Teoria dos Números, a mais pura disciplina dentro da mais pura das Ciências - da Matemática - tem uma longa história, originando-se nas antigas civilizações da hu- manidade. Listamos primeiro alguns nomes famosos de matemáticos que voltarão a aparecer no contexto do nosso curso: Pitagoras (569-500 a. C.) Euclides (≈ 350 a. C.) Eratóstenes (276-196 a. C.) Diofantos (≈ 250 d. C.) Plutarco (≈ 100 d. C.) Marin Mersenne (1588-1648) Pierre de Fermat (1601-1665) Blaise Pascal (1623-1662) Christian Goldbach (1690-1764) Leonhard Euler (1707-1783) Joseph Louis Lagrange (1736-1813) John Wilson (1741-1793) Adrien Marie Legendre (1752-1833) Carl Friedrich Gauss (1777-1855) Augustin Louis Cauchy (1789-1857) Peter Gustav Dirichlet (1805-1859) P. L. Tchebychef (1821-1894) Frederick Nelson Cole (1861-1927) Axel Thue (1863-1922) Jacques Salomon Hadamard (1865-1963) Charles de la Vallée Poussin (1866-1962) 1 Dedicaremos os nossos estudos durante este curso às propriedades dos números inteiros racionais. Lidaremos então com o conjunto ZZ = { . . . , −3,−2,−1, 0, 1, 2, 3 , . . . } dos números inteiros e seus subconjuntos, particularmente com os subconjuntos IN 0 = { 0, 1, 2, 3 , . . . } e IN = { 1, 2, 3 , . . . } dos números inteiros não-negativos e dos números naturais. Iniciamos, lembrando exemplos de algumas seqüências importantes no conjunto IN dos números naturais: 1.1 Exemplo. Seqüências importantes em IN são: A seqüência a) (n) n∈IN = (1, 2, 3 , . . . , n , . . .) de todos os números naturais, b) (2n) n∈IN = (2, 4, 6 , . . . , 2n , . . .) dos números naturais pares, c) (2n−1) n∈IN = (1, 3, 5 , . . . , 2n−1 , . . .) dos números ı́mpares, d) ( n2 ) n∈IN = ( 1, 4, 9 , . . . , n2 , . . . ) dos quadrados perfeitos, e) ( n3 ) n∈IN = ( 1, 8, 27 , . . . , n3 , . . . ) dos cubos perfeitos, f) (2n) n∈IN = (2, 4, 8 , . . . , 2n , . . .) das potências de 2 g) (pn)n∈IN = (2, 3, 5 , . . . , pn , . . .) dos números primos, h) etc. Dizemos também: n é o n-ésimo número natural, 2n é o n-ésimo número par, 2n− 1 é o n-ésimo número ı́mpar, n2 é o n-ésimo quadrado perfeito, etc. Temos duas operações internas em IN 0 e também em ZZ a adição + e a multi- plicação · as quais queremos admitir sem mais explicações. A ordem natural em ZZ é dada por: ∀ n, m ∈ ZZ temos m ≤ n ⇐⇒ a equação m + x = n possui uma solução x ∈ IN 0 . Uma fundamantal propriedade do conjunto IN dos números naturais é: 2 O prinćıpio da indução. Todo conjunto não vazio S de números naturais possui um elemento mı́nimo. Em śımbolos: ∀ S ⊆ IN , S 6= 6O, ∃ m ∈ S tal que m ≤ n ∀ n ∈ S. Deste prinćıpio segue a importante 1.2 Proposição. Seja T um conjunto de números naturais (i.e. T ⊆ IN) satisfazendo às propriedades: a) 1 ∈ T b) Sempre se n ∈ T , então também n+1 ∈ T . Então T = IN é o conjunto de todos os números naturais. Demonstração: Suponhamos T 6= IN. Para o conjunto complementar S = IN \ T temos então 6O 6= S ⊆ IN. Pelo prinćıpio da indução existe m ∈ S tal que m ≤ n para todos os n ∈ S. Como 1 ∈ T pela propriedade a), temos 1 6∈ S, particularmente m > 1. Dáı concluimos n = m−1 ∈ T. Pela propriedade b) temos porém m = n+1 ∈ T , de onde sai o absurdo m ∈ S ∩ T = 6O. Isto mostra que S 6= 6O é imposśıvel. Temos que ter S = 6O e dáı T = IN. Proposição 1.2 aplica-se para verificar a validade geral de fórmulas as quais en- volvem números naturais, como mostra o seguinte 1.3 Exemplo. Para todos os números naturais n vale 1 + 3 + 5 + . . . + (2n−3) + (2n−1) = n2 (∗) . Em palavras: A soma dos n primeiros números naturais ı́mpares é o n-ésimo quadrado perfeito. Demonstração: Seja T = { n ∈ IN ∣∣∣ n∑ k=1 (2k−1) = n2 } o conjunto dos números naturais para os quais a fórmula (∗) é verdadeira (o ”conjunto verdade” ou o ”con- junto de validade” de (∗)). Para mostrar que T = IN , só é preciso verificar a) e b) 3 O teorema binomial Se n ∈ IN 0 entendemos por n! o produto n! = n∏ k=1 k = 1 · 2 · 3 · . . . · n , se n ∈ IN e acrescentamos 0! = 1 , se n = 0 (produto vazio) . n! lê-se: n fatorial. É imediato que se tem 0! = 1! = 1, 2! = 2, 3! = 2! · 3 = 6, 4! = 3! · 4 = 24, . . . , n! = (n−1)! · n, (n+1)! = n! · (n+1) , . . . . 1.5 Definição. Para todo n ∈ IN e todos os k ∈ IN 0 com 0 ≤ k ≤ n colocamos (n k ) = n! k!(n−k)! , número este que se chama o coeficiente binomial n sobre k. Temos as seguintes propriedades dos coeficientes binomiais: 1.6 Observação. Para todo n ∈ IN e todos os k ∈ IN 0 com 0 ≤ k ≤ n valem a) (n k ) = n(n−1) · . . . · (n−k+1) k! . b) (n k ) = ( n n−k ) . c) (n k ) + ( n k−1 ) = (n+1 k ) sek ≥ 1. Demonstração: a) (n k ) = n! k!(n− k)! = n(n−1) · · · (n− k + 1) · (n− k) · · · 2 · 1 k!(n− k)! = n(n−1) · · · (n− k + 1) k! . b) Observamos primeiro que com 0 ≤ k ≤ n temos também 0 ≤ n−k ≤ n. Pela definição temos de imediato( n n−k ) = n! (n−k)![n− (n−k)]! = n! (n− k)!k! = (n k ) . 6 c) Se k ≥ 1 calculamos (n k ) + ( n k−1 ) = n! k!(n− k)! + n! (k − 1)![n− (k − 1)]! = n!(n− k + 1) + n!k k!(n− k + 1)! = = n!(n + 1) k!(n− k + 1)! = (n + 1)! k![(n + 1)− k]! = (n+1 k ) . Eis alguns valores espećıficos de coeficientes binomiais: (n 0 ) = (n n ) = 1, (n 1 ) = ( n n−1 ) = n, (n 2 ) = ( n n−2 ) = n(n−1) 2 . Podemos enunciar e provar agora o fundamental teorema do desenvolvimento binomial: 1.7 Teorema. Para todo n ∈ IN e todos os números reais a, b temos (a + b)n = n∑ k=0 (n k ) an−kbk , por extenso: (a + b)n = = (n 0 ) anb0+ (n 1 ) an−1b1+ (n 2 ) an−2b2+ . . .+ (n k ) an−kbk + . . .+ ( n n−1 ) a1bn−1+ (n n ) a0bn . Demonstração: Demonstraremos isto por indução sobre o expoente n, isto é, provaremos 1 ∈ T e a implicação ”n ∈ T ⇒ n+1 ∈ T ”, quando T é o conjunto de validade da fórmula. Para n = 1 afirma-se que (a+b)1 = 1∑ k=0 (1 k ) a1−kbk = (1 0 ) a1−0b0 + (1 1 ) a1−1b1, sendo igual a a + b de ambos os lados, i.e. 1 ∈ T. Suponhamos então que, para algum n ∈ IN , já esteja provado (a + b)n = n∑ k=0 (n k ) an−kbk (∗) 7 e provamos a validade para n+1. Para isto multiplicamos os dois lados de (∗) por (a + b) e obtemos, usando-se a observação 1.6 c): (a + b)n+1 =  n∑ k=0 (n k ) an−kbk  (a + b) = n∑ k=0 (n k ) an−k+1bk + n∑ k=0 (n k ) an−kbk+1 = = an+1 + n∑ k=1 (n k ) an−k+1bk + n−1∑ k=0 (n k ) an−kbk+1 + bn+1 = = an+1 + bn+1 + n∑ k=1 (n k ) an−k+1bk + n∑ k=1 ( n k−1 ) an−k+1bk = = an+1 +bn+1 + n∑ k=1 [(n k ) + ( n k−1 )] an+1−kbk = an+1 +bn+1 + n∑ k=1 (n+1 k ) an−k+1bk = = n+1∑ k=0 (n+1 k ) an+1−kbk , isto é, (a + b)n+1 = n+1∑ k=0 (n+1 k ) an+1−kbk . Isto significa que, a partir da suposta validade da fórmula (∗) para algum n, con- seguimos provar a sua validade para n+1 (i.e. n ∈ T ⇒ n+1 ∈ T ). Concluimos que (∗) tem validade para todo n ∈ IN. É usual, escrever-se os coeficientes binomiais (n k ) (acrescentando-se ainda (0 0 ) = 1), ordenados no chamado Triângulo de Pascal, cuja n-ésima linha fornece então os coeficientes no desenvolvimento de (a + b)n para n = 0, 1, 2, 3 , . . . (0 0 ) (1 0 ) (1 1 ) (2 0 ) (2 1 ) (2 2 ) (3 0 ) (3 1 ) (3 2 ) (3 3 ) . . . . . . . . . . . . . . . .( n 0 ) ( n 1 ) . . . ( n k−1 ) ( n k ) . . . ( n n−1 ) ( n n ) ( n+1 0 ) ( n+1 1 ) . . . ( n+1 k ) . . . ( n+1 n ) ( n+1 n+1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Vejamos os primeiros casos desta fórmula. a) m = 1 : (1 + 1) · Sn(1) = (n + 1)1+1 − 1− 1−1∑ k=0 (1+1 k ) Sn(k) ou seja, 2 · Sn(1) = (n + 1)2 − 1− Sn(0) ou ainda 2 · Sn(1) = n2 + 2n + 1− 1− n = n(n + 1) o que dá para a soma dos n primeiros números naturais: Sn(1) = n(n + 1) 2 . b) m = 2 : (2 + 1) · Sn(2) = (n + 1)2+1 − 1− 2−1∑ k=0 (2+1 k ) Sn(k) ou seja, 3 · Sn(2) = (n + 1)3 − 1− Sn(0)− 3 · Sn(1) ou ainda 3 · Sn(2) = (n + 1)3 − (1 + n)− 3 · n(n + 1) 2 = = (n + 1) [ (n + 1)2 − 1− 3 2 n ] = (n + 1)(2n2 + n) 2 , o que dá para a soma dos n primeiros quadrados perfeitos: Sn(2) = n(n + 1)(2n + 1) 6 . c) m = 3 : (3 + 1) · Sn(3) = (n + 1)3+1 − 1− 3−1∑ k=0 (3+1 k ) Sn(k) ou seja, 4 · Sn(3) = (n + 1)4 − 1− Sn(0)− 4 · Sn(1)− 6 · Sn(2) ou ainda 4 · Sn(3) = (n + 1)4 − (1 + n)− 4 · n(n + 1) 2 − 6 · n(n + 1)(2n + 1) 6 = = (n + 1) [ (n + 1)3 − 1− 2n− n(2n + 1) ] = (n + 1) [ n3 + n2 ] = n2(n + 1)2 o que dá para a soma dos n primeiros cubos perfeitos: Sn(3) = n2(n + 1)2 4 . Comparando-se os casos m = 1 e m = 3 vemos que Sn(3) = ( Sn(1) )2 o que dá ainda a relação interessante (1 + 2 + 3 + . . . + n)2 = 13 + 23 + 33 + . . . + n3 , válida para todos os n ∈ IN. 11 Uma fórmula fechada para Sn(m) sem uso das anteriores podemos estabelecer em forma de um (m+1)× (m+1)-determinante: 1.11 Teorema. Para todo n ∈ IN e m ∈ IN 0 temos Sn(m) = 1 (m + 1)! · ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ (1 0 ) 0 0 . . . 0 0 (n+1)1−1(2 0 ) (2 1 ) 0 . . . 0 0 (n+1)2−1(3 0 ) (3 1 ) (3 2 ) . . . 0 0 (n+1)3−1 ... ... ... . . . ... ... ...( m 0 ) ( m 1 ) ( m 2 ) . . . ( m m−2 ) ( m m−1 ) (n+1)m−1( m+1 0 ) ( m+1 1 ) ( m+1 2 ) . . . ( m+1 m−2 ) ( m+1 m−1 ) (n+1)m+1−1 ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ . Demonstração: Nossa fórmula de recursão (m + 1) · Sn(m) = (n + 1)m+1 − 1− m−1∑ k=0 ( m+1 k ) Sn(k) podemos reescrever, substituindo-se m = `, como ∑̀ k=0 ( `+1 k ) Sn(k) = (n + 1) `+1 − 1 . Explicitando-se esta para ` = 0, 1, 2 , . . . , m, obtemos um sistema de m + 1 equações lineares nas m + 1 incognitas Sn(0), Sn(1), Sn(2) , . . . , Sn(m): (1 0 ) Sn(0) = (n+1) 1−1(2 0 ) Sn(0) + (2 1 ) Sn(1) = (n+1) 2−1(3 0 ) Sn(0) + (3 1 ) Sn(1) + (3 2 ) Sn(2) = (n+1) 3−1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .( m 0 ) Sn(0) + ( m 1 ) Sn(1) + . . . + ( m m−1 ) Sn(m−1) = (n+1)m−1( m+1 0 ) Sn(0) + ( m+1 1 ) Sn(1) + . . . + ( m+1 m−1 ) Sn(m−1) + ( m+1 m ) Sn(m) = (n+1) m+1−1 O determinante dos coeficientes deste sistema (o produto dos coeficientes da diag- onal neste caso) é 12 (1 0 )(2 1 )(3 2 ) . . . ( m m−1 )(m+1 m ) = (m + 1)! . A aplicação da regra de Cramer fornece para a incógnita Sn(m), como afirmado: Sn(m) = 1 (m + 1)! · ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ (1 0 ) 0 0 . . . 0 0 (n+1)1−1(2 0 ) (2 1 ) 0 . . . 0 0 (n+1)2−1(3 0 ) (3 1 ) (3 2 ) . . . 0 0 (n+1)3−1 ... ... ... . . . ... ... ...( m 0 ) ( m 1 ) ( m 2 ) . . . ( m m−2 ) ( m m−1 ) (n+1)m−1( m+1 0 ) ( m+1 1 ) ( m+1 2 ) . . . ( m+1 m−2 ) ( m+1 m−1 ) (n+1)m+1−1 ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ . Os números triangulares 1.12 Definição. Para todo m ∈ IN indicamos por tm = m(m + 1) 2 . tm chama-se o m-ésimo número triangular. Desta definição decorre imediatamente: 1.13 Observação. Para todo m ∈ IN temos tm = Sm(1) = 1 + 2 + 3 + . . . + m = (m+1 2 ) tal como t m+1 = tm + (m + 1) . A seqüência dos números triangulares é (tm)m∈IN = ( 1, 3, 6, 10 , . . . , m(m + 1) 2 , . . . ) . A denominação ”número triangular” para os números desta seqüência explica-se pelo seguinte triângulo equilâtero de lados m o qual contém exatamente tm pontos: 13 Um outro exemplo. Seja A a asserção: ”está chovendo”, (também isto pode ser verdadeiro ou falso aqui e agora), B a asserção: ”a praça está molhada”. Também neste caso temos A =⇒ B, pois, se realmente está chovendo, temos certeza que a praça está molhada. Assim, podemos dizer: ”estar chovendo implica que a praça está molhada”, ”estar chovendo é condição suficiente para termos uma praça molhada”, ”uma praça molhada é condição necessária para estar chovendo”, ”está chovendo somente se a praça está molhada”, ”a praça está molhada se está chovendo”, ”se está chovendo, então a praça está molhada”. Exerćıcio: Pensando-se num certo quadrângulo Q, façam o mesmo com as asserções A: ”Q é um quadrado”, B: ”Q é um losângo”. É claro que a seta numa implicação A =⇒ B não pode ser simplesmente invertida: Se A é condição suficiente para B, isto significa que B é condição necessária para A, mas não que B é condição suficiente para A: O fato de ”n ser par ” é condição necessária mas não suficiente para ”n ser múltiplo de 4”. O fato de ”n ser múltiplo de 4” é condição suficiente mas não necessária para ”n ser par ”: Também 6 é par sem ser múltiplo de 4. O fato de termos ”uma praça molhada” é condição necessária mas não suficiente para ”estar chovendo”. O fato de ”estar chovendo ”é condição suficiente mas não necessária para termos ”uma praça molhada”: A praça pode estar molhada sem que esteja chovendo (por exemplo devido a uma operação dos bombeiros). Existem asserções A e B que ambas implicam na outra, ou seja, as quais satis- fazem simultâneamente 16 A =⇒ B e B =⇒ A. Nesta situação temos então que A é suficiente para B e também A é necessário para B. Dizemos que A é (condição) necessário(a) e suficiente para B, ou também A vale se e somente se vale B. Este fato indicamos por A ⇐⇒ B. Dizemos também que A e B são asserções equivalentes, ou ainda que A con- stitui uma propriedade caracteŕıstica para B (e vice versa). Por exemplo: Seja A a asserção: ”n é múltiplo de 6 ”, B a asserção: ”n é um número par que é múltiplo de 3 ”. Cada uma destas duas propriedades, as quais um número n pode ter ou não, é su- ficiente para a outra. Cada uma é necessária para a outra. Cada uma é necessária e suficiente para a outra. Cada uma vale se e somente se a outra vale. Exerćıcio: Pensar sobre as asserções equivalentes, quando Q é um certo quadrângulo: A: ”Q é um quadrado” B: ”Q é um losângo que é um retângulo”. Se A é uma asserção, indicamos por A a asserção ”não-A”, a qual é verdadeira se e somente se A é falsa. Sejam A e B duas asserções e suponha A =⇒ B. O que acontece com esta implicação se negarmos as duas asserções ? A resposta é que devemos também inverter a seta da implicação, ou seja, teremos A ⇐= B. Em outras palavras: Se A é suficiente para B, então B é suficiente para A. Ou também: Se A é suficiente para B, então A é necessário para B. Por exemplo, se negarmos a implicação ”ser múltiplo de 4 é suficiente para ser par ”, (”ser um quadrado é suficiente para ser um retângulo”), 17 a implicação negada é: ”não ser múltiplo de 4 é necessário para ser ı́mpar ”, (”não ser um quadrado é necessário para não ser retângulo”) mas, não ser múltiplo de 4 (não ser quadrado) não é suficiente para ser ı́mpar (não ser retângulo). Claro que numa equivalência podemos negar as assercões dos dois lados, ou seja, não importa se escrevemos A ⇐⇒ B ou A ⇐⇒ B. Na Proposição 1.14 já conhecemos mais um exemplo de duas propriedades equivalentes, a saber, uma caracterização de um número natural n ser triangular: Necessário e suficiente para n ser triangular é a propriedade de 8n+1 ser um quadrado perfeito. Existem teoremas que afirmam simplesmente implicações, de modo que na sua demonstração deve ser verificado que uma certa propriedade B é conseqüência de uma propriedade A (a hipótese). outros teoremas matemáticos afirmam equivalências de certas propriedades. Eles tem a forma: Sob certas condicões são equivalentes: a) Vale a propriedade A b) Vale a propriedade B. A demonstração de um tal teorema sempre se divide em duas partes: ”a) ⇒ b)”: ....... Aqui deve ser mostrado que A é suficiente para B. Isto pode ser mostrado diretamente, mostrando-se que B é verdade, supondo-se a veracidade de A. Ou indiretamente, supondo-se a veracidade de B e concluindo- se que A é verdade. ”b) ⇒ a)”: ....... Aqui deve ser mostrado que A é necessário para B (que B é suficiente para A). Isto pode ser mostrado, verificando-se que A é verdade, supondo-se a veracidade de B. Ou indiretamente, supondo-se que A é falso e concluindo-se que B é falso. 18 § 2 Teoria de divisibilidade nos números inteiros O algoritmo geral de divisão 2.1 Proposição. (O algoŕıtmo de divisão ) Sejam a, b dois números inteiros com b > 0. Então existem únicos números inteiros q, r tais que a = qb + r e 0 ≤ r < b . q chama-se o quociente, r o menor resto não-negativo na divisão de a por b. Demonstração: A existência de q e r: Dados a, b ∈ ZZ com b > 0 consideremos o conjunto S = { a− bx ∣∣∣ x ∈ ZZ, a− bx ≥ 0} . Temos obviamente S ⊆ IN 0 . Para x = − |a| obtemos a − bx = a − b ( − |a| ) = a + b |a| ≥ a + |a| ≥ 0 pois b ≥ 1. Isto mostra que S 6= 6O. Pelo prinćıpio da indução temos que existe um r ∈ S ḿınimo, i.e. r ≤ y ∀ y ∈ S. Como r ∈ S existe um x = q ∈ ZZ com r = a − bq. Segue então a = bq + r. Falta provar que 0 ≤ r < b. Como r ∈ S certamente r ≥ 0. Supondo-se r ≥ b segue a−bq−b = r−b ≥ 0, ou seja, r > a−(q+1)b ∈ S contradizendo a minimalidade do r ∈ S. Isto mostra que r ≥ b é imposśıvel. Temos que ter r < b. A unicidade de q e r: Suponhamos que q, r e q′, r′ são inteiros tais que a = bq + r = bq′ + r′ e 0 ≤ r, r′ < b . Então r′ − r = bq − bq′ = b(q − q′) e segue |r′ − r| = |b(q − q′)| = b |q − q′| . Agora, adicionando-se as desigualdades  0 ≤ r ′ < b −b < −r ≤ 0 segue −b < r ′ − r < b, ou seja, |r′ − r| < b. Dáı temos a contradição b > |r′ − r| = b |q − q′| ≥ b , no caso q 6= q′. Concluimos q = q′ e então r = r′. 21 2.2 Exemplo. Para a = 100 e b = 7 temos q = 14 e r = 2 pois 100 = 7 · 14 + 2. Para a = −100 e b = 7 temos q = −15 e r = 5 pois −100 = 7 · (−15) + 5. 2.3 Teorema. (Algoritmo de divisão geral) Para quaisquer números a, b ∈ ZZ com b 6= 0 existem únicos q, r ∈ ZZ tais que a = bq + r e 0 ≤ r < |b| . Demonstração: Temos |b| > 0. Por 2.1, existem únicos q′, r ∈ ZZ com a = |b| q′ + r com 0 ≤ r < |b|. Se b > 0 então |b| = b e podemos considerar q = q′ junto com r. Se b < 0 então |b| = −b e podemos considerar q = −q′ junto com r obtendo a = |b| q′ + r = (−b)q′ + r = b(−q′) + r = bq + r. 2.4 Exemplo. Para a = 100 e b = −7 temos q = −14 e r = 2 pois 100 = (−7) · (−14) + 2. Para a = −100 e b = −7 temos q = 15 e r = 5 pois −100 = (−7) · 15 + 5. 2.5 Conseqüência. a) Considerando-se b = 2 temos para qualquer a ∈ ZZ um q ∈ ZZ com a = 2q ou a = 2q + 1 e conseqüentemente ZZ = { 2q ∣∣∣ q ∈ ZZ} ∪ { 2q + 1 ∣∣∣ q ∈ ZZ} tal que { 2q ∣∣∣ q ∈ ZZ} ∩ { 2q + 1 ∣∣∣ q ∈ ZZ} = 6O , isto é, temos uma decomposição do conjunto ZZ dos inteiros em dois subcon- juntos disjuntos - os inteiros pares e os inteiros ı́mpares. b) De forma semelhante, considerando-se b = 3 temos para qualquer a ∈ ZZ um q ∈ ZZ com a = 3q ou a = 3q + 1 ou a = 3q + 2 e conseqüentemente ZZ = { 3q ∣∣∣ q ∈ ZZ} ∪̇ { 3q + 1 ∣∣∣ q ∈ ZZ} ∪̇ { 3q + 2 ∣∣∣ q ∈ ZZ} , uma decomposição de ZZ em três subconjuntos disjuntos. c) Para b = 4 obtemos ZZ = { 4q ∣∣∣ q ∈ ZZ} ∪̇ { 4q + 1 ∣∣∣ q ∈ ZZ} ∪̇ { 4q + 2 ∣∣∣ q ∈ ZZ} ∪̇ { 4q + 3 ∣∣∣ q ∈ ZZ} 22 d) Em geral, para b = n ∈ IN obtemos ZZ = { nq ∣∣∣ q ∈ ZZ} ∪̇ { nq + 1 ∣∣∣ q ∈ ZZ} ∪̇ . . . ∪̇ { nq + (n−1) ∣∣∣ q ∈ ZZ} Observação: Os n conjuntos{ nq ∣∣∣ q ∈ ZZ} , { nq + 1 ∣∣∣ q ∈ ZZ} , { nq + 2 ∣∣∣ q ∈ ZZ} , . . . , { nq + (n−1) ∣∣∣ q ∈ ZZ} chamam-se as classes de resto módulo n (ver §6). 2.6 Definição. Dizemos que um inteiro b é diviśıvel por um inteiro a (também: a divide b ou b é multiplo de a) se existe q ∈ ZZ com b = aq. Notação: Escrevemos a ∣∣∣b se a divide b e a† b se isto não ocorre. Por exemplo: 3 ∣∣∣ −12, 5 ∣∣∣15, −7 ∣∣∣21. Vale 1 ∣∣∣b para todo b ∈ ZZ e a ∣∣∣0 para todo a ∈ ZZ. Porém: ±4† ± 10, ±49† ± 77. 2.7 Proposição. (Regras) Para todos os números a, b, c, d ∈ ZZ valem a) a ∣∣∣0, 1 ∣∣∣b, a ∣∣∣a. b) a ∣∣∣1 ⇐⇒ a = ±1; 0 ∣∣∣b ⇐⇒ b = 0. c) Se a ∣∣∣b e c ∣∣∣d então ac ∣∣∣bd. d) Se a ∣∣∣b e b ∣∣∣c então a ∣∣∣c. e) a ∣∣∣b e b ∣∣∣a ⇐⇒ a = ±b. f) Se a ∣∣∣b e b 6= 0 então |a| ≤ |b| . g) Se a ∣∣∣b e a ∣∣∣c então a ∣∣∣bx + cy ∀ x, y ∈ ZZ. Estas propriedades são conseqüências fáceis da definição e deixamos a sua demon- stração como exerćıcio. Provemos, por exemplo, o item g): a ∣∣∣b e a ∣∣∣c significa que existem q1 , q2 ∈ ZZ tais que aq1 = b e aq2 = c. Segue então bx + cy = (aq1)x + (aq2)y = a(q1x + q2y) com q1x + q2y ∈ ZZ, mostrando 23 Mencionamos algumas conseqüências desta caracterização dos números relativa- mente primos. 2.13 Conseqüência. Sejam a, b ∈ ZZ, não ambos nulos e d = mdc(a, b). Então mdc ( a d , b d ) = 1 . (Observamos que a d e b d são números inteiros!) Demonstração: De ax + by = d para certos x, y ∈ ZZ, segue adx + b dy = 1. Por 2.12 concluimos a afirmação. 2.14 Conseqüência. Sejam a, b, c ∈ ZZ tais que a ∣∣∣c e b ∣∣∣c. Se mdc(a, b) = 1, então temos também ab ∣∣∣c . Demonstração: Existem r, s, x, y ∈ ZZ tais que ar = c = bs e ax + by = 1. Dáı concluimos c = c · 1 = c(ax + by) = cax + cby = (bs)ax + (ar)by = ab(sx + ry) , com sx + ry ∈ ZZ. Segue ab ∣∣∣c. 2.15 Conseqüência. (O Lema de Euclides) Sejam a, b, c ∈ ZZ tais que a ∣∣∣bc e mdc(a, b) = 1. Então a ∣∣∣c. Demonstração: Temos r, x, y ∈ ZZ tais que ar = bc e ax + by = 1. Dáı concluimos c = c · 1 = c(ax + by) = cax + cby = cax + ary = a(cx + ry) . Segue a ∣∣∣c. 2.16 Conseqüência. Sejam a, b, c ∈ ZZ tais que mdc(a, b) = mdc(a, c) = 1. Então temos também mdc(a, bc) = 1, 26 Demonstração: Temos x, y, u, v ∈ ZZ tais que ax + by = 1 = au + cv. Dáı concluimos 1 = 1 · 1 = (ax + by)(au + cv) = a2xu + axcv + byau + bycv = = a(axu + xcv + byu) + bc(yv) , onde axu+xcv+byu, yv ∈ ZZ. Concluimos mdc(a, bc) = 1. O algoritmo Euclidiano Para dois números a, b ∈ ZZ com b 6= 0 consideremos o seguinte processo: Colocamos r0 = |b|. Existem q1 , r1 ∈ ZZ tais que a = bq1 + r1 com 0 ≤ r1 < r0 . Se r1 = 0, o processo pára. Se r1 6= 0 existem q2 , r2 ∈ ZZ tais que r0 = r1q2 + r2 com 0 ≤ r2 < r1 . Se r2 = 0, o processo pára. Se r2 6= 0 existem q3 , r3 ∈ ZZ tais que r1 = r2q3 + r3 com 0 ≤ r3 < r2 . . . . . . . . . . . . . . . . Se o processo já chegou em r k−2 = rk−1qk + rk com 0 ≤ rk < rk−1 , o próximo passo é: Se r k = 0, o processo pára. Se r k 6= 0 existem q k+1 , rk+1 ∈ ZZ tais que r k−1 = rkqk+1 + rk+1 com 0 ≤ rk+1 < rk . . . . . . . . . . . . . . . 27 Obtemos assim uma cadeia decrescente |b| = r0 > r1 > r2 > . . . > rk > rk+1 > . . . ≥ 0 de inteiros não-negativos. Existe portanto um determinado n ∈ IN 0 tal que rn 6= 0 porém rn+1 = 0 . Assim, este processo termina como r n−3 = rn−2qn−1 + rn−1 com 0 < rn−1 < rn−2 r n−2 = rn−1qn + rn com 0 < rn < rn−1 r n−1 = rnqn+1 . O processo o qual acabamos de descrever, chama-se o algoritmo Euclidiano para a e b. Temos o seguinte 2.17 Teorema. No algoritmo Euclidiano para a e b temos que rn = mdc(a, b) . Em palavras: O último resto não nulo no algoritmo Euclidiano é o máximo divisor comum de a e b. Demonstração: Considerando-se a cadeia das equações estabelecidas a partir da última (r n−1 = rnqn+1), vemos que rn divide todos os restos anteriores. Finalmente, rn divide r1 e r0 = |b| e a. Isto torna rn um divisor comum de a e b. Partindo da primeira das equações com um qualquer divisor comum c de a e b vemos que c divide todos os restos, particularmente c ∣∣∣rn. Isto mostra a afirmação. 2.18 Exemplo. Determinar mdc(±7519,±8249) . Podemos nos restringir a valores positivos e encarar a = 7519 e b = 8249. O algoritmo Euclidiano dá 28 2.23 Teorema. Sejam a, b, c ∈ ZZ, a, b não ambos zero. a) A equação Diofantina ax + by = c (∗) admite pelo menos uma solução x, y ∈ ZZ se e somente se d = mdc(a, b) ∣∣∣c. b) Suponha d ∣∣∣c e seja (x 0 , y 0 ) uma solução (particular) de (∗). Então a solução geral (i. e. o conjunto de todas as soluções) de (∗) é dada por  x = x 0 + b d t y = y 0 − a d t (t ∈ ZZ) . Demonstração: a) Como d ∣∣∣a e d ∣∣∣b temos também d ∣∣∣c para qualquer posśıvel solução (x, y) de (∗). Logo, d ∣∣∣c é uma condição necessária para a solubilidade de (∗). Reciprocamente, seja d ∣∣∣c, digamos d` = c para algum ` ∈ ZZ. Por 2.9 sabemos que existem x1 , y1 ∈ ZZ com d = ax1 + by1. Segue c = a ( `x1 ) + b ( `y1 ) e vemos que (`x1 , `y1) é uma solução particular de (∗). b) Seja (x 0 , y 0 ) uma solução particular e t ∈ ZZ. Provamos primeiro que qualquer par de números  x = x 0 + bd t y = y 0 − ad t (t ∈ ZZ) satisfaz a equação também: ax + by = a(x 0 + bdt) + b(y0 − a dt) = ax0 + ab d t + by0 − ba d t = ax0 + by0 = c. Seja reciprocamente (x, y) uma qualquer solução de (∗). Temos então ax 0 +by 0 = c = ax + by e dáı a(x− x 0 ) = b(y 0 − y) . Existem r, s ∈ ZZ tais que a = rd e b = ds e vale mdc(r , s) = mdc ( a d , b d ) = 1. Segue dr(x− x 0 ) = ds(y 0 − y) e dáı r(x− x 0 ) = s(y 0 − y) , pois d 6= 0. Podemos supor a 6= 0. Concluimos r ∣∣∣s(y 0 − y) e dáı r ∣∣∣y 0 − y pois mdc(r, s) = 1. Logo existe t ∈ ZZ tal que rt = y 0 − y de onde vem y = y 0 − rt = y 0 − adt. 31 Segue r(x − x 0 ) = s(y 0 − y) = srt e então x − x 0 = st, pois r 6= 0. Isto dá x = x 0 + st = x 0 + bdt. Logo temos x = x 0 + b d t y = y 0 − a d t para algum t ∈ ZZ, como afirmado. 2.24 Exemplo. Determinar a solução geral de 54x + 21y = 906 . Solução: Temos mdc(54, 21) = 3 ∣∣∣906. Logo a equação é solúvel e simplifica para 18x + 7y = 302 (∗) com mdc(18, 7) = 1 . Temos que (2,−5) é uma solução de 18x + 7y = 1 o que dá 302 · (2,−5) = (604,−1510) como solução particular de (∗). Isto dá como solução geral x = 604 + 7t y = −1510− 18t (t ∈ ZZ). 2.25 Exemplo. Um teatro vende ingressos e cobra RS 18.− por adulto e RS 7, 50 por criança. Numa noite, arrecada-se RS 900.−. Quantos adultos e crianças assistiram ao es- petáculo, sabendo-se que eram mais adultos do que crianças? Solução. Seja x o número de crianças, y o número de adultos que assistiram. Temos que resolver então a equação Diofantina 7,5x + 18y = 900 sob a condição adicional y > x ≥ 0 . ou seja 15x + 36y = 1800 . Observando-se ainda mdc(15, 36) = 3 ∣∣∣1800, esta equivale a 5x + 12y = 600 (∗). 32 Como (120, 0) é obviamente uma solução de (∗), vemos que a solução geral de (∗) é dada por  x = 120 + 12ty = −5t (t ∈ ZZ) . De y > x ≥ 0 decorre −5t > 120 + 12t ≥ 0 e dáı −7, 05... = −120 17 > t ≥ −120 12 = −10 , ou seja, −10 ≤ t < −7, 05... , o que dá t ∈ { −10,−9,−8 } . As 3 posśıveis soluções são então: x = 0y = 50  x = 12y = 45  x = 24y = 40 . 33 Por indução concluimos r−1 = s−1 (i.e. r = s) e p2 = q2 , p3 = q3 , . . . , pr = qr . Junto com p1 = q1 isto dá a afirmação. É comum, formular o teorema fundamental da aritmética da seguinte forma: 3.3’ O teorema da decomposição primária. Para todo número 1 < n ∈ IN existem únicos primos distintos p1 , p2 , . . . , pr (os quais podemos supor em ordem natural p1 < . . . < pr) e únicos números a1 , a2 , . . . , ar ∈ IN de tal maneira que n = pa1 1 · pa2 2 · . . . · par r = r∏ k=1 pak k O produto r∏ k=1 pak k chama-se a decomposição primária de n. A quantidade dos divisores de um número n Como o conjunto dos divisores de um número n ∈ IN é finito, podemos nos in- teressar pelo tamanho deste conjunto, isto é, pela quantidade dos divisores de n. Dado n ∈ IN , vamos indicar por τ(n) = ∣∣∣ { t ∈ IN ∣∣∣ t divide n}∣∣∣ a quantidade dos divisores naturais de n. Por exemplo, temos τ(n) = 1 ⇐⇒ n = 1, τ(n) = 2 ⇐⇒ n = p é primo. Lembrando-se que t ∣∣∣n ⇐⇒ ∃, s = nt ∈ IN tal que n = st vemos que também n t divide n. Como ainda n n t = t, temos que { t ∣∣∣ t divide n} = { nt ∣∣∣ t divide n} . Por exemplo, para os divisores de 12 temos{ 1, 2, 3, 4, 6, 12 } = { 12 1 , 12 2 , 12 3 , 12 4 , 12 6 , 12 12 } . É fácil verificar a seguinte observação interessante: 36 3.4 Proposição. Para todo n ∈ IN temos ∏ t|n t = nτ(n)/2 ( = √ nτ(n) ) . Em palavras: O produto formado sobre todos os divisores positivos de n é a potência τ(n)/2-ésima de n. Demonstração: Temos∏ t|n t  2 = ∏ t|n t  · ∏ t|n n t  = ∏ t|n t · nt = ∏ t|n n = nτ(n) , pois τ(n) é a quantidade dos fatores n deste último produto. Extraindo-se ainda a ráız quadrada de ambos os lados, vemos a afirmação. Podemos determinar τ(n) também a partir da decomposição primária de n. 3.5 Observação. Seja 1 < n ∈ IN escrito na decomposição primária n = r∏ k=1 pak k com p1 , . . . , pr primos distintos, r, a1 , . . . , ar ∈ IN . Um número t ∈ IN é divisor de n se e somente se t = r∏ k=1 p`k k com 0 ≤ `1 ≤ a1 , . . . , 0 ≤ `r ≤ ar . Demonstração: Seja t = r∏ k=1 p`k k com 0 ≤ `1 ≤ a1 , . . . , 0 ≤ `r ≤ ar . Temos t · r∏ k=1 pak−`k k = r∏ k=1 p`k k · r∏ k=1 pak−`k k = r∏ k=1 pak k = n , onde r∏ k=1 pak−`k k ∈ IN , pois a k − ` k ≥ 0. Logo, t é divisor de n. Reciprocamente, qualquer divisor t de n tem que ter esta forma, pela unicidade da decomposição primária de t e n. Logo, a afirmação vale. 37 3.6 Conseqüência. Seja n ∈ IN escrito como n = r∏ k=1 pak k com p1 , p2 , . . . , pr primos distintos e a1 , a2 , . . . , ar ∈ IN. Então τ(n) = r∏ k=1 (a k + 1) . Demonstração: Pela observação 3.5 temos que os divisores t ∈ IN de n correspondem, biunivocamente, às r-uplas (`1 , `2 , . . . , `r) com 0 ≤ `1 ≤ a1 , . . . , 0 ≤ `r ≤ ar . Portanto τ(n) é a quantidade destas r-uplas. Mas, na k-ésima coordenada temos as a k + 1 possibilidades 0, 1, 2 , . . . , a k para escolhermos ` k (1 ≤ k ≤ r). Isto dá um total de (a1 + 1)(a2 + 1) · . . . · (ar + 1) ecolhas e fornece a afirmação. 3.7 Conseqüência. Seja n ∈ IN . n é um quadrado perfeito ⇐⇒ τ(n) é ı́mpar . Demonstração: Seja n = r∏ k=1 pak k a decomposição primária de n. Temos que n é um quadrado perfeito ⇐⇒ todos os expoentes a1 , a2 , . . . , ar são pares ⇐⇒ todos os a1 + 1, a2 + 1 , . . . , ar + 1 são ı́mpares ⇐⇒ o produto (a1 + 1)(a2 + 1) . . . (ar + 1) = τ(n) é ı́mpar. A decomposição primária é útil para determinar o mdce o mmcde dois números: Dados dois números n, m ∈ IN , existem primos distintos p1 , . . . , pr (os pri- mos que dividem em pelo menos um de n ou m) e expoentes não-negativos a1 , . . . , ar , b1 , . . . , br ∈ IN0 tais que, simultâneamente, n = r∏ k=1 pak k e m = r∏ k=1 pbk k . 38 Por exemplo temos [ 17 4 ] = [ 19 4 ] = 4, [√ 5 ] = 2, [π] = 3, [−π] = −4. Quando x ≥ 0 tem a forma decimal x = n, ... com n ∈ IN 0 , temos claramente [n, ...] = n. 3.10 Teorema. Para cada n ∈ IN a decomposição primária de n! é dada por n! = ∏ p∈IP pap(n) , onde os expoentes ap(n) são calculados por ap(n) = ∞∑ k=1 [ n pk ] . Observamos que esta soma ∞∑ k=1 [ n pk ] a qual é formalmente uma soma infinita, na verdade contém somente finitos somandos não-nulos, já que [ n pk ] = 0, sempre quando pk > n. Particularmente, ap(n) = 0, se p > n. Isto significa que no pro- duto (formalmente infinito) para n! na verdade aparecem automáticamente só os primos p ≤ n. Demonstração: Seja p um primo qualquer. Existe um único `1 ∈ IN0 tal que `1p ≤ n < (`1 + 1)p . Da mesma forma, existe um único `2 ∈ IN0 tal que `2p 2 ≤ n < (`2 + 1)p 2 , . . . . . . . . . . . . . . . . . . . . . . . . em geral, para todo k ∈ IN existe um único ` k ∈ IN 0 tal que ` k pk ≤ n < (` k + 1)pk . . . . . . . . . . . . . . . . . . . . . . . . . Agora, em n! aparecem `1 fatores p devido os fatores p, 2p, 3p , . . . , `1p , 41 mais `2 fatores p, ainda não contados, devidos a p2, 2p2, 3p2 , . . . , `2p 2 , . . . . . . . . . . . . . . . . . . . . . . . . mais ` k fatores p, ainda não contados, devido a pk , 2pk , 3pk , . . . , ` k pk . . . . . . . . . . . . . . . . . . . . . . . . Isto dá um total de ap(n) = `1 + `2 + . . . + `k + . . . fatores p contidos em n!. Mas, de ` k pk ≤ n < (` k + 1)pk segue ` k ≤ npk < (`k + 1), ou seja, ` k = [ n pk ] . Logo temos como afirmado ap(n) = ∞∑ k=1 [ n pk ] . Observa-se que sempre a2(n) ≥ a3(n) ≥ a5(n) ≥ . . . ≥ ap(n) ≥ aq(n) ≥ . . . se p < q . Uma conseqüência disto é, por exemplo, que n! termina em a5(n) zeros. 3.11 Exemplo. a) Em quantos zeros termina 357! ? b) Qual é a maior potência de 165 que divide em 2000! ? Respostas: a) Em a5(357) = ∞∑ k=1 [ 357 5k ] = [ 357 5 ] + [ 357 25 ] + [ 357 125 ] = 71 + 14 + 2 = 87 zeros. b) Temos 165 = 3·5·11 e vale a11(2000) = ∞∑ k=1 [ 2000 11k ] = [ 2000 11 ] + [ 2000 121 ] + [ 2000 1331 ] = 181 + 16 + 1 = 198. Logo é a 198-ésima a maior potência de 165 - e também a maior de 11 - que divide 2000! . 42 Estimativas sobre quantidades de primos 3.12 Teorema. (Euclides) O conjunto IP dos números primos é infinito. Demonstração: Suponhamos IP = { p1 , p2 , . . . , pr } fosse um conjunto finito. Consideremos o número natural n = p1 ·p2 · . . . ·pr +1. Pelo Teorema fundamental da aritmética, este n > 1 é diviśıvel por algum primo q. Pela suposição, q = p k para algum k ∈ { 1, 2 , . . . , r } . Dáı segue o absurdo que q ∣∣∣1. Logo, nenhum con- junto finito pode abranger todos os primos. 3.13 Proposição. Para o n-ésimo número primo pn vale a estimativa pn ≤ 22 n−1 . Demonstração: Para n = 1 afirma-se 2 = p1 ≤ 2 21−1 = 21 = 2 o que certa- mente é verdade. Suponhamos já provadas as desigualdades p1 ≤ 2 20 p2 ≤ 2 21 p3 ≤ 2 22 . . . . . . pn ≤ 22 n−1 . Se IP 3 q ∣∣∣p1 · p2 · . . . · pn + 1, então q > pn , particularmente, pn+1 ≤ q. Segue p n+1 ≤ p 1 · p 2 · . . . · pn + 1 ≤ 21+2+2 2+...2n−1 + 1 = 22 n−1 + 1 ≤ 22n−1 + 22n−1 = 22n . Convém observar que esta cota superior para o tamanho de pn não é muito boa. Uma cota melhor obtem-se, admitindo-se (sem demonstração) o seguinte mais profundo 43 3.22 Conseqüência. Se n ∈ IN é composto, então n é diviśıvel por algum primo p ≤ √ n. Demonstração: Podemos escolher em 3.21 b) um divisor primo p de s. Esta última observação tem importância prática na procura de números primos e é a base do chamado crivo do Eratóstenes: Desejamos deteminar os primos ≤ n para um dado 2 ≤ n ∈ IN. Para isto escreve- mos os números 2, 3, 4, 5, 6 , . . . , n . Guardamos o 2 como primo e riscamos todos os números pares 4 ≤ 2k ≤ n. Depois guardamos o 3 e riscamos todos os múltiplos de 3 com 6 ≤ 3k ≤ n. O proximo número não riscado é o primo 5. Riscamos seus múltiplos 10 ≤ 5k ≤ n e continuamos desta maneira. Vemos que, depois de riscar os múltiplos de todos os primos até o maior primo p ≤ √ n, sobram somente os números primos até n. Por exemplo, para n = 100 : Depois de riscar entre os números 2, 3, 4, 5, 6 , . . . , 100 os múltiplos (próprios) de 2, 3, 5 e 7, sobram os 25 primos 2, 3, 5, 7, 11, 13 , . . . , 83, 89, 97. Isto é claro por 3.22, pois qualquer n ≤ 100 composto é múltiplo de um dos primos 2, 3, 5, 7 ≤ 10 = √ 100. Também podemos pensar assim: Para se verificar se um dado número n é primo ou composto, só é preciso testar como posśıveis divisores os primos p ≤ √ n. Se nenhum deles divide, n será primo. Portanto, para ver se um n ≤ 100 é primo ou não, os quatro testes 2 ∣∣∣n(?), 3 ∣∣∣n(?), 5 ∣∣∣n(?), 7 ∣∣∣n(?) são suficientes, dos quais 2 ∣∣∣n(?) e 5 ∣∣∣n(?) têm resposta obvia. Da mesma maneira, somente os testes com (no máximo) os primos p ≤ 13 são suficientes para conseguir uma posśıvel decomposição de um qualquer n ≤ 200. p ≤ 31 para qualquer n ≤ 1000, p ≤ 97 para n ≤ 10000. 46 3.23 Proposição. Seja n ∈ IN ı́mpar. Entre os pares de inteiros (x, y) com 0 ≤ y < x ≤ n = x2 − y2 e os pares (r, s) com 1 ≤ s ≤ r ≤ n = rs existe uma correspondência biuńıvoca natural. Demonstração: Se n = x2 − y2 com 0 ≤ y < x ≤ n, façamos r = x + y e s = x− y e segue n = rs e 1 ≤ s ≤ r ≤ n. Seja, reciprocamente, n = rs com 1 ≤ s ≤ r ≤ n. Como n é ı́mpar, temos que r e s são ı́mpares e r±s2 são inteiros. Façamos x = r+s 2 e y = r−s 2 . Temos x, y ∈ IN0 e 0 ≤ y < x ≤ n. Além disso vale x2 − y2 = (r+s) 2−(r−s)2 4 = rs = n. 3.24 Conseqüência. Seja n ∈ IN ı́mpar. a) n possui tantas decomposições distintas n = x2 − y2 como diferença de dois quadrados quantas decomposições multiplicativas distintas n = rs ele admite. b) n é primo, se e somente se n = ( n + 1 2 )2 − ( n−1 2 )2 é a única decomposição de n como diferença de dois quadrados. 3.25 Exemplos. a) Para n = 33 = 33 ·1 = 11 ·3 temos as decomposições correspondentes como diferença de dois quadrados: 33 = 172 − 162 = 72 − 42 . b) Para n = 9 = 9 · 1 = 3 · 3 temos 9 = 52 − 42 = 32 − 02 . 47 c) Em geral, para n = pq = pq · 1 = p · q onde p ≥ q são primos, temos as decomposições correspondentes como diferença de dois quadrados: pq = ( pq + 1 2 )2 − ( pq − 1 2 )2 = ( p + q 2 )2 − ( p− q 2 )2 . d) Para n = 105 = 105 · 1 = 35 · 3 = 21 · 5 = 15 · 7 temos 105 = 632 − 622 = 192 − 162 = 132 − 82 = 112 − 42 . A descoberta de uma decomposição de um número ı́mpar n como diferença de dois quadrados pode ser favorável quando n é ”quase um quadrado perfeito”, i.e. quando n = rs com y = r − s ”pequeno”. Isto pode servir para descobrir a de- composição primária de um tal número. Vejamos alguns exemplos: Queremos descobrir se o número n = 2438323 é primo ou não. Temos √ n = 1561, 51... e as tentativas se este n é diviśıvel por algum primo p ≤ 1561, é decepcionante, experimentando-se com p = 3, 7, 11, 13 , . . . . Escrevendo-se porém y2 = x2 − n, começando com x = 1562, vemos na hora que x2 − n é de fato um quadrado perfeito y2 com y = 39. Isto nos dá a decomposição n = (1562 + 39)(1562 − 39) = 1601 · 1523. Esta é a decomposição completa de n, pois 1523 e 1601 são realmente primos (senão n já teria sido diviśıvel por algum p ≤ 37). Para ganhar a decomposição de n = 17 473, calculamos √ n = 132, 18... e as colocações x = 133, 134, 135 . . . mostram na quinta tentativa para x = 137 que realmente 1372 − n = 362. Mais uma vez descobrimos a decomposição n = (137 + 36)(137− 36) = 173 · 101. Se n = p(p+2) é por exemplo (sem que se tenha conhecimento antecipado disso!) o produto dos primos de um gêmeo, este método - observando-se p < √ n = √ p(p + 2) < √ p2 + 2p + 1 = p + 1 - fornece logo no primeiro passo para x = p + 1: (p + 1)2 − n = (p + 1)2 − p(p + 2) = 12 , ou seja, a decomposição n = [ (p + 1) + 1 ] · [ (p + 1)− 1 ] . Mais algumas observações com respeito a números primos. 48 Demonstração do Exemplo 3.30: Suponhamos IP = IP ∩ { 4n+3 ∣∣∣ n = 0, 1, 2, 3 , ...} é finito, digamos IP = { p1 =3, p2 =7 , . . . , pr } . Consideremos o número N = 4p1p2...pr − 1 = 4(p1p2...pr − 1) + 3 > 1 e seja N = q1 · q2 · . . . · qs com primos q1 , . . . , qs ∈ IP . Todo número ı́mpar é da forma 4k + 1 ou 4k + 3. Como N é da forma 4` + 3, por 3.31, nem todo qi pode ter a forma 4k i + 1, ou seja, existe um qi ∈ IP , digamos qi = pj . Mas então segue qi ∣∣∣4p1...pr −N = 1, um absurdo. Logo, IP não pode ser finito. Polinômios e primos Queremos encerrar este parágrafo, pensando sobre o natural desejo de escrever o n-ésimo número primo pn como uma função transparente de n. Será que existe alguma expressão polinomial f(n) = asn s + a s−1n s−1 + . . . + a1n + a0 com coe- ficientes inteiros, que forneça a seqüência dos números primos - ou pelo menos - forneça somente primos? O seguinte exemplo é interessante neste contexto. 3.32 Exemplo. Para f(n) = n2 + n + 41 temos f(n) ∈ IP para todo n = 1, 2, 3 , . . . , 39 . Entretanto, f(40) = 412 e f(41) = 41 · 43. A resposta geral é decepcionante: Nenhum polinômio (não constante) pode as- sumir somente números primos, como mostra 3.33 Proposição. Seja f(n) = asn s + a s−1n s−1 + . . . + a1n + a0 uma expressão polinomial com coeficientes a0 , a1 , . . . , as ∈ ZZ e as > 0, s ≥ 1. Então a seqüência ( f(n) ) n∈IN assume infinitos valores naturais compostos. Demonstração: Claro que f(n) pode assumir somente finitos valores negativos, pois as > 0. Se f(n) sempre é composto, não há nada para provar. Podemos supor 51 então que exista n 0 ∈ IN tal que f(n 0 ) = p é primo e f(n) > 0 para n ≥ n 0 . Para todo t ∈ IN temos f(n 0 + tp) = as(n0 + tp) s + . . . + a1(n0 + tp) + a0 = = asn s 0 + . . . + a1n0 + a0 + ktp = p(1 + kt) com kt ∈ IN apropriado. Segue que os valores f(n 0 + tp) = p(1 + kt) com t ∈ IN são números compostos. Como kt = asp sts ± . . . assume infinitos valores naturais distintos quando t ∈ IN , concluimos a afirmação. 52 § 4 Triplos Pitagóricos e a conjetura de Fermat Triplos Pitagóricos 4.1 Definição. Um triplo de números naturais (x, y, z) chama-se um triplo Pitagórico se x2 + y2 = z2 . O triplo (x, y, z) chama-se primitivo se mdc(x, y, z) = 1 (é claro como o mdc de mais de dois números deve ser entendido). 4.2 Exemplo. (4, 3, 5) , (8, 6, 10) , . . . , (4n, 3n, 5n) , . . . (12, 5, 13), (24, 10, 26) , . . . , (12n, 5n, 13n) , . . . são triplos Pitagóricos, sendo que (4, 3, 5) e (12, 5, 13) são primitivos. É imediata a seguinte 4.3 Observação. Com qualquer triplo Pitagórico ( x1 , y1 , z1 ) (primitivo) e qualquer n ∈ IN , também ( nx1 , ny1 , nz1 ) é um triplo Pitagórico. Para n > 1 estes últimos não são primitivos. Também reciprocamente temos 4.4 Observação. Seja (x, y, z) um qualquer triplo Pitagórico, d = mdc(x, y, z) e ponhamos x1 = x d , y1 = y d , z1 = z d . Então ( x1 , y1 , z1 ) é um triplo Pitagórico primi- tivo e vale (x, y, z) = (dx1 , dy1 , dz1). Demonstração: É claro que mdc(x1 , y1 , z1) = 1 e vale (x, y, z) = ( dx1 , dy1 , dz1 ) . Além disso, x2 1 + y2 1 = ( x d )2 + ( y d )2 = x2 + y2 d2 = ( z d )2 = z2 1 , mostrando que( x1 , y1 , z1 ) é triplo Pitagórico primitivo. 53 Demonstração: a) Temos x2+y2 = (2st)2+(s2−t2)2 = 4s2t2+s4+t4−2s2t2 = s4+2s2t2+t4 = (s2+t2)2 = z2, mostrando que (x, y, z) é um triplo Pitagórico. Suponha p ∣∣∣mdc(x, y, z) para algum primo p. Então p é ı́mpar e de p ∣∣∣2st segue que p ∣∣∣s ou p ∣∣∣t. De z = s2 + t2 (ou de y = s2 − t2) segue então que p ∣∣∣s e p ∣∣∣t , dando o absurdo p ≤ mdc(s, t) = 1. Assim, (x, y, z) é um triplo primitivo. b) Seja (x, y, z) um qualquer triplo Pitagórico primitivo com x par, y ı́mpar. Temos x2 = z2 − y2 = (z + y)(z − y) e dáı IN 3 x 2 4 = z + y 2 · z − y 2 . Então ( x 2 )2 = uv com u = z + y 2 e v = z − y 2 . Se d = mdc(u, v), então d ∣∣∣u ± v. Mas, u + v = z + y 2 + z − y 2 = z e u − v = z + y 2 − z − y 2 = y, dando d ∣∣∣mdc(y, z). Por 4.6 sabemos mdc(y, z) = 1 pois (x, y, z) é primitivo. Logo mdc(u, v) = 1. Concluimos por 4.7 que u e v são individualmente quadrados perfeitos. Coloque- mos u = s2 e v = t2 com s, t ∈ IN. Temos então mdc(s, t) = mdc(u, v) = 1 e s − t é ı́mpar. Além disso, s2 − t2 = u − v = y e s2 + t2 = v + u = z. De x2 4 = uv = t2s2 segue x = √ 4t2s2 = 2st. 4.9 Conseqüência. Os triplos Pitagóricos, primitivos e não-primitivos, são obtidos por( 2nst, n(s2 − t2), n(s2 + t2) ) onde n, s, t ∈ IN com s > t ≥ 1, mdc(s, t) = 1, s− t ı́mpar. Num qualquer triplo Pitagórico primitivo (x, y, z), x é múltiplo de 4 e y é ı́mpar > 1. Os triplos Pitagóricos primitivos são numerosos, como mostra 4.10 Proposição. a) Qualquer número ı́mpar > 1 é o y de pelo menos um triplo Pitagórico primitivo. b) Todo número natural diviśıvel por 4 é o x de pelo menos um triplo Pitagórico primitivo. 56 Demonstração: a) Se y = 2k − 1 = s2 − t2 > 1 é dado, podemos resolver s + t = 2k − 1 e s− t = 1, obtendo que s = k e t = k − 1. Assim,( 2k(k − 1), 2k − 1, 2k(k − 1) + 1 ) é um exemplo para um triplo primitivo com y dado. b) Se x = 4k = 2st é dado, podemos considerar s = 2k e t = 1 e obtemos( 4k, 4k2 − 1, 4k2 + 1 ) como triplo primitivo com x dado. Para y > 1 ı́mpar obtemos tantos triplos primitivos (· , y, ·) quantas existem decomposições multiplicativas y = k` com mdc(k, `) = 1 (compare 3.24). Par- ticularmente temos 4.11 Exemplo. Para qualquer primo p > 2, o único triplo Pitagórico da forma (· , p, ·) é( p2 − 1 2 , p, p2 + 1 2 ) . Ele necessariamente é primitivo. 4.12 Exemplo. a) Para qualquer primo p > 2 dado, os triplos Pitagóricos da forma( · , p2, · ) são: Um único não-primitivo p · ( p2 − 1 2 , p , p2 + 1 2 ) , e um único primitivo ( p4 − 1 2 , p2, p4 + 1 2 ) . e em geral: b) Para qualquer primo p > 2 e n ∈ IN dados, os triplos Pitagóricos da forma (· , pn, ·) são: Um único primitivo ( p2n − 1 2 , pn, p2n + 1 2 ) . 57 e n− 1 não-primitivos pn−k · ( p2k − 1 2 , pk , p2k + 1 2 ) , obtidos para k = 1, 2, . . . , n−1. 4.13 Exemplo. Para quaisquer dois primos 2 < q < p, os triplos da forma (· , pq, ·) são: Dois não-primitivos p · ( q2 − 1 2 , q , q2 + 1 2 ) e q · ( p2 − 1 2 , p , p2 + 1 2 ) e dois primitivos( p2q2 − 1 2 , pq , p2q2 + 1 2 ) e ( p2 − q2 2 , pq , p2 + q2 2 ) . Demonstrações: Exerćıcio. A conjetura de Fermat A conjetura de Fermat (também: o ”último Teorema” de Fermat) afirma que a equação Diofantina xn + yn = zn não é solúvel por nenhum triplo (x, y, z) com x, y, z ∈ IN se n ≥ 3. Demonstraremos esta afirmação no caso 4 ∣∣∣n, já provado pelo próprio Pierre de Fermat (1601-1665). Mencionamos que, o enigma desta conjetura de Fermat, entretanto e finalmente em 1994/95, depois de ocupar as mentes matemáticas mais capacitadas por mais de 350 anos, tem sido provado pelo matemático Andrew Wiles. Ver na revista Annals of Mathematics, 142 (1995), os artigos: Modular eliptic curves and Fermat’s Last Theorem, pgs. 443-551, de A. Wiles e Ring-theoretic properties of certain Hecke algebras, pgs. 553-572, de Richard Taylor e A. Wiles. 58 § 5 Números deficientes - abundantes - perfeitos e de Mersenne Números deficientes, abundantes e perfeitos Além da função τ(n), da quantidade dos divisores de n, introduzimos agora 5.1 Definição. Para todo n ∈ IN indicamos por σ(n) = ∑ t|n t a soma de todos os divisores naturais de n. 5.2 Exemplo. σ(1) = 1, σ(p) = p + 1, se p é primo, σ(6) = 1 + 2 + 3 + 6 = 12, σ(12) = 1 + 2 + 4 + 3 + 6 + 12 = 28. 5.3 Proposição. Seja n = pa para algum primo p e a ∈ IN 0 . Então σ(pa) = pa+1 − 1 p− 1 . Demonstração: Temos que { 1, p, p2, . . . , pa } são os divisores deste n. Logo, por 1.4 σ(pa) = ∑ t|n t = a∑ k=0 pk = pa+1 − 1 p− 1 . É claro que σ(n) = 1 + n + . . . ≥ n + 1 > n para todo n ≥ 2. Também: σ(n) = n + 1 ⇐⇒ n = p é primo. Procuramos classificar os números naturais agora sob o aspecto de comparar σ(n) com n, pela seguinte 61 5.4 Definição. Um número n ∈ IN chama-se a) deficiente, se σ(n) < 2n b) abundante, se σ(n) > 2n c) perfeito, se σ(n) = 2n. 5.5 Exemplos. n = 15 : σ(15) = 24 2n = 30 σ(15) < 2 · 15 . Portanto, 15 é deficiente. n = 12 : σ(12) = 28 2n = 24 σ(12) > 2 · 12 . Portanto, 12 é abundante. n = 6 : σ(6) = 12 2n = 12 σ(6) = 2 · 6 . Portanto, 6 é perfeito. De verificação imediata é (fazer o gráfico da função !): 5.6 Observação. A função real y = x x− 1 é decrescente e vale 1 < x x− 1 ≤ 2 para x ≥ 2 . 5.7 Proposição. a) Se p é primo e a ∈ IN , então pa é deficiente. b) 3 · 2k é abundante para todo k ≥ 2. Demonstração: a) Usando-se 5.3 e 5.6, obtemos σ(pa) = ∑ t|pa t = pa+1 − 1 p− 1 < pa+1 p− 1 = pa · p p− 1 ≤ 2 · pa . b) σ ( 3 · 2k ) = 1 + 2 + 4 + . . . + 2k−1 + 2k + 3 + 3 · 2 + 3 · 4 + . . . + 3 · 2k = (1 + 3) · (1 + 2 + . . . + 2k) = 4 · ( 2k+1 − 1 ) = 2 · 2k ( 4− 1 2k−1 ) > 2 · ( 2k · 3 ) , pois k ≥ 2 . 62 5.8 Proposição. Sejam 2 < p < q primos. Então, para todos os a, b ∈ IN , o número n = pa · qb é deficiente. Demonstração: σ(n) = = 1 + p + . . . + pa + q(1 + p + . . . + pa) + . . . + qb(1 + p + . . . + pa) = (1 + p + . . . + pa)(1 + q + . . . + qb) = pa+1 − 1 p− 1 · q b+1 − 1 q − 1 < pa+1qb+1 (p− 1)(q − 1) = = paqb · pq (p− 1)(q − 1) = n · p p− 1 · q q − 1 ≤ n · 3 3− 1 · 5 5− 1 = 15 8 n < 2n , usando-se que a função x x− 1 é decrescente (5.6) e p ≥ 3, q ≥ 5. 5.9 Observação. Sejam n, m ∈ IN com mdc(m, n) = 1. Então a) d ∣∣∣mn ⇐⇒ d = st com s ∣∣∣n e t ∣∣∣m. b) Se s1, s2 ∣∣∣n e t1, t2 ∣∣∣m e se s1t1 = s2t2, então s1 = s2 e t1 = t2. (i.e. os divisores de mn são obtidos de forma única, por combinação dos divisores de n com os de m.) Demonstração: a) ” ⇐ ” é claro. ” ⇒ ” : Sejam n = r∏ k=1 pak k e m = r ′∏ k=1 qbk k as decomposições primárias de n e m. Como mdc(m,n) = 1, temos que mn = pa1 1 · . . . · par r · qb1 1 · . . . · qbr ′r ′ é a decom- posição primária de mn. Portanto, se d ∣∣∣mn, então d = p`1 1 · . . . · p`r r qu1 1 · . . . · qur ′ r ′ com 0 ≤ `1 ≤ a1, . . . , 0 ≤ `r ≤ ar , 0 ≤ u1 ≤ b1, . . . , 0 ≤ ur ′ ≤ br ′ . Com s = p`1 1 · . . . · p`r r e t = qu1 1 · . . . · qur ′ r ′ temos assim d = st, s ∣∣∣n e t ∣∣∣m. b) Também este item é fácilmente verificado pela comparação das decomposições primárias de s1t1 e s2t2. 63 Na terceira coluna da seguinte tabela temos os primeiros números perfeitos : k 2k − 1 2k−1 ( 2k − 1 ) 2 3 6 3 7 28 5 31 496 7 127 8128 13 8191 33550336 17 131071 65536 · 131071 19 524287 262144 · 524287 31 231 − 1 230 ( 231 − 1 ) ... ... ... 44497 244497 − 1 244496 ( 244497 − 1 ) ... ... ... Ver também Ex. 7.6. Devemos mencionar aqui que é desconhecido se existe algum número perfeito ı́mpar. Para os maiores números perfeitos, hoje explicitamente conhecidos, ver a Nota no final deste parágrafo 5. Números de Mersenne Para o estudo dos números perfeitos, acabamos de ver que os números da forma 2k − 1 são de fundamental importância. 5.13 Definição. Os números da seqüência ( 2k − 1 ) k≥2 chamam-se os números de Mersenne. Colocamos M k = 2k − 1 k = 2, 3, 4, . . . . Assim, a seqüência dos números de Mersenne começa como( M k ) k≥2 = ( 3, 7, 15, 31, 63, 127, 255, 511, 1023 , . . . , 2k−1 , . . . ) . 66 Particularmente interessa, quando um M k é primo. Uma condição necessária para que M k possa ser primo, é dada na 5.14 Proposição. Se M k fôr primo, então k = p é primo . Esta condição necessária certamente não é suficiente, pois M11 = 2047 = 23 · 89 não é primo, apesar de k = 11 ser primo. A demonstração de 5.14 é conseqüência da seguinte 5.15 Observação. Sejam 2 ≤ a, k ∈ IN . Se ak − 1 fôr primo, então a = 2 e k é primo. Demonstração: Temos (fazendo-se k − 1 = n em 1.4): ak − 1 = (a− 1) ( 1 + a + a2 + . . . + ak−1 ) com (1 + a + ... + ak−1) > 1, pois k ≥ 2. Ora, se ak − 1 fôr primo, concluimos a− 1 = 1, ou seja, a = 2. Seja k = rs composto com 1 < s ≤ r < k. Temos (com a = 2r e n + 1 = s em 1.4) a decomposição 2k − 1 = (2r − 1) ( 1 + 2r + 22r + . . . + 2(s−1)r ) na qual 2r − 1 > 1 e 1 + 2r + ... + 2(s−1)r > 1, pois s > 1. Logo 2k − 1 não é primo quando k é composto. Assim, { M k ∣∣∣ 2 ≤ k ∈ IN } ∩ IP = {M k ∣∣∣ k ∈ IP } ∩ IP i. e. ao procurar primos M k na seqüência dos números de Mersenne, somente os ı́ndices k=p primos interessam. 67 5.16 Definição. Um número Mp com p ∈ IP chama-se um primo de Mersenne se Mp fôr primo. 5.17 Exemplo. Os primeiros primos de Mersenne para p = 2, 3, 5, . . . são: M2 =3, M3 =7, M5 = 31, M7 = 127, M13 = 8191, M17 = 131071, M19 = 524287, M31 . . . . Entretanto, 23 ∣∣∣M11, 47 ∣∣∣M23, 233 ∣∣∣M29, 223 ∣∣∣M37, . . .. Ainda mencionamos o resultado de Cole (1902): M67 = 193707721 · 761838257287 onde 193707721 é o menor divisor primo de M67 ! Mais propriedades de divisibilidade dos números de Mersenne conheceremos nos próximos parágrafos em conexão com os teoremas de Fermat e de Wilson e as congruências quadráticas. Nota : Mencionamos que, em Maio de 2004, para p = 24 036 583 , o 41o e por enquanto maior primo de Mersenne Mp = 2 24 036 583 − 1 foi encontrado por Josh Findley. Ele possui entre 7 e 8 milhões de d́ıgitos (pois log10 2 24 036 583 = 24 036 583 · log10 2 = 24 036 583 · 0, 3010 ≈ 7, 235 · 106 !). O número perfeito correspondente - com mais de 14 milhões de d́ıgitos - é P = 224 036 582 · (224 036 583 − 1) . O penúltimo (40o ) primo de Mersenne foi encontrado em Novembro de 2003 por Michael Shafer para p = 20 996 011 : M20 996 011 = 2 20 996 011 − 1 . 68 6.8 Observação. Sejam n ∈ IN , q0 , q1 , . . . , qn−1 ∈ ZZ. Então{ nq0 , nq1+1 , . . . , nqn−1+(n−1) } é um sistema completo de reśıduos mod n. Além disso, todo sistema completo de restos mod n é obtido desta forma. 6.9 Teorema. (Propriedades fundamentais das congruências) Sejam n ∈ IN , a, b, c, d ∈ ZZ. O seguinte vale: a) a ≡ a mod n b) Se a ≡ b mod n, então b ≡ a mod n. c) Se a ≡ b mod n e b ≡ c mod n, então a ≡ c mod n. d) Se a ≡ b mod n e c ≡ d mod n, então a + c ≡ b + d e ac ≡ bd mod n. Demonstração: Estas propriedades são fácilmente verificadas a partir da definição e deixaremos os detalhes ao leitor. Provemos, por exemplo o item d): a ≡ b e c ≡ d mod n significa que existem q1 , q2 ∈ ZZ tais que nq1 = a − b e nq2 = c − d. Segue (a + c) − (b + d) = (a− b) + (c− d) = n(q1 + q2), i. e. a + c ≡ b + d mod n. Também ac − bd = ac − cb + cb − bd = c(a − b) + b(c − d) = n(cq1 + bq2), ou seja ac ≡ bd mod n. Particularmente, de a ≡ b mod n seguem a + c ≡ b + c e ac ≡ bc mod n e também ak ≡ bk mod n para todo k ∈ IN. Estas regras dizem que congruências mod n se comportam (mantendo-se um certo cuidado em relação ao cancelamento de fatores comuns [ver 6.16/6.17] e com potências de expoentes negativos), como se fossem igualdades. Vejamos a utilidade do cálculo com congruências em alguns exemplos. 71 6.10 Exemplos. a) 233 ∣∣∣M29 = 229 − 1. b) 107 ∣∣∣M53 + 2 = 253 + 1. Demonstração: a) De 28 = 256 ≡ 23 mod 233 segue 216 = (28)2 ≡ 232 = 529 ≡ 63 mod 233. Dáı 224 = 28 · 216 ≡ 23 · 63 ≡ 51 mod 233 e finalmente 229 = 224 · 25 ≡ 51 · 32 ≡ 1 mod 233. Mas isto significa exatamente 233 ∣∣∣229 − 1. b) De maneira semelhante concluimos: De 27 = 128 ≡ 21 mod 107 segue 214 = (27)2 ≡ 212 = 441 ≡ 13 mod 107 e 228 = (214)2 ≡ 132 = 169 ≡ 62 mod 107. Dáı 242 = 214 · 228 ≡ 13 · 62 ≡ 57 mod 107 e finalmente 253 = 27 · 24 · 242 ≡ 21 · 16 · 57 ≡ 15 · (−50) ≡ −1 mod 107. Assim 107 ∣∣∣253 + 1. Algumas congruências módulo 10, 100, 1000 , . . . 6.11 Proposição. Para k ≥ 2 coloquemos R k = 2k−1(2k − 1) . a) Se k ≡ 1 mod 4, então R k termina em 6. b) Se k ≡ 3 mod 4, então R k termina em 28. Demonstração: a) Afirma-se R k ≡ 6 mod 10 desde que k ≡ 1 mod 4: Temos então k = 4` + 1 para algum ` ≥ 1 e segue R k = 24`(24`+1 − 1) = 16`(2 · 16` − 1) ≡ 6`(2 · 6` − 1) ≡ 6(12− 1) ≡ 6 · 1 = 6 mod 10. b) Afirma-se R k ≡ 28 mod 100 desde que k ≡ 3 mod 4: Temos então k = 4` + 3 para algum ` ≥ 0. Escrevemos ainda ` = 5t + r com r ∈ { 0, 1, 2, 3, 4 } . Observando-se 165 ≡ 76 ≡ 76t mod 100 para todo t ≥ 1, obtemos mod 100 : R k = 24`+2(24`+3 − 1) = 4 · 16`(8 · 16` − 1) = 4 · 165t+r(8 · 165t+r − 1) ≡ 72 ≡ 4 · 76 · 16r(8 · 76 · 16r − 1) ≡ 4 · 16r(8 · 16r − 1) ≡  4 · 7 = 28 se r = 0 64 · 27 ≡ 28 se r = 1 24 · 47 ≡ 28 se r = 2 84 · 67 ≡ 28 se r = 3 44 · 87 ≡ 28 se r = 4 . Assim, R k ≡ 28 mod 100 em todos os 5 casos de r. Observamos que, por 5.12, particularmente os números perfeitos pares têm a forma dos R k em 6.11. Portanto temos: 6.12 Conseqüência. Todo número perfeito par termina em 6 ou 28. 6.13 Exemplo. Quais são os últimos 1, 2, 3, 4 , . . . d́ıgitos de n = 1! + 2! + 3! + 4! + . . . + 100! ? Solução: Como 10 ∣∣∣k! para k ≥ 5, o último digito de n é o mesmo de 1! + 2! + 3! + 4! ≡ 3 mod 10. Os últimos 2 digitos de n são os de 1!+2!+3!+ . . .+9!, pois 100 ∣∣∣k! para k ≥ 10. Mas, 1! + 2! + . . . + 9! ≡ 33 + 20 + 20 + 40 + 20 + 80 ≡ 13 mod 100. 1! + 2! + . . . + 100! ≡ 1! + 2! + . . . + 14! ≡ 313 mod 1000 etc. Congruências lineares 6.14 Definição. Dado n ∈ IN . Uma congruência linear é uma congruência da forma ax ≡ b mod n onde a, b ∈ ZZ são dados e as soluções x ∈ ZZ são procuradas. Por exemplo: 2x ≡ 5 mod 6: Não tem solução, enquanto 4x ≡ 2 mod 6: Possui duas soluções incongruentes x ≡ 2 e x ≡ 5 mod 6. Sobre as soluções das congruências lineares vale 73 x ≡ a1 mod n1 x ≡ a2 mod n2 x ≡ a3 mod n3 ... ... ... x ≡ ar mod nr possuem uma solução simultânea. Além disso, quaisquer duas soluções são congruentes módulo o produto n1 · n2 · . . . · nr . Demonstração: Coloquemos N = n1n2 . . . nr e para todo k = 1, 2 , . . . , r : N k = r∏ k 6=j=1 n j = n1 . . . nk−1nk+1 . . . nr (1 ≤ k ≤ r) , isto é, N1 = N n 1 , N2 = N n 2 , . . . , Nr = N nr . Para todo k = 1, 2 , . . . , r temos mdc ( N k , n k ) = 1, pois os n1 , . . . , nr são relativamente primos em pares ( IP 3 p ∣∣∣N k = n1...nk−1nk+1...nr =⇒ p ∣∣∣n j para algum j 6= k =⇒ p†n k ) .Logo, a congruência N k x ≡ 1 mod n k possui uma solução. Seja x k ∈ ZZ, tal que N k x k ≡ 1 mod n k (1 ≤ k ≤ r). Afirmamos que x = N1x1a1 + N2x2a2 + . . . + Nrxrar é uma solução simultânea das congruências. De fato: Para todo k = 1, 2, 3 , . . . , r temos: Como n k divide N1 , N2 , . . . , Nk−1 , Nk+1 , . . . , Nr segue x ≡ 0 + ... + 0 + N k x k a k + 0 + ... + 0 ≡ 1 · a k = a k mod n k . Como N ≡ 0 mod n1 , N ≡ 0 mod n2 , . . . , N ≡ 0 mod nr , qualquer número que difere de x por um múltiplo de N é solução simultânea das congruências também. Reciprocamente, se x̄ ∈ ZZ é uma qualquer solução das congruências, então x̄ ≡ a k ≡ x mod n k e assim n k ∣∣∣x̄ − x para todo k = 1, 2, . . . , r. Concluimos x̄ ≡ x mod n1n2...nr , pois os n1 , n2 , . . . , nr são relativamente primos em pares e portanto, seu minimo múltiplo comum é seu produto. 76 6.19 Exemplo. Determinar os números n ∈ ZZ com |n| ≤ 12, 4×106, que deixam simultâneamente os restos 37, 54, 17 e 100 quando divididos respectivamente, por 40, 63, 23 e 143. Solução: Temos r = 4, a1 = 37, a2 = 54, a3 = 17, a4 = 100, n1 = 40, n2 = 63, n3 = 23, n4 = 143 e devemos resolver as congruências simultâneas x ≡ 37 mod 40 x ≡ 54 mod 63 x ≡ 17 mod 23 x ≡ 100 mod 143 . Como os n1 , n2 , n3 , n4 são relativamente primos, dois a dois, existe uma solução a qual é determinada módulo N = 40 · 63 · 23 · 143 = 8288280. Calculamos N1 = N 40 = 207207 N2 = N 63 = 131560 N3 = N 23 = 360360 N4 = N 143 = 57960 . As congruências  N1x ≡ 1 mod n1 N2x ≡ 1 mod n2 N3x ≡ 1 mod n3 N4x ≡ 1 mod n4 são  207207x ≡ 1 mod 40 131560x ≡ 1 mod 63 360360x ≡ 1 mod 23 57960x ≡ 1 mod 143 as quais se reduzem para  7x ≡ 1 mod 40 16x ≡ 1 mod 63 19x ≡ 1 mod 23 45x ≡ 1 mod 143 . Suas soluções são  x1 ≡ 23 mod 40 x2 ≡ 4 mod 63 x3 ≡ 17 mod 23 x4 ≡ 89 mod 143 . Uma solução simultânea é então x = N1x1a1 + N2x2a2 + N3x3a3 + N4x4a4 = 207207 · 23 · 37 + 131560 · 4 · 54 + 360360 · 17 · 17 + 57960 · 89 · 100 ≡ 4198437 ≡ 12486717 ≡ −4089843 ≡ −12378123 mod 8288280. Os números procurados n com |n| ≤ 12, 4× 106 são portanto: n = 4198437, n = −4089843 e n = −12378123 . 77 § 7 Os Teoremas de Fermat e de Wilson Queremos tratar neste parágrafo algumas propriedades referentes a congruências módulo números primos. O pequeno teorema de Fermat O primeiro resultado neste contexto é: 7.1 Teorema. (O ”pequeno teorema” de Fermat) Seja p ∈ IP e a ∈ ZZ de tal maneira que p†a. Então ap−1 ≡ 1 mod p . Demonstração: Dados p e a com p†a, consideremos os conjuntos{ 1, 2, 3 , . . . , p−1 } e { a, 2a, 3a , . . . , (p−1)a } . Temos a, 2a , . . . , (p−1)a 6≡ 0 mod p. Se i, j ∈ { 1, 2 , . . . , p−1 } e ia ≡ ja mod p, concluimos i ≡ j mod p, já que mdc(a, p) = 1. Então i = j, pois 0 ≤ |i− j | < p. Isto significa que os números a, 2a , . . . , (p−1)a são incongruentes entre si mod p. Logo, os a, 2a, . . . , (p−1)a são congruentes, em alguma ordem, aos 1, 2 , . . . , p−1. Podemos concluir então que (p− 1)! = 1 · 2 · 3 · . . . · (p−1) ≡ a · 2a · 3a · . . . · (p−1)a , ou seja (p− 1)! ≡ ap−1 · (p−1)! mod p . Como mdc(p, (p−1)!) = 1, por 6.17 podemos cancelar nesta congruência o fator (p− 1)! e obtemos, como afirmado, ap−1 ≡ 1 mod p . 7.1’ Teorema de Fermat (2a formulação ). Para qualquer primo p e qualquer a ∈ ZZ temos ap ≡ a mod p 78 Outra vez, por 7.3: p = k 0 ∣∣∣q − 1. Logo, existe ` ∈ IN com p` = q − 1, ou seja, q = p` + 1. Como p, q são ı́mpares, concluimos que ` = 2k é par. Assim, q = 2kp + 1. 7.5 Exemplos. a) q ∣∣∣M11 =⇒ q = 22k + 1. De fato: M11 = 23 · 89 com  23 = 22 · 1 + 189 = 22 · 4 + 1 b) q ∣∣∣M29 =⇒ q = 58k + 1. De fato: M29 = 233 · 1103 · 2089 com  233 = 58 · 4 + 1 1103 = 58 · 19 + 1 2089 = 58 · 36 + 1 c) (Ver Ex. 5.15) q ∣∣∣M67 =⇒ q = 134k + 1. De fato: M67 = 193707721 · 761838257287 com  193707721 = 134 · 1445580 + 1761838257287 = 134 · 5685360129 + 1 7.6 Exemplo. Os números de Mersenne M13 , M17 e M19 são primos . Demonstração: Para M13 : Temos √ M13 = 90, 5.... Um posśıvel divisor primo q próprio de M13 é ≤ 89 e da forma 26k + 1. As únicas possibilidades são q = 53 e q = 79 que ambos não dividem M13 = 8191. Para M17 : Temos √ M17 = 362, 03.... Um posśıvel divisor primo q próprio de M17 é ≤ 359 e da forma 34k + 1. As únicas possibilidades são q ∈ { 103, 137, 239, 307 } que todos não dividem M17 = 131071. Para M19 : Temos √ M19 = 724, 07.... Um posśıvel divisor primo q próprio de M19 é ≤ 724 e da forma 38k + 1. As únicas possibilidades são q ∈ { 191, 229, 419, 457, 571, 647 } que todos não dividem M19 = 524287. 81 7.7 Conseqüência. Qualquer posśıvel divisor t de Mp = 2 p − 1 (inclusive 1 e o próprio número Mp) é da forma t = 2kp + 1 com algum k ∈ IN. Demonstração: Produtos de números da forma 2kp + 1 (i.e. números ı́mpares ≡ 1 mod p) continuam da mesma forma. Qualquer t ∣∣∣Mp é produto de primos desta forma. (Observe que, como p ∣∣∣2p − 2 temos para o próprio Mp : 2p − 1 = 2p − 2 + 1 = 2kp + 1 !) 7.8 Exemplo. A decomposição completa de M23 é M23 = 47 · 178481 , pois, qualquer posśıvel divisor primo q próprio de 178481 é da forma q = 46k + 1 e q ≤ 422, 47.... Isto dá q ∈ { 47, 139, 277 } que não dividem 178481. O teorema de Wilson Mais uma congruência básica módulo números primos é dada no 7.9 Teorema. (Wilson) Para todo primo p vale (p− 1)! ≡ −1 mod p . 7.10 Proposição. Seja p > 2 um primo e a, b ∈ ZZ. a) a2 ≡ b2 mod p ⇐⇒ a ≡ ±b mod p. b) a2 ≡ 1 mod p ⇐⇒ a ≡ ±1 mod p. Demonstração: a) ”⇐ ”: De a ≡ ±b mod p segue a2 ≡ (±b)2 = b2 mod p. ” ⇒ ”: De a2 ≡ b2 mod p segue b2 − a2 = (b − a)(b + a) ≡ 0 mod p, ou seja, 82 p ∣∣∣(b − a)(b + a). Dáı p ∣∣∣b−a ou p ∣∣∣b + a, pois p é primo. Isto significa a ≡ b ou a ≡ −b mod p. b) É o caso particular b ≡ 1 mod p de a). (Lembremos que uma tal conclusão não poderia ser feita se o módulo não é primo: módulo 8 temos por exemplo: 12 ≡ 32 ≡ 52 ≡ 72 ≡ 1 apesar de 3, 5 6≡ ±1 mod 8!) 7.11 Observação. Seja p > 2 um primo e seja 2 ≤ a ≤ p− 2. Então existe um único b ∈{ 2 , . . . , p−2 } tal que ab ≡ 1 mod p. Além disso, a 6= b. Demonstração: A congruência ax ≡ 1 mod p possui uma única solução x = b ∈ { 1, 2 , . . . , p−1 } . Necessáriamente, b 6= 1 e b 6= p−1, pois a 6≡ ±1 mod p. Portanto 2 ≤ b ≤ p−2. Por 7.10 temos também a 6≡ b mod p, i.e. a 6= b. Estamos agora em condições para provar o Teorema de Wilson. Demonstração de 7.9: Escrevemos o conjunto { 2 , . . . , p−2 } sob o aspecto de 7.11: ∀ a ∈ { 2 , . . . , p−2 } ∃ único b ∈ { 2 , . . . , p−2 } com ab ≡ 1 mod p e a 6= b. Podemos então reordenar o conjunto { 2 , . . . , p−2 } como { 2 , . . . , p−2 } = { a1 , b1 , a2 , b2 , . . . , ap−3 2 , bp−3 2 } , onde a1b1 ≡ a2b2 ≡ . . . ≡ ap−3 2 bp−3 2 ≡ 1 mod p . Segue (p− 1)! = 1 · 2 · . . . · (p−1) = 1 · ( a1b1 ) · ( a2b2 ) · . . . · ( ap−3 2 bp−3 2 ) (p−1) ≡ ≡ 1 · 1 · 1 · . . . · 1 · (p−1) ≡ −1 mod p . 83 { 12, 22 , . . . , (p−2)2 , (p−1)2 } = = { 12, 22 , . . . , ( p−3 2 )2 , ( p−1 2 )2 , ( p+1 2 )2 , ( p+3 2 )2 , . . . , (p−2)2 , (p−1)2 } ={ 12, 22 , . . . , ( p−3 2 )2 , ( p−1 2 )2 , ( p− p−12 )2 , ( p− p−32 )2 , . . . , (p−2)2 , (p−1)2 } ≡ ≡ { 12, 22 , . . . , ( p−3 2 )2 , ( p−1 2 )2 , ( −p−12 )2 , ( −p−32 )2 , . . . , (−2)2 , (−1)2 } = = { 12, 22 , . . . , ( p−3 2 )2 , ( p−1 2 )2} Estes últimos p−12 números são incongruentes entre si, pois x 2 ≡ b2 mod p possui exatamente as duas soluções incongruentes x ≡ ±b mod p. Podemos afirmar então que sempre existem p−12 restos quadráticos e p−1 2 restos não-quadrádicos entre { 1, 2 , . . . , p−1 } . A tarefa é separá-los. Como o exemplo acima (mod 19) mostra, não há nenhuma regularidade viśıvel nisso. Queremos caracterizar primeiro os primos p módulo os quais, −1 (i.e. p−1) é um resto quadrático. 8.3 Proposição. Seja p > 2 um primo. A congruência x2 ≡ −1 mod p admite uma solução ⇐⇒ p ≡ 1 mod 4 . Demonstração: ” ⇒ ”: Seja x2 ≡ −1 mod p solúvel. Então existe b ∈ ZZ tal que b2 ≡ −1 mod p. Por Fermat (7.1) obtemos 1 ≡ bp−1 = (b2)p−12 ≡ (−1)p−12 mod p e dáı (−1)p−12 = +1, pois 1 6≡ −1 mod p. Segue que p−12 = 2k é par e portanto p = 4k + 1 ≡ 1 mod 4. ”⇐ ”: Seja p ≡ 1 mod 4. Concluimos por Wilson (7.9) −1 ≡ (p−1)! = 1 · 2 · . . . · p−12 · p+1 2 · . . . · (p−2) · (p−1) ≡ ≡ 1 · 2 · . . . · p−12 · ( −p−12 ) · . . . · (−2) · (−1) ≡ ≡ (−1)p−12 · [( p−1 2 ) ! ]2 ≡ [(p−12 )!]2 mod p , pois ( − 1 )p−1 2 = +1, já que p ≡ 1 mod 4. Logo a congruência x2 ≡ −1 mod p é satisfeita por b = ( p−1 2 ) ! . 86 Eis uma tabela dos primos p ≤ 97 que são ≡ 1 mod 4 e as duas soluções incon- gruentes < p de x2 ≡ −1 mod p: p ≡ 1 sols. x e p− x de mod 4 x2 ≡ −1 mod p 5 2, 3 13 5, 8 17 4, 13 29 12, 17 37 6, 31 41 9, 32 53 23, 30 61 11, 50 73 27, 46 89 34, 55 97 22, 75 Estamos agora em condicões para provar mais um caso particular (b = 4, a = 1) do teorema de Dirichlet (3.29), a saber 8.4 Exemplo. Existem infinitos primos da forma 4n + 1 com n ∈ IN. Demonstração: Suponhamos { p1=5, p2=13, p3 , . . . , pr } fosse o conjunto de todos os primos ≡ 1 mod 4. Consideremos N = ( 2p1p2...pr )2 + 1 ∈ IN. Se q ∈ IP e q ∣∣∣N, então (2p1p2...pr)2+1 ≡ 0 mod q. Isto significa que a congruência x2 ≡ −1 mod q é solúvel por x = 2p1p2...pr . Por 8.3 concluimos q ≡ 1 mod 4. Assim, q ∈ { p1 , p2 , . . . , pr } , o que dá o absurdo q ∣∣∣1. Logo, o conjunto{ p1 , p2 , . . . , pr } não pode estar completo. 87 Um Lema de Euler Uma primeira informação sobre restos quadráticos é dada na 8.5 Proposição. (Lema de Euler) Seja p > 2 um primo, a ∈ ZZ, p†a. a) Sempre a p−1 2 ≡ ±1 mod p b) a p−1 2 ≡ +1 mod p ⇐⇒ a é resto quadrádico mod p. b’) a p−1 2 ≡ −1 mod p ⇐⇒ a é resto não-quadrádico mod p. Demonstração: a) Por Fermat (7.1) temos 1 ≡ ap−1 = ( a p−1 2 )2 mod p e conseqüentemente 0 ≡ ap−1 − 1 = ( a p−1 2 − 1 ) ( a p−1 2 + 1 ) mod p. Isto significa p ∣∣∣∣(ap−12 − 1) (ap−12 + 1) . Como p é primo, concluimos p ∣∣∣ap−12 − 1 ou p ∣∣∣ap−12 + 1 e dáı a p−1 2 ≡ ±1 mod p . b) e b’) são obviamente as mesmas afirmações. Provemos b): ” ⇐ ”: Suponhamos, a é quadrado módulo p. Assim, existe b ∈ ZZ tal que a ≡ b2 mod p. Segue por Fermat a p−1 2 = (b2) p−1 2 = bp−1 ≡ 1 mod p. ”⇒ ”: Suponhamos, a não é quadrado módulo p. Para todo c ∈ { 1, 2 , . . . , p−1 } , a congruência cx ≡ a mod p possui exatamente uma solução c ′ ∈ { 1, 2 , . . . , p−1 } . Além disso, c 6= c ′ (senão a ≡ cc ′ = c2 seria um quadrado!). Escrevemos o con- junto { 1, 2 , . . . , p−1 } como { 1, 2 , . . . , p−1 } = { c1 , c ′ 1 , c2 , c ′ 2 , . . . , cp−1 2 , c′p−1 2 } , tal que c k c′ k ≡ a mod p para 1 ≤ k ≤ p−12 . Segue agora por Wilson: −1 ≡ (p−1)! = 1 · 2 · . . . · (p−1) = = ( c1c ′ 1 ) · ( c2c ′ 2 ) · . . . · ( cp−1 2 c′p−1 2 ) ≡ a · a · . . . · a = ap−12 mod p . 88 Um lema de Gauss Um Lema técnico para a determinação de ( a p ) é dado na seguinte 8.11 Proposição. (Lema de Gauss). Seja p > 2 um primo e a ∈ ZZ com p†a. Consideremos o conjunto S = { a, 2a, 3a , . . . , p−12 a } . Dividindo-se estes números por p, para cada k = 1 , . . . , p−12 vão existir in- teiros q k , t k tais que ka = pq k + t k onde 1 ≤ t k ≤ p−1 . Sejam  r1 , r2 , . . . , rm os números em { t1 , t2 , . . . , tp−12 } com r i < p2 s1 , s2 , . . . , sn os números em { t1 , t2 , . . . , tp−12 } com s j > p2 . Então vale ( a p ) = (−1)n . Em palavras: Para saber se um a 6≡ 0 mod p é um resto quadrádico ou não, considera-se os menores restos não-negativos t1 , t2 , . . . , tp−12 que os a, 2a , . . . , p−12 a deixam na divisão por p. Decisivo para o valor de ( a p ) é se a quantidade n destes restos que jazem acima de p 2 é par ou ı́mpar. Demonstração: Observamos primeiro que a, 2a, 3a , . . . , p−12 a não são diviśıveis por p. Eles também são incongruentes mod p entre si (ka ≡ `a ⇒ (k−`)a ≡ 0 mod p ⇒ p ∣∣∣(k−`)a ⇒ p ∣∣∣k−` ⇒ k ≡ ` mod p ⇒ k = `, pois 0 ≤ |k−`| < p). Conseqüentemente, os t1 , t2 , . . . , tp−12 são distintos e tk ≥ 1. Temos { t1 , t2 , . . . , tp−12 } = { r1 , r2 , . . . , rm , s1 , s2 , . . . , sn } e dáı m + n = p−12 . Consideremos{ r1 , r2 , . . . , rm , p−s1 , p−s2 , . . . , p−sn } . Temos 1 ≤ r i , p−s j ≤ p−12 < p 2 . Os ri são distintos entre si, o mesmo acontecendo com os p−s j . Será que r i = p−s j para algum par de ı́ndices i, j ? Então r i + s j = p. Existem k, ` ∈ { 1, 2 , . . . , p−12 } tais que ka ≡ r i e `a ≡ 91 s j mod p. Segue p = r i + s j ≡ a(k + `) mod p com 0 < k + ` ≤ p−12 + p−1 2 = p−1 < p. Isto é imposśıvel. Logo r i 6= p−s j ∀ 1 ≤ i ≤ m; 1 ≤ j ≤ n. Concluimos que{ r1 , . . . , rm , p−s1 , . . . , p−sn } = { 1, 2 , . . . , p−12 } . Segue então ( p− 1 2 ) ! = r1 · . . . · rm · (p−s1) · . . . · (p−sn) ≡ r1 · . . . · rm · s1 · . . . · sn · (−1) n = t1 · t2 · . . . · tp−12 · (−1) n ≡ a · 2a · . . . · p−12 a · (−1) n = ( p−1 2 ) ! · ap−12 · (−1)n mod p. Como mdc (( p−1 2 ) !, p ) = 1, concluimos por cancelamento do fator ( p−1 2 ) ! dos dois lados desta congruência, que 1 ≡ ap−12 · (−1)n mod p ou também ap−12 ≡ (−1)n mod p . Agora, por 8.10 c) vemos ( a p ) ≡ ap−12 mod p. Logo temos, como afirmado, ( a p ) = (−1)n . O śımbolo de Legendre ( 2 p ) Como primeira aplicação do Lema de Gauss vamos determinar quando a = 2 é um resto quadrático módulo p. 8.12 Proposição. Seja p > 2 um primo. Temos( 2 p ) =  1 se p ≡ 1 ou 7 mod 8−1 se p ≡ 3 ou 5 mod 8 Demonstração: Consideremos no Lema de Gauss (para a = 2) o conjunto{ 1 · 2, 2 · 2, 3 · 2 , . . . , p−12 · 2 } . Estes números são coincidentes com seus menores restos não-negativos na divisão por p e aparecem em ordem natural, i.e.{ 1 · 2, 2 · 2, 3 · 2 , . . . , p−12 · 2 } = { t1 , t2 , . . . , tp−12 } ={ r1 , r2 , . . . , rm , s1 , s2 , . . . , sn } = = { 2, 4, 6 , . . . , [ p 4 ] · 2, ([ p 4 ] + 1 ) · 2 , . . . , p−12 · 2 } , 92 onde 2, 4, 6 , . . . , [ p 4 ] · 2 são os restos < p2 e ([ p 4 ] + 1 ) · 2 , . . . , p−12 · 2 os > p 2 . Temos então n = p− 1 2 − [ p 4 ] . O lema de Gauss (8.11) diz que( 2 p ) = (−1) p−1 2 −[ p 4 ] . Caso 1): p ≡ 1 mod 8, digamos, p = 8` + 1. Segue n = 4` − [2` + 14 ] = 4` − 2` = 2`. Logo ( 2 p ) = (−1)2` = 1. Caso 2): p ≡ 3 mod 8, digamos, p = 8` + 3. Segue n = 4` + 1− [2` + 34 ] = 4` + 1− 2` = 2` + 1. Logo ( 2 p ) = (−1)2`+1 = −1. Caso 3): p ≡ 5 mod 8, digamos, p = 8` + 5. Segue n = (4` + 2)− [2` + 54 ] = (4` + 2)− (2` + 1) = 2` + 1. Logo ( 2 p ) = (−1)2`+1 = −1. Caso 4): p ≡ 7 mod 8, digamos, p = 8` + 7. Segue n = (4` + 3)− [2` + 74 ] = (4` + 3)− (2` + 1) = 2` + 2. Logo ( 2 p ) = (−1)2`+2 = 1. A proposição 8.12 também podemos formular assim: 8.12’ Proposição. Seja p > 2 um primo. Temos ( 2 p ) = (−1) p2−1 8 . Demonstração: Primeiro observamos que p2 − 1 = (p−1)(p + 1) é o produto de dois números pares consecutivos e portanto é diviśıvel por 8. Logo p 2−1 8 ∈ IN. Além disso temos p2−1 8 é ı́mpar ⇔ 16†p2 − 1 ⇔ 8†p−1 e 8†p + 1 ⇔ p 6≡ ±1 mod 8 ⇔ p 6≡ 1 ou 7 mod 8 ⇔ p ≡ 3 ou 5 mod 8 ⇔ ( 2 p ) = −1. 93