Teorema Cinese Del Resto Generalizzato (no anelli)

[mind]

Salve, mi chiedevo quando un sistema di congruenze del tipo

a_1*x = b_1 mod m_1
...
a_n*x = b_n mod m_n

con m_i coprimi a due a due abbia soluzioni.

In pratica ho provato a imporre il sistema omogeneo

x_k = 1 mod m_k
x_k = 0 mod m_i, per ogni i diverso da k

poi moltiplico per b_k e ottengo b_k*x_k = b_k mod_k e resto tutto a
zero.
(poi andando avanti nel teorema cinese sommerei i vari x_k che trovo
per avere la soluzione finale ecc)
Fin qui niente di nuovo ma come faccio se ho un fattore a_k davanti a
x_k?
Per a_k | b_k trovo facilmente una soluzione ma non riesco a capire il
caso generale (che deve esserci comunque poiché ho fatto un esercizio
in cui a_k non divideva b_k ma aveva solo un fattore in comune). Può
essere che debba valere a_k | b_k*x_k ? (intendo un se e solo se)

Saluti, Gil

[Enrico Gregorio]

Post by mind
Salve, mi chiedevo quando un sistema di congruenze del tipo
a_1*x = b_1 mod m_1
...
a_n*x = b_n mod m_n
con m_i coprimi a due a due abbia soluzioni.
In pratica ho provato a imporre il sistema omogeneo
x_k = 1 mod m_k
x_k = 0 mod m_i, per ogni i diverso da k
poi moltiplico per b_k e ottengo b_k*x_k = b_k mod_k e resto tutto a
zero.
(poi andando avanti nel teorema cinese sommerei i vari x_k che trovo
per avere la soluzione finale ecc)
Fin qui niente di nuovo ma come faccio se ho un fattore a_k davanti a
x_k?
Per a_k | b_k trovo facilmente una soluzione ma non riesco a capire il
caso generale (che deve esserci comunque poiché ho fatto un esercizio
in cui a_k non divideva b_k ma aveva solo un fattore in comune). Può
essere che debba valere a_k | b_k*x_k ? (intendo un se e solo se)

Se a_i è coprimo con m_i, hai la situazione come nel teorema cinese,
perché puoi moltiplicare per l'inverso di a_i (modulo m_i).

In generale, sia d_i = mcd(a_i,m_i). Se x è una soluzione, hai

a_i x = b_i + r m_i

e quindi è necessario che d_i divida b_i. Dividendo per d_i i tre
numeri, ti sei ridotto al caso in cui a_i è coprimo con m_i. Ovviamente
con questa trasformazione i moduli rimangono a due a due coprimi e
quindi il sistema modificato ha sicuramente una soluzione.

Perciò la condizione è che mcd(a_i,m_i) divida b_i.

Ciao
Enrico

[mind]

Post by Enrico Gregorio

Post by mind
Salve, mi chiedevo quando un sistema di congruenze del tipo
a_1*x = b_1 mod m_1
...
a_n*x = b_n mod m_n
con m_i coprimi a due a due abbia soluzioni.
In pratica ho provato a imporre il sistema omogeneo
x_k = 1 mod m_k
x_k = 0 mod m_i, per ogni i diverso da k
poi moltiplico per b_k e ottengo b_k*x_k = b_k mod_k e resto tutto a
zero.
(poi andando avanti nel teorema cinese sommerei i vari x_k che trovo
per avere la soluzione finale ecc)
Fin qui niente di nuovo ma come faccio se ho un fattore a_k davanti a
x_k?
Per a_k | b_k trovo facilmente una soluzione ma non riesco a capire il
caso generale (che deve esserci comunque poiché ho fatto un esercizio
in cui a_k non divideva b_k ma aveva solo un fattore in comune). Può
essere che debba valere a_k | b_k*x_k ? (intendo un se e solo se)

Se a_i è coprimo con m_i, hai la situazione come nel teorema cinese,
perché puoi moltiplicare per l'inverso di a_i (modulo m_i).
In generale, sia d_i = mcd(a_i,m_i). Se x è una soluzione, hai
a_i x = b_i + r m_i
e quindi è necessario che d_i divida b_i. Dividendo per d_i i tre
numeri, ti sei ridotto al caso in cui a_i è coprimo con m_i. Ovviamente
con questa trasformazione i moduli rimangono a due a due coprimi e
quindi il sistema modificato ha sicuramente una soluzione.
Perciò la condizione è che mcd(a_i,m_i) divida b_i.
Ciao
Enrico

Grazie. Gil