Przeskocz do treści

Delta mi!

Loading

Kongruencje z królikiem

Robert Kwieciński

o artykule ...

  • Publikacja w Delcie: styczeń 2017
  • Publikacja elektroniczna: 30 grudnia 2016
  • Autor: Robert Kwieciński
    Afiliacja: Student, Wydział Matematyki i Informatyki, Uniwersytet Adama Mickiewicza

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ą.

obrazek

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.


obrazek

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.