Sistemi di congruenze non lineari - Teorema Cinese del Resto
Ciao a tutti!
Ho bisogno di aiuto per risolvere una tipologia di esercizi che mi lascia alquanto perplessa: sistemi di congruenze non lineari.
Il testo dell'esercizio è solitamente di questo tipo:
"Determinare tutti gli elementi di ordine 3 del gruppo degli invertibili di $ ZZ_91 $ ."
Ora, sulle dispense che ho, l'esercizio viene svolto fattorizzando $ 91=7*13 $ , e considerando singolarmente le due equazioni $ x^(3) -= 1 mod(7) $ (le cui soluzioni sono 1,2,4) e $ x^(3) -= 1 mod(13) $ (le cui soluzioni sono 1,3,9). (Qui se anche le soluzioni sono state trovate "a tentoni" va ancora bene, dato che si tratta di numeri relativamente piccoli).
A questo punto le dispense dichiarano, "Le soluzioni di $ x^(3) -= 1 mod(91) $ si ottengono applicando il teorema cinese del resto, e troviamo $ 3*3 $ soluzioni, e quindi 9-1=8 elementi di ordine 3, che sono 9,16,22,29,53,74,79,81."
Ora, io il Teorema Cinese del Resto non l'ho mai sentito applicato a sistemi di congruenze NON lineari, e onestamente non so proprio che conti vadano svolti per trovare le soluzioni... ma non oso davvero pensare di dover provare tutti i numeri compresi tra 1 e 91 finché non ne trovo nove tali che elevati al cubo diano 1... o sì?
Qualcuno sa di come vada svolto questo esercizio senza andare a tentoni?? Io sto brancolando nel buio!!
Ho bisogno di aiuto per risolvere una tipologia di esercizi che mi lascia alquanto perplessa: sistemi di congruenze non lineari.
Il testo dell'esercizio è solitamente di questo tipo:
"Determinare tutti gli elementi di ordine 3 del gruppo degli invertibili di $ ZZ_91 $ ."
Ora, sulle dispense che ho, l'esercizio viene svolto fattorizzando $ 91=7*13 $ , e considerando singolarmente le due equazioni $ x^(3) -= 1 mod(7) $ (le cui soluzioni sono 1,2,4) e $ x^(3) -= 1 mod(13) $ (le cui soluzioni sono 1,3,9). (Qui se anche le soluzioni sono state trovate "a tentoni" va ancora bene, dato che si tratta di numeri relativamente piccoli).
A questo punto le dispense dichiarano, "Le soluzioni di $ x^(3) -= 1 mod(91) $ si ottengono applicando il teorema cinese del resto, e troviamo $ 3*3 $ soluzioni, e quindi 9-1=8 elementi di ordine 3, che sono 9,16,22,29,53,74,79,81."
Ora, io il Teorema Cinese del Resto non l'ho mai sentito applicato a sistemi di congruenze NON lineari, e onestamente non so proprio che conti vadano svolti per trovare le soluzioni... ma non oso davvero pensare di dover provare tutti i numeri compresi tra 1 e 91 finché non ne trovo nove tali che elevati al cubo diano 1... o sì?
Qualcuno sa di come vada svolto questo esercizio senza andare a tentoni?? Io sto brancolando nel buio!!
Risposte
In realtà qui il trucco sta nello studiare le soluzioni del polinomio [tex]x^3-1 \equiv 0 (91)[/tex].
Questo si fattorizza come sai come:
[tex]x^3-1=(x-1)(x^2+x+1)[/tex]
e da qui si prosegue genialmente con il calcolo di:
[tex]x^2+x+1 \equiv 0 (91)[/tex]
e qui pari pari come viene fatto per le equazioni di secondo grado:
[tex]x^2+2\cdot 2^{-1}x+1 \equiv 0 (91)[/tex]
e qui hai che:
[tex]2^{-1}\equiv -45 (91)[/tex]
quindi:
[tex]x^2+2\cdot 45x+45^2-45^2 +1 \equiv 0 (91)[/tex]
[tex](x+45)^2 \equiv -1-45^2 (91)[/tex]
[tex](x+45)^2 \equiv -24(91)[/tex]
[tex](x+45)^2 \equiv 67(91)[/tex]
e qui usiamo il mitico simbolo di Jacobi ed il teorema di reciprocità:
[tex](\frac{67}{91})\cdot(\frac{91}{67})=(-1)^{\frac{(67-1)(91-1)}{4}}=-1[/tex]
allora abbiamo che:
[tex](\frac{67}{91})=-(\frac{91}{67})=-(\frac{7}{67})(\frac{13}{67})=-(-1)(\frac{13}{67})=(\frac{13}{67})=(\frac{2}{13})=-1[/tex]
ovvero che non si direbbe un quadrato! Allora necessariamente deve essere che:
[tex]x^3-1=(x-1)(x^2+x+1)=91k[/tex]
ed allora o vale:
[tex](x-1)\equiv 7 (91)[/tex]
ed anche:
[tex](x^2+x+1)\equiv 13 (91)[/tex]
oppure il contrario. Dovrebbe essere tutto!
Questo si fattorizza come sai come:
[tex]x^3-1=(x-1)(x^2+x+1)[/tex]
e da qui si prosegue genialmente con il calcolo di:
[tex]x^2+x+1 \equiv 0 (91)[/tex]
e qui pari pari come viene fatto per le equazioni di secondo grado:
[tex]x^2+2\cdot 2^{-1}x+1 \equiv 0 (91)[/tex]
e qui hai che:
[tex]2^{-1}\equiv -45 (91)[/tex]
quindi:
[tex]x^2+2\cdot 45x+45^2-45^2 +1 \equiv 0 (91)[/tex]
[tex](x+45)^2 \equiv -1-45^2 (91)[/tex]
[tex](x+45)^2 \equiv -24(91)[/tex]
[tex](x+45)^2 \equiv 67(91)[/tex]
e qui usiamo il mitico simbolo di Jacobi ed il teorema di reciprocità:
[tex](\frac{67}{91})\cdot(\frac{91}{67})=(-1)^{\frac{(67-1)(91-1)}{4}}=-1[/tex]
allora abbiamo che:
[tex](\frac{67}{91})=-(\frac{91}{67})=-(\frac{7}{67})(\frac{13}{67})=-(-1)(\frac{13}{67})=(\frac{13}{67})=(\frac{2}{13})=-1[/tex]
ovvero che non si direbbe un quadrato! Allora necessariamente deve essere che:
[tex]x^3-1=(x-1)(x^2+x+1)=91k[/tex]
ed allora o vale:
[tex](x-1)\equiv 7 (91)[/tex]
ed anche:
[tex](x^2+x+1)\equiv 13 (91)[/tex]
oppure il contrario. Dovrebbe essere tutto!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo