Dołącz do czytelników
Brak wyników

Koło matematyczne

15 maja 2019

NR 38 (Maj 2019)

„Chińskie mutanty” liczb złożonych

0 55

Od końca ubiegłego roku moje artykuły w ramach „Koła”1–3 nieprzerwanie dotyczą pewnego starego zadania, pochodzącego z niegdysiejszego „Konkursu zadaniowego”, dziś już, niestety, nieistniejącego działu „Matematyki”. Zadanie to miało swój niezaprzeczalny urok, któremu sam uległem i w efekcie odkryłem najpierw dla siebie, a potem we wspomnianych wyżej artykułach także dla Czytelników (mam nadzieję) jego bogate tło teoretyczne.

W ostatnim z tych artykułów wstępnie omówiłem związki pewnego (prostszego) wariantu tego zadania z „bardzo klasycznym” twierdzeniem elementarnej arytmetyki (teorii liczb), tzw. Chińskim Twierdzeniem o Resztach. Dziś dokończę to omówienie i zaprzestanę w ten sposób, przynajmniej na jakiś czas, „męczenia” Czytelników tym zadaniem.

Dla krótkiego przypomnienia: urok wspomnianego zadania polegał na tym, że było ono stare – pochodziło z 1958 r.; miało „wielkiego” autora: – był nim prof. W. Sierpiński; miało „okrągły” numer – 1000; a jego treść była zwodniczo prosta – patrz niżej; ponadto bardzo długo pozostawało nierozwiązane. Rzeczywiście, jego rozwiązanie pojawiło się dopiero w 2007 r.4

I w końcu „wisienka na torcie” – rozwiązanie to było bardzo „nowoczesne”: zostało uzyskane z użyciem komputera. Ten fakt nie tylko dodawał temu zadaniu pewnego powabu nowoczesności, ale również kazał mi zapytać, czy rozwiązanie go bez użycia komputera, na bazie jakiejś teorii, jest w ogóle możliwe. Stąd wzięły się prostsze warianty tego zadania, które kolejno przedstawiałem i omawiałem w kilku wcześniejszych odcinkach „Koła”. Przy okazji można tu zauważyć, że nie jestem jedynym, który formułował jakieś uproszczone, aczkolwiek odmienne jego warianty5, 6.

Nie będę tu streszczał całości moich dotychczasowych rozważań (te można znaleźć w poprzednich artykułach1–3), ale dla ułatwienia Czytelnikowi lektury ponownie przytoczę treść samego zadania i jego prostszych, sformułowanych przez mnie wariantów. Tak więc zadanie, które nieustannie jest przedmiotem moich obecnych rozważań, w swoim pierwotnym sformułowaniu brzmiało następująco:

1000. Liczba złożona. Znaleźć liczbę złożoną, która pozostaje złożoną przy każdej zmianie którychkolwiek dwóch jej cyfr.

Niestety, jak wydaje się pokazywać to artykuł Jarnickiego i Żenczykowskiego4, w tej postaci zadanie to okazuje się być bardzo trudne do jakiegoś „teoretycznego” rozwiązania. W istocie jest ono zapewne za trudne do takiego (tzn. teoretycznego) rozwiązania go przez uczniów, nawet tych uzdolnionych matematycznie, np. olimpijczyków. Dlatego zaproponowałem zastąpienie powyższego oryginału zbiorem jego „uproszczonych analogonów” (definicję „analogonu” można znaleźć w literaturze7), w którym zmniejsza się liczbę cyfr podlegających zmianie do jednej, ale dopuszcza się podstawy zapisu cyfrowego odmienne od 103:

Liczba złożona (p, 1). Znaleźć liczbę złożoną, która pozostanie złożoną przy każdej zmianie którejkolwiek jej pojedynczej cyfry w zapisie przy podstawie p.

