bc1405 – Teoria Aritmética dos Números. Relação de equivalência.

Teoria dos números é uma disciplina da matemática dedicada principalmente ao estudo das propriedades dos números inteiros em geral, e dos números primos em particular, bem como as propriedades dos objetos obtidos a partir dos números inteiros (e.g., números racionais) ou de generalizações dos números inteiros (e.g., inteiros algébricos). Propriedades de números reais e números complexos são estudados em Análise Real e Análise Complexa.

A primeira descoberta histórica de natureza aritmética parece ter sido a Tábula de Plimpton 322, 1800 aC.

Este primeiro contato com a Teoria dos Números é por meio da Teoria Elementar dos Números. Através desta disciplina introduziremos propriedades interessantes e notáveis dos números inteiros.

— Pra que estudar Teoria dos Números? —

Números estão na base da construção do conhecimento matemático, em particular, o conjunto dos números naturais, em alguns aspectos, é a peça mais básica da matemática pois você pode construir os demais conjuntos numéricos a partir de números naturais

\displaystyle  {\mathbb N} \xrightarrow{\ -\ } {\mathbb Z} \xrightarrow{\ \div\ } {\mathbb Q} \xrightarrow{\ \epsilon\ } {\mathbb R} \xrightarrow{\ i\ } {\mathbb C}

daí você pode chegar ao cálculo, a topologia e outras disciplinas da Matemática. Também, pelo outro lado, a Teoria dos Números utiliza técnicas dessas disciplinas (álgebra, análise, geometria e topologia, lógica e a ciência da computação) para resolver as questões que lhes são próprias, e muitas vezes direciona desenvolvimentos nestes campos.

Além disso, Teoria dos Números é um ótimo lugar para aprender a ler e escrever provas. É uma rica fonte de conjecturas que são fáceis de enunciar e muito difíceis de provar. Por exemplo, aqui estão alguns problemas na teoria dos números que permanecem sem solução

  • (conjectura de Goldbach) Todo inteiro {n >2} par é soma de dois primos?
  • (conjectura dos primos gêmeos) Há um número infinito de primos gêmeos? (primos gêmeos diferem por {2}, como {11} e {13})
  • A sequência de números de Fibonacci tem infinitos números primos?
  • Existem infinito primos de Mersenne (da forma {2^p+1}, com {p} primo)?
  • {n^2-n+41} é primo para {n} de {1} até {40}, há infinitos primos dessa forma?
  • Há um primo entre {n^2} e {(n+1)^2}?
  • Há uma quantidade infinita de números perfeitos? (perfeito se é a soma de seus divisores, {6=3+2+1} por exemplo)
  • Existe um número ímpar perfeito?
  • Existe um algoritmo eficiente para fatorar inteiros?
  • (Conjectura de Collatz — conjectura {3n + 1}) Comece com qualquer inteiro {n}. Obtenha um novo número inteiro {m} dividindo na metade {n}, se for par, ou tomando {3n + 1}, se for ímpar. Repita, se {m} é par, tome a metade, senão tome {3m + 1}. E assim por diante. É verdade que este procedimento iterativo sempre resuta em {1}, independente do valor inicial?
  • (Problema de Catalan) Os números 8 e 9 são as únicas duas potências consecutivas? Ou seja, as únicas soluções nos naturais para {x^a -y^b=1}, {x,y,a,b>1}, são {x=3}, {a=2}, {y=2} e {b=3}?
  • (Conjectura dos números palíndromos) Escolha um inteiro. Inverta seus dígitos e adicione ao resultado o inteiro original. Se o resultado não é um palíndromo, repita o processo. Será que todos os números inteiros, eventualmente, tornam-se palíndromos por este processo?
  • Existem inifinitos primos com todos os dígitos iguais a {1}?
  • (Hipótese de Riemann) Essa não dá pra descrever de modo simples!!! Mas pra motivar, se você resolver o problema, ganha US$1.000.000,00.

E não é só isso, a Teoria dos Números tem algumas grandes aplicações. Todo sistema digital está baseado nos números inteiros. Duas aplicações modernas são os códigos corretores de erros e a criptografia de chave pública.

Códigos corretores de erros: fazem parte do nosso cotidiano de várias formas, e.g., ao falar pelo telefone, ao ouvir um CD de música, ao assistir um filme em DVD ou navegar pela Internet. Códigos corretores de erros são usados frequentemente em aplicações militares para proteção contra interferência inimiga intencional. Quando queremos transmitir uma informação através de um canal de comunicação (linha telefônica, DVD, internet) podem ocorrer ruídos, o que acaba provocando erros na informação inicial. Detectar tais erros e, se possível, corrigi-los é o objetivo dos códigos corretores de erros. A Álgebra, a Combinatória e a Teoria de Números são ferramentas fundamentais no estudo da Teoria de Códigos.

codigos2

Criptografia RSA:

  1. Escolha dois números primos {p} e {q}, por exemplo, {p = 3 \text{ e } q = 11}
  2. Compute {n = p * q}, no exemplo {n = 33}
  3. Compute {\phi(n) = (p - 1) * (q - 1)}, {\phi(33) = 20}
  4. Escolha {e \in \{ 2,3,\dots \phi(n)\}} com {e} e {n} coprimos, {e = 7}
  5. Compute {d} tal que {(d * e) \div \phi (n)} deixa resto {1}, {d = 3}

  6. Chave pública {(e, n)=} {(7, 33)}
  7. Chave privada {(d, n)=}{(3, 33)}

Para criptografar convertemos a mensagem num inteiro {m} e calculamos {c=m^e \pmod n}, {m=2}, {c=29}.
Para decodificar, calculamos {c^d \pmod n}, {m = 29^3 \pmod {33} = 2}.

A conversão pra inteiro não é problema, informação é normavelmente codificada em computador usando um sistema de numeração

String: teoria aritmética dos números
ASCII (decimal): 116 101 111 114 105 97 32 97 114 105 116 109 101 116 105 99 97 32 100 111 115 32 110 117 109 101 114 111 115
Binário: 01110100 01100101 01101111 01110010 01101001 01100001 00100000 01100001 01110010 01101001 01110100 01101101 01100101 01110100 01101001 01100011 01100001 00100000 01100100 01101111 01110011 00100000 01101110 01110101 01101101 01100101 01110010 01101111 01110011
Hexadecimal: 74 65 6F 72 69 61 20 61 72 69 74 6D 65 74 69 63 61 20 64 6F 73 20 6E 75 6D 65 72 6F 73

Texto comum: teoria aritmética dos números
Texto criptografado (representado em hex): c40bd12d61340e76830f00de6e590e
98f58cacf59b314d791824c280943770d4984caca3543496c543459d0051a299f57ce6
03aeff7745572ec659159ab0613e0a9ed6d5accb2f7588c60b7aaf13b05df9f4a51735b
0ca71d52922a94e9dff1f271285c3defad9fb5605f9e4c9e58c26898e40f47c078f328b7
3814ed6c6555b

— Preliminares: partição e relação de equivalência —

Uma família de conjuntos {\mathcal A = \{A_1,A_2,\dots,A_n\}} particiona o conjunto {X} se seus elementos são não-vazio, disjuntos e a união deles é {X}, isto é,

\displaystyle  A_i \neq \emptyset \text{ para todo } i \ \ \ \ \ (1)

\displaystyle   A_i \cap A_j = \emptyset \text{ para todo } i\neq j,  \ \ \ \ \ (2)

\displaystyle   A_1\cup A_2\cup \cdots \cup A_n = X. \ \ \ \ \ (3)

Dizemos que {\mathcal A} é uma partição de {X}. Notemos que {A_i \subset X} para todo {i}. A definição é a mesma no caso em que {\mathcal A } não é finito.

Exemplo 1 Sejam {R_0}, {R_1} e {R_2} subconjuntos de {{\mathbb N}} definidos por

\displaystyle R_i = \{n\colon n \text{ dividido por } 3 \text{ deixa resto }i \}

{\{R_0,R_1,R_2\}} é uma partição de {{\mathbb N}}.

