Gaussa teoria liczb - kongruencja, czyli przystawanie

Next: "Nie samą matematyką ..." Up: Carl Friedrich Gauss Previous: Carl Friedrich Gauss

Gaussa teoria liczb - kongruencja, czyli przystawanie

,,Matematyka to królowa nauk, a teoria liczb to królowa Matematyki''.

Jeżeli nawet Gauss nie był autorem tego powiedzenia, to było ono z pewnością mottem numer 1. (były i inne) jego twórczego życia. Teoria liczb fascynowała i fascynuje matematyków od najdawniejszych czasów. Mistyczne skojarzenia Pitagorejczyków, zażarte poszukiwania liczb doskonałych (ojciec Mersenne), małe i wielkie twierdzenie Fermat'a - to tylko kilka z nieprzebranej różnorodności problemów. teoria liczb jest na swój sposób łatwa i trudna: łatwa, bo można do niej ,,wystartować'' bez specjalnego przygotowanie formalnego, trudna - bo niektóre oczywiste (?) przypuszczenia opierają się przez setki lat rygorystycznym dowodom. Niekiedy rzeczy ,,trudne'' stają się dziecinnie łatwe - jeżeli tylko pojawi się sprytna metoda uwidaczniania (i udowadniania) pewnych własności. Taką metodą jest właśnie teoria kongruencji, albo przystawania liczb. Nie jest ona wyłącznie dziełem Gaussa, ale została przez niego dopracowana, skodyfikowana i ...wykorzystana do rozstrzygnięcia wielu pytań związanych z podzielnością liczb.

Definicja:
Niech n będzie dodatnią liczbą całkowitą, natomiast a i b - dowolnymi liczbami (całkowitymi - rozmawiamy wyłącznie o liczbach całkowitych). Liczby a i b nazywamy przystającymi (kongruentnymi) modulo n i piszemy

$\begin{displaymath}a \equiv b \mbox{\rm (mod } n), \end{displaymath}$

jeżeli różnica a - b jest podzielna przez n:

$\begin{displaymath}a - b = kn, \;\;\; (k \mbox{\rm -- całkowite}).\end{displaymath}$

Na przykład:

$\begin{displaymath}3 \equiv 23 \mbox{\rm (mod } 7); \;\;\; -31 \equiv 11 \mbox{\rm (mod } 7);\;\;\; -15 \equiv -64 \mbox{\rm (mod } 7), \end{displaymath}$

bo mamy:

$\begin{displaymath}3 -24 = 21 = 3\cdot 7; \;\;\; -31-11 = -42 = -6\cdot 7; \;\;\; -15-(-64) = 49 = 7\cdot 7. \end{displaymath}$

Analogicznie, możemy mówić o liczbach, które nie są przystające modulo n i pisać

$\begin{displaymath}a \not\equiv b \mbox{\rm (mod } n).\end{displaymath}$

Na przykład: $25\not\equiv 12 \mbox{\rm (mod } 7)$ , bo 25-12 = 13 - liczbie, która nie jest podzielna przez 7. Z definicji natychmiast wynika oczywiste twierdzenie: warunkiem koniecznym i wystarczającym aby $a \equiv b \mbox{\rm (mod } n)$ jest aby reszty z dzielenia a i b przez n były równe. Dowód (w obie strony )jest banalnie prosty. Ale i tak zachęcam do spróbowania. Na przykład:

$\begin{eqnarray*}-56 & \equiv & -11 \mbox{\rm (mod } 9) \rightarrow \\ -56 & = & (-7)\cdot 9 + 7 \\ -11 & = & (-2)\cdot 9 + 7 \end{eqnarray*}$

- reszta w obu przypadkach wynosi 7. Kongruencja albo (po polsku) przystawanie liczb całkowitych okazuje się mieć podobne własności w stosunku do operacji dodawania, mnożenia i potęgowania jak zwykła relacja równości. Podstawowe własności kongruencji to:

1.: $a \equiv a \mbox{\rm (mod } n)$ ;
2.: $a \equiv b \mbox{\rm (mod } n) \rightarrow b \equiv a \mbox{\rm (mod } n)$
3.: $\{ a \equiv b \mbox{\rm (mod } n) \mbox{\rm i } b \equiv c \mbox{\rm (mod } n)\} \rightarrow a \equiv c \mbox{\rm (mod } n)$ ;
4.: $\{ a \equiv b \mbox{\rm (mod } n) \mbox{\rm i } c \equiv d \mbox{\rm (mod } n)\}$
$\rightarrow a + c \equiv b+ d \mbox{\rm (mod } n) \mbox{\rm oraz } a \cdot c \equiv b\cdot d \mbox{\rm (mod } n)$
5.: $a \equiv b \mbox{\rm (mod } n) \rightarrow \{ a + c \equiv b+ c \mbox{\rm (mod } n) \mbox{\rm oraz } a \cdot c \equiv b\cdot c \mbox{\rm (mod } n) \}$ ;
6.: $a \equiv b \mbox{\rm (mod } n) \rightarrow a^k \equiv b^k \mbox{\rm (mod } n)$

I znowu dowody powyższych własności są bardzo proste. Jeżeli chcesz się naprawdę nacieszyć następnymi przykładami i zadaniami to radzę - udowodnij sam(a). Jeżeli jesteś leniuszek, to - proszę - choć, prawdę mówiąc, efekt z oglądania dowodów będzie mizerniutki.

Jean Pierre Fermat miał pomysł (jeden z wielu !), że wszystkie liczby o postaci 2^{2^k} +1 są liczbami pierwszymi (pamiętasz, dla liczb p naprawdę pierwszych o tej postaci, Gauss udowodnił możliwość ,,Euklidesowej'' konstrukcji regularnego p-kąta). Dla k=0,1,2,3 i 4 wszystko jest OK, ale już Euler (ca. 1735) zauważył, że 2^2⁵ +1 dzieli się przez 641. Wykazanie tego, korzystając z kongruencji, jest szybkie, łatwe i przyjemne. W języku ,,przystawania'' mamy wykazać, że:

$\begin{displaymath}2^{2^5} +1 = 2^{32} +1 \equiv 0 \mbox{\rm (mod } 641) .\end{displaymath}$

W tym celu musimy w liczbie 641 doszukać się podobnej struktury, jak w 2³² + 1. Dość oczywisty pomysł (ważne są potęgi dwójki!), to:

$\begin{displaymath}641 = 640 +1 = 5\cdot 128 +1 = 5\cdot 2^7 + 1.\end{displaymath}$

A więc

$\begin{displaymath}5\cdot 2^7 \equiv -1 \mbox{\rm (mod } 641).\end{displaymath}$

Wykorzystajmy teraz własność (6) - k=4:

$\begin{displaymath}5^4\cdot (2^7)^4 \equiv (-1)^4 \mbox{\rm (mod } 641) \mbox{\rm albo}\end{displaymath}$

$\begin{displaymath}5^4\cdot 2^{28} \equiv 1 \mbox{\rm (mod } 641).\end{displaymath}$

W naszej 2^2⁵ +1 mamy jednak tylko potęgę (32-gą) dwójki, a nie uświadczysz w niej potęgi piątki. Musimy znaleźć jakąś kongruencją (modulo 641) która zachodzi między potęgami dwójki i piątki. Każdy widzi, że 5⁴ to 625, które odległe jest od 641 o 16 = 2⁴. Jesteśmy w domu:

$\begin{displaymath}5^4 \equiv -16 = -(2^4)\mbox{\rm (mod } 641).\end{displaymath}$

I już możemy wykazać, że nie jest możliwa euklidesowa konstrukcja 2^2⁵ +1-kąta foremnego:

$\begin{displaymath}2^{32} +1 = 2^{4}\cdot 2^{28} +1 \equiv -(5^4)\cdot 2^{28} +1 \equiv -1 + 1 = 0 \mbox{\rm (modulo } 641). \end{displaymath}$

Sympatyczna liczba Mersenne'a 2⁸³ - 1 (postulowana przez swojego patrona jako kandydatka na liczbę pierwszą) dzieli się przez 167 (to też pokazał Euler). Tutaj dwójka występuję w potędze przeszło dwa i pół raza większej niż w poprzednim przykładzie. To nic, trzeba pobawić się w podnoszenie do kwadratu i szukać partnerów kongruentnych (modulo 167) dla kolejnych potęg:

$\begin{eqnarray*}2^8 & = & 256 \equiv 89 \mbox{\rm (mod } 167), \\ 2^{16} & \e... ...\\ 2^{64} & \equiv & 7^2 = 49 \equiv 7 \mbox{\rm (mod } 167) \end{eqnarray*}$

Teraz tylko pozostało inteligentne rozpisanie 83-ej potęgi dwójki. 83 = 16 + 67. A 67 nie jest dalekie od 64:

$\begin{displaymath}2^{67} = 2^3\cdot 2^{64} \equiv 8\cdot 49\mbox{\rm (mod } 167) = 392 \mbox{\rm (mod } 167) \equiv 58 \mbox{\rm (mod } 167).\end{displaymath}$

Jesteśmy w domu:

$\begin{displaymath}2^{83} - 1 = 2^{67}\cdot 2^{16} - 1 \equiv 58\cdot 72 \mbox{\... ...od } 167) -1 = 4167 -1 = 4166 \equiv 0 \mbox{\rm (mod } 167).\end{displaymath}$

Quod erat demonstrandum.

Podoba się? No to, do roboty. Kilka nie za trudnych i sympatycznych problemików:

Udowodnij:

a² $\textstyle \equiv$ $\displaystyle 0 \mbox{\rm lub } 1 \mbox{\rm (mod 3)}$ (2)

a³ $\textstyle \equiv$ $\displaystyle 0 \mbox{\rm lub } 1 \mbox{\rm lub } -1 \mbox{\rm (mod 7)}$ (3)

a⁴ $\textstyle \equiv$ $\displaystyle 0 \mbox{\rm lub } 1 \mbox{\rm (mod 5)}$ (4)
Czy 5³⁶ -1 dzieli się przez 13? A 10⁴⁹ + 5³ przez 7?
Jaką resztę otrzymasz z dzielenia sumy:

$\begin{displaymath}1! + 2! + 3! + 4! + \ldots + 100! \end{displaymath}$

przez 12? (Na wszelki przypadek, pozwalam sobie zauważyć, że 12 to 4!)

Nie podaję rozwiązań. Ale zawsze służę (p)odpowiedzią, jeżeli ktoś ładnie poprosi. Miłego przystawania do teorii liczb!

Next: "Nie samą matematyką ..." Up: Carl Friedrich Gauss Previous: Carl Friedrich Gauss

Andrzej Lenda
1999-06-15

a²	$\textstyle \equiv$	$\displaystyle 0 \mbox{\rm lub } 1 \mbox{\rm (mod 3)}$	(2)
a³	$\textstyle \equiv$	$\displaystyle 0 \mbox{\rm lub } 1 \mbox{\rm lub } -1 \mbox{\rm (mod 7)}$	(3)
a⁴	$\textstyle \equiv$	$\displaystyle 0 \mbox{\rm lub } 1 \mbox{\rm (mod 5)}$	(4)