Okazuje się, że tak sformułowane zadanie jest dość łatwe do rozwiązania „teoretycznego”. Istotnie, szukamy liczby, która jest „bardzo” złożona, przy czym chcemy, żeby owa złożoność jakoś odzwierciedlała się w jej zapisie cyfrowym. Najprostszy pomysł sugeruje, by wyjść od liczby, której zapis przy zadanej podstawie p kończył się zerem, tzn. od liczby podzielnej przez p. 

Wtedy zmiany każdej cyfry innej niż ostatnia zachowują końcowe zero i poza kilkoma „zdegenerowanymi” przypadkami liczby n (np. gdy tylko jedna cyfra zapisu n jest różna od zera) otrzymana po takiej zmianie liczba również będzie podzielna przez p, a więc na ogół złożona.

Jedynym problemem, który będzie należało rozwiązać w przypadku liczby n podzielnej przez p, będzie więc zagwarantowanie, że również liczby powstałe z n przez zastąpienie jej ostatniej cyfry, a więc przez zastąpienie zera dowolną inną cyfrą zapisu o podstawie p, są złożone.

Zauważmy, że w istocie chodzi tu o liczby n + 1, n + 2, …, n + (p − 2), n + (p  – 1). Ponieważ niewiele wiemy tak o n, jak i o p, więc najprostszy pomysł na zapewnienie złożoności wszystkich liczb postaci n + i, i = 1, 2, …, p – 1 polegałby na zagwarantowaniu, że i dzieli n + i, tzn. i | n + i, i = 1, 2, …, p – 1. Oczywiście, w konsekwencji oznacza to, że n musi być podzielne przez każde i = 2, 3, …, p − 1. Ponadto początkowy wybór n polegał na tym, że liczba ta miała być podzielna również przez p. Tak więc chcemy, by n było takie, że i | n, i = 2, 3, …, p. A ponieważ cały czas staramy się operować możliwie prostymi środkami, zatem wybór n nie powinien obecnie przedstawiać większych trudności – bierzemy n = 2 ∙ 3 · …· (p – 1) · p = p!, tzn. zaczynamy od liczby n będącej silnią liczby p.

Rzeczywiście, przy takim wyborze n mamy p | n, 2 | n + 2, 3 | n + 3, …, (p – 1) | n + (p – 1). Zatem, o ile tylko p > 2, to wszystkie te liczby są złożone, tak jak tego chcieliśmy. Jednak, niestety, to za mało. Istotnie, w powyższym ciągu liczb złożonych brakuje liczby n + 1, a warunki zadania wymagają, aby i ta liczba była złożona.
Czytelnicy dobrze znający (elementarną) teorię liczb powinni w tym momencie przypomnieć sobie, że istnieje twierdzenie, które w zasadzie gwarantuje złożoność liczb postaci p! + 1. Chodzi o następujące twierdzenie, znane jako twierdzenie Wilsona8:
 

TWIERDZENIE (WILSONA)

Jeśli liczba p + 1 jest pierwsza, to (p + 1) | p! + 1..


Oczywiście, jest to tylko twierdzenie o podzielności p! + 1 przez p + 1, skąd niekoniecznie wynika złożoność p! + 1. Na przykład dla p = 2 mówi ono tylko, że (2 + 1) | 2! + 1, tzn. że 3 | 3, co jest oczywiście prawdą, mimo że 2! + 1 = 3 nie jest liczbą złożoną. Cóż, doznaliśmy pewnego niepowodzenia, albowiem twierdzenie Wilsona nie gwarantuje nam, że przy każdym p ciąg liczb p!, p! + 1, p! + 2, …, p! + (p – 2), p! + (p – 1) składa się wyłącznie...

Pozostałe 70% treści dostępne jest tylko dla Prenumeratorów.

Co zyskasz, kupując prenumeratę?
  • 6 wydań czasopisma "Matematyka"
  • Dostęp do wszystkich archiwalnych artykułów w wersji online
  • Możliwość pobrania materiałów dodatkowych, testów i zadań
  • ...i wiele więcej!
Sprawdź

Przypisy