[A-L] (2023/24) Foglio 4 - Esercizio 3

[Elia-Belli]

[CuriousCI]

(Nota: ho usato la notazione $\equiv _n$ per indicare la congruenza modulo $n$ ).
Il problema si può rappresentare con un sistema di congruenze di tipo cinese

$$ \begin{cases} x \equiv _{13} 11\\ x \equiv _{11} 7\\ x \equiv _7 6 \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 = 13 \cdot 11 \cdot 7 = 1001$, si calcolano

$$R_1 = \frac{R}{13} = 11 \cdot 7 = 77$$

$$R_2 = \frac{R}{11} = 13 \cdot 7 = 91$$

$$R_3 = \frac{R}{7} = 13 \cdot 11 = 143$$

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

$$R_1 \tilde{x}_1 \equiv _{13} 11 \implies 77 \tilde{x}_1 \equiv _{13} 11 \implies 12 \tilde{x}_1 \equiv _{13} 11 \implies \tilde{x}_1 \equiv _{13} 2 $$

$$R_2 \tilde{x}_2 \equiv _{11} 7 \implies 91 \tilde{x}_2 \equiv _{11} 7 \implies 3 \tilde{x}_2 \equiv _{11} 7 \implies \tilde{x}_2 \equiv _{11} 6$$

$$R_3 \tilde{x}_3 \equiv _7 6 \implies 143\tilde{x}_3 \equiv _7 6 \implies 3 \tilde{x}_3 \equiv _7 6 \implies \tilde{x}_3 \equiv _7 2 $$

Quindi $\tilde{x} = 77 \cdot 2 + 91 \cdot 6 + 143 \cdot 2 \equiv _{1001} 986$.

La risposta è $986$ caramelle. Infatti, $986 \equiv_{13} 11$, $986 \equiv_{11} 7$ e $986 \equiv_7 6$

[dahKidou]

(Nota: ho usato la notazione ≡n per indicare la congruenza modulo n ). Il problema si può rappresentare con un sistema di congruenze di tipo cinese

{x≡1311x≡117x≡76

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

x~=R1x1+R2x2+R3x~3

Dove, dato R=13⋅11⋅7=1001, si calcolano

R1=R13=11⋅7=77

R2=R11=13⋅7=91

R3=R7=13⋅11=143

Ora si possono trovare x1,x2,x~3

R1x1≡1311⟹77x1≡1311⟹12x1≡1311⟹x1≡132

R2x2≡117⟹91x2≡117⟹2x2≡117⟹x2≡119

R3x3≡76⟹143x3≡76⟹3x3≡76⟹x3≡72

Quindi x~=77⋅2+91⋅9+143⋅2≡10011259≡1001258.

La risposta è 1259 caramelle.

credo che R2x2 sia sbagliato, in quanto 91 in modulo 11 è 11 * 8 + 3

[CuriousCI]

credo che R2x2 sia sbagliato, in quanto 91 in modulo 11 è 11 * 8 + 3

Hai ragione, errore mio. Ero sicuro di aver controllato che il sistema torni, ma in realtà 258 % 11 fa 5, non 7, correggo subito.

[CiottoloMaggico]

Utilizzando sostituzione

Utilizzando dimostrazione metodo cinese