Como resolver $x^2 \equiv 12 \pmod {13}$?

Question

Resolver $x^2 \equiv 12 \pmod {13}$

Ao adivinhar, posso dizer que as soluções são $5$ e $8$, mas existe outra maneira de encontrar a solução além de adivinhar?

Answer 1

Como cosmo5 mencionou em seu comentário. Você pode fazer o seguinte, o que é um pouco melhor do que adivinhar, pois provavelmente você pode reconhecer instantaneamente os números quadrados. Para cada número natural$n$ temos $$ x^2 \equiv 12 \mod 13 \quad\Leftrightarrow\quad x^2 \equiv 12+13n \mod 13. $$ Portanto, você pode começar $$ \begin{array}{c|c} n & 12+13n \\ \hline 1 & 25 \\ 2 & 38 \\ 3 & 51 \\ 4 & 64 \end{array} $$ Então você vai ver isso por $n=1$ Você tem $5^2$ e para $n=4$ Você tem $8^2$, que fornece as soluções $x_1=5$ e $x_2=8$.

Alternativamente, você pode fazer uma divisão polinomial depois de encontrar uma solução, porque $$ x^2-12 \equiv (x-x_1)(x-x_2) \mod 13. $$ No entanto, isso pode levar mais tempo do que adivinhar para números pequenos.

Answer 2

Dica:

Como $x^2 \equiv a^2 \pmod {n}$ é mais fácil de manusear e $12\equiv25 \pmod {13}$, temos

$$ x^2 \equiv (\pm 5)^2 \pmod {13}$$

Answer 3

No caso especial de tentar encontrar uma raiz quadrada de $-1$ modulo a prime $p \equiv 1 \pmod{4}$, podemos usar o seguinte algoritmo: primeiro, selecione algum número inteiro aleatório $a$ com $1 < a < p - 1$. Agora se$p-1 = 2^k \cdot q$ com $q$ estranho, então forma $a^q \operatorname{mod} p$. Se você conseguir algo diferente de$1$ ou $-1$ neste ponto, então quadrar repetidamente até obter $-1$. Então, o número logo antes$-1$ será uma raiz quadrada de $-1$. (O motivo pelo qual isso funciona: pelo pequeno teorema de Fermat,$a^{p-1} \equiv 1 \pmod{p}$, então depois de pegar o quadrado $k$ vezes, você consegue $1$. Desde a$p$ é primo, o número antes de você chegar $1$ pela primeira vez é forçado a ser $-1$.)

Por outro lado, se $a^q \equiv \pm 1 \pmod{p}$ já, então volte e escolha outro valor aleatório de $a$tentar. Desde a$q < \frac{p - 1}{2}$, é impossível para todos os valores de $a$ satisfazer $a^q \equiv \pm 1 \pmod{p} \Leftrightarrow a^{2q} \equiv 1 \pmod{p}$.

Então, no caso de $p = 13$, Onde $p - 1 = 2^2 \cdot 3$ e entao $q = 3$, vamos primeiro começar com um teste de $a = 2$. Então,$a^q = 2^3 = 8$ e $8 \not\equiv \pm 1 \pmod{13}$, então estamos prontos para ir. Daqui,$8^2 = 64 \equiv -1 \pmod{13}$, e assim encontramos 8 como uma raiz quadrada de $-1 \pmod{13}$.

Answer 4

No campo ${\displaystyle \mathbb {Z} /13\mathbb {Z}}$, $\,[1] + [1] \ne [0]$e, portanto, há zero ou dois $\text{modulo-}13$ soluções para,

$\tag 1 x^2 \equiv 12 \pmod{13}$

Quando uma solução $[u]$ foi encontrada, a outra solução é $-[u]$.

Nós temos

$\; \large x^2 \equiv 12 \pmod{13} \; \text{ iff }$
$\; \large x^2 \equiv 2^{-2} \cdot (2^2 \cdot 12) \pmod{13} \; \text{ iff }$
$\; \large x^2 \equiv 2^{-2} \cdot (3^2) \pmod{13} \; \text{ iff }$
$\; \large x^2 \equiv \bigr(2^{-1} \cdot 3^1\bigr)^2 \pmod{13}$

Agora o inverso de $[2]$ é facilmente calculado,

$\quad [2]^{-1} = [\frac{13 + 1}{2}] = [7]$

e então uma solução para $\text{(1)}$ É dado por

$\quad x \equiv 7 \cdot 3 \equiv 8 \pmod{13}$

A outra solução é dada por

$\quad x \equiv -8 \equiv 5 \pmod{13}$

---

Nota: O exame desta questão resultou em uma conjectura ,

$\quad$ Um novo método para encontrar uma solução (quando houver) para $x^2 = a \pmod p$?