$x^17 \equiv 13 (253)$
Come risolvereste questo problema??? Ed ancora, quante soluzioni ha?
Ovviamente a breve posto una mia soluzione!
Ovviamente a breve posto una mia soluzione!
Risposte
Equivale a studiare gli zeri del polinomio $x^17 -[13]$ nell'anello $ZZ_253$ (anche se, francamente, questa strada mi sembra impraticabile...)
Io ho ragionato così. Se esiste una soluzione $x$ (tale per cui $MCD(x,253)=1$) si deve avere, per il teorema di Eulero:
$x^220 equiv 1 (mod 253)$
ove $220=phi(253)$ ($phi$ è la funzione totiente di Eulero)
inoltre $220=17*12+16$ e quindi, per le proprietà delle congruenze:
$x^17 equiv 13 (mod 253) => (x^17)^12 equiv 13^12 (mod 253) => (x^17)^12*x^16 equiv 13^12*x^16 (mod 253)$
ovverosia:
$13^12*x^16 equiv 1 (mod 253)$ (*)
detta ora $k$ l'unica soluzione modulo $253$ di (*), abbiamo che:
$x^16 equiv k (mod 253)$.
Iterando il procedimento, s'otterrà un progressivo abbassamento dell'esponente di $x$ (è un po' come l'algoritmo di Euclide: il resto della $n$-esima divisione diventa il divisore della $n+1$-esima divisione...). Se ad un certo punto dovessimo bloccarci, a causa di una congruenza irrisolubile, concluderemmo che non esistono soluzioni coprime con $253$ (e quindi rimmarrebbero da controllare gli interi del tipo $11^n*23^m$,$n,m in NN$ noto che $253=11*23$). Mentre se, ad un certo punto, otteniamo un resto (diverso da $1$) che divide $phi(253)$, l'algoritmo si ferma, senza dare informazioni su $x$:
[size=75]EDIT: questo è il nostro caso, si termina con la semplificazione:
$x^4 equiv 48 (mod 253)$[/size]
EDIT: Se $x=11^n*23^m$,$n,m in NN$, abbiamo a che fare con un divisore dello zero, cioè esiste $y in NN$ tale che $x*y equiv 0 mod 253$. Ma allora, sempre per le proprietà delle congruenze:
$x^17 equiv 13 (mod 253) => x^16*(x*y) equiv 13*y (mod 253) => 0 equiv 13*y (mod 253)$, assurdo, $13$ non è divisore dello zero, in $ZZ_253$...
Quindi se l'algoritmo "fallisce" a causa di una congruenza senza soluzioni, non esistono soluzioni all'equazione data.
Io ho ragionato così. Se esiste una soluzione $x$ (tale per cui $MCD(x,253)=1$) si deve avere, per il teorema di Eulero:
$x^220 equiv 1 (mod 253)$
ove $220=phi(253)$ ($phi$ è la funzione totiente di Eulero)
inoltre $220=17*12+16$ e quindi, per le proprietà delle congruenze:
$x^17 equiv 13 (mod 253) => (x^17)^12 equiv 13^12 (mod 253) => (x^17)^12*x^16 equiv 13^12*x^16 (mod 253)$
ovverosia:
$13^12*x^16 equiv 1 (mod 253)$ (*)
detta ora $k$ l'unica soluzione modulo $253$ di (*), abbiamo che:
$x^16 equiv k (mod 253)$.
Iterando il procedimento, s'otterrà un progressivo abbassamento dell'esponente di $x$ (è un po' come l'algoritmo di Euclide: il resto della $n$-esima divisione diventa il divisore della $n+1$-esima divisione...). Se ad un certo punto dovessimo bloccarci, a causa di una congruenza irrisolubile, concluderemmo che non esistono soluzioni coprime con $253$ (e quindi rimmarrebbero da controllare gli interi del tipo $11^n*23^m$,$n,m in NN$ noto che $253=11*23$). Mentre se, ad un certo punto, otteniamo un resto (diverso da $1$) che divide $phi(253)$, l'algoritmo si ferma, senza dare informazioni su $x$:
[size=75]EDIT: questo è il nostro caso, si termina con la semplificazione:
$x^4 equiv 48 (mod 253)$[/size]
EDIT: Se $x=11^n*23^m$,$n,m in NN$, abbiamo a che fare con un divisore dello zero, cioè esiste $y in NN$ tale che $x*y equiv 0 mod 253$. Ma allora, sempre per le proprietà delle congruenze:
$x^17 equiv 13 (mod 253) => x^16*(x*y) equiv 13*y (mod 253) => 0 equiv 13*y (mod 253)$, assurdo, $13$ non è divisore dello zero, in $ZZ_253$...
Quindi se l'algoritmo "fallisce" a causa di una congruenza senza soluzioni, non esistono soluzioni all'equazione data.
Premetto che è tardi e sono stanco... Se dico cretinate troppo grosse vi prego di farmelo notare...
la congruenza $x^17 equiv 13 (mod253)$ non si può spezzare nel sistema di congruenze
$\{[x^17 equiv 13 (mod 11)],[x^17 equiv 13 (mod 23)]:}$
(ad esempio con un cambio di variabile $x^17=y$ e poi applicando il teorema cinese del resto o qualcosa di simile)?
Adesso sembrerebbe leggermente più attaccabile...
Ad esempio la prima congruenza diventa (per il teorema di Eulero) $x^7 equiv 2(mod 11)$.
Adesso non riesco più ad andare avanti, ma domani ci riprovo... A voi che cosa sembra? Ho detto una cretinata?
la congruenza $x^17 equiv 13 (mod253)$ non si può spezzare nel sistema di congruenze
$\{[x^17 equiv 13 (mod 11)],[x^17 equiv 13 (mod 23)]:}$
(ad esempio con un cambio di variabile $x^17=y$ e poi applicando il teorema cinese del resto o qualcosa di simile)?
Adesso sembrerebbe leggermente più attaccabile...
Ad esempio la prima congruenza diventa (per il teorema di Eulero) $x^7 equiv 2(mod 11)$.
Adesso non riesco più ad andare avanti, ma domani ci riprovo... A voi che cosa sembra? Ho detto una cretinata?
Allora ho determinato una soluzione. Essa è $x equiv 8 (mod 253)$. Tuttavia devo confessare che è in parte empirica.
Posto il metodo.
La prima congruenza del sistema che ho postato prima diventa equivalente per il teorema di Eulero a $x^7 equiv 2 (mod 11) rarr x^7*x^3 equiv 2*x^3 (mod 11)$ (lo posso fare perché $x equiv 0 (mod 11)$ non è soluzione). Quindi l'equazione diventa $x^3 equiv 6 (mod 11)$. Dal momento che $11-2=9$ è divisibile per tre, ogni numero in $ZZ_11$ è un residuo cubico. La soluzione sarà $6^27 (mod 11)$ (sono in grado di giustificare quest'affermazione), cioè $x equiv 8 (mod 11)$.
L'altra congruenza, invece, sempre per il teorema di Eulero equivale a $13x^5 equiv 1 (mod 23) rarr x^5 equiv 16 (mod 23)$.
Qui io non sono in grado di dare una soluzione generale dell'equazione a differenza di prima. Quindi devo procedere empiricamente; ho trovato anche in questo caso la soluzione $x equiv 8 (mod 23)$, da cui segue la mia affermazione iniziale.
Se conoscete un metodo per risolvere non empiricamente quella congruenza, vi prego di farmelo sapere, sono molto curioso.
E' lo stesso procedimento che hai usato tu, Lord K?
Posto il metodo.
La prima congruenza del sistema che ho postato prima diventa equivalente per il teorema di Eulero a $x^7 equiv 2 (mod 11) rarr x^7*x^3 equiv 2*x^3 (mod 11)$ (lo posso fare perché $x equiv 0 (mod 11)$ non è soluzione). Quindi l'equazione diventa $x^3 equiv 6 (mod 11)$. Dal momento che $11-2=9$ è divisibile per tre, ogni numero in $ZZ_11$ è un residuo cubico. La soluzione sarà $6^27 (mod 11)$ (sono in grado di giustificare quest'affermazione), cioè $x equiv 8 (mod 11)$.
L'altra congruenza, invece, sempre per il teorema di Eulero equivale a $13x^5 equiv 1 (mod 23) rarr x^5 equiv 16 (mod 23)$.
Qui io non sono in grado di dare una soluzione generale dell'equazione a differenza di prima. Quindi devo procedere empiricamente; ho trovato anche in questo caso la soluzione $x equiv 8 (mod 23)$, da cui segue la mia affermazione iniziale.
Se conoscete un metodo per risolvere non empiricamente quella congruenza, vi prego di farmelo sapere, sono molto curioso.
E' lo stesso procedimento che hai usato tu, Lord K?
Ho operato un metodo molto siile a quello di Dorian usando poi i risultati di un post precedente. La domanda he mi sorge poi, al di là dell'effettiva soluzione, è che pare non esserci un metodo di "esistenza" valido. Avete qualche idea in merito???
P.S. Sto cercando a questo proposito la versione della teoria di Galois per i campi finiti...
P.S. Sto cercando a questo proposito la versione della teoria di Galois per i campi finiti...
Per quanto riguarda ad esempio i residui cubici io ho trovato questo (in analogia con i residui quadratici). Se si tratta di risolvere la congruenza $x^3 equiv a (mod p)$, allora vale il seguente risultato:
1) se $p-1 equiv 0 (mod 3)$ allora la congruenza a soluzione se e solo se $a^((p-1)/3) equiv 1 (mod p)$;
2) se $p-2 equiv 0 (mod 3)$ allora una soluzione della congruenza è sempre $(a^((p-2)/3))^(-1)$, dove con l'elevamento alla meno 1 intendo l'elemento inverso alla moltiplicazione.
Credo che il punto 1 possa essere generalizzato ai residui k-esimi in generale, mentre il punto 2 mi sa che è più difficoltoso...
1) se $p-1 equiv 0 (mod 3)$ allora la congruenza a soluzione se e solo se $a^((p-1)/3) equiv 1 (mod p)$;
2) se $p-2 equiv 0 (mod 3)$ allora una soluzione della congruenza è sempre $(a^((p-2)/3))^(-1)$, dove con l'elevamento alla meno 1 intendo l'elemento inverso alla moltiplicazione.
Credo che il punto 1 possa essere generalizzato ai residui k-esimi in generale, mentre il punto 2 mi sa che è più difficoltoso...
Se fosse come proponi tu maurer, avresti che:
$x^n \equiv a(p)$ implicherebbe l'esistenza della soluzione se $(a/p)_k \equiv a^((p-1)/k)(p)$
ma come detto non sono convinto e sto per produrti un controesempio.
$x^n \equiv a(p)$ implicherebbe l'esistenza della soluzione se $(a/p)_k \equiv a^((p-1)/k)(p)$
ma come detto non sono convinto e sto per produrti un controesempio.
Non lo so, io la dimostrazione nel caso dei residui k-esimi in generale non l'ho mai vista né ho mai provato a farla...
Tutto quello che so è che nel caso particolare dei residui cubici quello che ho scritto è corretto; la dimostrazione però l'ho fatta io... potrei anche avere sbagliato qualcosa... se vuoi provo a postarla (anche se è un pochino lunga...)
Tutto quello che so è che nel caso particolare dei residui cubici quello che ho scritto è corretto; la dimostrazione però l'ho fatta io... potrei anche avere sbagliato qualcosa... se vuoi provo a postarla (anche se è un pochino lunga...)
"Lord K":
...pare non esserci un metodo di "esistenza" valido. Avete qualche idea in merito???
Ignoro... è la prima volta che tratto congruenze non lineari...
Anzi, seconda... Una volta ho risolto una semplice congruenza di secondo grado... Tutta un'altra cosa, ovviamente!
La teoria di Galois è fatta su campi in generale ed anche in un qualsiasi $ZZ_p$ è valida.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo