Aritmética modular

Aspeto mover para a barra lateral ocultar

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW • CAPES • Google (N • L • A) (Agosto de 2021)

Em matemática, aritmética modular (chamada também de aritmética do relógio) é um sistema de aritmética para inteiros, onde os números "retrocedem" quando atingem um certo valor, o módulo. O matemático suíço Euler foi o pioneiro na abordagem de congruência por volta de 1750, quando ele explicitamente introduziu a ideia de congruência módulo um número natural N. A abordagem moderna da aritmética modular foi desenvolvida por Carl Friedrich Gauss em seu livro Disquisitiones Arithmeticae, publicado em 1801.

A cronometragem neste relógio usa aritmética módulo 12

Um uso familiar da aritmética modular é no relógio de ponteiro, no qual o dia é divido em dois períodos de 12 horas cada. Se são 7:00 agora, então 8 horas depois serão 3:00. A adição usual sugere que o tempo futuro deveria ser 7 + 8 = 15 {\displaystyle 7+8=15} $7+8=15$ , mas o relógio "retrocede" a cada 12 horas. Da mesma forma, se o relógio começa em 12:00(meio-dia) e 21 horas passam, então a hora será 9:00 do dia seguinte, em vez de 33:00. Como o número de horas começa de novo depois que atinge 12, esta aritmética é chamada aritmética módulo 12. Em termos da definição abaixo, 15 {\displaystyle 15} $15$ é congruente com 3 {\displaystyle 3} $3$ módulo 12 {\displaystyle 12} $12$ , então "15:00" em um relógio de 24 horas é exibido "3:00 "em um relógio de 12 horas.

Congruência

Dado um inteiro n > 1 {\displaystyle n>1} $n>1$ , chamado módulo, dois inteiros são considerados congruentes (ou côngruos) módulo n {\displaystyle n} $n$ , se n {\displaystyle n} $n$ for um divisor de sua diferença (ou seja, se houver um inteiro k {\displaystyle k} $k$ tal que a − b = k n {\displaystyle a-b=kn} $a-b=kn$ ).

A congruência módulo n {\displaystyle n} $n$ é uma relação de congruência, o que significa que é uma relação de equivalência compatível com as operações de adição, subtração e multiplicação. A congruência módulo n {\displaystyle n} $n$ é denotada como:

a ≡ b ( mod n ) . {\displaystyle a\equiv b{\pmod {n}}.}

a\equiv b{\pmod {n}}.

Os parênteses significam que ( mod n ) {\displaystyle ({\text{mod}}\ n)} $({\text{mod}}\ n)$ se aplica a toda a equação, não apenas ao lado direito (aqui b {\displaystyle b} $b$ ). Esta notação não deve ser confundida com a notação b mod n {\displaystyle b{\bmod {n}}} $b{\bmod {n}}$ (sem parênteses), que se refere à operação módulo. Na verdade, b mod n {\displaystyle b{\bmod {n}}} $b{\bmod {n}}$ denota o número inteiro único a {\displaystyle a} $a$ tal que 0 ≤ a < n {\displaystyle 0\leq a<n} $0\leq a<n$ e a ≡ b ( mod n ) {\displaystyle a\equiv b\;({\text{mod}}\;n)} $a\equiv b\;({\text{mod}}\;n)$ (ou seja, o restante de b {\displaystyle b} $b$ quando dividido por n {\displaystyle n} $n$ ).

A relação de congruência pode ser reescrita como

a = k n + b , {\displaystyle a=kn+b,}

a=kn+b,

mostrando explicitamente sua relação com a divisão euclidiana. No entanto, o b {\displaystyle b} $b$ aqui não precisa ser o resto da divisão de a {\displaystyle a} $a$ por n {\displaystyle n} $n$ . Em vez disso, o que a declaração a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$ afirma é que a {\displaystyle a} $a$ e b {\displaystyle b} $b$ têm o mesmo resto quando divididos por n {\displaystyle n} $n$ . Isso é,

a = p n + r , {\displaystyle a=pn+r,}

a=pn+r,

b = q n + r , {\displaystyle b=qn+r,}

b=qn+r,

onde 0 ≤ r < n {\displaystyle 0\leq r<n} $0\leq r<n$ é o resto comum. Subtraindo essas duas expressões, recuperamos a relação anterior:

a − b = k n , {\displaystyle a-b=kn,}

a-b=kn,

definindo k = p − q {\displaystyle k=p-q} $k=p-q$ .

Exemplos

Exemplo 1

No módulo 12, pode-se afirmar que:

38 ≡ 14 ( mod 12 ) {\displaystyle 38\equiv 14{\pmod {12}}}

38\equiv 14{\pmod {12}}

porque 38 − 14 = 24 {\displaystyle 38-14=24} $38-14=24$ , que é um múltiplo de 12. Outra maneira de expressar isso é dizer que 38 e 14 têm o mesmo resto 2—quando dividido por 12.

A definição de congruência também se aplica a valores negativos. Por exemplo:

− 8 ≡ 7 ( mod 5 ) 2 ≡ − 3 ( mod 5 ) − 3 ≡ − 8 ( mod 5 ) . {\displaystyle {\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}

{\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}

Exemplo 2 38 ≡ 2 ( mod 12 ) {\displaystyle 38\equiv 2{\pmod {12}}}

38\equiv 2{\pmod {12}}

pois 38 − 2 = 36 {\displaystyle 38-2=36} $38-2=36$ , que é múltiplo de 12. Note que 38 12 {\displaystyle {\frac {38}{12}}} ${\frac {38}{12}}$ e 2 12 {\displaystyle {\frac {2}{12}}} ${\frac {2}{12}}$ tem o mesmo resto 2. Observe que também, utilizando o exemplo anterior, 14 − 2 = 12 {\displaystyle 14-2=12} $14-2=12$ é inteiro múltiplo de 12, isto é 14 ≡ 2 ( mod 12 ) {\displaystyle 14\equiv 2{\pmod {12}}} $14\equiv 2{\pmod {12}}$ , concordando com a definição inicial de relação de congruência.

Notação

Como é comum considerar várias relações de congruência com diferentes módulos ao mesmo tempo, o módulo é incorporado na notação. Mesmo a notação sendo ternária, a relação de congruência para um módulo fixado é uma relação binária. Isto deve estar claro se a notação a ≡ n b {\displaystyle a\equiv _{n}b} $a\equiv _{n}b$ for usada, em vez da notação tradicional.

Propriedades

A relação de congruência satisfaz todas as condições de uma relação de equivalência:

Reflexividade: a ≡ a ( mod n ) {\displaystyle a\equiv a{\pmod {n}}} $a\equiv a{\pmod {n}}$
Simetria: a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$ se b ≡ a ( mod n ) {\displaystyle b\equiv a{\pmod {n}}} $b\equiv a{\pmod {n}}$ para todo a {\displaystyle a} $a$ , b {\displaystyle b} $b$ e n {\displaystyle n} $n$ .
Transitividade: Se a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$ e b ≡ c ( mod n ) {\displaystyle b\equiv c{\pmod {n}}} $b\equiv c{\pmod {n}}$ , então a ≡ c ( mod n ) {\displaystyle a\equiv c{\pmod {n}}} $a\equiv c{\pmod {n}}$

Se a 1 ≡ b 1 ( mod n ) {\displaystyle a_{1}\equiv b_{1}{\pmod {n}}} $a_{1}\equiv b_{1}{\pmod {n}}$ e a 2 ≡ b 2 ( mod n ) {\displaystyle a_{2}\equiv b_{2}{\pmod {n}}} $a_{2}\equiv b_{2}{\pmod {n}}$ , ou se a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$ , então:

a + k ≡ b + k ( mod n ) {\displaystyle a+k\equiv b+k{\pmod {n}}} $a+k\equiv b+k{\pmod {n}}$ para qualquer inteiro k {\displaystyle k} $k$ (compatibilidade com translação)
k a ≡ k b ( mod n ) {\displaystyle ka\equiv kb{\pmod {n}}} $ka\equiv kb{\pmod {n}}$ para qualquer inteiro k {\displaystyle k} $k$ (compatibilidade com escala)
a 1 + a 2 ≡ b 1 + b 2 ( mod n ) {\displaystyle a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}} $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$ (compatibilidade com adição)
a 1 − a 2 ≡ b 1 − b 2 ( mod n ) {\displaystyle a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}} $a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}$ (compatibilidade com subtração)
a 1 a 2 ≡ b 1 b 2 ( mod n ) {\displaystyle a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}} $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}$ (compatibilidade com multiplicação)
a k ≡ b k ( mod n ) {\displaystyle a^{k}\equiv b^{k}{\pmod {n}}} $a^{k}\equiv b^{k}{\pmod {n}}$ para qualquer inteiro não negativo k {\displaystyle k} $k$ (compatibilidade com exponenciação)
p ( a ) ≡ p ( b ) ( mod n ) {\displaystyle p(a)\equiv p(b){\pmod {n}}} $p(a)\equiv p(b){\pmod {n}}$ , para qualquer polinômio p ( x ) {\displaystyle p(x)} $p(x)$ com coeficientes inteiros (compatibilidade com avaliação polinomial)

