Come risolvere questo tipo di congruenze?
Come da oggetto del topic chiedo aiuto per risolvere queste due congruenze. Ci ho provato, ma usando il teorema di Fermat - Capelli per risolverle il risultato è sbagliato.
1) x^9≡5 mod23 il risultato che mi esce è 9mod23
2) x^5≡16 mod27 il risultato che mi esce è 23mod27
Qualcuno gentilmente mi potrebbe dare una mano?..grazie mille..
1) x^9≡5 mod23 il risultato che mi esce è 9mod23
2) x^5≡16 mod27 il risultato che mi esce è 23mod27
Qualcuno gentilmente mi potrebbe dare una mano?..grazie mille..
Risposte
leggendo x, viene in mente che si tratti di equazioni nell'incognita x.... non so se è quello che ti serve, ma, scrivendo $x^9=23k+5$ ed applicando le proprietà dei logaritmi, si arriva a $x=(23k+5)^(1/9)$ non so se è accettabile una soluzione con k. Qual è il risultato che dovresti ottenere?
"adaBTTLS":
leggendo x, viene in mente che si tratti di equazioni nell'incognita x.... non so se è quello che ti serve, ma, scrivendo $x^9=23k+5$ ed applicando le proprietà dei logaritmi, si arriva a $x=(23k+5)^(1/9)$ non so se è accettabile una soluzione con k. Qual è il risultato che dovresti ottenere?
Allora la prima l'ho risolta in questo modo:
MCD(9,23) = 1 --> Esiste una soluzione
MCD(5,phi(23)) = MCD(5,18) = 1 --> Uso il teorema di Fermat - Capelli per risolvere la congruenza:
Trovo un inverso di (5,18)
18 = 3*5 + 3 --> 3 = 18 + (-3)*5
5 = 1*3 + 2 --> 2 = 5 + (-1)*3 = 5 + (-1)*(18+(-3)*5) = 4*5 + (-1)*18
3 = 1*2 + 1 --> 1 = 3 + (-1)*2 = 18 + (-3)*5 + (-1)*(4*5+(-1)*18) = 2*18 + (-7)*5
quindi l'inverso di 5mod18 = -7mod18 = 11mod18
Di conseguenza il risultato è dato dalle classi fatte in questo modo:
2^d mod 23 dove d = 11
quindi 2^11mod23 = 2048mod23 = 1mod23
ma sostituendo nella congruenza iniziale verrebbe:
$1^9-=5 (mod23)$
cioè
$1-=5 (mod23)$
ed è sbagliato...perchè? lo stesso procedimento l'ho fatto con l'altro e viene il risultato che ho scritto sopra..
il risultato corretto non lo so perchè nn c'è sulla scheda dell'esercizio da cui ho rpeso gli esercizi..
qualcuno sa dirmi gentilmente dove ho sbagliato?
"adaBTTLS":
leggendo x, viene in mente che si tratti di equazioni nell'incognita x.... non so se è quello che ti serve, ma, scrivendo $x^9=23k+5$ ed applicando le proprietà dei logaritmi, si arriva a $x=(23k+5)^(1/9)$ non so se è accettabile una soluzione con k. Qual è il risultato che dovresti ottenere?
In questo caso la soluzione deve essere intera visto che il problema è di aritmetica modulare...
se $a\equivbmodn$ allora $a^i\equivb^imodn$ e $a^phi(n)\equiv1modn$
nella prima equazione elevo tutti e due i membri alla 5 (potrei aggiungere qualche soluzione in più in questo modo) ($phi(23)=22$)
$(x^9)^5=x^45=(x^22)^2*x=x$
$5^5=5^2*5^2*5=2*2*5=20$ quindi $x=20$
la seconda ora non ho tempo casomai domani, dovrebbe essere giusto ma dai una ricontrollata
nella prima equazione elevo tutti e due i membri alla 5 (potrei aggiungere qualche soluzione in più in questo modo) ($phi(23)=22$)
$(x^9)^5=x^45=(x^22)^2*x=x$
$5^5=5^2*5^2*5=2*2*5=20$ quindi $x=20$
la seconda ora non ho tempo casomai domani, dovrebbe essere giusto ma dai una ricontrollata
allora, la soluzione che mi hai dato te è esatta, e infatti poi sono riuscita a trovarla per tentativi..il problema è che con il metodo che ci ha dato il nostro prof non risulta 20mod23...assodato che avevo sbagliato a scrivere il phi(23) perchè effettivamente è 22 e non 18 ho rifatto i calcoli e viene fuori che l'inverso di 9mod22 è 5mod22 e la soluzione finale è 32mod23 = 9mod23 ed è ancora sbagliata..perchè?...grazie e scusate la mia ignoranza
credo che sbagli ad applicare il teorema, io non lo conoscevo però mi pare che nei passaggi ho fatto quello che di fatto fa il teorema. il problema è che te lo applichi male le soluzioni non possono essere $2^d$ sempre, saranno piuttosto il termine noto dell'equazione elevato alla d. nel caso di prima infatti $5^5\equiv20$, ricontrolla gli appunti. Non funziona neanche se consideri, ad esempio, $x^5\equiv0mod3$ la soluzione è chiaramente 0 (ed è unica) mentre facendo $2^d$ indipendentemente da d non ti viene zero, insomma questo 2 che c'è sempre non va secondo me. ciao
"rubik":
se $a\equivbmodn$ allora $a^i\equivb^imodn$ e $a^phi(n)\equiv1modn$
nella prima equazione elevo tutti e due i membri alla 5 (potrei aggiungere qualche soluzione in più in questo modo) ($phi(23)=22$)
$(x^9)^5=x^45=(x^22)^2*x=x$
$5^5=5^2*5^2*5=2*2*5=20$ quindi $x=20$
la seconda ora non ho tempo casomai domani, dovrebbe essere giusto ma dai una ricontrollata
Ineccepibile. L'unica soluzione è infatti
$x-=20 mod 23$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo