Małe twierdzenie Fermata

Bob odkrył coś ciekawego, robiąc kolorowe kolczyki z koralików do swojego sklepu. Klientki lubią odmianę, Bob postanawia więc zrobić każdy możliwy styl w każdym rozmiarze. Zaczyna od rozmiaru 3. Najpierw wymyśla wszystkie możliwe style. Każdy kolczyk zaczyna się jako ciąg koralików. Potem zbliża się końcówki, tworząc kółko. Po pierwsze: ile jest możliwych ciągów? Przy dwóch kolorach i trzech koralikach, są 3 możliwości wyboru, każda z dwóch kolorów. Dwa razy dwa razy dwa… to osiem możliwych odrębnych ciągów. Potem Bob odejmuje ciągi mające tylko jeden kolor. Jednokolorowe. Robi tylko wielokolorowe kolczyki. Później skleja ciągi w kółka. Sądził, że na końcu będzie miał 6 różnych kolczyków, ale coś się stało. Nie może odróżnić większości z nich. Okazuje się, że ma tylko dwa style, bo każdy styl należy teraz do jednej grupy z dwoma identycznymi kolczykami. Zawsze możecie je dopasować, obracając. Wielkość tych grup musi zależeć od tego, ilu trzeba obrotów, by wrócić do oryginału. Albo ilu trzeba obrotów, żeby zakończyć cykl. To znaczy, że 1. zestaw wszystkich wielokolorowych ciągów dzieli się równo na grupy rozmiaru 3. Czy to okaże się prawdą także dla innych rozmiarów? To by było wygodne, ponieważ Bob chce tyle samo w każdym stylu. Próbuje z czterema koralikami. Najpierw układa wszystkie możliwe ciągi. Koraliki są cztery. Dla każdego - wybiera z dwóch kolorów. 2 razy 2 razy 2 razy 2 to 16. Bob usuwa dwa jednokolorowe ciągi, a pozostałe łączy w kółka. Czy stworzą grupy tej samej wielkości? Wygląda na to, że nie. Co się stało? Zauważcie, jak pierwszy zestaw ciągów dzieli się na style. Gdy ciągi są w tym samym stylu, można przerobić jeden na drugi, chwytając koraliki z jednego końca i przyklejając je do końca drugiego. Jeden styl ma tylko dwa zestawy, bo jest zbudowany z powtarzającej się jednostki długości 2. Tylko dwa obroty są potrzebne do ukończenia cyklu. Dlatego ta grupa zawiera tylko 2 elementy. Bob nie może ich podzielić. Co z rozmiarem 5? Czy sznurki podzielą się równo między style? Zaraz. Nagle Bob zdaje sobie sprawę: nie musi ich budować, by się o tym przekonać. To musi działać, bo pięciu nie zrobi się z powtarzalnego wzoru. Bo pięciu nie podzieli się na równe części. To liczba pierwsza. Niezależnie, z jakim rodzajem kolorowego ciągu zaczynacie, zawsze trzeba będzie pięciu obrotów, czy zamian koralików, by wrócić do stanu pierwotnego. Długość cyklu każdego ciągu musi wynosić 5. Sprawdźmy. Najpierw zrobimy wszystkie możliwe ciągi i usuniemy dwa jednokolorowe. Potem podzielimy ciągi na grupy należące do tego samego stylu i zrobimy jeden kolczyk dla każdego stylu. Każdy kolczyk obraca się dokładnie 5 razy, by ukończyć cykl. Gdybyśmy więc skleili wszystkie ciągi w kółka, muszą się podzielić na równe grupy po 5. Bob idzie o krok dalej. Teraz używa tylko dwóch kolorów, ale uświadamia sobie, że to musi działać przy dowolnej ich liczbie. Bo każdy wielokolorowy kolczyk z liczbą pierwszą koralików, p, musi mieć długość cyklu p, bo liczb pierwszych nie da się podzielić na równe części. Jednak przy użyciu złożonej liczby koralików, np. 6, zawsze zdarzą się ciągi o krótszym cyklu, bo są zbudowane z powtarzających się segmentów. Utworzą więc mniejsze grupy. Zdumiewające: natknął się na Małe Twierdzenie Fermata. Mając a kolorów i chcąc z nich utworzyć ciągi o długości p (liczba pierwsza), uzyskujemy, że liczba możliwych ciągów to a razy a razy a… p razy, czyli a do potęgi p. A kiedy usuwa jednokolorowe ciągi, to jest ich dokładnie a. Jeden dla każdego koloru. To pozostawia mu a do potęgi p minus a ciągów. A gdy skleja te ciągi, podzielą się na grupy wielkości p, bo każdy kolczyk musi mieć cykl długości p. Dlatego p dzieli a do potęgi p minus a. I już. Możemy wyrazić to również w arytmetyce modułowej. Pomyślcie: jeśli dzielicie a do potęgi p przez p, to zostanie wam reszta a. Możemy to zapisać jako: a do potęgi p jest przystające do a mod p. Natknęliśmy się na jeden z podstawowych wzorów w teorii liczb, po prostu bawiąc się koralikami.