Se a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$ , então geralmente é falso que k a ≡ k b ( mod n ) {\displaystyle k^{a}\equiv k^{b}{\pmod {n}}} $k^{a}\equiv k^{b}{\pmod {n}}$ . No entanto, o seguinte é verdadeiro:

Se c ≡ d ( mod φ ( n ) ) {\displaystyle c\equiv d{\pmod {\varphi (n)}}} $c\equiv d{\pmod {\varphi (n)}}$ , onde φ {\displaystyle \varphi } $\varphi$ é a função totiente de Euler, então a c ≡ a d ( mod n ) {\displaystyle a^{c}\equiv a^{d}{\pmod {n}}} $a^{c}\equiv a^{d}{\pmod {n}}$ —desde que a {\displaystyle a} $a$ seja coprimo com n {\displaystyle n} $n$ .

Para o cancelamento dos termos comuns, temos as seguintes regras:

Se a + k ≡ b + k ( mod n ) {\displaystyle a+k\equiv b+k{\pmod {n}}} $a+k\equiv b+k{\pmod {n}}$ para qualquer inteiro k {\displaystyle k} $k$ , então a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$
Se k a ≡ k b ( mod n ) {\displaystyle ka\equiv kb{\pmod {n}}} $ka\equiv kb{\pmod {n}}$ e k {\displaystyle k} $k$ é coprimo com n {\displaystyle n} $n$ , então a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$

O inverso multiplicativo modular é definido pelas seguintes regras:

Existência: existe um inteiro denotado a − 1 {\displaystyle a^{-1}} $a^{-1}$ tal que a a − 1 ≡ 1 ( mod n ) {\displaystyle aa^{-1}\equiv 1{\pmod {n}}} $aa^{-1}\equiv 1{\pmod {n}}$ se e somente se a {\displaystyle a} $a$ é coprimo com n {\displaystyle n} $n$ . Este inteiro a − 1 {\displaystyle a^{-1}} $a^{-1}$ é chamado de inverso multiplicativo modular de a {\displaystyle a} $a$ módulo n {\displaystyle n} $n$ .
Se a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} $a\equiv b{\pmod {n}}$ e a − 1 {\displaystyle a^{-1}} $a^{-1}$ existem, então a − 1 ≡ b − 1 ( mod n ) {\displaystyle a^{-1}\equiv b^{-1}{\pmod {n}}} $a^{-1}\equiv b^{-1}{\pmod {n}}$ (compatibilidade com o inverso multiplicativo e, se a = b {\displaystyle a=b} $a=b$ , unicidade módulo n {\displaystyle n} $n$ )
Se a x ≡ b ( mod n ) {\displaystyle ax\equiv b{\pmod {n}}} $ax\equiv b{\pmod {n}}$ e a {\displaystyle a} $a$ é coprimo com n {\displaystyle n} $n$ , então a solução para esta congruência linear é dada por x ≡ a − 1 b ( mod n ) {\displaystyle x\equiv a^{-1}b{\pmod {n}}} $x\equiv a^{-1}b{\pmod {n}}$

O inverso multiplicativo x ≡ a − 1 ( mod n ) {\displaystyle x\equiv a^{-1}{\pmod {n}}} $x\equiv a^{-1}{\pmod {n}}$ pode ser eficientemente calculado resolvendo a equação de Bézout a x + n y = 1 {\displaystyle ax+ny=1} $ax+ny=1$ para x , y {\displaystyle x,y} $x,y$ —usando o algoritmo Euclidiano estendido.

Em particular, se p {\displaystyle p} $p$ é um número primo, então a {\displaystyle a} $a$ é coprimo com p {\displaystyle p} $p$ para todo a {\displaystyle a} $a$ tal que 0 < a < p {\displaystyle 0<a<p} $0<a<p$ ; assim, existe um inverso multiplicativo para todo a {\displaystyle a} $a$ que não é congruente a zero módulo p {\displaystyle p} $p$ .

Algumas das propriedades mais avançadas das relações de congruência são as seguintes:

Pequeno teorema de Fermat: Se p {\displaystyle p} $p$ é primo e não divide a {\displaystyle a} $a$ , então a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} $a^{p-1}\equiv 1{\pmod {p}}$ .
Teorema de Euler: Se a {\displaystyle a} $a$ e n {\displaystyle n} $n$ são coprimos, então a a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} $a^{\varphi (n)}\equiv 1{\pmod {n}}$ , onde φ {\displaystyle \varphi } $\varphi$ é a função totiente de Euler
Uma consequência simples do pequeno teorema de Fermat é que se p {\displaystyle p} $p$ é primo, então a − 1 ≡ a p − 2 ( mod p ) {\displaystyle a^{-1}\equiv a^{p-2}{\pmod {p}}} $a^{-1}\equiv a^{p-2}{\pmod {p}}$ é o inverso multiplicativo de 0 < a < p {\displaystyle 0<a<p} $0<a<p$ . De maneira mais geral, a partir do teorema de Euler, se a {\displaystyle a} $a$ e n {\displaystyle n} $n$ são coprimos, então a − 1 ≡ a φ ( n ) − 1 ( mod n ) {\displaystyle a^{-1}\equiv a^{\varphi (n)-1}{\pmod {n}}} $a^{-1}\equiv a^{\varphi (n)-1}{\pmod {n}}$ .
Outra consequência simples é que se a ≡ b ( mod φ ( n ) ) {\displaystyle a\equiv b{\pmod {\varphi (n)}}} $a\equiv b{\pmod {\varphi (n)}}$ , onde φ {\displaystyle \varphi } $\varphi$ é a função totiente de Euler, então k a ≡ k b ( mod n ) {\displaystyle k^{a}\equiv k^{b}{\pmod {n}}} $k^{a}\equiv k^{b}{\pmod {n}}$ desde que k {\displaystyle k} $k$ seja coprimo com n {\displaystyle n} $n$ .
Teorema de Wilson: p {\displaystyle p} $p$ é primo se e somente se ( p − 1 ) ! ≡ − 1 ( mod p ) {\displaystyle (p-1)!\equiv -1{\pmod {p}}} $(p-1)!\equiv -1{\pmod {p}}$ .
Teorema do resto chinês: Para qualquer a {\displaystyle a} $a$ , b {\displaystyle b} $b$ e coprimo m {\displaystyle m} $m$ , n {\displaystyle n} $n$ , existe um único x ( mod m n ) {\displaystyle x{\pmod {mn}}} $x{\pmod {mn}}$ tal que x ≡ a ( mod m ) {\displaystyle x\equiv a{\pmod {m}}} $x\equiv a{\pmod {m}}$ e x ≡ b ( mod n ) {\displaystyle x\equiv b{\pmod {n}}} $x\equiv b{\pmod {n}}$ . De fato, x ≡ b m n − 1 m + a n m − 1 n ( mod m n ) {\displaystyle x\equiv b{m_{n}}^{-1}m+a{n_{m}}^{-1}n{\pmod {mn}}} $x\equiv b{m_{n}}^{-1}m+a{n_{m}}^{-1}n{\pmod {mn}}$ onde m n − 1 {\displaystyle {m_{n}}^{-1}} ${m_{n}}^{-1}$ é o inverso de m {\displaystyle m} $m$ módulo n {\displaystyle n} $n$ e n m − 1 {\displaystyle {n_{m}}^{-1}} ${n_{m}}^{-1}$ é o inverso de n {\displaystyle n} $n$ módulo m {\displaystyle m} $m$ .
Teorema de Lagrange: A congruência f ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}} $f(x)\equiv 0{\pmod {p}}$ , onde p {\displaystyle p} $p$ é primo, e f ( x ) = a 0 x n + . . . + a n {\displaystyle f(x)=a_{0}x^{n}+...+a_{n}} $f(x)=a_{0}x^{n}+...+a_{n}$ é um polinômio com coeficientes inteiros tais que a 0 ≠ 0 ( mod p ) {\displaystyle a_{0}\neq 0{\pmod {p}}} $a_{0}\neq 0{\pmod {p}}$ , tem no máximo n {\displaystyle n} $n$ raízes.
Raiz primitiva módulo n: Um número g {\displaystyle g} $g$ é uma raiz primitiva módulo n {\displaystyle n} $n$ se, para cada inteiro um coprimo com n {\displaystyle n} $n$ , existe um inteiro k {\displaystyle k} $k$ tal que g k ≡ a ( mod n ) {\displaystyle g^{k}\equiv a{\pmod {n}}} $g^{k}\equiv a{\pmod {n}}$ . Uma raiz primitiva módulo n {\displaystyle n} $n$ existe se e somente se n {\displaystyle n} $n$ for igual a 2 {\displaystyle 2} $2$ , 4 {\displaystyle 4} $4$ , p k {\displaystyle p^{k}} $p^{k}$ ou 2 p k {\displaystyle 2p^{k}} $2p^{k}$ , onde p {\displaystyle p} $p$ é um número primo ímpar e k {\displaystyle k} $k$ é um inteiro positivo. Se existe uma raiz primitiva módulo n {\displaystyle n} $n$ , então existem exatamente φ ( φ ( n ) ) {\displaystyle \varphi (\varphi (n))} $\varphi (\varphi (n))$ tais raízes primitivas, onde φ {\displaystyle \varphi } $\varphi$ é a função totiente de Euler.
Resíduo quadrático: Um inteiro a {\displaystyle a} $a$ é um resíduo quadrático módulo n {\displaystyle n} $n$ , se existir um inteiro x {\displaystyle x} $x$ tal que x 2 ≡ a ( mod n ) {\displaystyle x^{2}\equiv a{\pmod {n}}} $x^{2}\equiv a{\pmod {n}}$ . O critério de Euler afirma que, se p {\displaystyle p} $p$ é um primo ímpar, e a {\displaystyle a} $a$ não é um múltiplo de p {\displaystyle p} $p$ , então a {\displaystyle a} $a$ é um resíduo quadrático módulo p {\displaystyle p} $p$ se e somente se

