Liczby naturalne są najbardziej podstawowymi, czyli elementarnymi, obiektami badanymi przez matematyków. Elementarnymi, lecz w żadnym wypadku nie trywialnymi. Brak trywialności przejawia się często w oporze, z jakim liczby naturalne poddają się badaniu. Często tajemnicza niechęć, z jaką liczby naturalne ujawniają swoją strukturę w połączeniu z przejawianą prostotą sformułowań problemów, stanową silny magnes przyciągający wielu do bliższego się im przyjrzenia. Część matematyki, w której bada się liczby naturalne przyjęto nazywać teorią liczb.

Jedną z pierwszych własności, jaką poznajemy o liczbach naturalnych, jest to, że występuje wśród nich relacja podzielności, tj. jedna liczba może być częscią składową, dzielnikiem, drugiej. Na przykład \(1\) dzieli każdą liczbę naturalną. Podobnie, mając liczbę \(n\) jej dzielnikiem jest również… \(n\). Stąd dla dowolnej liczby \(n\) mówimy, że \(1\) i \(n\) są jej dzielnikami trywialnymi.

Nasuwa się naturalne pytanie, czy istnieją liczby których jedynymi dzielnikami są dzielniki trywialne? Odpowiedź jest twierdząca: tak, istnieją, a nazywa się je liczbami pierwszymi. Co więcej, jeszcze ze szkoły wiemy, że liczb tych jest nieskończenie wiele. Zatem jeżeli oznaczymy przez
\[
d(n) \text{ − liczba dzielników liczby } n,
\]
to dla każdej liczby pierwszej \(p\) mamy
\[
d(p) = 2,
\]
a dalej
\begin{equation}\label{ograniczeniedolne}
d(n)\geq 2
\end{equation}
dla dowolnej liczby naturalnej większej od \(1\).

W tym momencie można zadać jak najbardziej naturalne pytanie: ile maksymalnie może być dzielników liczby \(n\) lub, innymi słowy, skoro \(d(n)\geq 2\) daje nam ograniczenie dolne na \(d(n)\), to jakie jest ograniczenie górne?

Aby odpowiedzieć na powyższe pytanie zauważmy najpierw, że jeżeli liczba \(\delta\) jest dzielnikiem liczby \(n\), to znaczy, że istnieje następujący rozkład \(n\) na czynniki \(n= \delta \delta’ \), gdzie \(\delta’\) jest pewną liczbą naturalną. W konsekwencji jedna z liczb \(\delta\) lub \(\delta ‚\) nie może być większa od \(n^{1/2}\), bo w przeciwnym razie \(\delta \delta’ > n\). Zatem w ,,najgorszym przypadku”, wszystkie liczby mniejsze lub równe \(n^{1/2}\) są dzielnikami \(n\), a ponieważ dzielniki występują w parach (\(n= \delta \delta’ \)), zatem

\begin{equation*}\label{ograniczeniegorne1}
d(n)\leq 2n^{1/2}
\end{equation*}
dla wszystkich liczb naturalnych \(n\).

Zobaczmy jak wygląda tabela liczby dzielników dla wybranych liczb \(n\)

Już na tak małej próbce widać, że ograniczenie górne \(d(n)\leq 2n^{1/2}\) jest dalekie od rzeczywistej wielkości. Pojawia się zatem kolejne pytanie: czy można je poprawić? Odpowiedź brzmi: tak! Jednak aby to zrobić, trzeba powiedzieć więcej o liczbie dzielników.

Zauważmy, że jeżeli liczby \(m\) oraz \(n\) są względnie pierwsze, to znaczy, że nie posiadają wspólnego dzielnika różnego od \(1\), to każdy dzielnik liczby \(mn\) jest postaci \(\gamma\delta\), gdzie \(\gamma\) jest dzielnikiem \(m\), zaś \(\delta\) dzielnikiem \(n\). Zatem, aby wyznaczyć liczbę \(d(mn)\) wystarczy wyznaczyć \(d(m)\) oraz \(d(n)\) i je pomnożyć. W ten sposób otrzymujemy zależność
\[
d(mn) = d(m)d(n)\quad \text{o ile \(m\) i \(n\) są względnie pierwsze}.
\]
Własność powyższą nazywamy multiplikatywnością.

