Come risolvere $x^2 \equiv 12 \pmod {13}$?

Question

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

Indovinando posso dire che le soluzioni sono $5$ e $8$, ma c'è un altro modo per trovare la soluzione oltre a indovinare?

Answer 1

Come ha detto cosmo5 nel suo commento. Puoi fare quanto segue, il che è un po 'meglio che indovinare poiché probabilmente puoi riconoscere immediatamente i numeri quadrati. Per ogni numero naturale$n$ noi abbiamo $$ x^2 \equiv 12 \mod 13 \quad\Leftrightarrow\quad x^2 \equiv 12+13n \mod 13. $$ Quindi, puoi iniziare $$ \begin{array}{c|c} n & 12+13n \\ \hline 1 & 25 \\ 2 & 38 \\ 3 & 51 \\ 4 & 64 \end{array} $$ Allora lo vedrai per $n=1$ hai $5^2$ e per $n=4$ hai $8^2$, che ti dà le soluzioni $x_1=5$ e $x_2=8$.

In alternativa puoi fare una divisione polinomiale dopo aver trovato una soluzione, perché $$ x^2-12 \equiv (x-x_1)(x-x_2) \mod 13. $$ Tuttavia, questo potrebbe richiedere più tempo rispetto a indovinare per piccoli numeri.

Answer 2

Suggerimento:

Come $x^2 \equiv a^2 \pmod {n}$ è più facile da gestire e $12\equiv25 \pmod {13}$, noi abbiamo

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

Answer 3

Nel caso speciale di provare a trovare una radice quadrata di $-1$ modulo un primo $p \equiv 1 \pmod{4}$, possiamo usare il seguente algoritmo: per prima cosa, seleziona un numero intero casuale $a$ con $1 < a < p - 1$. Ora se$p-1 = 2^k \cdot q$ con $q$ strano, quindi forma $a^q \operatorname{mod} p$. Se ottieni qualcosa di diverso da$1$ o $-1$ a questo punto, quindi ripetutamente quadrato fino ad ottenere $-1$. Quindi, il numero appena prima$-1$ sarà una radice quadrata di $-1$. (Il motivo per cui funziona: dal piccolo teorema di Fermat,$a^{p-1} \equiv 1 \pmod{p}$, quindi dopo aver preso la piazza $k$ volte, puoi $1$. Da$p$ è primo, il numero appena prima di raggiungerlo $1$ per la prima volta è costretto ad esserlo $-1$.)

D'altra parte, se $a^q \equiv \pm 1 \pmod{p}$ già, quindi torna indietro e scegli un altro valore casuale di $a$provare. Da$q < \frac{p - 1}{2}$, è impossibile per ogni valore di $a$ per soddisfare $a^q \equiv \pm 1 \pmod{p} \Leftrightarrow a^{2q} \equiv 1 \pmod{p}$.

Quindi, nel caso di $p = 13$, dove $p - 1 = 2^2 \cdot 3$ e così $q = 3$, iniziamo prima con una prova di $a = 2$. Poi,$a^q = 2^3 = 8$ e $8 \not\equiv \pm 1 \pmod{13}$, quindi siamo a posto. Da qui,$8^2 = 64 \equiv -1 \pmod{13}$, e quindi troviamo 8 come radice quadrata di $-1 \pmod{13}$.

Answer 4

Nel campo ${\displaystyle \mathbb {Z} /13\mathbb {Z}}$, $\,[1] + [1] \ne [0]$, e quindi ci sono o zero o due distinti $\text{modulo-}13$ soluzioni per,

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

Quando una soluzione $[u]$ è stata trovata l'altra soluzione è $-[u]$.

abbiamo

$\; \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}$

Ora l'inverso di $[2]$ è facilmente calcolabile,

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

e quindi una soluzione per $\text{(1)}$ è dato da

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

L'altra soluzione è data da

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

---

Nota: l'esame di questa domanda ha portato a una congettura ,

$\quad$ Un nuovo metodo per trovare una soluzione (quando esistono) a $x^2 = a \pmod p$?