Cercasi esercizi equazioni congruenziali

[smartmouse]

Salve, come da oggetto, cerco esercizi del tipo:

\( \displaystyle {299}{x}\equiv{52}{\left({247}\right)} \)

Grazie

[smartmouse]

Nessuno? Intanto mi dite se almeno li svolgo correttamente? Ecco un esercizio che ho fatto:

\( \displaystyle {12}{x}\equiv{21}{\left({81}\right)} \)

a = 12
b = 21
m = 81

d = MCD(12,81)

81 = 12 * 6 + 9
12 = 9 * 1 + 3
9 = 3 * 3 + 0

MCD(12,81) = 3

d = au + mv

3 = 12 - 9
= 12 - (81 - 12 * 6)
= 12 - 81 + 12 * 6
= 12 * 1 - 81 + 12 * 6
= 12 * 7 + 81 * (-1)

u = 7; v = -1

\( \displaystyle {x}_{{0}}={\frac{{{b}}}{{{d}}}}\cdot{u} \)

\( \displaystyle {x}_{{0}}={\frac{{{21}}}{{{3}}}}\cdot{7}={7}\cdot{7}={49} \)


49 è una delle 3 soluzioni possibili, pertanto si scrive \( \displaystyle {\left[{49}\right]}_{{{81}}}\subseteq{S} \)

Le altre due soluzioni sono date dalla formula

\( \displaystyle {x}_{{k}}={x}_{{0}}+{k}\cdot{\frac{{{m}}}{{{d}}}} \) con \( \displaystyle {0}\le{k}\le{d}-{2} \)

e sono [76] e [103].


Ho fatto bene?

[GundamRX91]

Si, però le soluzioni non dovrebbero essere più di 3?

Guarda io l'esercizio lo risolvo in questo modo, poi dimmi se ti ci ritrovi.

\( \displaystyle {12}{x}\equiv{21}_{{\text{mod}{81}}} \) ha soluzione se e solo se \( \displaystyle {d}={\left({12},{81}\right)}={1} \) cioè sono coprimi.
Dato che \( \displaystyle {d}={\left({12},{81}\right)}={3} \) possiamo dividere ogni termine dell'equazione per \( \displaystyle {3} \), quindi abbiamo \( \displaystyle {4}{x}\equiv{7}_{{\text{mod}{27}}} \)
dove questa volta \( \displaystyle {d}={\left({4},{27}\right)}={1} \).

Di \( \displaystyle {4}{x}\equiv{7}_{{\text{mod}{27}}} \) calcolo l'inverso moltiplicativo al fine di semplificarlo che significa risolvere la seguente
equazione:

\( \displaystyle {4}{x}\equiv{1}_{{\text{mod}{27}}} \) cioè \( \displaystyle {27}{\mid}{4}{x}-{1}\Rightarrow\exists{y}\in\mathbb{Z} \) tale che \( \displaystyle {4}{x}-{1}={27}{y} \) e \( \displaystyle {4}{x}-{27}{y}={1} \) che ha soluzione per \( \displaystyle {x}={7} \) e \( \displaystyle {y}={1} \),
infatti \( \displaystyle {28}-{27}={1} \). Quindi \( \displaystyle {4}{x}\equiv{7}_{{\text{mod}{27}}} \) diventa \( \displaystyle {x}\equiv{49}_{{\text{mod}{27}}}\equiv{22}_{{\text{mod}{27}}} \); questo implica che

\( \displaystyle {27}{\mid}{x}-{22}\Rightarrow\exists{k}\in\mathbb{Z} \) tale che \( \displaystyle {x}-{22}={27}{k} \) e \( \displaystyle {x}={22}+{27}{k} \) che sono le (credo)infinite soluzione all'equazione congruenziale.

Ad esempio per \( \displaystyle {k}={0} \), \( \displaystyle {x}={22} \) e \( \displaystyle \frac{{81}}{{12}}\cdot{22}-{21}={3} \)
Per \( \displaystyle {k}={1} \), \( \displaystyle {x}={49} \) e \( \displaystyle {81}{\mid}{12}\cdot{49}-{21}={7} \)
Per \( \displaystyle {k}={2} \), \( \displaystyle {x}={76} \) e \( \displaystyle {81}{\mid}{12}\cdot{76}-{21}={11} \)

e così via (salvo smentite )

[smartmouse]

Ad esempio per \( \displaystyle {k}={0} \), \( \displaystyle {x}={22} \) e \( \displaystyle \frac{{81}}{{12}}\cdot{22}-{21}={3} \)
Per \( \displaystyle {k}={1} \), \( \displaystyle {x}={49} \) e \( \displaystyle {81}{\mid}{12}\cdot{49}-{21}={7} \)
Per \( \displaystyle {k}={2} \), \( \displaystyle {x}={76} \) e \( \displaystyle {81}{\mid}{12}\cdot{76}-{21}={11} \)

Non ho capito cosa fai nel primo rigo e poi ad esempio come ottieni 76?

[GundamRX91]

Intanto scusami perchè la formula è stata renderizzata male:

\( \displaystyle {k}={0},{x}={22}+{27}\cdot{k}={22}+{0}={22} \), da \( \displaystyle {12}{x}\equiv{21}_{{\text{mod}{81}}} \) hai che \( \displaystyle {12}\cdot{22}\equiv{21}_{{\text{mod}{81}}} \) e sai che \( \displaystyle {81}{\mid}{\left({12}\cdot{22}-{21}\right)} \) cioè \( \displaystyle {264}-{21}={81}{h} \) per \( \displaystyle {h}\in\mathbb{Z} \) da cui \( \displaystyle {243}={81}{h} \) e \( \displaystyle {h}=\frac{{243}}{{81}}={3} \).

E' chiaro ora?

[smartmouse]

Si, ma è completamente distante dalla mia soluzione.
Ad esempio io per trovare quelli che io chiamo u e v devo effettuare delle scomposizioni...
Era proprio a proposito di questo che volevo chiedere delle delucidazioni, in pratica in altre esercizi non riesco ad arrivare a quelle due variabili, sai se c'è un procedimento preciso alla base? Io praticamente l'ho fatto a tentativi fin quando non ottengo la u che serve a me, ma in altri esercizi non ci sono riuscito. Ne sai qualcosa?

[GundamRX91]

Forse il problema è che non ti è chiaro il concetto di relazione di congruenza e dei teoremi per le soluzioni delle equazioni congruenziali, oppure non so...

[smartmouse]

Forse il problema è che non ti è chiaro il concetto di relazione di congruenza e dei teoremi per le soluzioni delle equazioni congruenziali, oppure non so...

Teorema cinese e/o di Bezout?

[GundamRX91]

Anche questi, anche se forse sono sufficienti per risolvere esercizi di questo tipo; il punto è che arrivi alla soluzione non per tentativi ma applicando i vari teoremi/proposizioni e avendo ben chiara la relazione di congruenza.

[smartmouse]

Qui credo di aver risolto. Ho capito come ricavare la u e la v con Bezout (sono andato a rivedermi il teorema). Ora riesco a fare tutti gli esercizi come quello del mio esempio.
Grazie per il tuo aiuto.