Aritmética modular – Wikipédia, a enciclopédia livre

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (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.^[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 ${\displaystyle 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, ${\displaystyle 15}$ é congruente com ${\displaystyle 3}$ módulo ${\displaystyle 12}$, então "15:00" em um relógio de 24 horas é exibido "3:00 "em um relógio de 12 horas.

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

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

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

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

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

${\displaystyle a=kn+b,}$

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

${\displaystyle a=pn+r,}$

${\displaystyle b=qn+r,}$

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

${\displaystyle a-b=kn,}$

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

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

${\displaystyle 38\equiv 14{\pmod {12}}}$

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

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

${\displaystyle 38\equiv 2{\pmod {12}}}$

pois ${\displaystyle 38-2=36}$, que é múltiplo de 12. Note que ${\displaystyle {\frac {38}{12}}}$ e ${\displaystyle {\frac {2}{12}}}$ tem o mesmo resto 2. Observe que também, utilizando o exemplo anterior, ${\displaystyle 14-2=12}$ é inteiro múltiplo de 12, isto é ${\displaystyle 14\equiv 2{\pmod {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

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 ${\displaystyle a\equiv _{n}b}$ for usada, em vez da notação tradicional.

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

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

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

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

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

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

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

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

O inverso multiplicativo modular é definido pelas seguintes regras:

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

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

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

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

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

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

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

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

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

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

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

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

• ${\displaystyle {\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}}$
• ${\displaystyle {\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, ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ se torna um anel comutativo. Por exemplo, no anel ${\displaystyle \mathbb {Z} /24\mathbb {Z} }$, temos

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

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

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

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

O conjunto ${\displaystyle \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 ${\displaystyle \mathbb {Z} /0\mathbb {Z} }$ (que, como mencionado antes, é isomorfo ao anel ${\displaystyle \mathbb {Z} }$ dos inteiros), por exemplo quando discutindo característica de um anel.

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.

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

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

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

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

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

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.

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.

Considere a equação ${\displaystyle ax^{2}+bx+c\equiv 0{\pmod {p}}}$, onde ${\displaystyle a,b,c\in \mathbb {Z} }$, ${\displaystyle p}$ é um primo (ímpar) e ${\displaystyle a\not \equiv 0{\pmod {p}}}$. Podemos observar que ${\displaystyle (a,p)=1}$ e como ${\displaystyle p}$ é ímpar temos ${\displaystyle (4a,p)=1}$. Assim, a equação acima é equivalente a ${\displaystyle 4a(ax^{2}+bx+c)\equiv 0{\pmod {p}}}$. Ao completarmos quadrados obtemos ${\displaystyle (2ax+b)^{2}-(b^{2}-4ac)\equiv 0{\pmod {p}}}$. Ao fazermos ${\displaystyle y=2ax+b}$ e ${\displaystyle d=b^{2}-4ac}$, vem ${\displaystyle 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 ${\displaystyle x^{2}\equiv a{\pmod {p}}}$. Pois se ${\displaystyle p\mid a}$ (lê-se "p divide a") obtemos desinteressante a equação ${\displaystyle x^{2}\equiv 0{\pmod {p}}}$ e, por essa razão ${\displaystyle x\equiv 0{\pmod {p}}}$ o que torna indispensável assumir que ${\displaystyle p\nmid a}$ ("p não divide a") a fim de evitarmos soluções triviais.

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

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

• Portal da matemática