Mniej więcej w tym samym czasie, co o relacji podzielności, dowiadujemy się, że każda liczba naturalna daje się przedstawić w sposób jednoznaczny jako iloczyn potęg różnych liczb pierwszych. Na przykład
\begin{align*}
36&=2^2\cdot 3^2 \\
90&=2\cdot 3^2 \cdot5 \\
630&=2\cdot 3^2\cdot 5\cdot 7 \\
990&=2\cdot 3^2\cdot 5\cdot 11.
\end{align*}
W ogólności piszemy
\[
n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \dots p_{k}^{\alpha_{k}},
\]
gdzie \(p_i \neq p_j\) o ile \(i\neq j\) lub, innymi słowy, liczby \(p_1, p_2, \dots, p_k\) są \textit{parami różne}. Oczywiście jeżeli liczby pierwsze \(p_i\) oraz \(p_j\) są różne, to są względnie pierwsze. Podobnie dla \(p_i \neq p_j\) liczby \(p_{i}^{\alpha_{i}}\) oraz \(p_{j}^{\alpha_{j}}\) są względnie pierwsze. Ponieważ \(d(n)\) jest multiplikatywna, mamy
\[
d\left(p_{i}^{\alpha_{i}} p_{j}^{\alpha_{j}}\right) = d\left(p_{i}^{\alpha_{i}}\right)d\left(p_{j}^{\alpha_{j}}\right)\quad \text{o ile } p_i \neq p_j.
\]
W konsekwencji jeżeli \(n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \dots p_{k}^{\alpha_{k}}\), to
\begin{equation}
d(n) = d\left(p_{1}^{\alpha_{1}}\right)d\left(p_{2}^{\alpha_{2}}\right)\dots d\left(p_{k}^{\alpha_{k}}\right).
\end{equation}
W ten sposób, aby otrzymać bardziej jawną formułę na liczbę dzielników, a dalej punkt wyjścia do znalezienia lepszego ograniczenia górnego \(d(n)\), wystarczy wyznaczyć dokładną wartość dla \(d\left(p_{i}^{\alpha_{i}}\right)\).

Na prostym przykładzie \(p^5\), gdzie \(p\) jest dowolną liczbą pierwszą widać, że dzielnikami \(p^5\) są liczby \(p^0, p, p^2, p^3, p^4, p^5\) czyli jest ich \(6\). W ogólności zachodzi
\[
d\left(p^{\alpha}\right) = \alpha + 1.
\]
Ostatecznie, przy założeniu \(n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \dots p_{k}^{\alpha_{k}}\), otrzymujemy formułę jawną na \(d(n)\) postaci
\[
d\left(n\right) = \left(\alpha_1 + 1\right)\left(\alpha_2 + 1\right)\dots \left(\alpha_k + 1\right).
\]
Powyższa równość może wydawać się mało satysfakcjonująca, ponieważ do wyznaczenia liczb \(\alpha_i\) trzeba znaleźć rozkład na potęgi liczb pierwszych liczby \(n\), a stąd już mały krok do wyznaczenia wszystkich dzielników, lecz musimy pamiętać, że naszym obecnym celem nie jest znalezienie ,,łatwo obliczalnej” formuły, tylko ograniczenia górnego, lepszego niż dotychczasowe.

Przyjrzyjmy się zatem lepiej ograniczeniu
\[
d(n)\leq {\color{blue} 2} n^{\color{red}{1/2}}.
\]
Zauważmy, że składa się ono ze stałej (powyżej równej 2) oraz wykładnika (wyżej równego \(1/2\)). Zauważmy, że dla małych liczb \(n\) stała ma kluczowe znaczenie. Istotnie

Widać, że zmniejszając tylko stałą, można dla małych warości liczby \(n\) otrzymać liczby niebędące ograniczeniami górnymi \(d(n)\). Z kolei dla większych liczb mamy

Dla nich otrzymujemy nowe ograniczenie górne, które nadal jest dosyć odległe od rzeczywistej wartości. Widać, że zmniejszając wartość stałej utraciliśmy oszacowanie dla małych \(n\) zaś dla dużych poprawiliśmy, pozostawiając jednak znaczącą lukę między ograniczeniem górnym a wartością rzeczywistą.

