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
He7d3r.bot (discussão | contribs)
Correção de typos e formatação geral, typos fixed: adimite → admite utilizando AWB
Linha 10:
== Definição ==
{{Definição
|O inteiro <math>x\,\!</math> é dito congruente ao inteiro <math>y\,\!</math> módulo <math>m\,\!</math>, quando <math>m|x-y\,\!</math>. Neste caso, escreve-se <math>x \equiv y \!\!\!\!\pmod{m}\,\!</math>.
}}
 
Com essa notação, tem-se para quaisquer inteiros <math>x,y\,\!</math>:
:<math>x^2 + y^2 \not \equiv 3\!\!\!\!\pmod{4}\,\!</math>
pois
:<math>k \equiv 0\!\!\!\!\pmod{2} \Rightarrow k^2 \equiv 0\!\!\!\!\pmod{4} \,\!</math>
e
:<math>k \equiv 1\!\!\!\!\pmod{2} \Rightarrow k^2 \equiv 1\!\!\!\!\pmod{4} \,\!</math>
Como se pode ver na próxima tabela, onde são listadas todas as combinações possíveis para <math>x^2, y^2\,\!</math> e <math>x^2 + y^2\,\!</math> módulo <math>2\,\!</math>, a soma de dois quadrados nunca é congruente a <math>3\,\!</math> módulo <math>4\,\!</math>.
 
{| 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\,\!</math>.
 
;Nota:
:<math>x \equiv y \!\!\!\!\pmod{m} \Leftrightarrow m|x-y\,\!</math> <math>\Leftrightarrow \exists k \in \mathbb{Z}, x-y=mk \Leftrightarrow \exists k \in \mathbb{Z}, x = y + mk \,\!</math>
 
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>) que não são relevantes durante grande parte dos cálculos envolvendo divisibilidade. Atente para a semelhança (visual) entre as seguintes expressões:
:<math>x \equiv y \!\!\!\!\pmod{m} \,\!</math>
:<math>x = y + mk \,\!</math>
 
;Observação:
Conforme o [[../Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]], dados <math>a\in \mathbb{Z}\,\!</math> e <math>m \in \mathbb{Z}^*\,\!</math>existem únicos <math>q,r \in \mathbb{Z}\,\!</math> de modo que:
:<math>a = mq + r \,\!</math>, com <math>0\le r < m\,\!</math>
 
Isso significa que qualquer inteiro <math>a\,\!</math> é congruente ao seu resto <math>r\,\!</math> na divisão por um inteiro não nulo <math>m\,\!</math>. Uma vez que o resto obtido é único, pode-se definir para cada inteiro <math>m\not = 0\,\!</math> fixado, uma função <math>\rho_m \,\!</math> que a cada número <math>a\in \mathbb{Z}\,\!</math> associa o resto da divisão de <math>a\,\!</math> por <math>m\,\!</math>. A imagem de <math>a\,\!</math> por esta função é denotada por <math>a \!\!\!\!\pmod{m} \,\!</math>. Mais precisamente:
:<math>\rho_m: \mathbb{Z} \rightarrow \{0, 1, 2, \ldots ,m-1 \}\,\!</math>
:<math>\rho_m (a) = a \!\!\!\!\pmod{m} \,\!</math>
 
Quando não houver risco de confusão, o índice <math>m\,\!</math> será omitido e será escrito apenas <math>\rho \,\!</math> em vez de <math>\rho_m \,\!</math>.
 
== 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>, pode-se definir uma relação no conjunto dos números inteiros da seguinte forma:
:<math>x \sim y \Leftrightarrow x \equiv y \!\!\!\!\pmod{m}\,\!</math>
 
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>
# <math>x \equiv y \!\!\!\!\pmod{m} \Rightarrow y \equiv x \!\!\!\!\pmod{m} \,\!</math>
# <math>x \equiv y \!\!\!\!\pmod{m} \and y \equiv z \!\!\!\!\pmod{m} \Rightarrow x \equiv z \!\!\!\!\pmod{m} \,\!</math>
 
De modo geral, é sempre possível construir uma relação de equivalência sobre um conjunto <math>X\,\!</math> a partir de uma função cujo domínio seja <math>X\,\!</math>. De fato, se for definido que:
 
:<math>x \sim y \Leftrightarrow f(x) = f(y)\,\!</math>
 
