Aritmética modular

Predefinição:Mais notas

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.^[1] A abordagem moderna da aritmética modular foi desenvolvida por Carl Friedrich Gauss em seu livro Disquisitiones Arithmeticae, publicado em 1801.

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$ , 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$ é congruente com $3$ módulo $12$ , então "15:00" em um relógio de 24 horas é exibido "3:00 "em um relógio de 12 horas.

Congruência com expoentes maiores que 3 São congruentes a 7 módulo 12.

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

A congruência módulo $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$ é denotada como:

a \equiv b (\mod n) .

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

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

a = k n + b,

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

a = p n + r,

b = q n + r,

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

a - b = k n,

definindo $k = p - q$ .

Exemplos

Exemplo 1

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

38 \equiv 14 (\mod 12)

porque $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:

\begin{matrix} - 8 & \equiv 7 (\mod 5) \\ 2 & \equiv - 3 (\mod 5) \\ - 3 & \equiv - 8 (\mod 5) . \end{matrix}

Exemplo 2

38 \equiv 2 (\mod 12)

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

Padrão de distribuição dos expoentes dos números primos de Mersenne módulo 12^[3]

Congruência 1 (mod 12): 21.15%

Congruência 5 (mod 12): 40.38%

Congruência 7 (mod 12): 25.00%

Congruência 11 (mod 12): 9.62%

Números separados por congruência (mod 12):

Congruência 1: [13, 61, 2281, 3217, 23209, 44497, 132049, 13466917, 30402457, 42643801, 74207281]

Congruência 5: [5, 17, 89, 521, 4253, 9689, 9941, 11213, 19937, 21701, 859433, 1398269, 2976221, 3021377, 6972593, 32582657, 43112609, 57885161, 77232917, 82589933, 136279841]

Congruência 7: [7, 19, 31, 127, 607, 1279, 2203, 4423, 110503, 216091, 1257787, 20996011, 24036583]

Congruência 11: [107, 86243, 756839, 25964951, 37156667]

E todos os primos Mercenne maiores que 5 são congruentes a 7 módulo 12

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 \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 \equiv a (\mod n)$
Simetria: $a \equiv b (\mod n)$ se $b \equiv a (\mod n)$ para todo $a$ , $b$ e $n$ .
Transitividade: Se $a \equiv b (\mod n)$ e $b \equiv c (\mod n)$ , então $a \equiv c (\mod n)$

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

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

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

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

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

Se $a + k \equiv b + k (\mod n)$ para qualquer inteiro $k$ , então $a \equiv b (\mod n)$
Se $k a \equiv k b (\mod n)$ e $k$ é coprimo com $n$ , então $a \equiv b (\mod n)$

O inverso multiplicativo modular é definido pelas seguintes regras:

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

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

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

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

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

