Gasiti cel mai mic numar natural care se scrie numai cu cifra 8 si care este multiplu de 41 si 73.

Cod pari/gp mai intai...

(18:18) gp > 10^40 % 41
%32 = 1
(18:19) gp > 10^20 % 41
%33 = 1
(18:19) gp > 10^10 % 41
%34 = 1
(18:19) gp > 10^5 % 41
%35 = 1
(18:19) gp > 99999 / 41
%36 = 2439
(18:19) gp > 10^72 % 73
%37 = 1
(18:19) gp > 10^36 % 73
%38 = 72
(18:19) gp > 10^24 % 73
%39 = 1
(18:19) gp > 10^8 % 73
%40 = 1
(18:19) gp > 10^4 % 73
%41 = 72
(18:20) gp > 99999999 / 73
%42 = 1369863
(18:20) gp > N = 8 * ( 10^(5*8) -1 ) / 9
%43 = 8888888888888888888888888888888888888888
(18:20) gp > N / 41 / 73
%44 = 2969892712625756394550246872331737016
(18:21) gp > 8./ 9 / 41 / 73
%45 = 0.0002969892712625756394550246872
(18:22) gp > \p 100
realprecision = 105 significant digits (100 digits displayed)
(18:22) gp > 8./ 9 / 41 / 73
%46 = 0.0002969892712625756394550246872331737016
0002969892712625756394550246872331737016
00029698927126257563946

(ultima linie a fost rupta manual...)

Comentarii:
In conformitate cu mica teorema a lui Fermat, numarul
10 ^ (41-1) da restul 1 la impartirea cu numarul prim 41 .
Pentru a gasi cea mai mica putere a lui 10 cu proprietatea ca da restul 1 modulo 41, ne uitam la divizorii lui 40 . (Practic calculam ordinul clasei lui 10 in grupul multiplicativ al elementelor nenule = inversabile din corpul ZZ / 41 cu 41 de elemente. Ordinul lui 10 divide ordinul grupului, care este 40. Ramane sa chiar il calculam explicit.)

Mai sus am luat cu codul puterile de la 40 in jos, deci pe rand
40, 20, 10, 5 si m-am oprit aici, puterea intai sigur nu e buna...

Deoarece numerele 8 si 9 sunt relativ prime cu 41 (si 73) putem imparti cu 9 si inmulti cu 8... numerele 99999, 11111, 88888 se divid in acelasi timp cu 41, ajunge sa stim de unul din ele, intre timp stim de 99999 .

La fel procedam si cu 73.
Vedem ca 10 ^ 8 este cea mai mica putere a lui 10 care da restul 1 la impartirea cu 73.

De aici rezulta printr-un fel de algoritm al lui Euclid ca cea mai mica putere a lui 10 care da restul 1 la impartirea cu 41 * 73 este puterea de ordin 5 * 8 = 40 .

Alternativ puteam sa ne legam de scrierea zecimala a lui 1 / (41 * 73 ) si sa vedem cat de mare este perioada...

Se poate si "brutal", fara structura:

(18:36) gp > for( k=1, 40, N = 8/9 * (10^k-1); print( N, " mod 41*73 este ", N % (41*73) ) )
8 mod 41*73 este 8
88 mod 41*73 este 88
888 mod 41*73 este 888
8888 mod 41*73 este 2902
88888 mod 41*73 este 2091
888888 mod 41*73 este 2960
8888888 mod 41*73 este 2671
88888888 mod 41*73 este 2774
888888888 mod 41*73 este 811
8888888888 mod 41*73 este 2132
88888888888 mod 41*73 este 377
888888888888 mod 41*73 este 785
8888888888888 mod 41*73 este 1872
88888888888888 mod 41*73 este 770
888888888888888 mod 41*73 este 1722
8888888888888888 mod 41*73 este 2263
88888888888888888 mod 41*73 este 1687
888888888888888888 mod 41*73 este 1913
8888888888888888888 mod 41*73 este 1180
88888888888888888888 mod 41*73 este 2829
888888888888888888888 mod 41*73 este 1361
8888888888888888888888 mod 41*73 este 1646
88888888888888888888888 mod 41*73 este 1503
888888888888888888888888 mod 41*73 este 73
8888888888888888888888888 mod 41*73 este 738
88888888888888888888888888 mod 41*73 este 1402
888888888888888888888888888 mod 41*73 este 2056
8888888888888888888888888888 mod 41*73 este 2610
88888888888888888888888888888 mod 41*73 este 2164
888888888888888888888888888888 mod 41*73 este 697
8888888888888888888888888888888 mod 41*73 este 992
88888888888888888888888888888888 mod 41*73 este 949
888888888888888888888888888888888 mod 41*73 este 519
8888888888888888888888888888888888 mod 41*73 este 2205
88888888888888888888888888888888888 mod 41*73 este 1107
888888888888888888888888888888888888 mod 41*73 este 2099
8888888888888888888888888888888888888 mod 41*73 este 47
88888888888888888888888888888888888888 mod 41*73 este 478
888888888888888888888888888888888888888 mod 41*73 este 1795
8888888888888888888888888888888888888888 mod 41*73 este 0

Eu am gandit asa:

, adica

. Asta inseamna ca orice numar care are 5k cifre identice se divide cu 41.
Apoi

, adica

. Prin urmare orice numar care are 8m cifre identice se divide cu 73.Pentru ca numarul sa fie divizibil si cu 41 si cu 73 (si sa fie si cel mai mic!) trebuie sa aiba un numar de cifre identice egal cu [5,8]=40.