Kongruencje z królikiem

Artykuł o powyższym tytule wypada rozpocząć od przypomnienia, czym są kongruencje. Jeśli dwie liczby naturalne $|a$ i $b$ dają tę samą resztę z dzielenia przez liczbę naturalną $n$ (innymi słowy, jeśli $|a− b$ jest podzielne przez $n$ ), uczenie jest stwierdzić, że $a$ i $b$ przystają do siebie modulo $n$ i fakt ten zanotować jako $a ≡ b modn:$ W tym kontekście znaczek " $≡$ " (lub raczej to, co on sobą reprezentuje) nazywamy właśnie kongruencją.

Kongruencje mają wiele wdzięcznych własności, między innymi można je dodawać i mnożyć stronami tak jak zwykłe równania. Ich zastosowanie pozwala uprościć zawiłe nieraz rozumowania z zakresu teorii liczb. W moim artykule chciałbym skoncentrować się na problemach dotyczących początkowych cyfr liczb postaci $k n ,$ gdzie $|n$ i $k$ są liczbami naturalnymi. Rozpocznę od rozwiązania zadania, które skłoniło mnie do takich rozważań.

Rozwiązanie. Najpierw zauważmy, że dla dowolnego $n$ mamy $5 |n≡ n mod10.$ Istotnie, niech $A$ Jeśli $n$ jest podzielne przez 5, to oczywiście 5 dzieli również $|A.$ Z drugiej strony, jeśli $|n$ nie jest podzielne przez 5, to rozpatrując wszystkie niezerowe reszty z dzielenia $n$ przez 5, możemy się przekonać, że $n2$ daje resztę 1 lub 4 z dzielenia przez 5 i w obu przypadkach 5 dzieli $|A.$ W analogiczny (a nawet prostszy) sposób pokazujemy, że $A$ jest zawsze podzielne przez 2, skąd wnioskujemy podzielność $A$ przez 10 i $n | ≡ n5 mod10$ dla dowolnej liczby naturalnej $n.$ Zauważmy, że jeśli będziemy mnożyć tę kongruencję obustronnie przez $4 |n ,$ otrzymamy ciąg kongruencji

5 9 n≡ n ≡ n ≡ ... mod10.

Teraz już rozważamy tylko te potęgi $n,$ których wykładnik daje resztę 1 z dzielenia przez 4. Dzięki temu ostatnia cyfra $c$ liczby $|n$ będzie cyfrą, którą chcemy otrzymać jako pierwszą cyfrę liczby $n4k+1$ dla pewnego $k.$ Chcemy zatem uzyskać

c c+ 1 c ⋅10t ⩽ n4k+1 < (c + 1)10t, to znaczy-⋅10t ⩽n4k < -----⋅10t. n n

Po przyłożeniu do obu stron logarytmu dziesiętnego dostajemy równoważną postać

c c+ 1 t + log --⩽ 4k log n < t +log----. n n

Dzięki zlogarytmowaniu nasz problem wygląda następująco: mamy nieskończenie długą drogę, na której co 1 mamy dziurę długości

c+ 1 c ∆ = (log-----−log -) = (log(c + 1)− log c), n n

począwszy od $log c. n$ Po tej nieskończonej drodze skacze królik, który rozpoczyna w 0 i robi skoki długości $| 4logn.$ Chcemy pokazać, że nasz królik wpadnie kiedyś do dziury. Innymi słowy, potrzebujemy uzasadnić, że

log c-⩽ {4k logn} < log c-+ ∆ , n n

gdzie $| {x}$ oznacza część ułamkową liczby $| x.$ Zauważmy najpierw, że dla różnych liczb naturalnych $k,l$ liczby $|{4klog n}$ oraz $|{4llogn}$ są różne. W przeciwnym przypadku istniałoby takie $|m$ naturalne, że $4k | logn − 4llogn = m,$ czyli $n4 | k−l = 10m,$ co przeczy założeniu o niepodzielności $| n$ przez 10. Rozważmy teraz liczby $|{4logn}, {8logn}, ...,{4alog n},$ gdzie $a$ to pewna liczba naturalna, która jest większa od $|∆−1.$ Skoro wypisane liczby są różne, to pewne dwie leżą w odległości mniejszej niż $∆$ (odległość liczb $|p$ i $q$ należy tu rozumieć jako mniejszą z liczb $| p − q$ oraz $1 − p −q$ ). Oznaczmy je przez ${4x log n}$ oraz ${4y logn},$ gdzie $x > y.$ W tej sytuacji liczba $|{4(x −y) log n}$ leży w przedziale $|(0,∆)$ lub $(1− ∆ ,1).$ Patrząc na ciąg $|{4(x −y) log n},{8(x − y) log n},...$ widzimy teraz, że dla początkowych wyrazów jest on ściśle monotoniczny i dla pewnego $p$ naturalnego otrzymamy $|log c⩽ {4p(x − y) log n} < log c+ ∆.$ Wystarczy więc przyjąć $|k = p(x − y),$ aby zakończyć rozwiązanie zadania.