a^{(p - 1) / 2} \equiv 1 (\mod 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 ${\overline{a}}_{n}$ , é o conjunto ${\dots, a - 2 n, a - n, a, a + n, a + 2 n, \dots}$ . Este conjunto, consistindo dos inteiros congruentes a $a$ modulo $n$ , é chamado a classe de congruência ou classe de resíduos ou simplesmente resíduo do inteiro $a$ modulo $n$ . Quando o módulo $n$ é conhecido pelo contexto, este resíduo também pode ser denotado por $[a]$ .

Anel de classes de congruência

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

Quando $n \neq 0$ , $ℤ / n ℤ$ tem n elementos, e pode ser escrita como:

ℤ / n ℤ = {{\overline{0}}_{n}, {\overline{1}}_{n}, {\overline{2}}_{n}, \dots, {\overline{n - 1}}_{n}} .

Quando n = 0, $ℤ / n ℤ$ não tem elementos não nulos; daí é isomorfo a $ℤ$ , pois ${\overline{a}}_{0} = {a}$ .

Podemos definir adição, subtração e multiplicação em $ℤ / n ℤ$ pelas seguintes regras:

${\overline{a}}_{n} + {\overline{b}}_{n} = {\overline{(a + b)}}_{n}$
${\overline{a}}_{n} - {\overline{b}}_{n} = {\overline{(a - b)}}_{n}$
${\overline{a}}_{n} {\overline{b}}_{n} = {\overline{(a b)}}_{n} .$

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

Desta forma, $ℤ / n ℤ$ se torna um anel comutativo. Por exemplo, no anel $ℤ / 24 ℤ$ , temos

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

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

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

Em termos de grupos, a classe de resíduos ${\overline{a}}_{n}$ é a classe lateral de a no grupo quociente $ℤ / n ℤ$ , um grupo cíclico.^[4]

O conjunto $ℤ / n ℤ$ 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 $ℤ / 0 ℤ$ (que, como mencionado antes, é isomorfo ao anel $ℤ$ 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, Predefinição:Nowrap. 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 Predefinição:Nowrap, que pode ser encontrado usando divisão longa. Segue disso que enquanto é correto dizer Predefinição:Nowrap e Predefinição:Nowrap, é incorreto dizer Predefinição:Nowrap (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 Predefinição:Nowrap, em vez de Predefinição:Nowrap, 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 Predefinição:Nowrap ou Predefinição:Nowrap, ou são colocados em volta do divisor, por exemplo Predefinição:Nowrap. Notações como Predefinição:Nowrap 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 - ⌊ \frac{a}{n} ⌋ \times n,

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

\begin{matrix} a \equiv b (\mod n) e, \\ 0 \leq b < n . \end{matrix}

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

b = a - ⌊ \frac{a}{n} ⌋ \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.^[5]

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)^[6]

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

Exemplo

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

Como $(8, 23) = 1$ e $p = 23$ é primo ímpar temos que $(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 \equiv 0 (\mod 23) \Rightarrow (16 x + 5)^{2} \equiv 16 (\mod 23)$ . Com isso encontramos $16 x + 5 \equiv \pm 4 (\mod 23)$ , onde ao resolvermos a congruência linear $16 x \equiv - 1 (\mod 23)$ temos $x \equiv 10 (\mod 23)$ , enquanto a partir da congruência linear $x \equiv - 9 (\mod 23)$ , obtemos $x \equiv 21 (\mod 23)$ . Dessa maneira, $10$ e $21$ são as únicas soluções incongruentes. De fato, se $x = 10 \Rightarrow 8 x^{2} + 5 x + 1 = 851$ e $851 \equiv 0 (\mod 23)$ . Se $x = 21 \Rightarrow 8 x^{2} + 5 x + 1 = 3634$ e $3634 \equiv 0 (\mod 23)$ .

Referências

↑ http://www.ams.org/samplings/feature-column/fcarc-eulers-formula
↑ Predefinição:Citar web
↑ Predefinição:Citar periódico
↑ 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.

Predefinição:Teoria dos números Predefinição:Portal3

[enciclopédia_britânica-1] ttp://www.ams.org/samplings/feature-column/fcarc-eulers-formula

[:0-2] Predefinição:Citar web

[3] Predefinição:Citar periódico

[Arnaldo-4] Arnaldo Garcia e Yves Lequain. Elementos de Álgebra - Rio de Janeiro, IMPA, 2002. 326 páginas (Projeto Euclides), ISBN 978-85-244-0190-9

[Plinio-5] 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

[6] SAID, Sidki. Introdução à Teoria dos Números. Colóquio Brasileiro de Matemática, IMPA, 1975.

[1]

[2]

[3]

[4]

[5]

[6]

Aritmética modular

Índice

Congruência com expoentes maiores que 3 São congruentes a 7 módulo 12.

Exemplos

Exemplo 1

Exemplo 2

Notação

Propriedades

Classes de congruência

Anel de classes de congruência

Restos

Representação funcional da operação resto

Sistema de resíduos

Sistemas reduzidos de resíduos

Congruências quadráticas (ou do segundo grau)^[6]

Exemplo

Referências

Menu de navegação

Aritmética modular

Congruência com expoentes maiores que 3 São congruentes a 7 módulo 12.

Exemplos

Exemplo 1

Exemplo 2

Notação

Propriedades

Classes de congruência

Anel de classes de congruência

Restos

Representação funcional da operação resto

Sistema de resíduos

Sistemas reduzidos de resíduos

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

Exemplo

Referências

Menu de navegação

Pesquisa

Congruências quadráticas (ou do segundo grau)^[6]