então <math>\sim\,\!</math> será uma relação de equivalência em <math>X\,\!</math>, pois <math>\forall x, y \in X\,\!</math>:
# <math>f(x) = f(x)\,\!</math>
# <math>f(x)=f(y) \Rightarrow f(y)=f(x) \,\!</math>
# <math>f(x)=f(y) \and f(y) = f(z) \Rightarrow f(x) = f(z) \,\!</math>
 
E destas propriedades da igualdade seguem as propriedades correspondentes para a relação <math>\sim\,\!</math>.
Em particular, tomando <math>X = \mathbb{Z}\,\!</math>, e <math>f(x) = x \!\!\!\!\pmod{m} \,\!</math>, conclui-se que a congruência é uma relação de equivalência.
 
=== 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>é compatível com uma relação de equivalência <math>\sim\,\!</math> quando a partir de
:<math>\left\{\begin{matrix}
a & \sim & a'\\
b & \sim & b'\\
\end{matrix}\right.\,\!</math>
 
pode-se concluir que
 
:<math>a \star b\sim a' \star b'\,\!</math>
 
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> são números inteiros tais que:
:<math>\left\{\begin{matrix}
a \equiv a' \!\!\!\!\pmod{m}\\
b \equiv b' \!\!\!\!\pmod{m}\\
\end{matrix}\right.\,\!</math>
 
então:
Linha 99:
a + b \equiv a' + b' \!\!\!\!\pmod{m}\\
a b \equiv a' b' \!\!\!\!\pmod{m}\\
\end{matrix}\right.\,\!</math>
}}
 
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>, segue que existem inteiros <math>A, B \in \mathbb{Z}\,\!</math>, tais que
 
:<math>\left\{\begin{matrix}
a - a' = mA\\
b - b' = mB\\
\end{matrix}\right.\,\!</math>
 
Donde,
:<math>(a + b) - (a' + b')= m(A + B)\,\!</math>.
 
ou seja,
:<math>a + b \equiv a' + b' \!\!\!\!\pmod{m}\,\!</math>.
 
Além disso,
:<math>ab = (a'+mA)(b'+mB) = a'b' + a'mB + b'mA + m^2AB = a'b' + mC\,\!</math>
 
onde
:<math>C = a'B + b'A + mAB\,\!</math>
 
Logo,
:<math>ab - a'b' = mC\,\!</math>
 
ou seja,
:<math>ab \equiv a'b' \!\!\!\!\pmod{m}\,\!</math>
}}
 
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\,\!</math> sobre um conjunto <math>X\,\!</math> é possível definir uma partição <math>P\,\!</math> de tal conjunto. Uma coleção <math>P\,\!</math> de subconjuntos de <math>X\,\!</math> é chamada de '''partição de <math>X\,\!</math>''' se todo elemento de <math>X\,\!</math> pertence a exatamente um elemento de <math>P\,\!</math>. Os elementos de <math>P\,\!</math> são disjuntos dois a dois, e sua união é o próprio conjunto <math>X\,\!</math>.
 
Para definir uma partição de <math>\mathbb{Z}\,\!</math>, usando a congruência módulo <math>m\,\!</math>, primeiramente define-se para cada inteiro <math>a\,\!</math> a classe de equivalência de <math>a\,\!</math>, segundo <math>\sim\,\!</math>, como:
 
:<math>[a]_m = \{ x \in \mathbb{Z}; x \equiv a \!\!\!\!\pmod{m}\}\,\!</math>
 
Quando o inteiro <math>m\,\!</math> estiver subentendido, será utilizado apenas <math>[a]\,\!</math> para denotar <math>[a]_m\,\!</math>.
 
Nesses termos, o quociente de <math>\mathbb{Z}\,\!</math> pela relação <math>\equiv \!\!\!\!\pmod{m}\,\!</math> é a partição dada por:
:<math>\mathbb{Z}/_{\equiv \!\!\!\!\pmod{m}} = \{[a]_m; a \in \mathbb{Z}\}\,\!</math>
 
Por simplicidade, denota-se <math>\mathbb{Z}/_{\equiv \!\!\!\!\pmod{m}}\,\!</math> simplesmente como <math>\mathbb{Z}_m\,\!</math>.
 
Uma das formas de visualizar essa partição de <math>\mathbb{Z}\,\!</math> é imaginar que sobre um barbante foram marcados todos os números inteiros, separando os números adjacentes sempre por uma mesma distância. Depois disso, para obter uma representação de <math>\mathbb{Z}_m\,\!</math>, enrola-se o barbante em torno de uma circunferência (infinitas vezes!), de modo que o zero ocupe a mesma posição que os inteiros <math>\ldots, -2n, -n, n, 2n, 3n, \ldots\,\!</math>. Você pode então pensar nos elementos de <math>\mathbb{Z}_n\,\!</math> como sendo os n pontos sobre a circunferência que se formou. Veja uma ilustração:
 
[[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\,\!</math>, ou seja, o conjunto dos números inteiros que ficaram sobrepostos naquele ponto da circunferência.
 
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\,\!</math> novas operações de adição e multiplicação. O procedimento é o seguinte:
 
Fixado um inteiro <math>m\,\!</math>, e dadas as classes <math>[a], [b]\,\!</math>, define-se:
:<math>[a] + [b] = [a + b] \,\!</math>
:<math>[a] \times [b] = [a \times b] \,\!</math> (ou simplesmente <math>[a] [b] = [a b] \,\!</math>)
 
Em outras palavras, a soma (produto) das classes de congruência dos inteiros <math>a, b\,\!</math> é a classe de congruência de sua soma (produto).
 
É importante notar onde é utilizada a compatibilidade da congruência com as operações de <math>\mathbb{Z}\,\!</math>: Dadas duas classes de equivalência <math>A=[a]=[a']\,\!</math> e <math>B=[b]=[b']\,\!</math>, tanto faz obter <math>[A]+[B]\,\!</math> como sendo <math>[a+b],[a'+b],[a+b']\,\!</math> ou <math>[a'+b']\,\!</math>. Todas essas classes são idênticas!
 
Mais do que isso, ao definir essas operações, <math>(\mathbb{Z}_m, +, \times)\,\!</math> torna-se um [[w:Anel|anel]] com unidade, ou seja, são válidas as seguintes propriedades:
 
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> e <math>\mathbb{Z}_m = \{ m\mathbb{Z} + 0, m\mathbb{Z} + 1,\ldots , m\mathbb{Z} + (m-1) \} \,\!</math>:
:<math>\rho: \mathbb{Z} \rightarrow \mathbb{Z}_m \,\!</math>
:<math>\rho(x) = [x] = [x \!\!\!\!\pmod{m}]\,\!</math>
 
----
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\,\!</math>. Note que este é um número composto, e que (por esse motivo) existem elementos não nulos em <math>\mathbb{Z}_6\,\!</math> cujo produto é zero (no caso, <math>2\times 3 = 3\times 4 = 0\,\!</math>).
 
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>+\,\!</math> ||width="40px"| 0 ||width="40px"| 1 ||width="40px"| 2 ||width="40px"| 3 ||width="40px"| 4 ||width="40px"| 5
|-
! 0
Linha 219:
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>\times\,\!</math> ||width="40px"| 0 ||width="40px"| 1 ||width="40px"| 2 ||width="40px"| 3 ||width="40px"| 4 ||width="40px"| 5
|-
! 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}\,\!</math>, tem-se <math>6^2 = 0\,\!</math>.
 
Veja a tábua de multiplicação completa para o anel de inteiros módulo <math>12\,\!</math>:
 
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>\times\,\!</math> ||width="40px"| 0 ||width="40px"| 1 ||width="40px"| 2 ||width="40px"| 3 ||width="40px"| 4 ||width="40px"| 5 ||width="40px"| 6 ||width="40px"| 7 ||width="40px"| 8 ||width="40px"| 9 ||width="40px"| 10 ||width="40px"| 11
|-
! 0
Linha 285:
|}
 
O próximo passo é tentar compreender algebricamente os conjuntos <math>( \mathbb{Z}_{m} , + ) \,\!</math>.
 
{{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>:
:<math>\rho: \mathbb{Z} \rightarrow \mathbb{Z}_m\,\!</math>
:<math>G \ \ \ H\,\!</math>
:<math>mZ \rightarrow 0\,\!</math>
 
<math>H\,\!</math> é subgrupo aditivo de <math> \mathbb{Z}_m \,\!</math>.
 
<math>H = \rho (G)\,\!</math>, <math>G\,\!</math> subgrupo aditivo de <math> \mathbb{Z}_m \,\!</math>
 
:<math>mZ = ker (\rho) \subset G \,\!</math>
:<math>G = d \mathbb{Z}\,\!</math>
:<math>m \mathbb{Z} \subset d \mathbb{Z} \Leftrightarrow d|m\,\!</math>. Logo <math>H = d \mathbb{Z} / m \mathbb{Z} \,\!</math>
 
:<math>\overline{x} \in \mathbb{Z}_m\,\!</math>
:<math>ord^+_m(x) = k \,\!</math>
:<math>\overline{k \cdot x} = k \cdot \overline{x} = \overline{0}\,\!</math>
:<math>kx \equiv 0 \!\!\!\!\pmod{m} \,\!</math>
 
Menor <math> k \,\!</math> tal que <math> m | kx \,\!</math>. <math>kx = mmc (x,m) = \frac{x \cdot m}{(x,m)}\,\!</math>
 
:<math>ord^+_m(x) = \frac{m}{(x,m)}\,\!</math>
:<math>(x,m) = 1 \Rightarrow \overline{x}\,\!</math> gera <math> \mathbb{Z}_m \,\!</math>, ou seja são os blocos básicos.
 
Observe a seguinte tabela, onde constam as ''ordens aditivas'' módulo 6.
Linha 315:
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>+\,\!</math> ||width="40px"| 1 ||width="40px"| 2 ||width="40px"| 3 ||width="40px"| 4 ||width="40px"| 5 ||width="40px"| 6
|-
! 0
Linha 336:
|}
 
:<math>G = d \mathbb{Z}\,\!</math>
:<math>m \mathbb{Z} \subset d \mathbb{Z} \Leftrightarrow d|m\,\!</math>. Logo <math>H = d \mathbb{Z} / m \mathbb{Z} \,\!</math>
 
Corolário da p7
: Se p é primo então <math>\mathbb{Z}_p \,\!</math> não tem subgrupos triviais.
 
:<math>xy \equiv 0 \!\!\!\!\pmod{p} \,\!</math>
:<math>p|xy \Rightarrow p|x\,\!</math> ou <math>p|y\,\!</math>. Isso implica que <math>x = \overline{0}\,\!</math> ou <math>y = \overline{0}\,\!</math>, donde <math>\mathbb{Z}_p\,\!</math> é domínio de integridade e portanto, <math>\mathbb{Z}_p\,\!</math> é corpo (todo domínio finito é corpo).
 
Exemplo:
Linha 349:
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| <math>\times\,\!</math> ||width="40px"| 0 ||width="40px"| 1 ||width="40px"| 2 ||width="40px"| 3 ||width="40px"| 4
|-
! 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\,\!</math>, definida por <math>\mu (x) = z x\,\!</math> é injetiva, pois se <math>\mu (x) = \mu (x') \,\!</math>, ou seja, <math>z x \equiv z x' \!\!\!\!\pmod{p} \,\!</math>, então <math>z (x -x') \equiv 0 \!\!\!\!\pmod{p} \,\!</math>. Como <math>(z,p) = 1\,\!</math>, pode-se concluir que <math>x -x' \equiv 0 \!\!\!\!\pmod{p} \,\!</math>, ou seja, <math>x \equiv x' \!\!\!\!\pmod{p} \,\!</math>.
 
Em particular, da sobrejetividade de <math>\mu\,\!</math>, e de <math>1 \in \mathbb{Z}_p \,\!</math> (a imagem de <math>\mu\,\!</math>), segue a existência de <math>z' \in \mathbb{Z}_p \,\!</math> tal que <math>\mu (z') = 1\,\!</math>, ou seja, tal que <math>z z' \equiv 1 \!\!\!\!\pmod{p} \,\!</math>.
 
Algebricamente, o significado da sobrejetividade de <math>\mu\,\!</math> é a existência de um elemento inverso para cada <math>z \in \mathbb{Z}_p\,\!</math> (quando ''p'' é primo). No entanto, a argumentação anterior é não construtiva, pois não indica um método para obter o inverso de um certo <math>z \in \mathbb{Z}_p\,\!</math>.
 
Pode-se obter outra justificativa para a existência de elementos inversos em <math>\mathbb{Z}_p\,\!</math> usando o teorema de Bezout.
De fato, <math>\bar{z} \not = \bar{0}\,\!</math> se, e somente se, <math>p \not | z\,\!</math>, ou seja, se, e somente, <math>(p,z) = 1\,\!</math>. Usando o algoritmo de Euclides, pode-se então encontrar <math>u,v \in \mathbb{Z}\,\!</math> tais que <math>pu+zv=1\,\!</math>. Em particular, usando congruências módulo ''p'' segue <math>pu+zv\equiv 1 \!\!\!\!\pmod{p} \,\!</math>. Donde
<math>0+zv\equiv 1 \!\!\!\!\pmod{p} \,\!</math>, ou seja, <math>zv\equiv 1 \!\!\!\!\pmod{p} \,\!</math>. Portanto, o <math>z'\,\!</math> procurado é simplesmente <math>v \!\!\!\!\pmod{p} \,\!</math>.
 
==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}\,\!</math>, tem-se um anel finito <math>\mathbb{Z}_m\,\!</math>;
* São equivalentes:
** <math>\mathbb{Z}_m\,\!</math> é corpo;
** <math>\mathbb{Z}_m\,\!</math> é um domínio;
** <math>m\,\!</math> é um número primo;
::(propriedades algébricas dos conjuntos <math>\mathbb{Z}_m\,\!</math> -- anéis regulares --correspondem a propriedades aritméticas dos numeros inteiros <math>m\,\!</math>).
* São também equivalentes:
** <math>\mathbb{Z}_m\,\!</math> tem divisores de zero;
** <math>m\,\!</math> é um número composto;
 
== Unidades ==
Para um inteiro <math>m\,\!</math> arbitrário (seja ele primo ou não), podem ser considerada a questão:
:Quais elementos de <math>\mathbb{Z}_m\,\!</math> são inversíveis?
 
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\,\!</math> que possuem inverso multiplicativo:
 
{{Definição
|Um elemento de <math>\mathbb{Z}_m\,\!</math> é chamado de unidade quando possui inverso multiplicativo. O conjunto das unidades de <math>\mathbb{Z}_m\,\!</math> denota-se por <math>U_m\,\!</math>.
}}
 
=== Exemplos ===
* Se ''p'' é número primo, então <math>U_m = \mathbb{Z}_m / \{ 0 \} = \{ \bar{1}, \bar{2}, \ldots , \overline{p-1} \} \,\!</math>
 
* <math>U_6 = \{ \bar{1}, \bar{5} \} = \{ \pm \bar{1}\} \,\!</math>
 
* <math>U_7 = \{ \bar{1}, \bar{2}, \bar{3}, \bar{4}, \bar{5}, \bar{6}, \bar{7} \}\,\!</math>
 
=== Propriedades das unidades ===
Pode-se verificar que para qualquer <math>m\,\!</math>, o conjunto <math>U_m\,\!</math>, das unidades de <math>\mathbb{Z}_m\,\!</math>, é um grupo multiplicativo finito. Em particular, sempre que <math>u,v \in U_m\,\!</math>, tem-se <math>uv \in U_m\,\!</math>. Além disso, <math>1 \in U_m\,\!</math> e existe <math>v \in U_m\,\!</math> tal que <math>uv = 1 \,\!</math>.
 
Novamente, a estrutura de <math>U_m\,\!</math> reflete as propriedades aritméticas de <math>m\,\!</math>. Para melhor entender o que isso significa, é interessante saber para cada <math>m\,\!</math> a quantidade de elementos de <math>U_m\,\!</math>. É razoável esperar que esse número varie com <math>m\,\!</math>, então o melhor é definir uma função que associa <math>m\,\!</math> com a cardinalidade de <math>U_m\,\!</math>:
 
{{Definição
|A função <math>U_m\,\!</math> de Euler é a função que associa a cada <math>m\,\!</math> o número de elementos de <math>U_m\,\!</math>:
:<math>\phi (m ) = | U_m | \,\!</math>
}}
 
;Observações:
* Convenciona-se que <math>\phi (1) = 1\,\!</math>.
* O valor <math>\phi (m)\,\!</math> é justamente a quantidade de números de <math>1\,\!</math> a <math>m\,\!</math> que são coprimos com <math>m\,\!</math>:
{{Demonstração
|De fato, se <math>\bar{x} \in U_m \,\!</math>, então existe <math>\bar{y} \in U_m \,\!</math> tal que <math>\bar{x} \bar{y} = \overline{xy} = \bar{1} \,\!</math>, ou seja, <math>xy \equiv 1 \!\!\!\!\pmod{m} \,\!</math>. Isso significa que <math>xy=1+nk\,\!</math>, ou seja, que <math>xy + m(-k)=1 \,\!</math>. Segue que <math>(x,m)=1\,\!</math>.
 
Reciprocamente, se <math>(x,m)=1\,\!</math>, então <math>xy + mz =1 \,\!</math> (teorema de Bézout). Logo, <math>xy \equiv 1 \!\!\!\!\pmod{m} \,\!</math> e consequentemente, <math>\bar{x} \bar{y} = \bar{1} \,\!</math>. Neste caso, <math>\bar{x} \in U_m \,\!</math>.
}}
 
=== Exemplos ===
* Quando <math>p\,\!</math> é um número primo, tem-se <math>\phi (p) = p-1\,\!</math>.
* Por outro lado, para números compostos, <math>\phi (m)\,\!</math> pode ser bem menor do que <math>m-1\,\!</math>. Em particular, <math>\phi (6) = | U_6 | = | \{ \pm \bar{1}\} | = 2 < 5-1 = 4\,\!</math>.
 
=== Curiosidades ===
O valor de <math>\phi (m)\,\!</math> é justamente a quantidade de frações próprias não negativas com denominador <math>m\,\!</math> (ou seja, <math>\frac{0}{m}, \frac{1}{m} , \ldots, \frac{m-1}{m}\,\!</math>) que já estão na forma irredutível.
 
====Exemplo====
No caso <math>m = 6\,\!</math> apresentado anteriormente, temos as seguintes frações próprias com tal denominador:
 
:<math>\frac{0}{6}, \mathbf{\frac{1}{6}}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \mathbf{\frac{5}{6}}\,\!</math>
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}}\,\!</math>
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}\,\!</math> e <math>\frac{5}{6}\,\!</math>.
 