a ( p − 1 ) / 2 ≡ 1 ( mod p ) . {\displaystyle a^{(p-1)/2}\equiv 1{\pmod {p}}.}

a^{(p-1)/2}\equiv 1{\pmod {p}}.

Classes de congruência

Como qualquer relação de congruência, congruência módulo n é uma relação de equivalência, e as classes de equivalência do inteiro a, denotada por a ¯ n {\displaystyle {\overline {a}}_{n}} ${\overline {a}}_{n}$ , é o conjunto { … , a − 2 n , a − n , a , a + n , a + 2 n , … } {\displaystyle \left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}} $\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}$ . Este conjunto, consistindo dos inteiros congruentes a a {\displaystyle a} $a$ modulo n {\displaystyle n} $n$ , é chamado a classe de congruência ou classe de resíduos ou simplesmente resíduo do inteiro a {\displaystyle a} $a$ modulo n {\displaystyle n} $n$ . Quando o módulo n {\displaystyle n} $n$ é conhecido pelo contexto, este resíduo também pode ser denotado por {\displaystyle \displaystyle } $\displaystyle$ .

Anel de classes de congruência

O conjunto de todas as classes de congruência módulo n é denotado Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ ou Z / n {\displaystyle \mathbb {Z} /n} $\mathbb {Z} /n$ (a notação alternativa Z n {\displaystyle \mathbb {Z} _{n}} $\mathbb {Z} _{n}$ não é recomendada por causa da possível confusão com o conjunto dos inteiros p-ádicos). E é definida por: Z / n Z = { a ¯ n | a ∈ Z } . {\displaystyle \mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.} $\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.$

Quando n ≠ 0 {\displaystyle n\neq 0} $n\neq 0$ , Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ tem n elementos, e pode ser escrita como:

Z / n Z = { 0 ¯ n , 1 ¯ n , 2 ¯ n , … , n − 1 ¯ n } . {\displaystyle \mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.}

\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.

Quando n = 0, Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ não tem elementos não nulos; daí é isomorfo a Z {\displaystyle \mathbb {Z} } $\mathbb {Z}$ , pois a ¯ 0 = { a } {\displaystyle {\overline {a}}_{0}=\left\{a\right\}} ${\overline {a}}_{0}=\left\{a\right\}$ .

Podemos definir adição, subtração e multiplicação em Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ pelas seguintes regras:

a ¯ n + b ¯ n = ( a + b ) ¯ n {\displaystyle {\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}} ${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}$
a ¯ n − b ¯ n = ( a − b ) ¯ n {\displaystyle {\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}} ${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}$
a ¯ n b ¯ n = ( a b ) ¯ n . {\displaystyle {\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.} ${\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.$

A verificação que esta é uma definição adequada usa as propriedades mencionadas antes.

Desta forma, Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ se torna um anel comutativo. Por exemplo, no anel Z / 24 Z {\displaystyle \mathbb {Z} /24\mathbb {Z} } $\mathbb {Z} /24\mathbb {Z}$ , temos

12 ¯ 24 + 21 ¯ 24 = 9 ¯ 24 {\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {9}}_{24}}

{\overline {12}}_{24}+{\overline {21}}_{24}={\overline {9}}_{24}

como na aritmética do relógio de ponteiro.

A notação Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ é usada, por que ele é anel quociente de Z {\displaystyle \mathbb {Z} } $\mathbb {Z}$ pelo ideal n Z {\displaystyle n\mathbb {Z} } $n\mathbb {Z}$ consistindo de todos os inteiros divisíveis por n, onde 0 Z {\displaystyle 0\mathbb {Z} } $0\mathbb {Z}$ é o conjunto unitário { 0 } {\displaystyle \left\{0\right\}} $\left\{0\right\}$ . Assim Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ é um corpo quando n Z {\displaystyle n\mathbb {Z} } $n\mathbb {Z}$ é um ideal máximal, ou seja, quando n {\displaystyle n} $n$ é primo.

Em termos de grupos, a classe de resíduos a ¯ n {\displaystyle {\overline {a}}_{n}} ${\overline {a}}_{n}$ é a classe lateral de a no grupo quociente Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ , um grupo cíclico.

O conjunto Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } $\mathbb {Z} /n\mathbb {Z}$ tem várias propriedades matemáticas importantes que são o fundamento de vários ramos da matemática.