W powyższym dowodzie można wyróżnić dwie istotne części: pierwsza polega na wskazaniu podciągu potęg $|n,$ które kończą się tą samą cyfrą, a w drugiej pokazaliśmy, że dowolna cyfra może stać na początku pewnego wyrazu tego podciągu. Tę drugą część można nietrudno zmodyfikować tak, aby wykazać poniższe:

Twierdzenie 1. Dla dowolnej liczby naturalnej $n > 1,$ która nie jest potęgą dziesiątki, i dowolnego ciągu cyfr $|c1 ≠0,c2,$ $...,cs$ istnieje liczba naturalna $k,$ dla której początkowe cyfry liczby $nk$ to $|c1,...,cs.$

Z powyższego twierdzenia wynika, że dla dowolnego $n$ możemy znaleźć $|k,$ dla którego $|nk$ będzie się rozpoczynało, na przykład, od cyfr 100000, czyli będzie dość bliskie pewnej potędze dziesiątki. Warto zwrócić uwagę, że możemy oszacować wykładnik tej potęgi $n$ niezależnie od $|n.$

Twierdzenie 2. Jeśli $|n > 1$ jest liczbą naturalną niepodzielną przez 10, to dla dowolnego $ε > 0$ istnieją takie liczby naturalne $|k,l,$ że $10l(1− ε)⩽ nk ⩽ 10l(1+ ε)$ oraz $k ⩽ ⌊log(1 +ε)−1⌋.$

Dowód. Żądamy od naszego $k,$ aby

l k l 10 ⋅(1− ε)⩽ n ⩽ 10 ⋅(1 +ε)

dla pewnego naturalnego $|l.$ Ponownie równoważnie

l + log(1 −ε) ⩽ klogn ⩽ l + log(1+ ε),

więc

0 ⩽{k logn} ⩽ log(1+ ε) lub1+ log(1− ε)⩽ {k logn} < 1.

Łatwo wykazać, że

1+ log(1 − ε) < 1− log(1 + ε),

więc wystarczające jest, aby

0 ⩽{k logn} ⩽ log(1+ ε) lub1− log(1+ ε)⩽ {k logn} < 1.

Dalej postępujemy tak jak poprzednio - kolejne liczby postaci $|{klogn}$ są różne, zatem wśród pierwszych $⌊(log(1 + ε))−1⌋+ 1$ pewne dwie znajdują się w odległości mniejszej od $|log(1 + ε),$ a ich różnica jest szukaną wielokrotnością $log n.$

Należy podkreślić, że opisana w twierdzeniu liczba $k$ jest nie większa od $|⌊(log(1+ ε))−1⌋.$ Na przykład, biorąc $ε = 0,1,$ otrzymujemy, że dla dowolnej liczby $n$ istnieje liczba $k$ nie większa od $|24,$ taka, że $|n$ można przybliżyć potęgą dziesiątki z dokładnością do $|10%.$ Przykładową wartością $n,$ dla której przedstawione oszacowanie jest optymalne, jest $|11001.$ Podobny rezultat możemy, oczywiście, uzyskać, rozważając przybliżenia potęgami innych liczb naturalnych niż 10. Przykładowo, dla $p = 2$ przybliżamy $nk$ z dokładnością do $|10%$ liczbą postaci $l |2$ i wystarczy do tego $k$ nie większe niż 7.

Wróćmy do naszych początkowych cyfr. Wydaje się, że ciągi liczb, które nie są jakoś szczególnie zbudowane, mogą rozpoczynać się dowolnymi cyframi. Oczywiście, nie jestem w stanie udowodnić powyższego, bo cóż to są "szczególne ciągi"? Oto kolejny przykład liczb, które mogą rozpoczynać się od dowolnych cyfr:

Twierdzenie 3. Liczby postaci $|kn$ , gdzie $n$ jest ustalone, mogą rozpoczynać się od dowolnego ciągu cyfr $|c1,c2,...,cs.$

Szkic dowodu. Jeśli $|k$ jest dość duże, to $kn$ i $|(k+ 1)n$ zbyt wiele się nie różnią (względnie), gdyż iloraz $| k+1n n k$ staje się dowolnie bliski 1, zatem z czasem różnica jest mniejsza niż różnica między elementami ciągu geometrycznego o dowolnie małym ilorazie większym od 1. Teraz logarytmując, otrzymamy "królika", który robi skoki o długości malejącej do 0, więc z pewnością wpadnie do naszych dziur.

Ogólniej, dowolny ciąg liczb naturalnych $(an)∞n 1,$ dla którego granica ciągu $|(an- 1)∞ an n 1$ jest równa 1 ma tę własność, że dowolny skończony ciąg cyfr stanowi początkowe cyfry w zapisie dziesiętnym pewnego wyrazu ciągu $(an)∞n 1.$ Przykładem takiego ciągu jest również ciąg kolejnych liczb pierwszych (co wynika z klasycznego, lecz wielce nieoczywistego twierdzenia o liczbach pierwszych). Zachęcam Czytelników do poszukiwania innych ciągów, których prefiksy mogą być dowolnie ustalonym ciągiem cyfr.