Zmniejszmy więc wykładnik a stałą pozostawmy bez zmian. W przypadku małych \(n\) otrzymujemy

Zaś dla większych \(n\) mamy

Reasumując, zmniejszając stałą utraciliśmy ograniczenie górne dla małych \(n\), jednak w tym samym czasie poprawiliśmy (dwukrotnie) dla dużych \(n\). Zmniejszając wykładnik utraciliśmy ograniczenie górne zarówno dla małych jak i dla dużych \(n\). Przyjrzyjmy się jednak poniższemu zestawiemiu

Pokazuje ono, że po zwiększeniu stałej i jednoczesnym zmniejszeniu wykładnika otrzymaliśmy ograniczenie górne znacznie bliższe rzeczywistej wartości \(d(n)\) dla dużych \(n\).

Można zatem wysnuć hipotezę, że aby polepszyć oszacowanie górne trzeba zmniejszać wykładnik przy jednoczesnym zwiększeniu stałej. Spróbujmy zatem wcielić w życie tę ideę. Chcemy uzyskać oszacowanie postaci
\[
d(n) \leq \color{bleu}{C}n^{\color{red}\epsilon},\quad n\geq 1,
\]
gdzie stała C może być większa niż \(4\) lecz wykładnik \(\epsilon\) mały (mniejszy niż \(\frac{1}{4}\)). Rozważmy zatem wyrażenie postaci
\[
\frac{d(n)}{n^{\color{red}\epsilon}},\quad \text{gdzie}\quad 0 < \color{red}\epsilon \color{black} < \frac{1}{4}.
\]
Korzystając z rozkładu \(n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \dots p_{k}^{\alpha_{k}}\) oraz formuły \(d\left(n\right) = \left(\alpha_1 + 1\right)\left(\alpha_2 + 1\right)\dots \left(\alpha_k + 1\right)\) otrzymujemy
\begin{equation}\label{formulajawna1}
\frac{d(n)}{n^{\color{red}\epsilon}} = \frac{\left(\alpha_{1} + 1\right)}{p_{1}^{\alpha_{1}\color{red}\epsilon}} \frac{\left(\alpha_{2} + 1\right)}{p_{2}^{\alpha_{2}\color{red}\epsilon}}\dots \frac{\left(\alpha_{k} + 1\right)}{p_{k}^{\alpha_{k}\color{red}\epsilon}}.
\end{equation}
Będziemy starali się tak zwiększać stałą, aby dla małych \(n\) mieć dobre oszacowanie, przy utrzymaniu jednocześnie możliwie małego wykładnika. Zatem iloczyn po prawej stronie powyższej równości podzielimy na dwie części. Osobno rozpatrzymy iloczyn dla liczb pierwszych \(p < 2^{1/\color{red}\epsilon}\), czyli ,,małych” liczb pierwszych, których jest tylko skończenie wiele, a osobno dla \(p \geq 2^{1/\color{red}\epsilon}\), czyli ,,dużych” liczb pierwszych. Określenia ,,mała”, ,,duża” generalnie są umowne, jednak w tym kontekście chodzi o rozdzielenie zbioru liczb pierwszych na dwie części, skończoną i nieskończoną.

Dla \(p \geq 2^{1/\color{red}\epsilon}\) mamy, że \(p^{\color{red}\epsilon}\geq 2\) i w konsekwencji \(p^{\alpha\color{red}\epsilon}\geq 2^{\alpha}\) co daje nam
\[
\frac{\alpha + 1}{p^{\alpha\color{red}\epsilon}} \leq \frac{\alpha + 1}{2^{\alpha}} \leq 1.
\]

Zauważmy, że
\[
\alpha\color{red}\epsilon\color{black}\log 2 \leq \text{e}^{\alpha\color{red}\epsilon\log 2} = 2^{\alpha\color{red}\epsilon} \leq p^{\alpha\color{red}\epsilon}.
\]
Wtedy dla \(p < 2^{1/\color{red}\epsilon}\) mamy, że
\[
\frac{\alpha + 1}{p^{\alpha\color{red}\epsilon}} \leq 1 + \frac{\alpha}{p^{\alpha\color{red}\epsilon}} \leq 1 + \frac{1}{\color{red}{\epsilon}\log 2}.
\]
Ponieważ, jak wspomniano wyżej, liczb pierwszych \(p < 2^{1/\color{red}\epsilon}\), dla ustalonego \(\color{red}\epsilon\), jest skończenie wiele, zatem niech \(p_{\color{red}{max}}\) będzie największą z nich. Wtedy kładąc
\[
\underbrace{\left(1 + \frac{1}{\color{red}{\epsilon}\log 2}\right)\left(1 + \frac{1}{\color{red}{\epsilon}\log 2}\right)\dots \left(1 + \frac{1}{\color{red}{\epsilon} \log 2}\right)}_{p_{\color{red}{max}}-\text{razy}} = \color{bleu}{C}(\color{red}{\epsilon})
\]
otrzymujemy
\[
\frac{\left(\alpha_{1} + 1\right)}{p_{1}^{\alpha_{1}\color{red}{\epsilon}}} \frac{\left(\alpha_{2} + 1\right)}{p_{2}^{\alpha_{2}\color{red}{\epsilon}}}\dots\frac{\left(\alpha_{\color{red}{max}} + 1\right)}{p_{\color{red}{max}}^{\alpha_{\color{red}{max}}\color{red}\epsilon}}\frac{\left(\alpha_{\color{red}{max}\color{black}+1} + 1\right)}{p_{\color{red}{max}\color{black}+1}^{\alpha_{\color{red}{max}+1}\color{red}\epsilon}}\dots \frac{\left(\alpha_{k} + 1\right)}{p_{\color{black}k}^{\alpha_{k}\color{red}\epsilon}} \leq \color{bleu}{C}(\color{red}{\epsilon})
\]
a w konsekwencji na mocy \(d(n) = d\left(p_{1}^{\alpha_{1}}\right)d\left(p_{2}^{\alpha_{2}}\right)\dots d\left(p_{k}^{\alpha_{k}}\right)\) oraz powyższego oszacowania
\[
\frac{d(n)}{n^{\color{red}\epsilon}}\leq \color{bleu}{C}(\color{red}{\epsilon})
\]
czyli
\begin{equation}
d(n)\leq \color{bleu}{C}(\color{red}{\epsilon}) n^{\color{red}{\epsilon}}.
\end{equation}

Zobaczmy, co dostaliśmy na przykładzie \(\epsilon = \frac{1}{10}\). Wtedy \(2^{1/\epsilon} = 2^{10} = 1024\). Największą liczbą pierwszą mniejszą od \(1024\) , czyli \(p_{\color{red}{max}}\), jest \(1021\) a wszystkich liczb pierwszych mniejszych od \(1024\) jest \(172\). Czyli po podstawieniu do równania na \(\color{bleu}{C}(\color{red}{\epsilon})\) mamy
\[
\text{C}\left(\frac{1}{10}\right) = \left(1 + \frac{10}{\log 2}\right)^{172}\approx 2{,}442\cdot 10^{204}
\]
czyli astonomicznie wielką stałą. Pamiętajmy jednak, że ograniczenie, które dostaliśmy, jest pewne, niezależnie od tego jak wielkie liczby będziemy chcieli sprawdzić.

Pozostaje jeszcze pytanie, po co tak dokładnie szacować liczbę dzielników. Tak się składa, że znajomość tej liczby bywa użyteczna w ukrywaniu informacji, czyli kryptografii. Jednym z częściej wykorzystywanych algorytmów szyfrujących jest RSA. Bez wchodzenia w jego szczegóły, wspomnieć jednak warto, że kluczowe dla jego bezpiecznego działania są liczby naturalne posiadające dokładnie dwa dzielniki nietrywialne będące liczbami pierwszymi. Liczby te są ukryte wśród tych dla których \(d(n) = 4\). Opór z jakim \(d(n)\) poddaje się oszacowaniu z góry działa więc na naszą korzyść: trudniej złamać RSA. Zatem ten, kto lepiej potrafi ,,odgadywać” liczbę dzielników zbliża się do wielu sekretów. Skoro zaś wiedza to potęga − dividete et imperate!

Artykuł został sfinansowany dzięki wsparciu pozyskanemu przez Poznańską Fundację Matematyczną od Miasta Poznań na realizację projektu "Potęga matematyki".