Em vez de excluir o caso n=0, é mais útil incluir Z / 0 Z {\displaystyle \mathbb {Z} /0\mathbb {Z} } $\mathbb {Z} /0\mathbb {Z}$ (que, como mencionado antes, é isomorfo ao anel Z {\displaystyle \mathbb {Z} } $\mathbb {Z}$ dos inteiros), por exemplo quando discutindo característica de um anel.

Restos

A noção de aritmética modular está relacionada com a de resto da divisão. A operação de achar o resto é algumas vezes chamada de operação módulo, nesse contexto escrevemos, por exemplo, 2 = 14 (mod 12). A diferença está no uso da congruência, indicado por "≡", e da igualdade indicado por "=". Igualdade implica especificamente o "resíduo comum", o menor inteiro não negativo membro de uma classe de equivalência. Quando estamos trabalhando com aritmética modular, cada classe de equivalência é geralmente representada pelo seu resíduo comum, por exemplo 38 ≡ 2 (mod 12), que pode ser encontrado usando divisão longa. Segue disso que enquanto é correto dizer 38 ≡ 14 (mod 12) e 2 ≡ 14 (mod 12), é incorreto dizer 38 = 14 (mod 12) (com "=" no lugar de "≡").

A diferença é mais clara quando estamos dividindo um número negativo, porque neste caso os restos são negativos. Assim para expressar o resto devemos escrever −5 ≡ −17 (mod 12), em vez de 7 = −17 (mod 12), pois equivalência só pode ser considerada para resíduos com o mesmo sinal.

Em ciência da computação, o operador resto é normalmente indicado por "%" (p.ex. em C, Java, Javascript, Perl e Python) ou "mod" (p.ex. in Pascal, BASIC, SQL, Haskell), com exceções (p.ex. em Excel). Estes operadores são normalmente pronunciados como "mod", mas o que é efetivamente computado é um resto (pois em C++ são retornados números negativos se o primeiro argumento é negativo e em Python um número negativo é retornado se o segundo argumento é negativo). A função modulo em vez de mod, como em 38 ≡ 14 (modulo 12), é algumas vezes usada para indicar um resíduo comum em vez do resto (p.ex. em Ruby).

Os parenteses às vezes não são escritos na expressão, por exemplo 38 ≡ 14 mod 12 ou 2 = 14 mod 12, ou são colocados em volta do divisor, por exemplo 38 ≡ 14 mod (12). Notações como 38 (mod 12) também existem, mas são ambíguas sem um contexto.

Representação funcional da operação resto

A operação resto pode ser representada usando a função piso. Se b = a (mod n), onde n > 0, então se o resto é b ele é dado por

b = a − ⌊ a n ⌋ × n , {\displaystyle b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n,}

b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n,

onde ⌊ a n ⌋ {\displaystyle \left\lfloor {\frac {a}{n}}\right\rfloor } $\left\lfloor {\frac {a}{n}}\right\rfloor$ é o maior inteiro menor ou igual a a n {\displaystyle {\frac {a}{n}}} ${\frac {a}{n}}$ , então

a ≡ b ( mod n ) e, 0 ≤ b < n . {\displaystyle {\begin{array}{lcl}a\equiv b{\pmod {n}}{\text{ e,}}\\0\leq b<n.\end{array}}}

{\begin{array}{lcl}a\equiv b{\pmod {n}}{\text{ e,}}\\0\leq b<n.\end{array}}

Se em vez do resto b o intervalo −n ≤ b < 0 é requirido, então

b = a − ⌊ a n ⌋ × n − n . {\displaystyle b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n-n.}

b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n-n.

Sistema de resíduos

Cada classe de resíduo modulo n pode ser representada por um de seus membros, embora nós geralmente representemos cada classe residual pelo menor inteiro não negativo pertencente à classe (pois este é o próprio resto que resulta da divisão). Note que quaisquer dois membros de diferentes classes residuais módulo n são congruentes módulo n. Além disso cada inteiro pertence a uma e somente uma classe residual módulo n.

O conjunto de inteiros {0, 1, 2, ..., n - 1} é chamado o menor sistema de resíduos módulo n. Qualquer outro conjunto de n inteiros, com nenhum par deles congruente módulo n é chamado um sistema completo de resíduos módulo n.

