[Esame di prova 30 dicembre 2023] Esercizio 2

[Elia-Belli]

[CuriousCI]

Per poterci ridurre a un sistema cinese bisogna innanzitutto calcolare $12387^{8525} \mod 10$ usando il teorema di Eulero #382

1. $\phi(10) = \phi(5 * 2) = (5^1 - 5^0)(2^1 - 2^0) = (5 - 1)(2 - 1) = 4$
2. $8525 = 4 \cdot 2131 + 1$
3. $12387^{8525} = 12387^{4 \cdot 2131 + 1} = 12387^{4 \cdot 2131} \cdot 12387^1$
4. $12387^{4 \cdot 2131} \cdot 12387^1 \equiv_{10} 1 \cdot 12387^1$
5. $12387 = 1238 \cdot 10 + 7 \implies 12387 \equiv_{10} 7$

Quindi

$$ \begin{cases} 12387^{8525} x \equiv_{10} 1 \\ 13x + 7 \equiv_{12} 0 \end{cases} \implies \begin{cases} 7 x \equiv_{10} 1 \\ x \equiv_{12} 5 \end{cases} \implies \begin{cases} x \equiv_{10} 3 \\ x \equiv_{12} 5 \end{cases} $$

A questo punto si ha $(10, 12) = 2 \neq 1$ ma dato che $5 - 3 = 2$ e $(10, 12) \mid 2$ la soluzione è unica ed è modulo $\text{mcm}(10, 12) = 60$ ¹

Si può procedere per sostituzione: $x = 10 k + 3 \implies 10k + 3 \equiv_{12} 5 \implies 10k \equiv_{12} 2$, abbiamo che $(10, 12) = 2$, quindi possiamo scrivere $5k \equiv_6 1 \implies k \equiv_6 5$ quindi si ha che $x = 10 (6 + 5) + 3 = 60 + 53 \equiv_{60} 53$

Footnotes

1. Proposizione 4 di questo pdf, ringrazio @Elia-Belli per essersi posto il problema e aver trovato questa proposizione
   ↩

[interestingmaneuver]

Si può anche notare che, dato

$$ \begin{cases} x \equiv 3 \mod 10\\ x \equiv 5 \mod 12 \end{cases} $$

Siccome $10 = 2 \cdot 5$, $x \equiv 3 \mod 10$ è la soluzione unica del sistema

$$ \begin{cases} x \equiv 3 \equiv 1 \mod 2\\ x \equiv 3 \mod 5\\ \end{cases} $$

E siccome $12 = 3 \cdot 2^2$, $x \equiv 5 \mod 12$ è la soluzione unica del sistema

$$ \begin{cases} x \equiv 5 \equiv 2 \mod 3\\ x \equiv 5 \equiv 1 \mod 4\\ \end{cases} $$

Racchiudendo tutto in un unico sistema, si ha:

$$ \begin{cases} x \equiv 1 \mod 2\\ x \equiv 3 \mod 5\\ x \equiv 2 \mod 3\\ x \equiv 1 \mod 4\\ \end{cases} $$

Però $x \equiv 1 \mod 4 \implies x \equiv 1 \mod 2$, quindi il sistema si riduce a

$$ \begin{cases} x \equiv 3 \mod 5\\ x \equiv 2 \mod 3\\ x \equiv 1 \mod 4\\ \end{cases} $$

che ha moduli coprimi ed è equivalente al sistema di partenza.

[CiottoloMaggico]

[Elia-Belli]

Soluzione Ufficiale