Exercițiul 226

$$\begin{cases} n = 8 \cdot c_1 + 5 \quad | \cdot 5\\ n = 5 \cdot c_2 + 3 \quad |\cdot 8 \end{cases}$$

Pas 1: Înmulțim cu $5$, respectiv $8$, pentru a ajunge la împărțitorul cerut (acel $40$):

$$\begin{cases} 5n = 40 \cdot c_1 + 25\\ 8n = 40 \cdot c_2 + 24 \end{cases}$$

Dacă în urma diferenței am fi obținut doar $n$ (în loc de $3n$), problema ar fi fost ca și terminată. Așadar, în pașii următori vom încerca să ajungem la $n$.

Pas 2: (opțional): Cum $5n<8n$, schimbăm ordinea celor două relații:
(Conform lemei, e de preferat ca $B$ să fie mai mic decât $A$)

$$\begin{cases} 8n = 40 \cdot c_2 + 24 \quad |\cdot x\\ 5n = 40 \cdot c_1 + 25 \quad | \cdot y \end{cases}$$

Pas 3: Căutăm două numere $x$ și $y$ astfel încât $8n \cdot x - 5n \cdot y = n,$ adică rezolvăm ecuația diofantică $\boxed{8x-5y=1}.$

Conform unei leme pe care o vom demonstra ulterior, o ecuație în $\N \times \N$ de forma $Ax-By=1,$ cu $(A,B)=1$ are întotdeauna soluție, cu valoarea minimă a lui $x$ în interiorul mulțimii $\{1, 2, \ldots ,B-1\}.$ Deci, în cazul nostru, valoarea lui $x$ se află sigur în mulțimea $\{1, 2, 3, 4\}.$

• $x=1$, nu convine;
• $\boxed{x=2}$ convine, rezultă $\boxed{y=3}.$

Pas 4: Înmulțim cu $2$, respectiv $3$ și facem scăderea:

$$\begin{cases} 16n = 40 \cdot c_2 \cdot 2 + 48\\ 15n = 40 \cdot c_1 \cdot 3 + 75 \end{cases}$$

După scădere:
$n = 40(2c_2-3c_1) - 27 = 40(2c_2-3c_1-40) + 13,$ deci $\boxed{r=13}.$