É claro que o menor sistema de resíduos é uma sistema completo de resíduos e que um sistema completo de resíduos é simplesmente um conjunto contendo precisamente um representante de cada classe de resíduo módulo n. O menor sistema de resíduos módulo 4 é {0, 1, 2, 3}. Alguns outros sistemas de resíduos módulo 4 são:

{1,2,3,4}
{13,14,15,16}
{-2,-1,0,1}
{-13,4,17,18}
{-5,0,6,21}
{27,32,37,42}

Alguns conjuntos que não são um sistema completo de resíduos módulo 4 são:

{-5,0,6,22} pois 6 é congruente a 22 módulo 4.
{5,15} pois um sistema completo de resíduos deve ter exatamente 4 elementos.

Sistemas reduzidos de resíduos

Qualquer conjunto com φ(n) inteiros que são primos com n e que são incongruentes entre si módulo n, onde φ(n) denota a Função totiente de Euler, é chamado um sistema reduzido de resíduos módulo n.

Congruências quadráticas (ou do segundo grau)

Considere a equação a x 2 + b x + c ≡ 0 ( mod p ) {\displaystyle ax^{2}+bx+c\equiv 0{\pmod {p}}} $ax^{2}+bx+c\equiv 0{\pmod {p}}$ , onde a , b , c ∈ Z {\displaystyle a,b,c\in \mathbb {Z} } $a,b,c\in \mathbb {Z}$ , p {\displaystyle p} $p$ é um primo (ímpar) e a ≢ 0 ( mod p ) {\displaystyle a\not \equiv 0{\pmod {p}}} $a\not \equiv 0{\pmod {p}}$ . Podemos observar que ( a , p ) = 1 {\displaystyle (a,p)=1} $(a,p)=1$ e como p {\displaystyle p} $p$ é ímpar temos ( 4 a , p ) = 1 {\displaystyle (4a,p)=1} $(4a,p)=1$ . Assim, a equação acima é equivalente a 4 a ( a x 2 + b x + c ) ≡ 0 ( mod p ) {\displaystyle 4a(ax^{2}+bx+c)\equiv 0{\pmod {p}}} $4a(ax^{2}+bx+c)\equiv 0{\pmod {p}}$ . Ao completarmos quadrados obtemos ( 2 a x + b ) 2 − ( b 2 − 4 a c ) ≡ 0 ( mod p ) {\displaystyle (2ax+b)^{2}-(b^{2}-4ac)\equiv 0{\pmod {p}}} $(2ax+b)^{2}-(b^{2}-4ac)\equiv 0{\pmod {p}}$ . Ao fazermos y = 2 a x + b {\displaystyle y=2ax+b} $y=2ax+b$ e d = b 2 − 4 a c {\displaystyle d=b^{2}-4ac} $d=b^{2}-4ac$ , vem y 2 ≡ d ( mod p ) {\displaystyle y^{2}\equiv d{\pmod {p}}} $y^{2}\equiv d{\pmod {p}}$ . Para descobrir as soluções da equação quadrática, basta descobrir as soluções da equações da forma x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} $x^{2}\equiv a{\pmod {p}}$ . Pois se p ∣ a {\displaystyle p\mid a} $p\mid a$ (lê-se "p divide a") obtemos desinteressante a equação x 2 ≡ 0 ( mod p ) {\displaystyle x^{2}\equiv 0{\pmod {p}}} $x^{2}\equiv 0{\pmod {p}}$ e, por essa razão x ≡ 0 ( mod p ) {\displaystyle x\equiv 0{\pmod {p}}} $x\equiv 0{\pmod {p}}$ o que torna indispensável assumir que p ∤ a {\displaystyle p\nmid a} $p\nmid a$ ("p não divide a") a fim de evitarmos soluções triviais.

Exemplo

Resolva a congruência 8 x 2 + 5 x + 1 ≡ 0 ( mod 23 ) {\displaystyle 8x^{2}+5x+1\equiv 0{\pmod {23}}} $8x^{2}+5x+1\equiv 0{\pmod {23}}$ .

