Afiliacja: Wydział Nauk Ścisłych i Przyrodniczych, Uniwersytet Pedagogiczny w Krakowie
W \(1980\) roku indyjski matematyk-amator Dattathreya Ramachandra Kaprekar opisał pewien szczególny typ liczb naturalnych posiadających zaskakującą własność. Przedstawimy ją na przykładzie liczby \(297.\) Rozważmy kwadrat tej liczby i przyjrzyjmy się jego cyfrom: \[297^2=88209,\ \ \ 88+209=297.\] Zapis dziesiętny tego kwadratu został podzielony na dwa bloki złożone z dwóch lub trzech cyfr o tej własności, że suma bloków daje wyjściową liczbę. Taka własność i jej odpowiedniki pozwalają na zdefiniowanie liczby Kaprekara, a ściślej liczby \(n\)-Kaprekara. Jest to każda liczba całkowita dodatnia \(N,\) dla której \[N^2=Q\cdot 10^n+R, \ \ \ N=Q+R,\] gdzie \(Q\geq 1\) i \(0\leq R<10^n\) są liczbami naturalnymi. Ponadto mówimy, że \(N\) jest liczbą Kaprekara, gdy jest liczbą \(n\)-Kaprekara dla pewnego \(n.\) Poniżej prezentujemy inne liczby Kaprekara. \[\begin{aligned} 9^2 & =81 & 8+1 & =9 & n & =1 \\ 45^2 & =2025 & 20+25 & =45 & n & =2 \\ 297^2 & =88209 & 88+209 & =297 & n & =3 \\ 4879^2 & =23804641 & 238+4641 & =4879 & n & =5 \\ 538461^2 & =289940248521 & 289940+248521 & =538461 & n & =6 \end{aligned}{}\]
D. R. Kaprekar formalnie nie miał żadnego wyższego wykształcenia matematycznego, mimo to opublikował bardzo dużo artykułów naukowych i popularnonaukowych.
Przyjmuje się ponadto, że \(N=1\) jest liczbą \(n\)-Kaprekara dla dowolnego \(n.\) Przypadek ten, odpowiadający \(Q=0,\) \(R=1,\) nazywa się trywialnym.
Czwarty z podanych wyżej przykładów jednocześnie pokazuje, że może zdarzyć się, że \(R\) ma mniej niż \(n\) cyfr (pierwsza cyfra bloku to \(0,\) którą w naturalny sposób pomijamy w zapisie).
Trywialnym przykładem liczby \(n\)-Kaprekara jest \(10^n\); trochę bardziej ciekawym zaś \(10^n-1.\) Istotnie, \[\begin{aligned} & (10^n-1)^2=\underbrace{9\ldots9}_{\times n}{}^{2}=\underbrace{9\ldots9}_{\times (n-1)}8\underbrace{0\ldots0}_{\times (n-1)}1, \\ &\underbrace{9\ldots9}_{\times (n-1)}8+1=\underbrace{99\ldots9}_{\times n}. \end{aligned}\] Opisany powyżej przykład stanowi przyczynek do sformułowania pierwszego wyniku teoretycznego, opisującego jedną z podstawowych własności – liczności zbioru liczb Kaprekara.
Twierdzenie 1. Istnieje nieskończenie wiele liczb Kaprekara.
W dalszej części przyjrzymy się problemowi konstrukcji liczb Kaprekara. Niech \(K(M)\) będzie zbiorem wszystkich liczb naturalnych \(N\) takich, że \[\tag{1} \label{wz1} N^2 =QM+R,\] \[\tag{2} \label{wz2} N =Q+R,\] przy czym \(0\leq R < M.\) Ponadto będziemy pomijać przypadki trywialne \(N=M,\) dla których \(Q=M\) i \(R=0,\) czyli przyjmujemy, że \(M\notin K(M).\) Aby nie rozważać bardzo prostych przypadków, zakładamy też, że \(M>2.\) Zauważmy prostą własność zdefiniowanych przed chwilą zbiorów \(K(M).\)
Przypadek \(M=10^n\) opisuje zbiór liczb \(n\)-Kaprekara.
Jeśli \(M=1\) lub \(M=2,\) to przyjmujemy, że \(K(M)=\{1\}.\)
Twierdzenie 2. Zbiór \(K(M)\) jest niepusty.
Dowód. Oczywiste, gdyż \(1\in K(M).\) Można ponadto zauważyć, że również \(M-1\in K(M),\) wystarczy przyjąć \(Q=M-2\) oraz \(R=1.\)\(\Box\)
Zauważmy następnie, że warunki \(\eqref{wz1}\) i \(\eqref{wz2}\) dają \({N(N-1)=Q(M-1)},\) a stąd wnioskujemy \({1\leq N\leq M-1}.\) Istotnie, gdyby \(N> M,\) to \(Q>N,\) co przeczy \(\eqref{wz2}\). Tym samym udowodniliśmy kolejne twierdzenie.
Twierdzenie 3. Zbiór \(K(M)\) jest skończony, co najmniej dwuelementowy i zawarty w zbiorze \(\{1,2,\ldots, M-1\}.\)
W kolejnej części naszych rozważań wprowadzimy pojęcie dzielnika unitarnego. Powiemy, że liczba \(a\) jest dzielnikiem unitarnym \(N,\) jeśli \(N=ab\) oraz \(a\) i \(b\) są liczbami względnie pierwszymi.
Niech \(a\) i \(b\) będą liczbami względnie pierwszymi. Oznaczmy przez \(\text{Inv}(a,b)\) najmniejszą dodatnią liczbę naturalną \(m\) taką, że \(am\equiv 1 \pmod{b}.\) Innymi słowy, \(m=\text{Inv}(a,b)\) wtedy i tylko wtedy, gdy \(1\leq m<b\) i \(am\equiv 1\pmod{b}.\) Funkcja \(\text{Inv}(a,b)\) nie jest symetryczna, to jest na ogół \(\text{Inv}(a,b)\neq \text{Inv}(b,a).\) Niemniej zachodzi ciekawy związek między dwiema ostatnimi liczbami.
Mówimy, że dwie liczby całkowite \(x\) i \(y\) przystają modulo \(z,\) jeśli \(x-y\) jest podzielne przez \(z.\) Fakt ten zapisujemy jako \(x\equiv y\pmod{z}.\)
Fakt 1. Jeśli \(a\) i \(b\) są względnie pierwsze, to \({m=\text{Inv}(a,b)}\) oraz \(n=\text{Inv}(b,a)\) wtedy i tylko wtedy, gdy \(m\) i \(n\) są dodatnie oraz \(am+bn=ab+1.\)
Dowód. Równość \(am+bn=ab+1\) można przekształcić do postaci \(am - 1 = b(a - n),\) a więc \(am\equiv 1 \pmod{b}.\) Gdyby \(m\geq b,\) to \(am+bn\geq ab+bn>ab+1,\) sprzeczność, a więc \(m=\text{Inv}(a,b).\) Podobnie dowodzimy, że \(n=\text{Inv}(b,a).\)
Załóżmy teraz, że \(m=\text{Inv}(a,b)\) oraz \(n=\text{Inv}(b,a),\) a więc \(am\equiv 1\pmod{b}\) oraz \(bn\equiv 1\pmod{a}.\) Korzystając z chińskiego twierdzenia o resztach, otrzymujemy teraz, że \(am+bn\equiv 1\pmod{ab},\) czyli \(am+bn=1+k\cdot ab\) dla pewnej liczby całkowitej \(k.\) Wszystkie liczby \(a,\) \(b,\) \(m\) i \(n\) są dodatnie, zatem \(k\) też jest liczbą dodatnią. Ponieważ \(1\leq m<b\) oraz \(1\leq n<a,\) \[1+k\cdot ab=am+bn< ab+ba=2ab.\] Ponieważ wszystkie rozważane liczby są naturalne, powyższa nierówność może być prawdziwa tylko dla \({k = 1}.\) Ostatecznie więc otrzymaliśmy, że \({am+bn=1+ab}.\) Kończy to dowód faktu 1.\(\Box\)
Sformułujemy teraz praktyczne twierdzenie pozwalające wyznaczać liczby Kaprekara.
Twierdzenie 4. Liczba \(N\) jest elementem zbioru \(K(M)\) wtedy i tylko wtedy, gdy \(N=d\cdot \text{Inv}(d,(M-1)/d),\) gdzie \(d\) jest pewnym dzielnikiem unitarnym liczby \(M-1.\) Ponadto dla każdego \(N\in K(M)\) liczba \(M-N\) również jest elementem \(K(M).\)
Dowód. \(({\Longrightarrow})\) Wiemy już, że \(N(N-1)=Q(M-1).\) Ponieważ \({\text{NWD}(N,N-1)=1},\) istnieją względnie pierwsze liczby \(d\) i \(e\) i takie, że \({M-1=de}\) oraz:
\(d|N,\) i tym samym \(N=du\) dla pewnego \(u\) oraz (na mocy twierdzenia 3) \(du=N\leq M-1=de,\) to jest \(u\leq e,\)
\(e|(N-1),\) co daje istnienie \(v\) takiego, że \(ev+1=N,\) czyli \(du\equiv 1 \pmod{e}\) i w szczególności \(u\neq e.\)
Stąd \(u<e\) i możemy zatem zapisać \(u=\text{Inv}(d,e).\) Ponieważ \(e=(M-1)/d,\) liczba \(N\) ma żądaną postać.
\((\Longleftarrow)\) Liczba \(e=(M-1)/d\) jest całkowita. Ponadto z definicji
dzielnika unitarnego
wynika, że \(\text{NWD}(e,d)=1.\) Oznaczmy dalej
\(u=\text{Inv}(d,e).\) Z definicji \(u< e\) oraz istnieje taka liczba naturalna \(k,\) że \(du= ke+ 1.\) Ponieważ \(N=du,\) więc
\[\begin{aligned}
N^2 & =dudu=du(ke+1)=kued+du \\
& =ku(M-1)+du=kuM+(d-k)u.
\end{aligned}\]
Definiujemy \(Q=ku\) oraz \(R=(d-k)u.\) Wówczas \(Q+R=N\) oraz:
\(du=ke+1>ku+1>ku,\) stąd \(d>k\) i \(R>0,\)
\((d-k)u<(d-k)e=de-ke=M-1-ke<M,\) stąd \(R<M.\)
Widzimy zatem, że
\(N\) jest elementem zbioru \(K(M).\)
Pozostała część twierdzenia wynika z faktu 1: jeśli bowiem \(N\in K(M),\) to \({N=d\cdot \text{Inv}(d,(M-1)/d)}\) i oznaczając \(e=(M-1)/d,\) \(u=\text{Inv}(d,e)\) oraz \({u'=\text{Inv}(e,d)},\) mamy równość \(du+eu'=de+1=M,\) czyli \(eu'=M-N\) i liczba \({M-N}\) jest postaci jak w poprzedniej części dowodzonego właśnie twierdzenia.\(\Box\)
Dla zilustrowania twierdzenia 4 wybierzmy \(M=10^n\) i \(n=3\) (a więc szukamy liczb \(3\)-Kaprekara). Wtedy \(10^3-1=27\cdot 37\) i liczby \(27\) oraz \(37\) są względnie pierwsze, zatem są dzielnikami unitarnymi \(10^3-1.\) Sprawdzamy następnie, że \[\text{Inv}(27,37)=11,\ \ \ \text{Inv}(37,27)=19.\] Dlatego na mocy twierdzenia 4 liczby \(27\cdot 11=297\) oraz \(37\cdot 19=703\) są (jedynymi prócz trywialnych 1 i \(10^3-1\)) liczbami \(3\)-Kaprekara. Ponadto \(297+703=1000,\) zgodnie z przewidywaniami drugiej części twierdzenia 4.
Zauważmy, że jeśli w twierdzeniu 4 przyjmiemy \(M=b^n\) dla pewnej liczby naturalnej \(b,\) otrzymujemy liczby Kaprekara w systemie pozycyjnym o podstawie \(b.\) Przypadek \(b=2\) jest ponadto interesujący z następującego powodu.
Twierdzenie 5. Każda parzysta liczba doskonała jest liczbą Kaprekara w dwójkowym systemie pozycyjnym.
Liczba doskonała to liczba naturalna \(n,\) której suma dzielników jest równa \(2n.\) Na przykład \(28\) jest liczbą doskonałą, gdyż \({1+2+4+7+14+28=56=2\cdot 28}.\)
Dowód. Wiadomo, że każda parzysta liczba doskonała jest postaci \(2^{n-1}(2^n-1)\) dla pewnego \(n\) takiego, że \(2^n-1\) jest liczbą pierwszą. Ustalmy \(n\geq 1.\) Liczby \(2^n-1\) oraz \(2^n+1\) są względnie pierwsze oraz \[2^{n-1}(2^n-1)\equiv 1\pmod{2^n+1}, \ \ \ 0<2^{n-1}<2^n+1.\] Stąd \(2^{n-1}=\text{Inv}(2^{n}-1,2^n+1),\) a więc z twierdzenia 4 liczba \(2^{n-1}(2^n-1)\) jest elementem zbioru \(K(2^{2n}).\) Dowód twierdzenia jest więc zakończony.
Zilustrujmy twierdzenie 5 prostym przykładem. Liczba \(28\) jest doskonała (zobacz uwagę po twierdzeniu 5) oraz \(28=(11100)_2.\) Ponadto (działania rozważamy w systemie dwójkowym) \[11100^2=1100010000, \ \ \ 1100+010000=11100,\] czyli \((111000)_2\) jest liczbą \(6\)-Kaprekara.
Ostatnie twierdzenie pozwoli nam na obliczenie, ile dokładnie jest elementów zbioru \(K(M),\) ale będziemy potrzebowali jeszcze jednego lematu. Niech \(\omega(m)\) oznacza liczbę dzielników pierwszych liczby \(m.\)
Lemat 1. Liczba \(m\) posiada dokładnie \(2^{\omega(m)}\) dzielników unitarnych.
Dowód. Niech \(m=p_1^{a_1}\cdot p_2^{a_2}\cdot\ldots\cdot p_k^{a_k}\) (a więc \(\omega(m)=k\)) oraz niech \(a\) będzie dzielnikiem unitarnym i niech \(m=ab.\) Jeśli \(p_i|a,\) to musi być \(p_i^{a_i}|a,\) gdyż w przeciwnym wypadku \(p_i|b.\) Tym samym wybór \(a\) polega na wybraniu pewnych dzielników pierwszych \(m\) z najwyższymi potęgami. Takich wyborów jest z kolei \(2^k.\)\(\Box\)
Lemat 1 oraz twierdzenie 4 pozwalają już stwierdzić, ile jest liczb w zbiorze \(K(M).\)
Twierdzenie 6. Zbiór \(K(M)\) posiada dokładnie \(2^{\omega(M-1)}\) elementów.
Polecamy Czytelnikowi zweryfikowanie słuszności tego twierdzenia dla analizowanego wcześniej przykładu liczb 3-Kaprekara.