Risoluzione congruenza lineare.

[haru1]

Salve a tutti,

cortesemente sapreste spiegarmi in che modo risolvere la seguente congruenza lineare?
[tex]315x \equiv 18 (mod 153)[/tex]
inoltre determinare una soluzione [tex]x_{0}[/tex] tale che [tex]20 < x_{0} < 60[/tex].

quale strada bisognerebbe intraprendere per una corretta risoluzione di conguenze del genere?

se non sbaglio dovrei prima verificare se il MCD(315,153) divide 18, è così?
in questo caso si ha [tex]MCD(315,153) = 9 | 18[/tex] pertanto la congruenza ha soluzioni e ne ha 9 non conguenti modulo 153.

ma ora come cortesemente come si dovrebbe procedere?

mille grazie davvero.

[Alecc90]

Vedi la congruenza come l'equazione:

$ 315x +153y = 18 $

Allora devi calcolarti l'$MCD$ con l'algoritmo euclideo delle divisioni successive, quindi avrai:

$ 315 = 153*2 + 9 $
$ 153 = 9*17 + 0 $

(MCD = 9, che corrisponde al numero dopo l'uguale nella riga con resto = 0)

Quindi ora isoli i resti (escludendo la riga con resto = 0):

$ 9 = 315*1 - (153*2) $

Ma a noi serve che tutto quello sia uguale a $18$, quindi moltiplichiamo tutto per $2$

$ => 18 = 315*2 + 153*(-4) $

$=> x=2, y=-4 $

[Verifichiamo sostituendo: $ 630 - 612 = 18$ ? Sì!]

Ok, ora la formula generale per le $xn$ soluzioni (che in questo caso sono 9):

$ xn = x0 + (n/d)*k $
dove
$x0=2$ (prima soluzione $x$ trovata)
$n=153$ (numero del $mod$)
$d=9 ($MCD$)
$0<=k
poi trovi quindi le 9 soluzioni sostituendo e se:

- $xn >= n $ continui a sottrargli 153 (che è n), finché non rientri nel $mod153$ (range che va da 0 a 152)
- $xn < 0 $ continui ad aggiungergli 153 (che è n), finché non rientri nel $mod153$ (range che va da 0 a 152)

Ciao!

[blackbishop13]

puoi fare tutti quei conti oppure essere un pochino più scaltro e osservare che [tex]315 \equiv 9 \bmod{153}[/tex]
e quindi la tua congruenza diventa [tex]9x \equiv 18 \bmod{153}[/tex]

che per il teorema cinese del resto diventa [tex]x \equiv 2 \bmod{17}[/tex]

fine.

[haru1]

blackbishop13 intendi che la congruenza di partenza [tex]315x \equiv 18 (mod 153)[/tex] diventa [tex]9x \equiv 18 mod 153[/tex]?
ed inoltre in che modo ottieni tale risultato dal teorema cinese del resto?

[blackbishop13]

beh che [tex]315 \equiv 9 \bmod{153}[/tex] dovrebbe essere molto evidente, è la prima cosa a cui uno pensa vedendo questo esercizio.

poi se sai il teorema cinese allora ti basta osservare che [tex]153=9*17[/tex] e poi applicare il teorema.

[haru1]

è evidente che non è evidente per me ecco perchè l'ho chiesto...
anche perchè la prima cosa che penso quando guardo l'esercizio è come si fa?
cosa ti porta a ottenere la congruenza che hai scritto nell'ultimo post?
non voglio lo svolgimento completo dell'esercizio ma almeno dirmi per favore in che modo viene ottenuto il passaggio...
è talmente banale da non meritare risposta?

[blackbishop13]

[tex]a \equiv b \bmod{n}[/tex] cosa vuol dire?
ci sono non poche definizioni, vedi tu quale ti aggrada dal tuo libro.
un modo semplice è dire che [tex]a-b=kn[/tex] per un certo [tex]k[/tex], ovvero che [tex]a-b[/tex] è un multiplo di [tex]n[/tex].

perciò come faremo ad ottenere che [tex]315 \equiv 9 \bmod{153}[/tex] ?

P.S. io dò per scontato che tu sia uno studente universitario che sta seguendo un corso su questa roba, e che quindi tu abbia un libro e degli appunti dove studiare. o che perlomeno tu abbia studiato un po' di cose su internet o altrove a adesso ti metti a fare esercizi.
se così non è dillo!

[haru1]

perdonami blackbishop13 hai perfettamente ragione.
In realta la teoria l'ho consultata ma molte cose mi sono ancora poco chiare
e non riesco a fare bene gli esercizi come hai potuto purtroppo vedere.

Quindi finora dovrebbe essere che da [tex]315 \equiv 18 (mod 153) \Rightarrow 315 \equiv 9 (mod 153)[/tex] poichè il resto della divisione 315/153 è 9 e non 18?

e come ottieni [tex]9x \equiv 18 (mod 153)[/tex]?

[blackbishop13]

stai facendo una grandissima confusione.
tu hai l'equazione [tex]315x=18 \bmod{153}[/tex]

siccome il 315 al primo membro è scomodo, lo sostituisci con 9, visto che sono uguali, siccome lavoriamo modulo 153.
tutto qui.

[haru1]

ora mi è chiaro. 315 = 9 se si lavora modulo 153.
poi perchè fai riferimento al teorema cinese del resto?
Non si dovrebbero almeno avere due congruenze con i moduli a due a due coprimi e coefficiente della x = 1 e il tutto a sistema?
[tex]x \equiv 2 (mod 17)[/tex] non è il risultato della divisione per 9?

[blackbishop13]

"divisione per nove" è un concetto che non esiste dove stiamo lavorando.
però puoi anche metterla così. il punto è che devi sapere bene perché puoi farlo.

il teorema cinese del resto dice molte cose, basta saper leggere a fondo.

[haru1]

dalla congruenza [tex]9x \equiv 18 (mod 153)[/tex] se si considera [tex]153 = 9 \cdot 17[/tex]
la si spezza in due congruenze così da ottenere la seguente?

[tex]\begin{cases} 9x \equiv 18 (mod 9) \\ 9x \equiv 18 (mod 17) \end{cases}[/tex]

condizioni valide:
per la 1^ conguenza MCD (9,9) = 9 | 18
per la 2^ congruenza MCD (9,17) = 1 | 18
per i due moduli MCD (9,17) = 1

quindi divido ogni congruenza per i rispettivi MCD

[tex]\begin{cases} x \equiv 2 (mod 1) \\ 9x \equiv 18 (mod 17) \end{cases}[/tex]

nella seconda moltiplico per 1/9 a entrambi i membri
o presumo in modo più corretto:
dal momento che MCD(9,17)=1 allora 9 è invertibile in [tex]\mathbb{Z}_{17}[/tex]
quindi in [tex]9x \equiv 18 (mod 17)[/tex]
considero il 18 in mod 17 e ottengo [tex]9x \equiv 1 (mod 17)[/tex]
devo trovare un numero che moltiplicato per 9 faccia 1:
[tex]9 \cdot 2 = 18 \equiv 1 (mod 17)[/tex]
quindi l'inverso di 9 è il numero 2.

[tex]\begin{cases} x \equiv 2 (mod 1) \\ x \equiv 2 (mod 17) \end{cases}[/tex]

e dovrei ottenere il sistema da sottoporre al teorema cinese del resto?
ma la prima è implicata nella seconda quindi ottengo solamente [tex]x \equiv 2 (mod 17)[/tex]

è giusto o sto sbagliando ancora?

[blackbishop13]

molto bene.
solo che hai un approccio ancora troppo algoritmico e poco ragionato.
ad esempio la congruenza [tex]9x\equiv 18 \bmod{18}[/tex] è semplicemente verificata per ogni x, visto che [tex]9\equiv 18\equiv 0 \bmod{9}[/tex]
e quindi non c'è bisogno dello studio che hai fatto tu.
e anche quando dici "dividere per l' mcd" in realtà vuol dire rifare questo procedimento, ed è ovvio che nel secondo caso ti venga 1 questo mcd, perché era proprio quello l'obiettivo.
però va bene davvero, mi pare che hai capito tutto, bravo.

[haru1]

un'altra domanda banale.
[tex]153 = 9 \cdot 17[/tex] l'hai ottenuto calcolando l'MCD con l'algoritmo euclideo delle divisioni successive come ha fatto Alecc90?

ed inoltre effettivamente il teorema cinese del resto non abbiamo avuto bisogno di applicarlo no? ci siamo fermati prima, nella sua premessa.

[blackbishop13]

visto che 1+5+3=9, sai che 153 è divisibile per 9.
comunque non è che sia una grande conquista per l'umanità è una divisione e basta..

[haru1]

l'esercizio sarebbe stato completato correttamente se fosse fatta invece la divisione per 3 e ottenendo 153 = 51 * 3?

ed inoltre riguardo il secondo punto dell'esercizio:
determinare una soluzione [tex]x_{0}[/tex] tale che [tex]20 < x_{0} < 60[/tex].
Come bisognerebbe procedere?

cioè se considero ciò che ha scritto Alecc90 :

Ok, ora la formula generale per le $xn$ soluzioni (che in questo caso sono 9):

$ xn = x0 + (n/d)*k $
dove
$x0=2$ (prima soluzione $x$ trovata)
$n=153$ (numero del $mod$)
$d=9 ($MCD$)
$0<=k

dovrei ottenere le seguenti:

[tex]x_{0} = 2 + \frac{153}{9} \cdot 0 = 2[/tex]
[tex]x_{1} = 2 + \frac{153}{9} \cdot 1 = 19[/tex]
[tex]x_{2} = 2 + \frac{153}{9} \cdot 2 = 36[/tex]
[tex]x_{3} = 2 + \frac{153}{9} \cdot 3 = 53[/tex]
[tex]x_{4} = 2 + \frac{153}{9} \cdot 4 = 70[/tex]

36 e 53 sono quelle che soddisfano il quesito. o sbaglio?

ma se considero la congruenza che abbiamo ottenuto:
[tex]x \equiv 2 (mod 17)[/tex]
come si procede?

[haru1]

mi sa che è una domanda scontata.
il MCD lo vedo dalla congruenza [tex]9x \equiv 18 (mod 153)[/tex] ed esso è 9.
erroneamente cercavo di ricavare il MCD dalla congruenza finale [tex]x \equiv 2 (mod 17)[/tex].

mentre dalla congruenza finale [tex]x \equiv 2 (mod 17)[/tex] mi ricavo le soluzioni così come nel post precedente
e considero con n il modulo iniziale 153 e non il modulo 17 ottenuto alla fine:
[tex]x = x_{0} + \frac{n}{d} \cdot k[/tex] con [tex]0 \le k < 9[/tex]
[tex]x_{1} = 2 + \frac{153}{9} \cdot 1[/tex]
ecc...
.

[Talpone1]

COme si dovrebbe fare questa dimostrazione?

Sia G un gruppo ciclico con |G|=n.
Sia r>1 con r|n. Dimostrare che esiste una H < uguale G tale che |H|=r