Como ( 8 , 23 ) = 1 {\displaystyle (8,23)=1} $(8,23)=1$ e p = 23 {\displaystyle p=23} $p=23$ é primo ímpar temos que ( 4 ⋅ 8 , 23 ) = ( 32 , 23 ) = 1 {\displaystyle (4\cdot 8,23)=(32,23)=1} $(4\cdot 8,23)=(32,23)=1$ , no qual ao multiplicarmos a congruência em questão e completar quadrados obtemos ( 16 x + 5 ) 2 + 32 − 25 ≡ 0 ( mod 23 ) ⇒ ( 16 x + 5 ) 2 ≡ 16 ( mod 23 ) {\displaystyle (16x+5)^{2}+32-25\equiv 0{\pmod {23}}\Rightarrow (16x+5)^{2}\equiv 16{\pmod {23}}} $(16x+5)^{2}+32-25\equiv 0{\pmod {23}}\Rightarrow (16x+5)^{2}\equiv 16{\pmod {23}}$ . Com isso encontramos 16 x + 5 ≡ ± 4 ( mod 23 ) {\displaystyle 16x+5\equiv \pm 4{\pmod {23}}} $16x+5\equiv \pm 4{\pmod {23}}$ , onde ao resolvermos a congruência linear 16 x ≡ − 1 ( mod 23 ) {\displaystyle 16x\equiv -1{\pmod {23}}} $16x\equiv -1{\pmod {23}}$ temos x ≡ 10 ( mod 23 ) {\displaystyle x\equiv 10{\pmod {23}}} $x\equiv 10{\pmod {23}}$ , enquanto a partir da congruência linear x ≡ − 9 ( mod 23 ) {\displaystyle x\equiv -9{\pmod {23}}} $x\equiv -9{\pmod {23}}$ , obtemos x ≡ 21 ( mod 23 ) {\displaystyle x\equiv 21{\pmod {23}}} $x\equiv 21{\pmod {23}}$ . Dessa maneira, 10 {\displaystyle 10} $10$ e 21 {\displaystyle 21} $21$ são as únicas soluções incongruentes. De fato, se x = 10 ⇒ 8 x 2 + 5 x + 1 = 851 {\displaystyle x=10\Rightarrow 8x^{2}+5x+1=851} $x=10\Rightarrow 8x^{2}+5x+1=851$ e 851 ≡ 0 ( mod 23 ) {\displaystyle 851\equiv 0{\pmod {23}}} $851\equiv 0{\pmod {23}}$ . Se x = 21 ⇒ 8 x 2 + 5 x + 1 = 3634 {\displaystyle x=21\Rightarrow 8x^{2}+5x+1=3634} $x=21\Rightarrow 8x^{2}+5x+1=3634$ e 3634 ≡ 0 ( mod 23 ) {\displaystyle 3634\equiv 0{\pmod {23}}} $3634\equiv 0{\pmod {23}}$ .

Referências

↑ http://www.ams.org/samplings/feature-column/fcarc-eulers-formula
↑ «Comprehensive List of Algebra Symbols». Math Vault (em inglês). 25 de março de 2020. Consultado em 12 de agosto de 2020
↑ Arnaldo Garcia e Yves Lequain. Elementos de Álgebra - Rio de Janeiro, IMPA, 2002. 326 páginas (Projeto Euclides), ISBN 978-85-244-0190-9
↑ José Plinio de Oliveira Santos - Introdução à Teoria dos Números - Rio de Janeiro, IMPA, 1998. 198 péginas (projeto Euclides), ISBN 978-85-244-0142-8
↑ SAID, Sidki. Introdução à Teoria dos Números. Colóquio Brasileiro de Matemática, IMPA, 1975.

Tópicos principais sobre teoria dos números

Fundamentos

Conceitos	Anel adélico Aproximação diofantina Criptografia Curva elíptica Equação diofantina Espiral de Ulam Função aditiva Função geradora Função multiplicativa Zeta-Riemann Inteiro gaussiano Número algébrico Progressão aritmética Progressão geométrica Teoremas abeliano e tauberiano
Ferramentas	Aritmética modular Congruência Fatoração de inteiros Método do círculo Número l-ádico Número p-ádico Somas gaussianas
Números notáveis	Abundante Carmichael Deficiente Fermat Número de Mersenne Perfeito Primo Quasi-primo Semiprimo Sequência de Fibonacci Sequência de Lucas Sierpiński Sophie Germain Superabundante Ternos pitagóricos Triangular Wall–Sun–Sun

História

igual a 0	Erdős
igual a 1	Graham Hajnal Marcus Rényi Szemerédi Turán Vaughan Wintner
igual a 2	Adleman Bombieri Einstein Rivest Selberg Serre Shamir Tao
igual a 3	Born Fermi Feynman Friedman Nash Pauli
igual a 4	Chomsky Mangabeira Unger

Teoremas

Demonstrados	Barban–Davenport–Halberstam Bombieri-Vinogradov Brun–Titchmarsh Chen Dirichlet Erdős–Kac Erdős–Wintner Equidistribuição de Weyl Euclides Green-Tao Hadamard-Poussin Linnik Mordell-Weil Número poligonal de Fermat Pequeno teorema de Fermat Pitágoras Postulado de Bertrand Reciprocidade quadrática Teorema chinês do resto Último teorema de Fermat Wilson
Em aberto	Hipótese da densidade Hipótese de Riemann Goldbach Legendre

Teoria dos crivos

Teoristas