Risoluzione equazione congruenziale
Salve a tutti,
sto disperatamente cercando di capire come risolvere questa tipologia d'esercizio, purtroppo non ho trovato nessun libro o riferimento che spiegasse chiaramente il procedimento, quindi spero davvero in un vostro aiuto.
Dunque ho questo tipo d'esercizio dinanzi a me:
Si dica se l'equazione congruenziale $20x -= 4 (mod 34)$ ammette soluzioni. In caso di risposta affermativa, indicare l'insieme di tutte le soluzioni.
Dunque per iniziare trovo il $MCD(20, 34) = 2$, quindi le soluzioni dell'equazione esibita sono le medesime di $10x -= 1 (mod 17)$. A questo punto dovrei determinare gli $h,k in Z$ per i quali $1 = 10h + 17k$ e qui mi blocco perché non so come procedere. Qualcuno potrebbe chiarirmi le idee al riguardo?
Grazie mille per la disponibilità.
sto disperatamente cercando di capire come risolvere questa tipologia d'esercizio, purtroppo non ho trovato nessun libro o riferimento che spiegasse chiaramente il procedimento, quindi spero davvero in un vostro aiuto.
Dunque ho questo tipo d'esercizio dinanzi a me:
Si dica se l'equazione congruenziale $20x -= 4 (mod 34)$ ammette soluzioni. In caso di risposta affermativa, indicare l'insieme di tutte le soluzioni.
Dunque per iniziare trovo il $MCD(20, 34) = 2$, quindi le soluzioni dell'equazione esibita sono le medesime di $10x -= 1 (mod 17)$. A questo punto dovrei determinare gli $h,k in Z$ per i quali $1 = 10h + 17k$ e qui mi blocco perché non so come procedere. Qualcuno potrebbe chiarirmi le idee al riguardo?
Grazie mille per la disponibilità.
Risposte
scusa un attimo ma dato che $MCD(20,34)=2$ e $4/2=2$ perchè hai scritto 1? cioè dovrebbe essere $10x-=2(mod17)$ o sbaglio?? poi comunque ti conviene fare così trovare un inverso moltiplicativo di 10 in$Z17$ che dovrebbe essere 12 poichè $10*12=120$e $120-=1(mod17)$ poichè $17*7=119$.
moltiplichi allora tutto per 12 ed avrai:$x-=24(mod17)$; ora riduciamo 24 modulo 17 ed otterremo:$x-=7(mod17)$; una soluzione di questa è $7$ ma dato che le soluzioni sono infinite va aggiunto il periodo della soluzione cioè $17$ quindi abbiamo che $x=7+17*k$...dovrebbe essere così... mi scuso per eventuali errori
moltiplichi allora tutto per 12 ed avrai:$x-=24(mod17)$; ora riduciamo 24 modulo 17 ed otterremo:$x-=7(mod17)$; una soluzione di questa è $7$ ma dato che le soluzioni sono infinite va aggiunto il periodo della soluzione cioè $17$ quindi abbiamo che $x=7+17*k$...dovrebbe essere così... mi scuso per eventuali errori
Ciao Erdos,
intanto grazie mille per l'aiuto che mi dai. Purtroppo riesco a capire poco del suggerimento, perché non so cosa siano gli inversi moltiplicativi. Per la risoluzione di questo esercizio mi viene presentata la seguente casistica:
caso 1 - l'equazione congruenziale è del tipo $ax -= 1 (mod n)$ con $MCD(a,n) = 1$ e quindi determinare tramite l'algoritmo di Euclide delle divisioni successive gli interi $h$ e $k$ tali che $ah + nk = 1$ e $[a]_n$ è l'insieme di tutte le soluzioni;
caso 2 - l'equazione è del tipo $ax -= b (mod n)$, si verifica che $d = MCD(a,n) $ divida $b$, in tal modo ci si assicura del fatto che l'equazione abbia effettivamente delle soluzioni, se $d | b$ allora si pongono $a_1 = (a/d), b_1 = (b/d), n_1 = (n/d)$, si considera la nuova equazione congruenziale $a_1x -= b_1 (mod n_1)$ ed è tale che $MCD(a_1, n_1) = 1$ infine si determina la soluzione dell'equazione, risolvendo $a_1x -= 1 (mod n_1)$, ricadendo così nel caso precedente.
Ecco la motivazione dei calcoli che a te sembravano strani. Non è che sapresti indirizzarmi utilizzando questo tipo di metodo?
intanto grazie mille per l'aiuto che mi dai. Purtroppo riesco a capire poco del suggerimento, perché non so cosa siano gli inversi moltiplicativi. Per la risoluzione di questo esercizio mi viene presentata la seguente casistica:
caso 1 - l'equazione congruenziale è del tipo $ax -= 1 (mod n)$ con $MCD(a,n) = 1$ e quindi determinare tramite l'algoritmo di Euclide delle divisioni successive gli interi $h$ e $k$ tali che $ah + nk = 1$ e $[a]_n$ è l'insieme di tutte le soluzioni;
caso 2 - l'equazione è del tipo $ax -= b (mod n)$, si verifica che $d = MCD(a,n) $ divida $b$, in tal modo ci si assicura del fatto che l'equazione abbia effettivamente delle soluzioni, se $d | b$ allora si pongono $a_1 = (a/d), b_1 = (b/d), n_1 = (n/d)$, si considera la nuova equazione congruenziale $a_1x -= b_1 (mod n_1)$ ed è tale che $MCD(a_1, n_1) = 1$ infine si determina la soluzione dell'equazione, risolvendo $a_1x -= 1 (mod n_1)$, ricadendo così nel caso precedente.
Ecco la motivazione dei calcoli che a te sembravano strani. Non è che sapresti indirizzarmi utilizzando questo tipo di metodo?
ok allora ripeto tutto tu hai detto nel caso 2 che $b1=b/d$ poichè $d=2$ $b/d=2$;
ora portando il tutto nella forma del caso 2 avremo: $10x-=2(mod 17)$ giusto??
ora procediamo in questo modo...$MCD(10,17)=1$ e ci ritroviamo nel caso 1; a questo punto potremmo calcolare $x$ tramite l'identità di Bezout poichè sappiamo che $17|10x-2$ oppure potremmo ragionare in quest'altro modo (che è più efficace) cioè la consideriamo come un'equazione normale cioè operiamo isolando la x questo implica la moltiplicazione di ambo i membri per un numero che moltiplicato per 10 mi da 1 giusto? questo lo possiamo calcolare poichè 10 e 17 sono coprimi altrimenti 10 non sarebbe invertibile. Ora però noi stiamo lavorando in $Z17$ quindi l'inverso di 10 NON é $1/10$ ma si opera in questo modo: sappiamo che $MCD=1$ quindi utilizzando sempre il lemma di bezout troviamo $s,t $ tali che $10s+17t=1$; questa ha soluzione per $s=12$ e $t=7$ quindi l'inverso di 10 in Z17 è$12$ e moltiplichiamo ambo i membri per 12 e otteniamo:
$x-=24(mod17)$; poichè $24>17$ riduciamo il 24 modulo 17 e quindi $24-=7(mod17)$ quindi la nostra equazioni iniziale sarà equivalente a quella ottenuta che è:$x-=7(mod17)$; ovviamente una soluzione è $7$, ma noi sappiamo che Z17 è periodico quindi dobbiamo trovare tutte le altre soluzioni che in genere sono così definite:sia $x0$ una soluzione particolare e$xk$ la soluzione generale allora:$xk=x0+np$ dove $n$ indica il modulo e $p$ ogni numero appartenente a Z. quindi nel nostro caso avremo che $xk=7+17p$ con $p in Z$ non so se sono stato più chiaro ora
ora portando il tutto nella forma del caso 2 avremo: $10x-=2(mod 17)$ giusto??
ora procediamo in questo modo...$MCD(10,17)=1$ e ci ritroviamo nel caso 1; a questo punto potremmo calcolare $x$ tramite l'identità di Bezout poichè sappiamo che $17|10x-2$ oppure potremmo ragionare in quest'altro modo (che è più efficace) cioè la consideriamo come un'equazione normale cioè operiamo isolando la x questo implica la moltiplicazione di ambo i membri per un numero che moltiplicato per 10 mi da 1 giusto? questo lo possiamo calcolare poichè 10 e 17 sono coprimi altrimenti 10 non sarebbe invertibile. Ora però noi stiamo lavorando in $Z17$ quindi l'inverso di 10 NON é $1/10$ ma si opera in questo modo: sappiamo che $MCD=1$ quindi utilizzando sempre il lemma di bezout troviamo $s,t $ tali che $10s+17t=1$; questa ha soluzione per $s=12$ e $t=7$ quindi l'inverso di 10 in Z17 è$12$ e moltiplichiamo ambo i membri per 12 e otteniamo:
$x-=24(mod17)$; poichè $24>17$ riduciamo il 24 modulo 17 e quindi $24-=7(mod17)$ quindi la nostra equazioni iniziale sarà equivalente a quella ottenuta che è:$x-=7(mod17)$; ovviamente una soluzione è $7$, ma noi sappiamo che Z17 è periodico quindi dobbiamo trovare tutte le altre soluzioni che in genere sono così definite:sia $x0$ una soluzione particolare e$xk$ la soluzione generale allora:$xk=x0+np$ dove $n$ indica il modulo e $p$ ogni numero appartenente a Z. quindi nel nostro caso avremo che $xk=7+17p$ con $p in Z$ non so se sono stato più chiaro ora
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo