Teoria de números/Congruências

Carl Friedrich Gauss Carl Friedrich Gauss foi um famoso matemático, astrônomo e físico alemão.

Este módulo tem a seguinte tarefa pendente: Incluir breve biografia sobre Carl Friedrich Gauss, enfatizando suas contribuições na teoria de números.

Com essa notação, tem-se para quaisquer inteiros ${\displaystyle x,y}$:

${\displaystyle x^{2}+y^{2}\not \equiv 3\!\!\!\!{\pmod {4}}}$

pois

${\displaystyle k\equiv 0\!\!\!\!{\pmod {2}}\Rightarrow k^{2}\equiv 0\!\!\!\!{\pmod {4}}}$

e

${\displaystyle 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 ${\displaystyle x^{2},y^{2}}$ e ${\displaystyle x^{2}+y^{2}}$ módulo ${\displaystyle 2}$, a soma de dois quadrados nunca é congruente a ${\displaystyle 3}$ módulo ${\displaystyle 4}$.

${\displaystyle {}_{x^{2}}\!\!\diagdown \!\!^{y^{2}}}$	0	1
0	0	1
1	1	2

Em outras palavras, o simples cálculo feito acima mostra que ao somar dois quadrados perfeitos, o sucessor do resultado nunca é múltiplo de ${\displaystyle 4}$.

Nota

${\displaystyle x\equiv y\!\!\!\!{\pmod {m}}\Leftrightarrow m|x-y}$ ${\displaystyle \Leftrightarrow \exists k\in \mathbb {Z} ,x-y=mk\Leftrightarrow \exists k\in \mathbb {Z} ,x=y+mk}$

Sendo assim, a notação para congruências, introduzida por Gauss evita o uso de várias constantes (${\displaystyle k,c,m,t,\ldots }$) 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:

${\displaystyle x\equiv y\!\!\!\!{\pmod {m}}}$

${\displaystyle x=y+mk}$

Observação

Conforme o algoritmo da divisão, dados ${\displaystyle a\in \mathbb {Z} }$ e ${\displaystyle m\in \mathbb {Z} ^{*}}$existem únicos ${\displaystyle q,r\in \mathbb {Z} }$ de modo que:

${\displaystyle a=mq+r}$, com ${\displaystyle 0\leq r<m}$

Isso significa que qualquer inteiro ${\displaystyle a}$ é congruente ao seu resto ${\displaystyle r}$ na divisão por um inteiro não nulo ${\displaystyle m}$. Uma vez que o resto obtido é único, pode-se definir para cada inteiro ${\displaystyle m\not =0}$ fixado, uma função ${\displaystyle \rho _{m}}$ que a cada número ${\displaystyle a\in \mathbb {Z} }$ associa o resto da divisão de ${\displaystyle a}$ por ${\displaystyle m}$. A imagem de ${\displaystyle a}$ por esta função é denotada por ${\displaystyle a\!\!\!\!{\pmod {m}}}$. Mais precisamente:

${\displaystyle \rho _{m}:\mathbb {Z} \rightarrow \{0,1,2,\ldots ,m-1\}}$

${\displaystyle \rho _{m}(a)=a\!\!\!\!{\pmod {m}}}$

Quando não houver risco de confusão, o índice ${\displaystyle m}$ será omitido e será escrito apenas ${\displaystyle \rho }$ em vez de ${\displaystyle \rho _{m}}$.

A partir da noção de congruência módulo um certo inteiro ${\displaystyle m}$, pode-se definir uma relação sobre o conjunto dos números inteiros da seguinte forma:

${\displaystyle x\sim y\Leftrightarrow x\equiv y\!\!\!\!{\pmod {m}}}$

Como será mostrado logo a diante, a relação assim definida satisfaz as propriedades de reflexividade, simetria, transitividade. Sendo, por isso, considerada uma relação de equivalência:

1. ${\displaystyle \forall x,x\equiv x\!\!\!\!{\pmod {m}}}$
2. ${\displaystyle x\equiv y\!\!\!\!{\pmod {m}}\Rightarrow y\equiv x\!\!\!\!{\pmod {m}}}$
3. ${\displaystyle x\equiv y\!\!\!\!{\pmod {m}}\land 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 ${\displaystyle X}$ a partir de uma função cujo domínio seja ${\displaystyle X}$. De fato, se for definido que:

${\displaystyle x\sim y\Leftrightarrow f(x)=f(y)}$

então ${\displaystyle \sim }$ será uma relação de equivalência em ${\displaystyle X}$, pois ${\displaystyle \forall x,y\in X}$:

1. ${\displaystyle f(x)=f(x)}$
2. ${\displaystyle f(x)=f(y)\Rightarrow f(y)=f(x)}$
3. ${\displaystyle f(x)=f(y)\land f(y)=f(z)\Rightarrow f(x)=f(z)}$

E destas propriedades da igualdade seguem as propriedades correspondentes para a relação ${\displaystyle \sim }$. Em particular, tomando ${\displaystyle X=\mathbb {Z} }$, e ${\displaystyle f(x)=x\!\!\!\!{\pmod {m}}}$, conclui-se que a congruência é uma relação de equivalência.

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 ${\displaystyle \star }$é compatível com uma relação de equivalência ${\displaystyle \sim }$ quando a partir de

${\displaystyle \left\{{\begin{matrix}a&\sim &a'\\b&\sim &b'\\\end{matrix}}\right.}$

pode-se concluir que

${\displaystyle 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.

A verificação deste resultado é bem simples, como se pode ver a seguir.

Demonstração

Primeiramente, da hipótese sobre os inteiros ${\displaystyle a,a',b,b'}$, segue que existem inteiros ${\displaystyle A,B\in \mathbb {Z} }$, tais que ${\displaystyle \left\{{\begin{matrix}a-a'=mA\\b-b'=mB\\\end{matrix}}\right.}$ Donde, ${\displaystyle (a+b)-(a'+b')=m(A+B)}$. ou seja, ${\displaystyle a+b\equiv a'+b'\!\!\!\!{\pmod {m}}}$. Além disso, ${\displaystyle ab=(a'+mA)(b'+mB)=a'b'+a'mB+b'mA+m^{2}AB=a'b'+mC}$ onde ${\displaystyle C=a'B+b'A+mAB}$ Logo, ${\displaystyle ab-a'b'=mC}$ ou seja, ${\displaystyle ab\equiv a'b'\!\!\!\!{\pmod {m}}}$

Sempre que se tem uma relação de equivalência ${\displaystyle \sim }$ sobre um conjunto ${\displaystyle X}$ é possível definir uma partição ${\displaystyle P}$ de tal conjunto. Uma coleção ${\displaystyle P}$ de subconjuntos de ${\displaystyle X}$ é chamada de partição de ${\displaystyle X}$ se todo elemento de ${\displaystyle X}$ pertence a exatamente um elemento de ${\displaystyle P}$. Os elementos de ${\displaystyle P}$ são disjuntos dois a dois, e sua união é o próprio conjunto ${\displaystyle X}$.

Para definir uma partição de ${\displaystyle \mathbb {Z} }$, usando a congruência módulo ${\displaystyle m}$, primeiramente define-se para cada inteiro ${\displaystyle a}$ a classe de equivalência de ${\displaystyle a}$, segundo ${\displaystyle \sim }$, como:

${\displaystyle [a]_{m}=\{x\in \mathbb {Z} ;x\equiv a\!\!\!\!{\pmod {m}}\}}$

Quando o inteiro ${\displaystyle m}$ estiver subentendido, será utilizado apenas ${\displaystyle [a]}$ para denotar ${\displaystyle [a]_{m}}$.

Nesses termos, o quociente de ${\displaystyle \mathbb {Z} }$ pela relação ${\displaystyle \equiv \!\!\!\!{\pmod {m}}}$ é a partição dada por:

${\displaystyle \mathbb {Z} /_{\equiv \!\!\!\!{\pmod {m}}}=\{[a]_{m};a\in \mathbb {Z} \}}$

Por simplicidade, denota-se ${\displaystyle \mathbb {Z} /_{\equiv \!\!\!\!{\pmod {m}}}}$ simplesmente como ${\displaystyle \mathbb {Z} _{m}}$.

Uma das formas de visualizar essa partição de ${\displaystyle \mathbb {Z} }$ é 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 ${\displaystyle \mathbb {Z} _{m}}$, 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 ${\displaystyle \ldots ,-2n,-n,n,2n,3n,\ldots }$. Você pode então pensar nos elementos de ${\displaystyle \mathbb {Z} _{n}}$ como sendo os n pontos sobre a circunferência que se formou. Veja uma ilustração:

Deste modo, cada ponto da circunferência representa uma das classes de equivalência módulo ${\displaystyle n}$, 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 ${\displaystyle \mathbb {Z} _{m}}$ novas operações de adição e multiplicação. O procedimento é o seguinte:

Fixado um inteiro ${\displaystyle m}$, e dadas as classes ${\displaystyle [a],[b]}$, define-se:

${\displaystyle [a]+[b]=[a+b]}$

${\displaystyle [a]\times [b]=[a\times b]}$ (ou simplesmente ${\displaystyle [a][b]=[ab]}$)

Em outras palavras, a soma (produto) das classes de congruência dos inteiros ${\displaystyle a,b}$ é a classe de congruência de sua soma (produto).

É importante notar onde é utilizada a compatibilidade da congruência com as operações de ${\displaystyle \mathbb {Z} }$: Dadas duas classes de equivalência ${\displaystyle A=[a]=[a']}$ e ${\displaystyle B=[b]=[b']}$, tanto faz obter ${\displaystyle [A]+[B]}$ como sendo ${\displaystyle [a+b],[a'+b],[a+b']}$ ou ${\displaystyle [a'+b']}$. Todas essas classes são idênticas!

Mais do que isso, ao definir essas operações, ${\displaystyle (\mathbb {Z} _{m},+,\times )}$ torna-se um anel com unidade, ou seja, são válidas as seguintes propriedades:

Além disso, tem-se um homomorfismo de anéis entre ${\displaystyle \mathbb {Z} =\{0,\pm 1,\pm 2,\pm 3,\ldots \}}$ e ${\displaystyle \mathbb {Z} _{m}=\{m\mathbb {Z} +0,m\mathbb {Z} +1,\ldots ,m\mathbb {Z} +(m-1)\}}$:

${\displaystyle \rho :\mathbb {Z} \rightarrow \mathbb {Z} _{m}}$

${\displaystyle \rho (x)=[x]=[x\!\!\!\!{\pmod {m}}]}$

---

Recordando...

Um anel com unidade é um conjunto R equipado com duas operações binárias + : R × R ? R e · : R × R ? R (onde × denota o produto cartesiano), chamadas de adição e multiplicação, tais que:

• (R, +) é um grupo abeliano com elemento identidade, isto é, para todo a, b, c em R, vale o seguinte:
  • (a + b) + c = a + (b + c) (+ é associativa)
  • 0 + a = a (0 é a identidade)
  • a + b = b + a (+ é comutativa)
  • para cada a em R existe −a em R tal que a + (−a) = (−a) + a = 0 (−a é o elemento inverso de a)
• (R, ·) é um monóide com elemento identidade 1, isto é, para todo a, b, c em R, vale:
  • (a · b) · c = a · (b · c) (· é associativa)
  • 1 · a = a · 1 = a (1 é a identidade)
• Multiplicação se distribui em relação a adição:
  • a · (b + c) = (a · b) + (a · c)
  • (a + b) · c = (a · c) + (b · c).

---

As próximas tabelas são as tabuadas das operações de adição e multiplicação no anel ${\displaystyle \mathbb {Z} _{6}}$. Note que este é um número composto, e que (por esse motivo) existem elementos não nulos em ${\displaystyle \mathbb {Z} _{6}}$ cujo produto é zero (no caso, ${\displaystyle 2\times 3=3\times 4=0}$).

${\displaystyle +}$	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

${\displaystyle \times }$	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	2	3	4	5
2	0	2	4	0	2	4
3	0	3	0	3	0	3
4	0	4	2	0	4	2
5	0	5	4	3	2	1

Outro fato curioso que pode ser identificado em alguns anéis é a presença de elementos nilpotentes, ou seja, tais que alguma de suas potências é nula. Por exemplo, em ${\displaystyle \mathbb {Z} _{12}}$, tem-se ${\displaystyle 6^{2}=0}$.

Veja a tábua de multiplicação completa para o anel de inteiros módulo ${\displaystyle 12}$:

${\displaystyle \times }$	0	1	2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	10	11
2	0	2	4	6	8	10	0	2	4	6	8	10
3	0	3	6	9	0	3	6	9	0	3	6	9
4	0	4	8	0	4	8	0	4	8	0	4	8
5	0	5	10	3	8	1	6	11	4	9	2	7
6	0	6	0	6	0	6	0	6	0	6	0	6
7	0	7	2	9	4	11	6	1	8	3	10	5
8	0	8	4	0	8	4	0	8	4	0	8	4
9	0	9	6	3	0	9	6	3	0	9	6	3
10	0	10	8	6	4	2	0	10	8	6	4	2
11	0	11	10	9	8	7	6	5	4	3	2	1

O próximo passo é tentar compreender algebricamente os conjuntos ${\displaystyle (\mathbb {Z} _{m},+)}$.

Este módulo tem a seguinte tarefa pendente: 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 ${\displaystyle (\mathbb {Z} _{m},+)}$:

${\displaystyle \rho :\mathbb {Z} \rightarrow \mathbb {Z} _{m}}$

${\displaystyle G\ \ \ H}$

${\displaystyle mZ\rightarrow 0}$

${\displaystyle H}$ é subgrupo aditivo de ${\displaystyle \mathbb {Z} _{m}}$.

${\displaystyle H=\rho (G)}$, ${\displaystyle G}$ subgrupo aditivo de ${\displaystyle \mathbb {Z} _{m}}$

${\displaystyle mZ=ker(\rho )\subset G}$

${\displaystyle G=d\mathbb {Z} }$

${\displaystyle m\mathbb {Z} \subset d\mathbb {Z} \Leftrightarrow d|m}$. Logo ${\displaystyle H=d\mathbb {Z} /m\mathbb {Z} }$

${\displaystyle {\overline {x}}\in \mathbb {Z} _{m}}$

${\displaystyle ord_{m}^{+}(x)=k}$

${\displaystyle {\overline {k\cdot x}}=k\cdot {\overline {x}}={\overline {0}}}$

${\displaystyle kx\equiv 0\!\!\!\!{\pmod {m}}}$

Menor ${\displaystyle k}$ tal que ${\displaystyle m|kx}$. ${\displaystyle kx=mmc(x,m)={\frac {x\cdot m}{(x,m)}}}$

${\displaystyle ord_{m}^{+}(x)={\frac {m}{(x,m)}}}$

${\displaystyle (x,m)=1\Rightarrow {\overline {x}}}$ gera ${\displaystyle \mathbb {Z} _{m}}$, ou seja são os blocos básicos.

Observe a seguinte tabela, onde constam as ordens aditivas módulo 6.

${\displaystyle +}$	1	2	3	4	5	6
0	0
1	1	2	3	4	5	0
2	2	4	0
3	3	0
4	4	2	0
5	5	4	3	2	1	0

${\displaystyle G=d\mathbb {Z} }$

${\displaystyle m\mathbb {Z} \subset d\mathbb {Z} \Leftrightarrow d|m}$. Logo ${\displaystyle H=d\mathbb {Z} /m\mathbb {Z} }$

Corolário da p7

Se p é primo então ${\displaystyle \mathbb {Z} _{p}}$ não tem subgrupos triviais.

${\displaystyle xy\equiv 0\!\!\!\!{\pmod {p}}}$

${\displaystyle p|xy\Rightarrow p|x}$ ou ${\displaystyle p|y}$. Isso implica que ${\displaystyle x={\overline {0}}}$ ou ${\displaystyle y={\overline {0}}}$, donde ${\displaystyle \mathbb {Z} _{p}}$ é domínio de integridade e portanto, ${\displaystyle \mathbb {Z} _{p}}$ é corpo (todo domínio finito é corpo).

Exemplo:

${\displaystyle \times }$	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Outra consequencia é que, fixado z não nulo em Z_p, a função ${\displaystyle \mu :\mathbb {Z} _{p}\rightarrow \mathbb {Z} _{p}}$, definida por ${\displaystyle \mu (x)=zx}$ é injetiva, pois se ${\displaystyle \mu (x)=\mu (x')}$, ou seja, ${\displaystyle zx\equiv zx'\!\!\!\!{\pmod {p}}}$, então ${\displaystyle z(x-x')\equiv 0\!\!\!\!{\pmod {p}}}$. Como ${\displaystyle (z,p)=1}$, pode-se concluir que ${\displaystyle x-x'\equiv 0\!\!\!\!{\pmod {p}}}$, ou seja, ${\displaystyle x\equiv x'\!\!\!\!{\pmod {p}}}$.

Em particular, da sobrejetividade de ${\displaystyle \mu }$, e de ${\displaystyle 1\in \mathbb {Z} _{p}}$ (a imagem de ${\displaystyle \mu }$), segue a existência de ${\displaystyle z'\in \mathbb {Z} _{p}}$ tal que ${\displaystyle \mu (z')=1}$, ou seja, tal que ${\displaystyle zz'\equiv 1\!\!\!\!{\pmod {p}}}$.

Algebricamente, o significado da sobrejetividade de ${\displaystyle \mu }$ é a existência de um elemento inverso para cada ${\displaystyle z\in \mathbb {Z} _{p}}$ (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 ${\displaystyle z\in \mathbb {Z} _{p}}$.

Pode-se obter outra justificativa para a existência de elementos inversos em ${\displaystyle \mathbb {Z} _{p}}$ usando o teorema de Bezout. De fato, ${\displaystyle {\bar {z}}\not ={\bar {0}}}$ se, e somente se, ${\displaystyle p\not |z}$, ou seja, se, e somente, ${\displaystyle (p,z)=1}$. Usando o algoritmo de Euclides, pode-se então encontrar ${\displaystyle u,v\in \mathbb {Z} }$ tais que ${\displaystyle pu+zv=1}$. Em particular, usando congruências módulo p segue ${\displaystyle pu+zv\equiv 1\!\!\!\!{\pmod {p}}}$. Donde ${\displaystyle 0+zv\equiv 1\!\!\!\!{\pmod {p}}}$, ou seja, ${\displaystyle zv\equiv 1\!\!\!\!{\pmod {p}}}$. Portanto, o ${\displaystyle z'}$ procurado é simplesmente ${\displaystyle v\!\!\!\!{\pmod {p}}}$.

Os fatos mais relevantes apresentados na discussão feita até agora podem ser sintetizados da seguinte forma:

• Para qualquer ${\displaystyle m\in \mathbb {Z} }$, tem-se um anel finito ${\displaystyle \mathbb {Z} _{m}}$;
• São equivalentes:
  • ${\displaystyle \mathbb {Z} _{m}}$ é corpo;
  • ${\displaystyle \mathbb {Z} _{m}}$ é um domínio;
  • ${\displaystyle m}$ é um número primo;

(propriedades algébricas dos conjuntos ${\displaystyle \mathbb {Z} _{m}}$ -- anéis regulares --correspondem a propriedades aritméticas dos numeros inteiros ${\displaystyle m}$).

• São também equivalentes:
  • ${\displaystyle \mathbb {Z} _{m}}$ tem divisores de zero;
  • ${\displaystyle m}$ é um número composto;

Para um inteiro ${\displaystyle m}$ arbitrário (seja ele primo ou não), podem ser considerada a questão:

Quais elementos de ${\displaystyle \mathbb {Z} _{m}}$ são inversíveis?

Antes de responder essa pergunta, convém introduzir uma notação específica para denotar o conjunto dos elementos ${\displaystyle u\in \mathbb {Z} _{m}}$ que possuem inverso multiplicativo:

• Se p é número primo, então ${\displaystyle U_{m}=\mathbb {Z} _{m}/\{0\}=\{{\bar {1}},{\bar {2}},\ldots ,{\overline {p-1}}\}}$

• ${\displaystyle U_{6}=\{{\bar {1}},{\bar {5}}\}=\{\pm {\bar {1}}\}}$

• ${\displaystyle U_{7}=\{{\bar {1}},{\bar {2}},{\bar {3}},{\bar {4}},{\bar {5}},{\bar {6}},{\bar {7}}\}}$

Pode-se verificar que para qualquer ${\displaystyle m}$, o conjunto ${\displaystyle U_{m}}$, das unidades de ${\displaystyle \mathbb {Z} _{m}}$, é um grupo multiplicativo finito. Em particular, sempre que ${\displaystyle u,v\in U_{m}}$, tem-se ${\displaystyle uv\in U_{m}}$. Além disso, ${\displaystyle 1\in U_{m}}$ e existe ${\displaystyle v\in U_{m}}$ tal que ${\displaystyle uv=1}$.

Novamente, a estrutura de ${\displaystyle U_{m}}$ reflete as propriedades aritméticas de ${\displaystyle m}$. Para melhor entender o que isso significa, é interessante saber para cada ${\displaystyle m}$ a quantidade de elementos de ${\displaystyle U_{m}}$. É razoável esperar que esse número varie com ${\displaystyle m}$, então o melhor é definir uma função que associa ${\displaystyle m}$ com a cardinalidade de ${\displaystyle U_{m}}$:

Observações

• Convenciona-se que ${\displaystyle \phi (1)=1}$.
• O valor ${\displaystyle \phi (m)}$ é justamente a quantidade de números de ${\displaystyle 1}$ a ${\displaystyle m}$ que são coprimos com ${\displaystyle m}$:

Demonstração

De fato, se ${\displaystyle {\bar {x}}\in U_{m}}$, então existe ${\displaystyle {\bar {y}}\in U_{m}}$ tal que ${\displaystyle {\bar {x}}{\bar {y}}={\overline {xy}}={\bar {1}}}$, ou seja, ${\displaystyle xy\equiv 1\!\!\!\!{\pmod {m}}}$. Isso significa que ${\displaystyle xy=1+nk}$, ou seja, que ${\displaystyle xy+m(-k)=1}$. Segue que ${\displaystyle (x,m)=1}$. Reciprocamente, se ${\displaystyle (x,m)=1}$, então ${\displaystyle xy+mz=1}$ (teorema de Bézout). Logo, ${\displaystyle xy\equiv 1\!\!\!\!{\pmod {m}}}$ e consequentemente, ${\displaystyle {\bar {x}}{\bar {y}}={\bar {1}}}$. Neste caso, ${\displaystyle {\bar {x}}\in U_{m}}$.

• Quando ${\displaystyle p}$ é um número primo, tem-se ${\displaystyle \phi (p)=p-1}$.
• Por outro lado, para números compostos, ${\displaystyle \phi (m)}$ pode ser bem menor do que ${\displaystyle m-1}$. Em particular, ${\displaystyle \phi (6)=|U_{6}|=|\{\pm {\bar {1}}\}|=2<5-1=4}$.

O valor de ${\displaystyle \phi (m)}$ é justamente a quantidade de frações próprias não negativas com denominador ${\displaystyle m}$ (ou seja, ${\displaystyle {\frac {0}{m}},{\frac {1}{m}},\ldots ,{\frac {m-1}{m}}}$) que já estão na forma irredutível.

No caso ${\displaystyle m=6}$ apresentado anteriormente, temos as seguintes frações próprias com tal denominador:

${\displaystyle {\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:

${\displaystyle {\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: ${\displaystyle {\frac {1}{6}}}$ e ${\displaystyle {\frac {5}{6}}}$.

Note que ao escrever cada fração em sua forma irredutível os denominadores que surgem são todos divisores de ${\displaystyle m=6}$. 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 ${\displaystyle 1+1+2+2=6}$ frações. Por outro lado, a seguinte tabela indica um fato muito interessante:

d	Número de frações com denominador d	${\displaystyle \phi (d)}$
1	1	1
2	1	1
3	2	2
6	2	2

Percebe-se que as duas últimas colunas coincidem. Mas o que isso significa?

Isso quer dizer que o número ${\displaystyle m=6}$ é, na verdade, igual a soma dos valores ${\displaystyle \phi (d)}$ de cada um dos divisores ${\displaystyle d}$. Em símbolos:

${\displaystyle 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:

• ${\displaystyle \phi (m)}$ é igual à quantidade de frações próprias não negativas com denominador que estão na forma irredutível.

• ${\displaystyle m=\sum _{d|m}{\phi (d)}}$

Justificativa
Fica a cargo do leitor justificar este fato. Sinta-se livre para melhorar a qualidade deste texto, incluindo a justificativa neste módulo.

Uma questão muito natural é investigar em que casos há alguma solução para equações lineares do tipo

${\displaystyle ax\equiv y\!\!\!\!{\pmod {m}}}$

Considere em ${\displaystyle \mathbb {Z} _{8}}$ a seguinte equação:

${\displaystyle 3x=2}$

ou, em termos de congruências,

${\displaystyle 3x\equiv 2\!\!\!\!{\pmod {8}}}$

Sabendo que ${\displaystyle mdc(3,8)=1}$, é possível determinar ${\displaystyle r,s}$ tais que

${\displaystyle 3r+8s=1}$

Por exemplo, pode-se tomar ${\displaystyle r=-5}$ e ${\displaystyle s=2}$. Outra possibilidade é ${\displaystyle r=3}$ e ${\displaystyle s=-1}$. Neste caso, nota-se que:

${\displaystyle 3\cdot 3+8\cdot (-1)\equiv 1\!\!\!\!{\pmod {8}}}$

ou seja,

${\displaystyle 3\cdot 3+0\equiv 1\!\!\!\!{\pmod {8}}}$

significando que ${\displaystyle 3=3^{-1}}$ em ${\displaystyle \mathbb {Z} _{8}}$, ou seja, que neste anel o inverso multiplicativo de ${\displaystyle 3}$ é ele mesmo. Sabendo disso, é possível resolver

${\displaystyle 3x\equiv 2\!\!\!\!{\pmod {8}}}$

de forma análoga à utilizada em ${\displaystyle \mathbb {Z} }$: Multiplicando-se ambos os membros pelo inverso de ${\displaystyle 3}$, segue:

${\displaystyle 3\cdot 3x\equiv 3\cdot 2\!\!\!\!{\pmod {8}}}$

ou seja,

${\displaystyle 1\cdot x\equiv 6\!\!\!\!{\pmod {8}}}$

Conclui-se então que, nesse exemplo, há uma somente uma solução em ${\displaystyle \mathbb {Z} _{8}}$ para a equação dada. Observe ainda que o número ${\displaystyle y=2}$ não teve qualquer influência no número de soluções para o problema. Isso pode ser percebido considerando para cada ${\displaystyle x\in \mathbb {Z} _{8}}$ o resultado de sua multiplicação por ${\displaystyle a=3}$:

	0	1	2	3	4	5	6	7
${\displaystyle \times 3}$	0	3	6	1	4	7	2	5

Note que se tem uma permutação dos elementos de ${\displaystyle \mathbb {Z} _{8}}$ e que, portanto, o único elemento que é levado em ${\displaystyle 2}$ ao ser multiplicado por ${\displaystyle 3}$ é o ${\displaystyle 6}$. Essa unicidade permaneceria se o ${\displaystyle 2}$ fosse trocado por qualquer outro elemento.

Considere a seguinte equação em ${\displaystyle \mathbb {Z} _{8}}$:

${\displaystyle 4x=5}$

que em termos de congruências se escreve como

${\displaystyle 4x\equiv 5\!\!\!\!{\pmod {8}}}$

Já foi mostrado que ela é equivalente à seguinte equação em ${\displaystyle \mathbb {Z} }$:

${\displaystyle 4x=5+8k}$

ou seja,

${\displaystyle 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 ${\displaystyle 4=\mathrm {mdc} (4,8)\nmid 5}$.

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 ${\displaystyle \mathbb {Z} _{m}}$, considere em ${\displaystyle \mathbb {Z} _{8}}$ a equação:

${\displaystyle 2x=6}$

ou seja,

${\displaystyle 2x\equiv 6\!\!\!\!{\pmod {8}}}$

O problema de encontrar soluções para esta equação é equivalente a encontrar inteiros ${\displaystyle x,y}$ tais que:

${\displaystyle 2x=6+8y}$

Dividindo ambos os membros por dois, obtem-se

${\displaystyle {\frac {2}{2}}x={\frac {6}{2}}+{\frac {8}{2}}y}$

ou seja,

${\displaystyle x=3+4y}$

Em termos de congruências, segue:

${\displaystyle x\equiv 3\!\!\!\!{\pmod {4}}}$

Os números inteiros que verificam essa congruência são os termos da progressão aritmética:

${\displaystyle \{\ldots ,-5,-1,3,7,11,15,19,\ldots \}}$

No entanto, como as soluções são buscadas em ${\displaystyle \mathbb {Z} _{8}}$, devemos considerar os números acima módulo ${\displaystyle 8}$:

${\displaystyle \{\ldots ,3,7,3,7,3,7,3,\ldots \}}$

ou seja, o conjunto das soluções é:

${\displaystyle S=\{3,7\}}$

Em suma, verificou-se através dos exemplos anteriores que é possível encontrar em ${\displaystyle \mathbb {Z} _{8}}$ equações do tipo ${\displaystyle ax=y}$ 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 ${\displaystyle \mathbb {R} }$, ${\displaystyle \mathbb {Q} }$ e ${\displaystyle \mathbb {Z} _{p}}$) e anéis. Por exemplo, em ${\displaystyle \mathbb {Q} }$ ou ${\displaystyle \mathbb {R} }$ você deve estar habituado a resolver ${\displaystyle ax=y}$, simplesmente dividindo os dois membros por ${\displaystyle a}$ (e talvez descrevendo esse procedimento como "passar o ${\displaystyle a}$ para o lado direito, dividindo..."). No entanto, é tempo de notar que isso só é possível quando ${\displaystyle a}$ possui inverso. Em ${\displaystyle \mathbb {Q} }$, 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 ${\displaystyle \mathbb {Z} _{m}}$. Fique atento!

1. Mostre que, se ${\displaystyle x\equiv y\!\!\!\!{\pmod {m}}}$ e ${\displaystyle f}$ é um polinômio com coeficientes inteiros, então ${\displaystyle f(x)\equiv f(y)\!\!\!\!{\pmod {m}}}$.
2. Que propriedade aritmética do número inteiro ${\displaystyle m}$ corresponde a existência de elementos nilpotentes em ${\displaystyle \mathbb {Z} _{m}}$? (Lembre-se, um elemento é nilpotente quando alguma de suas potências inteiras é igual a zero)