[Foglio 4] Esercizio 5 about algebra2324 HOT 2 CLOSED

(Nota: ho usato la notazione $\equiv _n$ per indicare la congruenza modulo $n$ e la notazione $(a, b)$ per indicare $MCD(a, b)$ ).

Prima di tutto, bisogna determinare se il sistema è risolvibile, quindi determinare se, per ogni congruenza nella forma $ax \equiv _n b$, $(a, n)$ divide $b$

$$(18, 30) = 6 \mid 12$$

$$(7, 9) = 1 \mid 4$$

$$(28, 98) = 14 \mid 14$$

È possibile ridurre le equazioni congruenziali

$$ \begin{cases} \frac{18}{6} x \equiv _{\frac{30}{6}} \frac{12}{6}\\ \frac{7}{1} x \equiv _{\frac{9}{1}} \frac{4}{1}\\ \frac{28}{14} x \equiv _{\frac{98}{14}} \frac{14}{14}\\ \end{cases} \implies \begin{cases} 3x \equiv _5 2\\ 7x \equiv _9 4\\ 2x \equiv _7 1\\ \end{cases} $$

Il sistema è risolvibile, e si può ridurre a un sistema cinese dato che $5$, $9$ e $7$ sono coprimi. È necessario trovare l'inverso di $3 \ mod \ 5$, l'inverso di $7 \ mod \ 9$ e l'inverso di $2 \ mod \ 7$

$$3 \bar{x} \equiv _5 1 \implies \bar{x} \equiv _5 2$$

$$7 \bar{x} \equiv _9 1 \implies \bar{x} \equiv _9 4$$

$$2 \bar{x} \equiv _7 1 \implies \bar{x} \equiv _7 4$$

Moltiplicando ambo i membri di ciascuna equazione per il rispettivo inverso, si ottiene un sistema cinese

$$ \begin{cases} 3 \cdot 2 x \equiv _5 2 \cdot 2\\ 7 \cdot 4 x \equiv _9 4 \cdot 4\\ 2 \cdot 4 x \equiv _7 1 \cdot 4\\ \end{cases} \implies \begin{cases} x \equiv _5 4\\ x \equiv _9 16\\ x \equiv _7 4\\ \end{cases} \implies \begin{cases} x \equiv _5 4\\ x \equiv _9 7\\ x \equiv _7 4\\ \end{cases} $$

È noto che la soluzione del sistema esiste, è unica ed è nella forma

$$ \tilde{x} = R_1\tilde{x}_1 + R_2\tilde{x}_2 + R_3\tilde{x}_3 $$

Dove, dato $R = 5 \cdot 9 \cdot 7 = 315$, si calcolano

$$R_1 = \frac{R}{5} = 9 \cdot 7 = 63$$

$$R_2 = \frac{R}{9} = 5 \cdot 7 = 35$$

$$R_3 = \frac{R}{7} = 5 \cdot 9 = 45$$

Ora si possono trovare $\tilde{x} _1, \tilde{x} _2, \tilde{x} _3$

$$R_1 \tilde{x}_1 \equiv _5 4 \implies 63 \tilde{x}_1 \equiv _5 4 \implies 3 \tilde{x}_1 \equiv _5 4 \implies \tilde{x}_1 \equiv _5 3$$

$$R_2 \tilde{x}_2 \equiv _9 7 \implies 35 \tilde{x}_2 \equiv _9 7 \implies 8 \tilde{x}_2 \equiv _9 7 \implies \tilde{x}_2 \equiv _9 2$$

$$R_3 \tilde{x}_3 \equiv _7 4 \implies 45 \tilde{x}_3 \equiv _7 4 \implies 3 \tilde{x}_3 \equiv _7 4 \implies \tilde{x}_2 \equiv _7 6$$

Quindi $\tilde{x} = 63 \cdot 3 + 35 \cdot 2 + 45 \cdot 6 \equiv _{315} 529 \equiv _{315} 214 $.

from algebra2324.

Analogo @CuriousCI

from algebra2324.