Uma relação binária {R} sobre um conjunto {A} é um conjunto de pares ordenados de elementos de {A}, em outras palavras, é um subconjunto {R \subset A \times A}.

Notação: Escrevemos {aRb} com o significado de {(a,b)\in R}.

Exemplo
{< \subset {\mathbb N}\times{\mathbb N}} é uma relação binária e {(2,3) \in <}, mas usamos {2 < 3}.

Uma relação binária {\sim} sobre um conjunto {A} é de equivalência se valem as propriedades

  • reflexiva {a\sim a} para todo {a\in A};
  • simétrica se {a\sim b}, então {b\sim a} para todos {a,b\in A};
  • transitiva se {a\sim b} e {b\sim c}, então {a\sim c} para todos {a,b,c\in A};

    Exemplo

    1. {=} é uma relação de equivalência em {{\mathbb N}}.
    2. {\leq} não é uma relação de equivalência em {{\mathbb N}}.
    3. Se {T} e {S} são triângulos no plano e {T\cong S} se os triângulos são semelhantes, então {\cong} é relação de equivalência sobre o conjunto de todos os triângulos no plano.
    4. Semelhança de matriz é uma relação de equivalência sobre o conjuntos de todas as matrizes quadradas de ordem {n} de números reais.
    5. {\subset} não é relação de equivalência sobre o conjunto das partes de {A}.

    Exemplo
    Seja {\{R_0,R_1,R_2\}} a partição de {{\mathbb N}} dada no exemplo 1. Definimos {\sim} sobre {{\mathbb N}} por

    \displaystyle  a \sim b \text{ se existe } i\in \{0,1,2\} \text{ tal que }a,b\in R_i

    ou seja, {a} e {b} pertencem a um mesmo conjunto da partição.

    Exercício 1 Se {\mathcal A} é uma partição de {X} então a relação definida por

    {a \sim b} se, e só se, {a\in A} e {b\in A}, para algum {A\in \mathcal A}

    é uma relação de equivalência.

    Solução: Sejam {\mathcal A}, {X} e {\sim} como no enunciado e vamos provar que {\sim} é uma relação binária reflexiva, simétrica e transitiva.

    Se {a\in X} então {a\in A} para algum {A\in \mathcal{A}}; da definição temos {a\sim a} para todo {a \in X}, logo a relação {\sim} é reflexiva.

    Se {a \sim b} então {a\in A} e {b\in A}, para algum {A\in \mathcal A}, mas também, {b\sim a}. Logo a relação {\sim} é simétrica.

    Finalmente, se {a \sim b} então {a\in A} e {b\in A}, para algum {A\in \mathcal A}, e se {b \sim c} então {b\in B} e {c\in B}, para algum {B\in \mathcal A}. Portanto {b\in A\cap B}.

    Como {\mathcal A} é partição {A\cap B=\emptyset} ou {A=B}. Vale a segunda opção. De {a,c\in A} temos {a\sim c}. Logo a relação {\sim} é transitiva. \Box

    Seja {\sim} uma relação de equivalência sobre o conjunto {X} e {a\in X}

    \displaystyle  [a] = \{ b\in X \colon b\sim a\}

    é o subconjunto de {X} formado por todos os elementos equivalentes a {a}, chamado de classe de equivalência de {a}. O elemento dentro dos colchetes é chamado de representante da classe.

    Por transitividade, qualquer elemento da classe pode ser seu representante. Seja {b\in X} com {b\sim a}. Para todo {c\in [a]} vale {c\sim a}, portanto, {c\sim b}, logo {c\in [b]}. Reciprocamente, se {c\in [b]} então {c\in [a]}, por argumento análogo. Assim {[a]=[b]}. Também, se {[a]=[b]} então de {a\in [a]} temos {a\in [b]}, portanto {a \sim b}. Com isso provamos

    \displaystyle  a\sim b \Leftrightarrow [a]=[b]. \ \ \ \ \ (4)

    O que podemos dizer no caso {[a]\neq [b]}? Imediatamente, por (4) que {a\not\sim b}. Para qualquer {c\in X}, se {c\sim a} então {b\not\sim c}, caso contrário teríamos uma contradição pela transitividade, de modo que {[a] \cap [b] = \emptyset}.

    Concluindo, dos parágrafos precedentes temos que para as classes de equivalência vale um dos casos: para quaisquer {a,b\in X}

    1. {[a]=[b]}, ou
    2. {[a]\cap [b] =\emptyset}.

    O conjunto quociente de {X} pela relação de equivalência {\sim} é o conjunto das classes de equivalência da relação

    \displaystyle   X/{\sim} = \{ [a] \colon a\in X\}. \ \ \ \ \ (5)

    Exercício 2 Prove que {X/{\sim}} é uma partição de {X}.

    No caso de exemplo 1

    \displaystyle  R_0 = [0] = \{0,3,6,9,12,15, \dots\}

    \displaystyle  R_1 = [1] = \{1,4,7,10,13,16, \dots\}

    \displaystyle  R_2 = [1] = \{2,5,8,11,14,17, \dots\}

    Observemos que {[0] =[3]=[6]}. O Teorema da Divisão (que veremos com detalhe nesse curso) garante que {R_0 \cup R_1\cup R_2 ={\mathbb N}}.

    Observação 1 Os exercícios 1 e 2 nos dizem que partição e relação de equivalência são definições equivalentes.

    — Exercícios —

    1. Verifique se são relações de equivalência:

      1. Em {{\mathbb R}}, {x\sim y} se {x-y\in {\mathbb Q}}.
      2. Em {{\mathbb R}}, {x\sim y} se {x \leq y}.
      3. Em {{\mathbb R}}, {x\sim y} se {|x - y| \leq 1}.
      4. Em {X} não vazio, {x\sim y} para todo {x, y\in X}.
      5. Em {{\mathbb R}^2}, {P\sim Q} se a reta {\overline{PQ}} passa pela origem.
      6. Em {[-1,1]}, {x\sim y} se {\sin^2(x)+\cos^2(y)=1}.
    2. Suponha que {\sim} é uma relação simétrica e transitiva sobre o conjunto {X}. Se {a\sim b}, então {b\sim a} por simetria e, então, {a\sim a } por transitividade, assim a propriedade reflexiva é dispensável na definição de relação de equivalência, pois é consequência das outras duas. O que está errado?

    3. Considere a relação {\mathbf{Z} \subset {\mathbb N}\times {\mathbb N}} definida por

      {\displaystyle  (a,b)\mathbf{Z}(n,m) \text{ se, e s\'o se }a+m=b+n  \ \ \ \ \ (6)}

      Para cada {(a,b)} definimos a classe de equivalência de {(a,b)} por

      \displaystyle   [(a,b)] := \big\{ (n,m)\in{\mathbb N}\times{\mathbb N}\colon (a,b)\mathbf{Z}(n,m) \big\}. \ \ \ \ \ (7)

      Por exemplo, {[(1,2)] = \big\{(0,1),(1,2),(2,3),(3,4),\dots\big\}} e {[(5,2)] = \big\{(3,0),(4,1),(5,2),(6,3),\dots\big\}.} Também definimos uma soma de classes de equivalência por

      \displaystyle   [(a,b)]+[(n,m)] := [(a+n,b+m)]. \ \ \ \ \ (8)

      1. Prove que {\mathbf{Z}} é uma relação de equivalência.
      2. Verifique que {[(1,2)]+[(5,2)] = [(0,1)]+[(3,0)]} e que {[(3,4)]+[(4,1)] = [(0,1)]+[(3,0)]}.
      3. Prove que a soma de conjuntos definida acima é compatível com a relação de equivalência, isto é, a soma não depende dos representantes de cada classe de equivalência envolvida.
  • Deixe uma resposta

    Preencha os seus dados abaixo ou clique em um ícone para log in:

    Logotipo do WordPress.com

    Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

    Imagem do Twitter

    Você está comentando utilizando sua conta Twitter. Sair / Alterar )

    Foto do Facebook

    Você está comentando utilizando sua conta Facebook. Sair / Alterar )

    Foto do Google+

    Você está comentando utilizando sua conta Google+. Sair / Alterar )

    Conectando a %s