Exercițiul 106

E.106. Se consideră numărul S=1+2+22+23+…+2219.S=1+2+2^2+2^3+ \ldots +2^{219}. Cel mai mic număr natural compus, de trei cifre, care este divizor al lui SS este egal cu:

a) 101101

b) 111111

c) 105105

d) 123123

e) 103103

Olimpiadă, etapa județeană, 2021
Răspuns | Soluție

Răspuns: c) 105105

Soluție:

Pentru calculul sumei Sn=1+21+22+…+2nS_n=1+2^1+2^2+ \ldots+2^n putem folosi tehnica "2Sn−Sn2S_n-S_n" sau putem folosi direct următorul rezultat:

Sn=1+21+22+⋯+2n=2n+1−1\hspace*{2em} \boxed{S_n = 1+2^1+2^2+ \dots + 2^n = 2^{n+1}-1}

În cazul nostru, S=2120−1.S=2^{120}-1.

Pentru a determina cel mai mic număr compus, va trebui să găsim cei mai mici divizoiri ai lui SS. Îi vom lua pe rând:

∙S=2120−1=M2−1≠M2\hspace*{2em} \bullet S=2^{120}-1 = M_2 - 1 \not = M_2
⇒S\hspace*{3em} \textcolor{red}{\Rightarrow} S nu are divizori pari.
∙S=(3+1)60−1=(M3+1)−1=M3\hspace*{2em} \bullet S=(3+1)^{60}-1 = (M_3+1) - 1 = M_3
∙S=(5−1)60−1=(M5+1)−1=M5\hspace*{2em} \bullet S=(5-1)^{60}-1 = (M_5+1) - 1 = M_5
∙S=(7+1)40−1=(M7+1)−1=M7\hspace*{2em} \bullet S=(7+1)^{40}-1 = (M_7+1) - 1 = M_7
…\hspace*{2em} \ldots
Deci cei mai mici divizori proprii ai lui SS sunt, în ordine, 33, 55, 77 etc.
Observăm că 3⋅5⋅7=105\boxed{3 \cdot 5 \cdot 7 = 105}. Cum 101101 și 103103 sunt numere prime, putem spune că 105 este cel mai mic număr compus care satisface condiția dată.