Teoria de números/Congruências: diferenças entre revisões
[edição não verificada] | [edição verificada] |
Conteúdo apagado Conteúdo adicionado
Correção de typos e formatação geral, typos fixed: adimite → admite utilizando AWB |
m hack obsoleto: as fórmulas já aparecem em PNG e não há mais como exibi-las em HTML nem MathML (futuramente teremos MathJax) |
||
Linha 10:
== Definição ==
{{Definição
|O inteiro <math>x
}}
Com essa notação, tem-se para quaisquer inteiros <math>x,y
:<math>x^2 + y^2 \not \equiv 3\!\!\!\!\pmod{4}
pois
:<math>k \equiv 0\!\!\!\!\pmod{2} \Rightarrow k^2 \equiv 0\!\!\!\!\pmod{4}
e
:<math>k \equiv 1\!\!\!\!\pmod{2} \Rightarrow k^2 \equiv 1\!\!\!\!\pmod{4}
Como se pode ver na próxima tabela, onde são listadas todas as combinações possíveis para <math>x^2, y^2
{| class="wikitable" style="text-align:center"
Linha 34:
|}
Em outras palavras, o simples cálculo feito acima mostra que ao somar dois quadrados perfeitos, o sucessor do resultado nunca é múltiplo de <math>4
;Nota:
:<math>x \equiv y \!\!\!\!\pmod{m} \Leftrightarrow m|x-y
Sendo assim, a notação para congruências, introduzida por [[w:Carl Friedrich Gauss|Gauss]] evita o uso de várias constantes (<math>k, c, m, t, \ldots
:<math>x \equiv y \!\!\!\!\pmod{m}
:<math>x = y + mk
;Observação:
Conforme o [[../Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]], dados <math>a\in \mathbb{Z}
:<math>a = mq + r
Isso significa que qualquer inteiro <math>a
:<math>\rho_m: \mathbb{Z} \rightarrow \{0, 1, 2, \ldots ,m-1 \}
:<math>\rho_m (a) = a \!\!\!\!\pmod{m}
Quando não houver risco de confusão, o índice <math>m
== A congruência vista como uma relação de equivalência ==
A partir da noção de congruência módulo um certo inteiro <math>m
:<math>x \sim y \Leftrightarrow x \equiv y \!\!\!\!\pmod{m}
Como será mostrado logo a diante, a relação assim definida satisfaz as propriedades de [[w:reflexividade|reflexividade]], [[w:simetria|simetria]], [[w:transitividade|transitividade]], sendo por isso considerada uma [[w:relação de equivalência|relação de equivalência]]:
# <math>\forall x, x \equiv x \!\!\!\!\pmod{m}
# <math>x \equiv y \!\!\!\!\pmod{m} \Rightarrow y \equiv x \!\!\!\!\pmod{m}
# <math>x \equiv y \!\!\!\!\pmod{m} \and y \equiv z \!\!\!\!\pmod{m} \Rightarrow x \equiv z \!\!\!\!\pmod{m}
De modo geral, é sempre possível construir uma relação de equivalência sobre um conjunto <math>X
:<math>x \sim y \Leftrightarrow f(x) = f(y)
então <math>\sim
# <math>f(x) = f(x)
# <math>f(x)=f(y) \Rightarrow f(y)=f(x)
# <math>f(x)=f(y) \and f(y) = f(z) \Rightarrow f(x) = f(z)
E destas propriedades da igualdade seguem as propriedades correspondentes para a relação <math>\sim
Em particular, tomando <math>X = \mathbb{Z}
=== Compatibilidade com as operações ===
Um fato importante, que não pode deixar de ser mencionado é que a relação de congruência é '''compatível''' com as operações do anel dos números inteiros, a saber, a adição e a multiplicação. Uma operação <math>\star
:<math>\left\{\begin{matrix}
a & \sim & a'\\
b & \sim & b'\\
\end{matrix}\right.
pode-se concluir que
:<math>a \star b\sim a' \star b'
No caso da relação de congruência, vê-se que a mesma é compatível tanto com a adição quanto com a multiplicação de números inteiros, como é sintetizado no próximo resultado.
{{Teorema
|Se <math>a, a', b, b'
:<math>\left\{\begin{matrix}
a \equiv a' \!\!\!\!\pmod{m}\\
b \equiv b' \!\!\!\!\pmod{m}\\
\end{matrix}\right.
então:
Linha 99:
a + b \equiv a' + b' \!\!\!\!\pmod{m}\\
a b \equiv a' b' \!\!\!\!\pmod{m}\\
\end{matrix}\right.
}}
A verificação deste resultado é bem simples, como se pode ver a seguir.
{{Demonstração
|Primeiramente, da hipótese sobre os inteiros <math>a, a', b, b'
:<math>\left\{\begin{matrix}
a - a' = mA\\
b - b' = mB\\
\end{matrix}\right.
Donde,
:<math>(a + b) - (a' + b')= m(A + B)
ou seja,
:<math>a + b \equiv a' + b' \!\!\!\!\pmod{m}
Além disso,
:<math>ab = (a'+mA)(b'+mB) = a'b' + a'mB + b'mA + m^2AB = a'b' + mC
onde
:<math>C = a'B + b'A + mAB
Logo,
:<math>ab - a'b' = mC
ou seja,
:<math>ab \equiv a'b' \!\!\!\!\pmod{m}
}}
Linha 134:
[[Image:Set partition.svg|right|thumb|Uma relação de equivalência particiona um conjunto em vários subconjuntos disjuntos, chamadas classes de equivalência.]]
Sempre que se tem uma relação de equivalência <math>\sim
Para definir uma partição de <math>\mathbb{Z}
:<math>[a]_m = \{ x \in \mathbb{Z}; x \equiv a \!\!\!\!\pmod{m}\}
Quando o inteiro <math>m
Nesses termos, o quociente de <math>\mathbb{Z}
:<math>\mathbb{Z}/_{\equiv \!\!\!\!\pmod{m}} = \{[a]_m; a \in \mathbb{Z}\}
Por simplicidade, denota-se <math>\mathbb{Z}/_{\equiv \!\!\!\!\pmod{m}}
Uma das formas de visualizar essa partição de <math>\mathbb{Z}
[[Imagem:Anillo cíclico.png|Representação dos inteiros módulo n sobre uma circunferência.]]
Deste modo, cada ponto da circunferência representa uma das classes de equivalência módulo <math>n
Mas o que há de interessante em particionar o conjunto dos números inteiros?
A grande utilidade de separar os números inteiros em várias classes de congruência é consequência da compatibilidade da congruência com as operações de adição e multiplicação: Sabendo-se que elas são compatíveis, é possível definir
em cada <math>\mathbb{Z}_m
Fixado um inteiro <math>m
:<math>[a] + [b] = [a + b]
:<math>[a] \times [b] = [a \times b]
Em outras palavras, a soma (produto) das classes de congruência dos inteiros <math>a, b
É importante notar onde é utilizada a compatibilidade da congruência com as operações de <math>\mathbb{Z}
Mais do que isso, ao definir essas operações, <math>(\mathbb{Z}_m, +, \times)
Além disso, tem-se um [[w:homomorfismo de anéis|homomorfismo de anéis]] entre <math>\mathbb{Z} = \{ 0, \pm 1, \pm 2, \pm 3, \ldots \}
:<math>\rho: \mathbb{Z} \rightarrow \mathbb{Z}_m
:<math>\rho(x) = [x] = [x \!\!\!\!\pmod{m}]
----
Linha 192:
=== Exemplos ===
As próximas tabelas são as tabuadas das operações de adição e multiplicação no anel <math>\mathbb{Z}_6
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>+
|-
! 0
Linha 219:
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>\times
|-
! 0
Linha 240:
|}
Outro fato curioso que pode ser identificado em alguns anéis é a presença de elementos [[Álgebra abstrata|nilpotentes]], ou seja, tais que alguma de suas potências é nula. Por exemplo, em <math>\mathbb{Z}_{12}
Veja a tábua de multiplicação completa para o anel de inteiros módulo <math>12
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>\times
|-
! 0
Linha 285:
|}
O próximo passo é tentar compreender algebricamente os conjuntos <math>( \mathbb{Z}_{m} , + )
{{tarefa|Revisar/reescrever/excluir o trecho a seguir (até onde diz "Corolário da p7").}}
No próximo diagrama pode ser observada a estrutura aditiva de <math>( \mathbb{Z}_{m} , + )
:<math>\rho: \mathbb{Z} \rightarrow \mathbb{Z}_m
:<math>G \ \ \ H
:<math>mZ \rightarrow 0
<math>H
<math>H = \rho (G)
:<math>mZ = ker (\rho) \subset G
:<math>G = d \mathbb{Z}
:<math>m \mathbb{Z} \subset d \mathbb{Z} \Leftrightarrow d|m
:<math>\overline{x} \in \mathbb{Z}_m
:<math>ord^+_m(x) = k
:<math>\overline{k \cdot x} = k \cdot \overline{x} = \overline{0}
:<math>kx \equiv 0 \!\!\!\!\pmod{m}
Menor <math> k
:<math>ord^+_m(x) = \frac{m}{(x,m)}
:<math>(x,m) = 1 \Rightarrow \overline{x}
Observe a seguinte tabela, onde constam as ''ordens aditivas'' módulo 6.
Linha 315:
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>+
|-
! 0
Linha 336:
|}
:<math>G = d \mathbb{Z}
:<math>m \mathbb{Z} \subset d \mathbb{Z} \Leftrightarrow d|m
Corolário da p7
: Se p é primo então <math>\mathbb{Z}_p
:<math>xy \equiv 0 \!\!\!\!\pmod{p}
:<math>p|xy \Rightarrow p|x
Exemplo:
Linha 349:
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>\times
|-
! 0
Linha 367:
|}
Outra consequencia é que, fixado z não nulo em Z_p, a função <math>\mu: \mathbb{Z}_p \rightarrow \mathbb{Z}_p
Em particular, da sobrejetividade de <math>\mu
Algebricamente, o significado da sobrejetividade de <math>\mu
Pode-se obter outra justificativa para a existência de elementos inversos em <math>\mathbb{Z}_p
De fato, <math>\bar{z} \not = \bar{0}
<math>0+zv\equiv 1 \!\!\!\!\pmod{p}
==Resumindo==
Linha 381:
Os fatos mais relevantes apresentados na discussão feita até agora podem ser sintetizados da seguinte forma:
* Para qualquer <math>m \in \mathbb{Z}
* São equivalentes:
** <math>\mathbb{Z}_m
** <math>\mathbb{Z}_m
** <math>m
::(propriedades algébricas dos conjuntos <math>\mathbb{Z}_m
* São também equivalentes:
** <math>\mathbb{Z}_m
** <math>m
== Unidades ==
Para um inteiro <math>m
:Quais elementos de <math>\mathbb{Z}_m
Antes de responder essa pergunta, convém introduzir uma notação específica para denotar o conjunto dos elementos <math>u \in \mathbb{Z}_m
{{Definição
|Um elemento de <math>\mathbb{Z}_m
}}
=== Exemplos ===
* Se ''p'' é número primo, então <math>U_m = \mathbb{Z}_m / \{ 0 \} = \{ \bar{1}, \bar{2}, \ldots , \overline{p-1} \}
* <math>U_6 = \{ \bar{1}, \bar{5} \} = \{ \pm \bar{1}\}
* <math>U_7 = \{ \bar{1}, \bar{2}, \bar{3}, \bar{4}, \bar{5}, \bar{6}, \bar{7} \}
=== Propriedades das unidades ===
Pode-se verificar que para qualquer <math>m
Novamente, a estrutura de <math>U_m
{{Definição
|A função <math>U_m
:<math>\phi (m ) = | U_m |
}}
;Observações:
* Convenciona-se que <math>\phi (1) = 1
* O valor <math>\phi (m)
{{Demonstração
|De fato, se <math>\bar{x} \in U_m
Reciprocamente, se <math>(x,m)=1
}}
=== Exemplos ===
* Quando <math>p
* Por outro lado, para números compostos, <math>\phi (m)
=== Curiosidades ===
O valor de <math>\phi (m)
====Exemplo====
No caso <math>m = 6
:<math>\frac{0}{6}, \mathbf{\frac{1}{6}}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \mathbf{\frac{5}{6}}
Escrevendo cada uma delas na forma irredutível obtém-se:
:<math>\frac{0}{1}, \mathbf{\frac{1}{6}}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \mathbf{\frac{5}{6}}
Pode-se então conferir que, como era esperado, só duas das frações já estavam em sua forma irredutível: <math>\frac{1}{6}
Note que ao escrever cada fração em sua forma irredutível os denominadores que surgem são todos divisores de <math>m = 6
* 1 fração com denominador 1
* 1 fração com denominador 2
* 2 fração com denominador 3
* 2 fração com denominador 6
Totalizando <math>1+ 1 + 2 + 2 = 6
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| d || Número de frações com denominador d ||width="40px"| <math>\phi (d)
|-
! 1
Linha 468:
Percebe-se que as duas últimas colunas coincidem. Mas o que isso significa?
Isso quer dizer que o número <math>m = 6
:<math>6 = 1+ 1 + 2 + 2 = \phi (1) + \phi (2) + \phi (3) + \phi (6)
Pode-se verificar que essas duas propriedades são válidas em geral:
* <math>\phi (m)
* <math>m = \sum_{d|m} {\phi (d)}
{{Justificativa}}
== Equações lineares ==
Uma questão muito natural é investigar em que casos há alguma solução para equações lineares do tipo
:<math>ax \equiv y \!\!\!\!\pmod{m}
===Exemplo de equação linear com apenas uma solução===
Considere em <math>\mathbb{Z}_8
:<math>3x = 2
ou, em termos de congruências,
:<math>3x \equiv 2 \!\!\!\!\pmod{8}
Sabendo que <math>mdc(3,8)=1
:<math>3r+8s=1
Por exemplo, pode-se tomar <math>r=-5
:<math>3\cdot 3 + 8\cdot (-1) \equiv 1 \!\!\!\!\pmod{8}
ou seja,
:<math>3\cdot 3 + 0 \equiv 1 \!\!\!\!\pmod{8}
significando que <math>3 = 3^{-1}
:<math>3x \equiv 2 \!\!\!\!\pmod{8}
de forma análoga à utilizada em <math>\mathbb{Z}
:<math>3\cdot 3x \equiv 3\cdot 2 \!\!\!\!\pmod{8}
ou seja,
:<math>1 \cdot x \equiv 6 \!\!\!\!\pmod{8}
Conclui-se então que, nesse exemplo, há uma somente uma solução em <math>\mathbb{Z}_8
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| ||width="40px"| 0 ||width="40px"| 1 ||width="40px"| 2 ||width="40px"| 3 ||width="40px"| 4 ||width="40px"| 5 ||width="40px"| <u>6</u> ||width="40px"| 7
|-
! <math>\times 3
| 0 || 3 || 6 || 1 || 4 || 7 || <u>2</u> || 5
|}
Note que se tem uma permutação dos elementos de <math>\mathbb{Z}_8
===Exemplo de equação linear sem solução===
Considere a seguinte equação em <math>\mathbb{Z}_8
:<math>4x = 5
que em termos de congruências se escreve como
:<math>4x \equiv 5 \!\!\!\!\pmod{8}
Já foi mostrado que ela é equivalente à seguinte equação em <math>\mathbb{Z}
:<math>4x = 5 + 8k
ou seja,
:<math>4(x - 2k) = 5
É claro que tal equação não admite sequer uma solução inteira, uma vez que à esquerda tem-se um número par e a direita um ímpar, ou para ser mais exato, pois <math>4 = \mathrm{mdc}(4,8) \nmid 5
===Exemplo de equação linear com duas soluções===
Como um último exemplo antes de conhecer o teorema que dá uma resposta definitiva sobre o número de soluções de uma equação linear em <math>\mathbb{Z}_m
:<math>2x = 6
ou seja,
:<math>2x \equiv 6 \!\!\!\!\pmod{8}
O problema de encontrar soluções para esta equação é equivalente a encontrar inteiros <math>x, y
:<math>2x = 6 + 8y
Dividindo ambos os membros por dois, obtem-se
:<math>\frac{2}{2}x = \frac{6}{2} + \frac{8}{2}y
ou seja,
:<math>x = 3 + 4y
Em termos de congruências, segue:
:<math>x \equiv 3 \!\!\!\!\pmod{4}
Os números inteiros que verificam essa congruência são os termos da progressão aritmética:
:<math>\{ \ldots, -5, -1, 3, 7, 11, 15, 19, \ldots \}
No entanto, como as soluções são buscadas em <math>\mathbb{Z}_8
:<math>\{ \ldots, 3, 7, 3, 7, 3, 7, 3, \ldots \}
ou seja, o conjunto das soluções é:
:<math>S = \{ 3, 7 \}
Em suma, verificou-se através dos exemplos anteriores que é possível encontrar em <math>\mathbb{Z}_8
== Exercícios ==
# Mostre que, se <math>x \equiv y \!\!\!\!\pmod{m}
# Que propriedade aritmética do número inteiro <math>m
{{AutoCat}}
|