Note que ao escrever cada fração em sua forma irredutível os denominadores que surgem são todos divisores de <math>m = 6\,\!</math>. Além disso, tem-se:
* 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\,\!</math> frações. Por outro lado, a seguinte tabela indica um fato muito interessante:
 
:{| class="wikitable" style="text-align:center"
|-
!width="40px"| d || Número de frações com denominador d ||width="40px"| <math>\phi (d)\,\!</math>
|-
! 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> é, na verdade, igual a soma dos valores <math>\phi (d)\,\!</math> de cada um dos divisores <math>d\,\!</math>. Em símbolos:
:<math>6 = 1+ 1 + 2 + 2 = \phi (1) + \phi (2) + \phi (3) + \phi (6)\,\!</math>
 
Pode-se verificar que essas duas propriedades são válidas em geral:
* <math>\phi (m)\,\!</math> é igual à quantidade de frações próprias não negativas com denominador que estão na forma irredutível.
 
* <math>m = \sum_{d|m} {\phi (d)} \,\!</math>
{{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}\,\!</math>
 
===Exemplo de equação linear com apenas uma solução===
Considere em <math>\mathbb{Z}_8\,\!</math> a seguinte equação:
:<math>3x = 2 \,\!</math>
ou, em termos de congruências,
:<math>3x \equiv 2 \!\!\!\!\pmod{8}\,\!</math>
 
Sabendo que <math>mdc(3,8)=1\,\!</math>, é possível determinar <math>r,s\,\!</math> tais que
:<math>3r+8s=1\,\!</math>
 
Por exemplo, pode-se tomar <math>r=-5\,\!</math> e <math>s=2\,\!</math>. Outra possibilidade é <math>r=3\,\!</math> e <math>s=-1\,\!</math>. Neste caso, nota-se que:
:<math>3\cdot 3 + 8\cdot (-1) \equiv 1 \!\!\!\!\pmod{8}\,\!</math>
ou seja,
:<math>3\cdot 3 + 0 \equiv 1 \!\!\!\!\pmod{8}\,\!</math>
significando que <math>3 = 3^{-1}\,\!</math> em <math>\mathbb{Z}_8\,\!</math>, ou seja, que neste anel o inverso multiplicativo de <math>3\,\!</math> é ele mesmo. Sabendo disso, é possível resolver
:<math>3x \equiv 2 \!\!\!\!\pmod{8}\,\!</math>
de forma análoga à utilizada em <math>\mathbb{Z}\,\!</math>: Multiplicando-se ambos os membros pelo inverso de <math>3\,\!</math>, segue:
:<math>3\cdot 3x \equiv 3\cdot 2 \!\!\!\!\pmod{8}\,\!</math>
ou seja,
:<math>1 \cdot x \equiv 6 \!\!\!\!\pmod{8}\,\!</math>
Conclui-se então que, nesse exemplo, há uma somente uma solução em <math>\mathbb{Z}_8\,\!</math> para a equação dada. Observe ainda que o número <math>y=2\,\!</math> não teve qualquer influência no número de soluções para o problema. Isso pode ser percebido considerando para cada <math>x\in\mathbb{Z}_8\,\!</math> o resultado de sua multiplicação por <math>a=3\,\!</math>:
:{| 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\,\!</math>
| 0 || 3 || 6 || 1 || 4 || 7 || <u>2</u> || 5
|}
 
Note que se tem uma permutação dos elementos de <math>\mathbb{Z}_8\,\!</math> e que, portanto, o único elemento que é levado em <math>2\,\!</math> ao ser multiplicado por <math>3\,\!</math> é o <math>6\,\!</math>. Essa unicidade permaneceria se o <math>2\,\!</math> fosse trocado por qualquer outro elemento.
 
===Exemplo de equação linear sem solução===
Considere a seguinte equação em <math>\mathbb{Z}_8\,\!</math>:
:<math>4x = 5\,\!</math>
que em termos de congruências se escreve como
:<math>4x \equiv 5 \!\!\!\!\pmod{8}\,\!</math>
Já foi mostrado que ela é equivalente à seguinte equação em <math>\mathbb{Z}\,\!</math>:
:<math>4x = 5 + 8k\,\!</math>
ou seja,
:<math>4(x - 2k) = 5\,\!</math>
 
É 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\,\!</math>.
 
===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>, considere em <math>\mathbb{Z}_8\,\!</math> a equação:
:<math>2x = 6\,\!</math>
ou seja,
:<math>2x \equiv 6 \!\!\!\!\pmod{8}\,\!</math>
O problema de encontrar soluções para esta equação é equivalente a encontrar inteiros <math>x, y\,\!</math> tais que:
:<math>2x = 6 + 8y\,\!</math>
Dividindo ambos os membros por dois, obtem-se
:<math>\frac{2}{2}x = \frac{6}{2} + \frac{8}{2}y \,\!</math>
ou seja,
:<math>x = 3 + 4y \,\!</math>
Em termos de congruências, segue:
:<math>x \equiv 3 \!\!\!\!\pmod{4}\,\!</math>
 
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 \}\,\!</math>
 
No entanto, como as soluções são buscadas em <math>\mathbb{Z}_8\,\!</math>, devemos considerar os números acima módulo <math>8\,\!</math>:
:<math>\{ \ldots, 3, 7, 3, 7, 3, 7, 3, \ldots \}\,\!</math>
 
ou seja, o conjunto das soluções é:
:<math>S = \{ 3, 7 \}\,\!</math>
 
Em suma, verificou-se através dos exemplos anteriores que é possível encontrar em <math>\mathbb{Z}_8\,\!</math> equações do tipo <math>ax=y\,\!</math> que possuam uma ou duas soluções, e mesmo equações que não adimitem solução. Essa é uma notavel diferença entre corpos (como <math>\mathbb{R}\,\!</math>, <math>\mathbb{Q}\,\!</math> e <math>\mathbb{Z}_p\,\!</math>) e anéis. Por exemplo, em <math>\mathbb{Q}\,\!</math> ou <math>\mathbb{R}\,\!</math> você deve estar habituado a resolver <math>ax=y\,\!</math>, simplesmente dividindo os dois membros por <math>a\,\!</math> (e talvez descrevendo esse procedimento como "passar o <math>a\,\!</math> para o lado direito, dividindo..."). No entanto, é tempo de notar que isso só é possível quando <math>a\,\!</math> possui inverso. Em <math>\mathbb{Q}\,\!</math>, todo número não nulo possui inverso. Mas isso não é verdade em todo anel! Por essa razão torna-se necessário tomar algum cuidado ao resolver equações nos aneis <math>\mathbb{Z}_m\,\!</math>. Fique atento!
 
== Exercícios ==
# Mostre que, se <math>x \equiv y \!\!\!\!\pmod{m}\,\!</math> e <math>f\,\!</math> é um polinômio com coeficientes inteiros, então <math>f(x)\equiv f(y)\!\!\!\!\pmod{m}\,\!</math>.
# Que propriedade aritmética do número inteiro <math>m\,\!</math> corresponde a existência de elementos nilpotentes em <math>\mathbb{Z}_m\,\!</math>? (Lembre-se, um elemento é nilpotente quando alguma de suas potências inteiras é igual a zero)
 
{{AutoCat}}