Kinesiska restsatsen - varför söker vi inverserna till Mi?

Hej!

På en föreläsning idag (min första kontakt med Kinesiska restsatsen, så jag är minst sagt en nybörjare), så gicks följande exempeluppgift igenom.

Lös ekvationssystemet

$x \equiv 1 \pmod{4}$

$x \equiv 2 \pmod{3}$

$x \equiv 4 \pmod{5}$

Lösningen som presenterades:

Eftersom 4,3,5 relativt prima så kan kinesiska restsatsen användas.

Tag fram $M_{1,2,3}$ enligt definitionen.

$M_{1}= 3 \cdot 5 = 15$ , $M_{2} = 4 \cdot 5 = 20$ , $M_{3} = 4 \cdot 3 = 12$

Nu vill vi lösa

$y_{1}=b_{1}15 \equiv_{4} 1$

$y_{2}=b_{2} 20 \equiv_{3} 1$

$y_{3}=b_{3} 12 \equiv_{5} 1$

Jag förstår här att vi vill hitta inversen till $M_i$ (det är det som det andra ekvationssteget gör).

Men jag förstår inte varför det funkar, eller varför man gör det? Det verkar ju vara en allmän metod att jobba så här med ekvationssystem av kongruenser.

Det kommer från det man säger är lösningen till det generella systemet i restsatsen

$x \equiv a_1 \pmod{m_1}$
$x \equiv a_2 \pmod{m_2}$
$\vdots$
$x \equiv a_k \pmod{m_k}$

Vi undersöker talet

$X = a_1 M_1 y_1 + a_2 M_2 y_2 + \dots a_k M_k y_k$

där $M_i$ är produkten av varje $m_j$ förutom $m_i$ ( $0 \leq i \leq k$ ), alltså
$M_i = m_1 \cdot m_2 \cdots m_{i-1} \cdot m_{i+1} \cdots m_k$

Nu undersöker vi vad som händer om $M_i y_i = 1$ :

När vi undersöker vad $X$ är kongruent med modulo $m_i$ får vi att varje $M_j$ där $j \neq i$ har talet $m_i$ som faktor och därmed är varje term förutom $a_i M_i y_i$ kongruent med $0$ mod $m_i$ . Då har vi att för detta $X$ och varje $i$

$X \equiv a_i M_i y_i \pmod{m_i}$

Sedan om $y_i$ var inversen till $M_i$ skulle vårt $X$ vara kongruent med $a_i$ och därmed lösa det urpsrungliga systemet.

Att komma fram till detta tal som lösning till systemet är en annan fråga, men hänger du med på hur, givet detta lösningsförslag, så är det önskvärt att ha $y_i$ och $M_i$ som inverser?

Ah, jag hänger med nu! Tack så mycket!

Svara