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) \).