Sa se afle numarul N care impartit la 243 da restul 3, impartit la 1246 da restul 6 si impartit la 2432 da restul 12.
Am incercat dar nu-i dau de cap.

Ce resturi se obtin la factorii puteri de numere prime din impartitorii dati?

Incerc sa raspund...

Problema mai simpla este in exemple mai simpla, numai buna de inteles, cam urmatoarea:

Sa zicem ca vrem sa dam de un numar X pentru care:
- restul impartirii lui X la 9 este 7
- restul impartirii lui X la 12 este 5
Ei bine, asa ceva nu se poate, 9 si 12 au divizorul comun 3, iar conditiile de mai sus se bat cap in cap. Prima vrea restul 1 (7=6+1) modulo 3, iar a doua vrea restul 2 (5=3+2) modulo 3. De aceea intrebarea pe care am pus-o mai sus. Revine la verificarea compatibilitatilor.
Sa ajustam:
Sa zicem ca vrem sa dam de un numar X pentru care:
- restul impartirii lui X la 9 este 7
- restul impartirii lui X la 12 este 4
Compatibilitatea e ok.
De obicei se cauta resturi la "bucatile prime". (Teorema factorilor invaranti... se vrea ceva cu scrierea in forma ZZ/9 x ZZ/4 ~ ZZ/36. Ceea ce cautam este partea algoritmica a teoremei chineze a resturilor, insa, in problema data cum a fost data.)
Problema mai simpla revine atunci la:
...vrem sa dam de un numar X pentru care:
- restul impartirii lui X la 9 este 7
- restul impartirii lui X la 4 este 0

Din teorema chineza a resturilor stim ca exact unul din numerele de la 0 pana la 36-1 va fi bun. Aici putem sa le luam pe rand, babeste, de exemplu uitandu-ne in progresia 7, 7+9, 7+18, 7+27 care numar da restul cerut la impartirea cu 4.
Din fericire 4 este 'mic' si ne descurcam cu ochiul liber.
dar sa zicem ca NU avem ochi liber si ca 4 este 'mare'. Atunci am cauta acel n cu proprietatea ca 7+9n este de forma 4k+0. Obtinem o ecuatie diofantiana liniara, 4k-9n = 7.
Aceasta se rezelova alogritmic dupa cum urmeaza.
Se cauta solutia pentru 4k'-9n' = 1.
Se scrie 9/4 ca fractie continua: 9/4 = ( 2+1/4 ) ~ [2,4] se ia redusa penultima, care este [2] si corespunde lui 2 = 2/1. Atunci 2 si 1 sunt (cu semne corespunzatoare) solutia... Intr-adevar, 4.2 - 9.1 = -1, aranjam semne, 4.(-2) - 9.(-1) = 1. Inmultim cu 7, dam de 4.(-7) - 9.(-7) = 7. Pe noi ne interesa doar n-ul, pe acel -7 din 9.(-7) il luam modulo 4 si dam de 1.

Bun.
Pentru problema data, avem:
(20:13) gp > factor(243)
[3 5]

(20:13) gp > factor(1246)
[2 1]
[7 1]
[89 1]

(20:13) gp > factor(2432)
[2 7]
[19 1]

Deci trebuie sa stabilim numai o compatibilitate modulo 2 pentru ultimele conditii. Da, 6 si 12 dau acelasi rest modulo 2.
Problema se reformuleaza:

Sa se gaseasca N cu proprietatile ca:
N modulo 243 este 3,
N modulo (1246/2 =) 623 este 6,
N modulo 2432 este 12.

In orice caz unul si exact unul dintre numerele de la 0 pana la M-1,
M = 243 x 623 x 2432 = cmmmc( 243, 1246, 2432 ),
va fi bun.

Incercam sa gasim un N bun pentru prima si ultima dintre conditii.
(Pana la 243 x 2432.) Numarul cautat este de forma
243 K + 3 si 2432 L + 12 .
Deci incercam sa rezolvam:
243 K + 3 = 2432 L + 12 .
Deci incercam sa rezolvam:
243 K = 2432 L + 9 .
Rezolvam mai intai
243 K' = 2432 L' + 1 (si vom inmulti cu 9 si vom lua numerele mai mici...)
Calculam fractia continua pentru 2432 / 243.
Avem 2432 / 243
= 10 + 2/243
= 10 + 1/( 243 / 2)
= 10 + 1/( 121 + 1/2 )
deci corespunde lui [10,121,2] (scriere formala de fractie continua).
Luam penultima redusa, deci fractia pentru [10,121], deci 10 + 1/121 =1211/121 .
(Redusele aproximeaza din ce in ce mai bine...)

Ei bine, calculam
2432 / 243 - 1211 / 121 = -1/ (produsul numitorilor)
si de aici dam de o solutie (cam) a ecuatiei de mai sus,
2432 . 121 - 1211 . 243 = -1 .

Inmultim cu 9 pentru a da de:
2432 . 1089 - 10899. 243 = -9 .
Putem sa ne aranjam mai bine cu numere mai mici,
2432 . (-4*243+1089) - (-4*2432+10899). 243 = -9 .
Deci
2432 . 117 - 1171 . 243 = -9 .

Deci
2432 . 117 + 9 = 1171 . 243 .
Deci
2432 . 117 + 12 = 1171 . 243 + 3 .

Acest numar, 284556, este bun pentru doua conditii, el se afla intre 0 si 2432 x 243 -1 .

Am redus astfel problema data la:

Sa se gaseasca N cu proprietatile ca:
N modulo 243 * 2432 = 590976 este 284556,
N modulo (1246/2 =) 623 este 6,

Nu mai insist, dar primul pas 'uman' ar fi sa calculam fractia continua pentru 590976 / 623 ...

Numarul de operatii facute este mic, dar complexitatea lor mare.
In astfel de cazuri, RAM-ul fiind intre timp ieftin si oamenii stresssati, se poate tipari si un program rapid... Eu sunt la lucru si am aici doar python.

Masina de lucru imi da raspunsul
29242380 .
(In python conteaza acele tabulatoare de spatiere, de aceea am dat drumul la latex si am facut o poza din cod... In schimb, numarul parantezelor este redus...) Cateva verificari:

(20:41) gp > 29242380 % 243
3

(20:48) gp > 29242380 % 1246
6

(20:48) gp > 29242380 % 2432
12

(20:48) gp > 29242380 % ( 243 * 2432 )
284556

N.B. Probabil ca am copiat numerele gresit... sau poate ca trebuia sa dau de un numar de telefon... In orice caz, sper ca lucrurile sunt mai clare acum.