Radici modulo m

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Radici modulo m

Messaggio da Ido Bovski » 21 set 2012, 00:56

Non parlo delle radici primitive modulo $m$, bensì delle radici $n$-esime modulo $m$. Ne ho sentito parlare al Senior (in realtà le ho soltato sentite citare), ed ho cercato di dar loro un senso.
Siano $a$ e $m>1$ due interi tali che $\gcd(a, m)=1$. Sia inoltre $k\in \mathbb{N}$ e $d={\rm ord}_m(a)$. Allora $\sqrt[n]{a}\equiv a^k \pmod m$ se e solo se $nk\equiv 1 \pmod d$.
Ad esempio, $\sqrt[3]{2}\equiv 2 \pmod 3$, o anche $\sqrt[7]{3}\equiv 3^3\equiv 2 \pmod 5$.
Ora le domande sono due:
-Ha senso la definizione che ho dato? (credo di sì)
-Come possono essere utili queste radici? Viene facile risolvere una cosa del tipo $x^7\equiv 3 \pmod 5$, infatti per il secondo esempio che ho dato $x\equiv 2 \pmod 5$. Ma credo ci sia dell'altro...

EvaristeG
Site Admin
Messaggi: 4772
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Radici modulo m

Messaggio da EvaristeG » 21 set 2012, 03:04

Hmm ... non capisco.
Più semplicemente, considera la funzione $f:x\mapsto x^n\ \bmod m$, che va da $\{0,1,\ldots, m-1\}$ a $\{0,1,\ldots, m-1\}$. Puoi chiamare radici $n-$esime di un numero $a$ modulo $m$ gli elementi $b$ tali che $f(b)=a$, ovvero $f^{-1}(a)$.
O, se vuoi, consideri le soluzioni dell'equazione $x^n\equiv a \bmod m$ (e questa, più che un'applicazione, è la definizione).
Per l'utilizzo, beh, pensa anche solo alla formula delle equazioni di II grado ... ti serve una radice quadrata, no?
Se consideri
$$x^2+2x+3\equiv 0 \bmod 11$$
puoi dire che
$$x=\frac{-2\pm\sqrt{4-4\cdot3}}{2}\equiv 6(-2\pm\sqrt{-8})\equiv 6(-2\pm5)\bmod 11$$
e dunque ci sono due soluzioni: $x=7$, $x=2$.
Infatti $(x-7)(x-2)=x^2-9x+14\equiv x^2+2x+3 \bmod 11\;.$
Ovviamente se ci sono più di due radici quadrate, si trovano più di due soluzioni, come in
$$x^2-5x+6\equiv 0 \bmod 15$$
Qui si ha $\Delta=25-24=1$ e $y^2\equiv 1\bmod 15$ ha come soluzioni $y=1,4,11,14$.
Dunque le soluzioni della prima equazione sono date dalla formula
$$x=\frac{5+y}{2}\equiv8(5+y)$$
che sono
$x=3$, $x=12$, $x=8$, $x=2$.
Infatti $(x-2)(x-3)=x^2-5x+6$, ma d'altra parte
$(8-2)(8-3)=6\cdot5=30\equiv0\bmod 15$
$(12-2)(12-3)=10\cdot9\equiv 0\bmod 15$
Quindi forse è più importante saperle tutte che non trovare quando ce n'è una sola.

BTW nella tua definizione richiedi implicitamente che $(n,\textrm{ord}_m(a))=1$, il che è condizione necessaria e sufficiente perché l'eq $x^n\equiv a$ abbia una soluzione e basta $\bmod m$.

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Radici modulo m

Messaggio da Ido Bovski » 21 set 2012, 16:14

Ok, chiaro, grazie :)

Rispondi