Romanian TST I 2008, Problema 5

[Laurian Filip]

Determinati cel mai mare divizor comun al numerelor
\( 2^{561}-2,3^{561}-3,...,561^{561}-561. \)

Dorin Andrica, Mihai Piticari

[Beniamin Bogosel]

E interesant, ca 561 este cel mai mic numar Carmichael, adica cel mai mic numar natural \( n \), neprim pentru care \( n|a^n-a \) pentru orice \( a \)....

[mihai++]

Din cate stiu eu numarul Carmichael are alta proprietate (mica teorema a lui Fermat).
Si in problema asta nu are nicio importanta daca e sau nu numarul lui Carmichael.

[Beniamin Bogosel]

Pai atunci rezolva tu problema cu 560 in loc de 561... Si incearca sa te uiti putin pe teoria numerelor sa vezi ce-i cu Cramichael ala, de exemplu aici http://mathworld.wolfram.com/CarmichaelNumber.html.

Si btw, ce am scris eu acolo e echivalent cu teorema lui Fermat...

[Filip Chindea]

Cine a "lecturat" forumul "din scoarta-n scoarta" ar fi observat aici (postat în Dec. 2007 - Ian. 2008) urmatoarele (ma repet):

Definitie. Orice intreg \( n > 1 \), compus se numeste pseudoprim Fermat in baza \( a \) daca \( a^n \equiv a \pmod{n} \).

Definitie. Orice intreg \( n > 1 \), compus se numeste Carmichael daca este pseudoprim in orice baza intreaga \( a \).

Teorema. \( n > 1 \), compus este Carmichael \( \Leftrightarrow \) este liber de patrate, \( \forall \ p \ \mathrm{prim}, \ p | n \Rightarrow p - 1 | n - 1 \), si, in plus, daca vreti, \( n \) este impar.

Demonstratie.
Implicatia directa. Daca \( p | n \), fie \( a \) un generator al lui \( \mathbb{Z}_p^{\ast} \). Din \( p | n | a^n - a \) deducem \( a^{n-1} \equiv 1 \pmod{p} \), de unde \( p - 1 = \mathrm{ord}_p(a) | n - 1 \). Daca, prin absurd, \( p^2 | n \) pentru un prim \( p \), fie \( a \) un generator al lui \( \left(\mathbb{Z}/p^2\mathbb{Z}\right)^{\times} \). De aici, \( p^2 | n | a^n - a \), si in final \( p | p(p-1) = \varphi(p^2) = \mathrm{ord}_{p^2}(a) | n - 1 \), deci \( p | n - 1 \) si \( p | n \), contradictie.
Implicatia reciproca. Fie un \( a \in \mathbb{Z} \). Cum \( n \) liber de patrate, este suficient sa aratam ca \( p | a^n - a \), pentru orice \( p \) factor al lui \( n \). Totul rezulta acum din Mica Teorema a lui Fermat. \( \qed \)

Solutia problemei. Fie acum un prim \( p > 561 \). Daca, prin absurd, \( \forall k \in \overline{1, 561} \), \( p | k^{560} - 1 \), avem \( \mathrm{ord}_p(k) | 560 \). Cum avem \( \varphi(d) \) elemente de ordin \( d | p - 1 \), numarul de astfel de clase de echivalenta este \( \sum_{d | 560} \varphi(d) = 560 \) (Gauss), deci avem cel mult \( 560 \) astfel de \( k \) - o contradictie.

Mai raman "doar" cazurile \( p < 561 \). Atunci orice element are ordinul divizandu-l pe \( 560 \), in particular \( p - 1 | 560 \) pentru un generator. Reciproc, aceste prime divid numerele respective. Apoi, \( p^{\alpha} | p^{560} - p \Rightarrow \alpha \le 1 \), deci acel divizor comun este liber de patrate.

In final, problema se incheie observand ca

\( \gcd_{k \in \overline{2,561}} \left(k^{561} - k\right) = \prod_{p - 1 | 560} p \), dupa toate primele \( p \). \( \qed \)

Este adevarat ca "mai era de munca" pana la solutie (inca 2-3 idei), insa lectura acelui topic ar fi fost un avantaj substantial pentru oricine nu era familiar cu ideile respective.

Problema este, evident, aceeasi pentru orice \( n \), \( 561 \) a fost dat pentru ca poate "pica" mai bine pe solutia autorului (insa este vorba despre acelasi numar si la problema de la TST 1996, deci cu atat mai multe motive de a face legatura).

Alte remarci. Inca din 1994 avem Teorema Alford-Granville-Pomerance, care ne garanteaza infinitudinea acestor numere. De fapt, acestia au aratat ca, daca \( \mathcal{C} \) este multimea acestor numere, iar \( A_{\mathcal{C}}(x) := |\{n \ : \ n \le x, \ n \in \mathcal{C} \}| \) - functia de numarare, exista \( x_0 \) suficient de mare cu \( A_{\mathcal{C}}(x) > x^{2/7} \) pentru orice \( x > x_0 \).

P. Erdos a obtinut, in 1956, un argument euristic care l-a condus la conjectura ca (in mod total anti-intuitiv !) pentru orice \( \epsilon > 0 \), exista un prag \( x_0(\epsilon) \) astfel incat \( A_{\mathcal{C}}(x) > x^{1 - \epsilon}, \forall x \ge x_0(\epsilon) \).