Teoria liczb

Cechy podzielności, liczby pierwsze, NWD i NWW — wzory i przykłady

Cechy podzielności przez 2–11 i 25 z uzasadnieniem, liczby pierwsze do 100, sito Eratostenesa, rozkład na czynniki, NWD, NWW, Euklides i 10 przykładów.

Cechy podzielności, liczby pierwsze, NWD i NWW to fundament szkolnej teorii liczb: od zadań o płytkach i autobusach na egzaminie ósmoklasisty, przez skracanie ułamków i wspólny mianownik, po dowody podzielności na maturze. Po tej lekcji będziesz w pamięci sprawdzać, czy liczba dzieli się przez 3, 4, 8, 9 albo 11, i będziesz rozumieć, dlaczego te reguły działają. Nauczysz się rozpoznawać liczby pierwsze, rozkładać liczby na czynniki pierwsze, obliczać największy wspólny dzielnik i najmniejszą wspólną wielokrotność dwoma sposobami (z rozkładu i algorytmem Euklidesa) oraz rozwiązywać typowe zadania tekstowe. Na maturze podstawowej te umiejętności wracają w zadaniach zamkniętych o resztach i podzielności oraz w krótkich dowodach typu „wykaż, że liczba … jest podzielna przez 6”, a na rozszerzeniu — w zadaniach z resztami i parametrem całkowitym. Dziesięć przykładów krok po kroku prowadzi od poziomu szkoły podstawowej do poziomu rozszerzonego.

Dzielnik, wielokrotność i reszta z dzielenia

Liczba całkowita \(a\) jest podzielna przez liczbę całkowitą \(d \neq 0\), jeśli istnieje liczba całkowita \(k\) taka, że \(a = d \cdot k\). Mówimy wtedy, że \(d\) jest dzielnikiem liczby \(a\), a \(a\) jest wielokrotnością liczby \(d\), i zapisujemy \(d \mid a\) (czytaj: „\(d\) dzieli \(a\)”). Na przykład \(6 \mid 42\), bo \(42 = 6 \cdot 7\), ale \(6 \nmid 45\).

Przykład: \(100 = 7 \cdot 14 + 2\), więc liczba 100 daje przy dzieleniu przez 7 resztę 2. Dla liczb ujemnych reszta też musi być nieujemna: \(-100 = 7 \cdot (-15) + 5\), czyli reszta wynosi 5, a nie \(-2\).

Kilka własności, z których korzysta się bez przerwy:

  • jeśli \(d \mid a\) i \(d \mid b\), to \(d \mid a + b\), \(d \mid a - b\) oraz \(d \mid k \cdot a\) dla każdej liczby całkowitej \(k\);
  • jeśli \(d \mid a\) i \(a \mid b\), to \(d \mid b\);
  • każda liczba dzieli się przez 1 i przez samą siebie, a zero dzieli się przez każdą liczbę różną od zera.

Pierwsza własność ma ważny wniosek: wspólny dzielnik dwóch liczb dzieli też ich różnicę. Dwie kolejne liczby naturalne \(n\) i \(n + 1\) różnią się o 1, więc ich jedynym wspólnym dzielnikiem naturalnym jest 1.

Cechy podzielności przez 2, 3, 4, 5, 6, 8, 9, 10, 11 i 25

Cecha podzielności to reguła, która pozwala rozstrzygnąć podzielność bez wykonywania dzielenia — tylko na podstawie cyfr. Wszystkie cechy wynikają z zapisu dziesiętnego: liczba 4725 to \(4 \cdot 1000 + 7 \cdot 100 + 2 \cdot 10 + 5\).

Cechy, które patrzą na końcówkę liczby

  • przez 2 — ostatnia cyfra jest parzysta: 0, 2, 4, 6 lub 8;
  • przez 5 — ostatnia cyfra to 0 lub 5;
  • przez 10 — ostatnia cyfra to 0;
  • przez 4 — liczba utworzona z dwóch ostatnich cyfr dzieli się przez 4 (np. 7316, bo \(16 = 4 \cdot 4\));
  • przez 25 — dwie ostatnie cyfry to 00, 25, 50 lub 75;
  • przez 8 — liczba utworzona z trzech ostatnich cyfr dzieli się przez 8 (np. 53 128, bo \(128 = 8 \cdot 16\)).

Skąd to się bierze? Liczbę zawsze można rozbić na „wszystko oprócz końcówki” i samą końcówkę. Przy cechach przez 2, 5 i 10 odcinamy ostatnią cyfrę: \(4725 = 472 \cdot 10 + 5\), a 10 dzieli się przez 2, 5 i 10, więc o podzielności decyduje tylko końcówka. Przy cechach przez 4 i 25 odcinamy dwie cyfry: \(7316 = 73 \cdot 100 + 16\), a \(100 = 4 \cdot 25\). Przy cesze przez 8 odcinamy trzy cyfry, bo \(1000 = 8 \cdot 125\).

Cecha podzielności przez 3 i przez 9 — suma cyfr

Dlaczego? Każda potęga dziesiątki to wielokrotność dziewiątki powiększona o jeden: \(10 = 9 + 1\), \(100 = 99 + 1\), \(1000 = 999 + 1\). Zatem

\[ 4725 = 4 \cdot 999 + 7 \cdot 99 + 2 \cdot 9 + (4 + 7 + 2 + 5). \]

Pierwsze trzy składniki dzielą się przez 9, a więc także przez 3. Liczba 4725 daje zatem przy dzieleniu przez 9 tę samą resztę co suma cyfr \(4 + 7 + 2 + 5 = 18\), czyli resztę 0. Rzeczywiście \(4725 = 9 \cdot 525\). Przy okazji dostajemy więcej niż samą cechę: liczba i jej suma cyfr dają tę samą resztę z dzielenia przez 9 i przez 3. Ta obserwacja przydaje się w zadaniach o resztach.

Cecha podzielności przez 11 — naprzemienna suma cyfr

Uzasadnienie jest podobne jak przy dziewiątce, tylko teraz potęgi dziesiątki są na przemian o jeden mniejsze i o jeden większe od wielokrotności 11: \(10 = 11 - 1\), \(100 = 99 + 1\), \(1000 = 1001 - 1\), \(10\,000 = 9999 + 1\), przy czym \(99 = 11 \cdot 9\), \(1001 = 11 \cdot 91\) i \(9999 = 11 \cdot 909\). Dla liczby 8547:

\[ 8547 = 8(1001 - 1) + 5(99 + 1) + 4(11 - 1) + 7 = 11(8 \cdot 91 + 5 \cdot 9 + 4) + (7 - 4 + 5 - 8). \]

Naprzemienna suma \(7 - 4 + 5 - 8 = 0\) dzieli się przez 11, więc \(11 \mid 8547\); faktycznie \(8547 = 11 \cdot 777\). Drugi przykład: dla liczby 918 082 mamy \(2 - 8 + 0 - 8 + 1 - 9 = -22\), więc ona też dzieli się przez 11.

Cechy złożone: przez 6, 12, 15, 18

Przez 6 dzieli się liczba, która dzieli się jednocześnie przez 2 i przez 3. Podobnie: przez 12 — przez 3 i przez 4, przez 15 — przez 3 i przez 5, przez 18 — przez 2 i przez 9. Działa to tylko dlatego, że w każdej parze liczby są względnie pierwsze, czyli nie mają wspólnego dzielnika większego niż 1. Para 4 i 6 nie nadaje się do sprawdzania podzielności przez 24: liczba 12 dzieli się przez 4 i przez 6, ale nie przez 24. Przez 24 sprawdzaj cechy przez 3 i przez 8. Z tych samych cech skorzystasz, szukając największej liczby pięciocyfrowej podzielnej przez daną liczbę.

Liczby pierwsze i złożone

Z definicji wynikają fakty, o które często pytają testy:

  • 1 nie jest ani liczbą pierwszą, ani złożoną — ma tylko jeden dzielnik naturalny;
  • 0 również nie jest ani pierwsze, ani złożone;
  • 2 jest jedyną parzystą liczbą pierwszą — każda większa liczba parzysta ma co najmniej trzy dzielniki: 1, 2 i samą siebie;
  • każdą liczbę złożoną da się zapisać jako iloczyn dwóch liczb naturalnych większych od 1, np. \(91 = 7 \cdot 13\).

Liczby pierwsze mniejsze od 100

Jest ich dokładnie 25:

\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71,\ 73,\ 79,\ 83,\ 89,\ 97 \]

Warto znać na pamięć przynajmniej te do 50. Liczby, które tylko wyglądają na pierwsze: \(51 = 3 \cdot 17\), \(57 = 3 \cdot 19\), \(87 = 3 \cdot 29\), \(91 = 7 \cdot 13\).

Sito Eratostenesa

Najprostszą metodę wypisania wszystkich liczb pierwszych do ustalonej granicy opisał Eratostenes z Cyreny ponad dwa tysiące lat temu. Dla liczb od 1 do 100 wygląda ona tak:

  1. Skreśl 1, bo nie jest liczbą pierwszą.
  2. Zostaw 2 i skreśl wszystkie dalsze wielokrotności dwójki: 4, 6, 8, …
  3. Pierwsza nieskreślona liczba to 3. Zostaw ją i skreśl jej dalsze wielokrotności: 6, 9, 12, … (część jest już skreślona).
  4. Następne nieskreślone liczby to 5 i 7 — z każdą postępuj tak samo.
  5. Wszystkie liczby, które zostały, są pierwsze.

Dlaczego można skończyć na siódemce? Każda liczba złożona nie większa niż 100 ma dzielnik pierwszy nie większy niż \(\sqrt{100} = 10\), czyli 2, 3, 5 albo 7 (uzasadnienie za chwilę). Najmniejsza liczba złożona, której wszystkie dzielniki pierwsze są większe od 7, to \(11 \cdot 11 = 121\) — leży już poza zakresem.

Sito Eratostenesa dla liczb od 1 do 100: 25 liczb pierwszych wyróżnionych, pozostałe skreślone123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100skreślamy wielokrotności 2, 3, 5, 7 — zostaje 25 liczb pierwszych
Sito Eratostenesa: po skreśleniu jedynki i wielokrotności liczb \(2, 3, 5, 7\) zostaje 25 liczb pierwszych mniejszych od 100

Jak sprawdzić, czy liczba jest pierwsza

Uzasadnienie: jeśli \(n = a \cdot b\) i \(1 < a \leq b\), to \(a^2 \leq a \cdot b = n\), czyli \(a \leq \sqrt{n}\). Liczba złożona ma więc zawsze dzielnik większy od 1 i nie większy niż jej pierwiastek, a najmniejszy dzielnik pierwszy tego dzielnika też spełnia ten warunek. Dla liczby 211 wystarczy sprawdzić 2, 3, 5, 7, 11 i 13, bo \(13^2 = 169 < 211 < 289 = 17^2\). Żadna z nich nie dzieli 211 (reszty z dzielenia przez 7, 11 i 13 to 1, 2 i 3), więc 211 jest liczbą pierwszą. Sprawdzanie aż do \(\frac{n}{2}\) nie jest błędem, ale to strata czasu.

Liczb pierwszych jest nieskończenie wiele

To twierdzenie udowodnił Euklides i jest to wzorcowy dowód nie wprost, którego pomysł wraca w zadaniach olimpijskich. Przypuśćmy, że liczb pierwszych jest skończenie wiele: \(p_1, p_2, \ldots, p_k\). Rozważmy liczbę \(N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1\). Jest ona większa od 1, więc ma jakiś dzielnik pierwszy \(p\), a ten musi być jedną z liczb \(p_1, \ldots, p_k\). Wtedy \(p\) dzieli zarówno iloczyn \(p_1 \cdot \ldots \cdot p_k\), jak i \(N\), więc dzieli ich różnicę, czyli 1 — sprzeczność. Uwaga: sama liczba \(N\) nie musi być pierwsza. Na przykład \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30\,031 = 59 \cdot 509\). Dowód mówi tylko, że dzielniki pierwsze liczby \(N\) są spoza listy.

Rozkład liczby na czynniki pierwsze

W praktyce rozkład wykonuje się na dwa sposoby. Dzieleniem: dzielisz liczbę przez najmniejszą liczbę pierwszą, która ją dzieli, wynik znów przez najmniejszą możliwą i tak dalej, aż dojdziesz do 1. Dla 360: \(360 : 2 = 180\), \(180 : 2 = 90\), \(90 : 2 = 45\), \(45 : 3 = 15\), \(15 : 3 = 5\), \(5 : 5 = 1\), więc

\[ 360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^3 \cdot 3^2 \cdot 5. \]

Drzewkiem: rozbijasz liczbę na dowolny iloczyn dwóch czynników, potem każdy czynnik złożony dalej, aż na końcach gałęzi zostaną same liczby pierwsze. Kolejność rozbijania nie ma znaczenia — dzięki jednoznaczności rozkładu zawsze dostaniesz ten sam zestaw czynników.

Drzewko rozkładu liczby 360 na czynniki pierwsze: 360 = 2 do potęgi 3 razy 3 do kwadratu razy 5236236362510360360 = 2 · 2 · 2 · 3 · 3 · 5 = 2³ · 3² · 5
Drzewko rozkładu: \(360 = 36 \cdot 10\), dalej aż do liczb pierwszych; liście dają \(360 = 2^3 \cdot 3^2 \cdot 5\)

Rozkład od razu mówi, ile liczba ma dzielników. Każdy dzielnik liczby 360 ma postać \(2^a \cdot 3^b \cdot 5^c\), gdzie \(a \in \{0, 1, 2, 3\}\), \(b \in \{0, 1, 2\}\), \(c \in \{0, 1\}\). Wykładniki wybieramy niezależnie, więc dzielników jest \((3 + 1)(2 + 1)(1 + 1) = 24\).

Rozkład szybko rozstrzyga też, czy liczba jest kwadratem liczby naturalnej: tak jest dokładnie wtedy, gdy wszystkie wykładniki w rozkładzie są parzyste, np. \(3600 = 2^4 \cdot 3^2 \cdot 5^2 = 60^2\).

Największy wspólny dzielnik (NWD)

Największy wspólny dzielnik liczb naturalnych \(a\) i \(b\), oznaczany \(\text{NWD}(a, b)\), to największa liczba naturalna, która dzieli jednocześnie \(a\) i \(b\). Liczby, dla których \(\text{NWD}(a, b) = 1\), nazywamy względnie pierwszymi — na przykład 8 i 15, choć żadna z nich nie jest liczbą pierwszą.

NWD z rozkładu na czynniki pierwsze

Dla \(180 = 2^2 \cdot 3^2 \cdot 5\) i \(252 = 2^2 \cdot 3^2 \cdot 7\) wspólne są czynniki 2 i 3, oba w potędze 2, więc \(\text{NWD}(180, 252) = 2^2 \cdot 3^2 = 36\). Piątka i siódemka nie wchodzą do NWD, bo każda występuje tylko w jednej z liczb.

Algorytm Euklidesa

Gdy liczby są duże i trudno je rozłożyć, szybszy jest algorytm Euklidesa. Opiera się na fakcie z pierwszej sekcji: wspólny dzielnik liczb \(a\) i \(b\) dzieli też \(a - b\), a więc także resztę \(r\) z dzielenia \(a\) przez \(b\), bo \(r = a - q \cdot b\). I odwrotnie, wspólny dzielnik \(b\) i \(r\) dzieli \(a = q \cdot b + r\). Obie pary mają więc te same wspólne dzielniki, czyli

\[ \text{NWD}(a, b) = \text{NWD}(b, r). \]

Zastępujemy parę \((a, b)\) parą \((b, r)\) i powtarzamy, aż reszta wyjdzie 0. Ostatnia niezerowa reszta to szukany NWD. Dla liczb 1001 i 357:

\[ 1001 = 2 \cdot 357 + 287, \quad 357 = 1 \cdot 287 + 70, \quad 287 = 4 \cdot 70 + 7, \quad 70 = 10 \cdot 7 + 0. \]

Ostatnia niezerowa reszta to 7, więc \(\text{NWD}(1001, 357) = 7\). Sprawdzenie: \(1001 = 7 \cdot 143\) i \(357 = 7 \cdot 51\), a liczby \(143 = 11 \cdot 13\) i \(51 = 3 \cdot 17\) nie mają wspólnych dzielników większych od 1. Geometryczny sens algorytmu zobaczysz w przykładzie 4: to odcinanie z prostokąta największych możliwych kwadratów.

Najmniejsza wspólna wielokrotność (NWW)

Najmniejsza wspólna wielokrotność liczb naturalnych dodatnich \(a\) i \(b\), oznaczana \(\text{NWW}(a, b)\), to najmniejsza liczba naturalna dodatnia, która dzieli się jednocześnie przez \(a\) i przez \(b\). Dla małych liczb wystarczy wypisać wielokrotności: wielokrotności 6 to 6, 12, 18, 24, …, a wielokrotności 8 to 8, 16, 24, …, więc \(\text{NWW}(6, 8) = 24\).

NWW z rozkładu na czynniki pierwsze

Dla \(180 = 2^2 \cdot 3^2 \cdot 5\) i \(252 = 2^2 \cdot 3^2 \cdot 7\) mamy \(\text{NWW}(180, 252) = 2^2 \cdot 3^2 \cdot 5 \cdot 7 = 1260\).

Związek NWD i NWW

Skąd ten wzór? Dla każdej liczby pierwszej NWD bierze mniejszy z dwóch wykładników, a NWW — większy. Suma mniejszego i większego to po prostu suma obu wykładników, czyli dokładnie tyle, ile razy ta liczba pierwsza występuje w iloczynie \(a \cdot b\). Sprawdzenie: \(36 \cdot 1260 = 45\,360 = 180 \cdot 252\).

Wzór pozwala policzyć NWW bez rozkładu: najpierw NWD algorytmem Euklidesa, potem

\[ \text{NWW}(a, b) = \frac{a \cdot b}{\text{NWD}(a, b)}. \]

Uwaga: wzór działa tylko dla dwóch liczb. Szczególny przypadek: dla liczb względnie pierwszych NWW jest równa ich iloczynowi, np. \(\text{NWW}(8, 15) = 120\).

NWW a wspólny mianownik

Najmniejszy wspólny mianownik dwóch ułamków to NWW ich mianowników. Ponieważ \(\text{NWW}(12, 18) = 36\),

\[ \frac{5}{12} + \frac{7}{18} = \frac{15}{36} + \frac{14}{36} = \frac{29}{36}. \]

Pomnożenie mianowników (\(12 \cdot 18 = 216\)) też prowadzi do poprawnego wyniku, ale na końcu trzeba skracać. Więcej o sprawnym rachowaniu znajdziesz w lekcji o liczeniu bez kalkulatora — ułamkach, procentach i potęgach.

Przykłady rozwiązane krok po kroku

Przykład 1 (szkoła podstawowa) — brakująca cyfra

Wyznacz wszystkie cyfry \(x\), dla których liczba czterocyfrowa \(\overline{7x36}\) jest podzielna przez 12. Dla jakiej cyfry \(x\) ta liczba jest podzielna przez 11?

Rozwiązanie. \(12 = 3 \cdot 4\), a 3 i 4 są względnie pierwsze, więc sprawdzamy osobno obie cechy. Dwie ostatnie cyfry tworzą liczbę 36, a \(36 = 4 \cdot 9\) — podzielność przez 4 zachodzi dla każdego \(x\). Suma cyfr to \(7 + x + 3 + 6 = 16 + x\) i musi dzielić się przez 3. Dla cyfry \(x\) suma przyjmuje wartości od 16 do 25, a wielokrotności 3 w tym zakresie to 18, 21 i 24. Stąd \(x = 2\), \(x = 5\) lub \(x = 8\), czyli liczby 7236, 7536 i 7836.

Cecha przez 11: naprzemienna suma od prawej to \(6 - 3 + x - 7 = x - 4\). Dla cyfry \(x\) ta wartość leży między \(-4\) a \(5\), a jedyna wielokrotność 11 w tym zakresie to 0. Zatem \(x = 4\) i rzeczywiście \(7436 = 11 \cdot 676\). Ta liczba nie dzieli się jednak przez 12 (suma cyfr 20), więc żadna cyfra nie spełnia obu warunków jednocześnie.

Przykład 2 (PP) — czy liczba jest pierwsza

Rozstrzygnij, czy liczby 391 i 397 są pierwsze.

Rozwiązanie. \(19^2 = 361\) i \(20^2 = 400\), więc \(\sqrt{391}\) i \(\sqrt{397}\) leżą między 19 a 20. Wystarczy sprawdzić dzielniki pierwsze 2, 3, 5, 7, 11, 13, 17 i 19.

Liczba 391 jest nieparzysta, ma sumę cyfr 13 i nie kończy się cyfrą 0 ani 5, więc nie dzieli się przez 2, 3 ani 5. Dalej: \(391 = 7 \cdot 55 + 6\), \(391 = 11 \cdot 35 + 6\), \(391 = 13 \cdot 30 + 1\), ale \(391 = 17 \cdot 23\). Liczba 391 jest złożona. Jej najmniejszy dzielnik pierwszy, 17, wcale nie jest mały — samymi cechami podzielności przez 2, 3 i 5 tego nie wykryjesz.

Liczba 397 jest nieparzysta, ma sumę cyfr 19 i kończy się cyfrą 7. Reszty z dzielenia przez kolejne liczby pierwsze: przez 7 — 5 (\(397 = 7 \cdot 56 + 5\)), przez 11 — 1, przez 13 — 7, przez 17 — 6, przez 19 — 17. Żadna liczba pierwsza nie większa od \(\sqrt{397}\) nie dzieli 397, więc 397 jest liczbą pierwszą.

Przykład 3 (PP) — NWD i NWW z rozkładu

Oblicz \(\text{NWD}(360, 84)\) oraz \(\text{NWW}(360, 84)\).

Rozwiązanie. Rozkład 360 już znamy: \(360 = 2^3 \cdot 3^2 \cdot 5\). Dla 84: \(84 : 2 = 42\), \(42 : 2 = 21\), \(21 : 3 = 7\), więc \(84 = 2^2 \cdot 3 \cdot 7\).

  • NWD: wspólne czynniki to 2 i 3, mniejsze potęgi to \(2^2\) i \(3^1\), więc \(\text{NWD}(360, 84) = 4 \cdot 3 = 12\).
  • NWW: wszystkie czynniki 2, 3, 5, 7 w większych potęgach, więc \(\text{NWW}(360, 84) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520\).

Sprawdzenie wzorem: \(12 \cdot 2520 = 30\,240\) oraz \(360 \cdot 84 = 30\,240\). Zgadza się. Na rysunku czynniki wspólne leżą w części wspólnej kół: ich iloczyn to NWD, a iloczyn wszystkich czynników z rysunku to NWW.

Czynniki pierwsze liczb 360 i 84: wspólne 2, 2, 3 dają NWD = 12, wszystkie razem NWW = 2520360842352237NWD = 2 · 2 · 3 = 12 (część wspólna)NWW = 2 · 2 · 3 · 2 · 3 · 5 · 7 = 2520 (wszystkie czynniki)
Czynniki pierwsze liczb \(360\) i \(84\): iloczyn części wspólnej to \(\text{NWD} = 12\), iloczyn wszystkich czynników to \(\text{NWW} = 2520\)

Przykład 4 (szkoła podstawowa, PP) — płytki i algorytm Euklidesa

Podłogę w kształcie prostokąta o wymiarach 252 cm na 198 cm trzeba wyłożyć jednakowymi kwadratowymi płytkami bez docinania. Jaki największy bok mogą mieć płytki i ile płytek wtedy potrzeba?

Rozwiązanie. Bok płytki musi dzielić zarówno 252, jak i 198, a ma być jak największy — szukamy \(\text{NWD}(252, 198)\). Algorytm Euklidesa:

\[ 252 = 1 \cdot 198 + 54, \quad 198 = 3 \cdot 54 + 36, \quad 54 = 1 \cdot 36 + 18, \quad 36 = 2 \cdot 18 + 0. \]

Ostatnia niezerowa reszta to 18, więc płytki mają bok 18 cm. Wzdłuż dłuższego boku mieści się \(252 : 18 = 14\) płytek, wzdłuż krótszego \(198 : 18 = 11\), razem \(14 \cdot 11 = 154\) płytki.

Rysunek pokazuje, co geometrycznie robi algorytm. Z prostokąta \(252 \times 198\) odcinamy jeden kwadrat o boku 198, z pozostałego paska \(54 \times 198\) — trzy kwadraty o boku 54, z paska \(54 \times 36\) — jeden kwadrat o boku 36, a resztę \(18 \times 36\) wypełniają dokładnie dwa kwadraty o boku 18. Kwadrat o boku 18 mieści się całkowitą liczbę razy w każdym wcześniejszym kwadracie, więc pokrywa też cały prostokąt. Sprawdzenie rozkładem: \(252 = 2^2 \cdot 3^2 \cdot 7\), \(198 = 2 \cdot 3^2 \cdot 11\), więc \(\text{NWD} = 2 \cdot 3^2 = 18\).

Prostokąt 252 na 198 pocięty na kwadraty: jeden o boku 198, trzy o boku 54, jeden o boku 36 i dwa o boku 18198545454361818252198252 = 1·198 + 54, 198 = 3·54 + 36, 54 = 1·36 + 18, 36 = 2·18
Algorytm Euklidesa jako cięcie prostokąta \(252 \times 198\) na kwadraty: najmniejszy kwadrat, o boku \(18 = \text{NWD}(252, 198)\), mieści się dokładnie w każdym większym

Przykład 5 (szkoła podstawowa) — podział na równe grupy

Kwiaciarka ma 96 czerwonych i 60 białych róż. Chce ułożyć z nich jak najwięcej jednakowych bukietów, wykorzystując wszystkie kwiaty. Ile bukietów ułoży i ile róż każdego koloru znajdzie się w bukiecie?

Rozwiązanie. Liczba bukietów musi dzielić 96 (żeby czerwone róże rozłożyły się po równo) i 60 (żeby białe rozłożyły się po równo), a ma być największa — szukamy NWD. Mamy \(96 = 2^5 \cdot 3\) i \(60 = 2^2 \cdot 3 \cdot 5\), więc \(\text{NWD}(96, 60) = 2^2 \cdot 3 = 12\). Kwiaciarka ułoży 12 bukietów, każdy z \(96 : 12 = 8\) czerwonych i \(60 : 12 = 5\) białych róż.

Sformułowania „jak najwięcej jednakowych grup” albo „jak największy kawałek” wskazują na NWD. Sformułowania „kiedy najwcześniej znów razem” albo „najmniejsza liczba podzielna przez obie” wskazują na NWW.

Przykład 6 (szkoła podstawowa, PP) — kiedy autobusy znów odjadą razem

Z pętli autobus linii A odjeżdża co 15 minut, a autobus linii B co 25 minut. O 6:00 oba odjechały jednocześnie. O której godzinie znów odjadą razem i ile razy zdarzy się to między 6:00 a 10:00 (licząc odjazd o 6:00)?

Rozwiązanie. Licząc minuty od 6:00, linia A odjeżdża w wielokrotnościach 15, a linia B w wielokrotnościach 25. Wspólne odjazdy to wspólne wielokrotności, a pierwszy po 6:00 wypada po NWW minutach. \(15 = 3 \cdot 5\) i \(25 = 5^2\), więc \(\text{NWW}(15, 25) = 3 \cdot 5^2 = 75\). Autobusy znów odjadą razem po 75 minutach, czyli o 7:15. Ten sam wynik daje wzór: \(\text{NWD}(15, 25) = 5\), więc \(\text{NWW} = \frac{15 \cdot 25}{5} = 75\).

Wspólne odjazdy powtarzają się co 75 minut: 6:00, 7:15, 8:30, 9:45. Następny byłby o 11:00, już po 10:00. Odpowiedź: 4 razy.

Oś czasu od 6:00 do 10:00: linia A co 15 minut, linia B co 25 minut, wspólne odjazdy o 6:00, 7:15, 8:30 i 9:456:007:158:309:45AB6:007:008:009:0010:00
Odjazdy linii A (co 15 min) i B (co 25 min): spotykają się co \(\text{NWW}(15, 25) = 75\) minut — o 6:00, 7:15, 8:30 i 9:45

Przykład 7 (PP) — reszty z dzielenia

Liczba całkowita \(a\) przy dzieleniu przez 7 daje resztę 3, a liczba całkowita \(b\) daje resztę 5. Jaką resztę z dzielenia przez 7 daje liczba \(a^2 + 2b\)?

Rozwiązanie. Zapisujemy \(a = 7k + 3\) oraz \(b = 7m + 5\), gdzie \(k\) i \(m\) są liczbami całkowitymi. Litery muszą być różne, bo \(a\) i \(b\) są od siebie niezależne. Wtedy

\[ a^2 + 2b = 49k^2 + 42k + 9 + 14m + 10 = 7(7k^2 + 6k + 2m) + 19. \]

Liczba 19 nie jest jeszcze resztą, bo jest większa od 7: \(19 = 2 \cdot 7 + 5\). Zatem \(a^2 + 2b = 7(7k^2 + 6k + 2m + 2) + 5\), a wyrażenie w nawiasie jest liczbą całkowitą, więc reszta wynosi 5. Skrót myślowy: w resztach można liczyć tak, jakby \(a = 3\) i \(b = 5\), czyli \(9 + 10 = 19\), a 19 daje przy dzieleniu przez 7 resztę 5.

Przykład 8 (PP) — suma kolejnych liczb całkowitych

Udowodnij, że suma trzech kolejnych liczb całkowitych jest podzielna przez 3, a suma czterech kolejnych liczb całkowitych nigdy nie jest podzielna przez 4.

Dowód. Trzy kolejne liczby całkowite zapisujemy jako \(n - 1\), \(n\), \(n + 1\), gdzie \(n\) jest liczbą całkowitą. Ich suma to \((n - 1) + n + (n + 1) = 3n\), a \(n\) jest liczbą całkowitą, więc suma dzieli się przez 3.

Cztery kolejne liczby całkowite to \(n\), \(n + 1\), \(n + 2\), \(n + 3\). Ich suma wynosi \(4n + 6 = 4(n + 1) + 2\), gdzie \(n + 1\) jest liczbą całkowitą. Suma daje więc przy dzieleniu przez 4 resztę 2, czyli nie jest podzielna przez 4, co należało udowodnić.

Wybór „środkowej” liczby jako \(n\) w pierwszej części to drobny trik, który upraszcza rachunek. Ogólniej: suma \(k\) kolejnych liczb całkowitych dzieli się przez \(k\) dokładnie wtedy, gdy \(k\) jest nieparzyste.

Przykład 9 (PP i PR) — liczba n³ − n

Udowodnij, że dla każdej liczby całkowitej \(n\) liczba \(n^3 - n\) jest podzielna przez 6. Wykaż ponadto, że dla nieparzystej liczby \(n\) jest ona podzielna przez 24.

Dowód. Wyłączamy \(n\) przed nawias i stosujemy wzór skróconego mnożenia na różnicę kwadratów:

\[ n^3 - n = n(n^2 - 1) = (n - 1) \cdot n \cdot (n + 1). \]

To iloczyn trzech kolejnych liczb całkowitych. Wśród nich co najmniej jedna jest parzysta i dokładnie jedna dzieli się przez 3 (kolejne liczby dają kolejne reszty z dzielenia przez 3). Iloczyn dzieli się więc przez 2 i przez 3, a ponieważ \(\text{NWD}(2, 3) = 1\) — także przez 6.

Niech teraz \(n = 2k + 1\), gdzie \(k\) jest liczbą całkowitą. Wtedy

\[ (n - 1) \cdot n \cdot (n + 1) = 2k \cdot (2k + 1) \cdot (2k + 2) = 4 \cdot k(k + 1) \cdot (2k + 1). \]

Iloczyn \(k(k + 1)\) dwóch kolejnych liczb całkowitych jest parzysty, więc całe wyrażenie dzieli się przez \(4 \cdot 2 = 8\). Z pierwszej części dzieli się też przez 3, a \(\text{NWD}(8, 3) = 1\), więc dzieli się przez 24, co należało udowodnić. Kontrola dla \(n = 5\): \(125 - 5 = 120 = 24 \cdot 5\).

Więcej takich rozumowań, w tym zapis przez reszty i to, za co egzaminator przyznaje punkty, znajdziesz w lekcji dowody na maturze — jak udowodnić nierówność i podzielność.

Przykład 10 (PR) — pary liczb o danym NWD i NWW

Znajdź wszystkie pary liczb naturalnych \(a \leq b\), dla których \(\text{NWD}(a, b) = 6\) i \(\text{NWW}(a, b) = 180\).

Rozwiązanie. Skoro 6 dzieli obie liczby, zapisujemy \(a = 6x\) i \(b = 6y\), gdzie \(x \leq y\) są liczbami naturalnymi dodatnimi. Gdyby \(x\) i \(y\) miały wspólny dzielnik \(d > 1\), to \(6d\) byłby wspólnym dzielnikiem \(a\) i \(b\) większym od 6 — sprzeczność. Zatem \(\text{NWD}(x, y) = 1\). Ze wzoru \(\text{NWD} \cdot \text{NWW} = a \cdot b\):

\[ 6 \cdot 180 = 6x \cdot 6y, \quad \text{czyli} \quad xy = 30. \]

Szukamy rozkładów \(30 = 2 \cdot 3 \cdot 5\) na dwa czynniki względnie pierwsze. Każda z trzech liczb pierwszych musi trafić w całości do \(x\) albo do \(y\) — inaczej byłaby wspólnym dzielnikiem. Daje to \(2^3 = 8\) przydziałów, a z warunkiem \(x \leq y\) zostaje połowa: \((x, y) \in \{(1, 30), (2, 15), (3, 10), (5, 6)\}\). Stąd szukane pary \((a, b)\) to \((6, 180)\), \((12, 90)\), \((18, 60)\) i \((30, 36)\).

Sprawdzenie ostatniej pary: \(30 = 2 \cdot 3 \cdot 5\) i \(36 = 2^2 \cdot 3^2\), więc NWD to \(2 \cdot 3 = 6\), a NWW to \(2^2 \cdot 3^2 \cdot 5 = 180\). Dzielenie przez 2 bierze się stąd, że przydziały \((x, y) = (1, 30)\) i \((x, y) = (30, 1)\) dają tę samą parę liczb, tylko w innej kolejności. Gdyby zadanie pytało o pary uporządkowane, odpowiedzi byłoby 8.

Typowe błędy

  • „1 jest liczbą pierwszą”. Nie jest — ma tylko jeden dzielnik. Najmniejsza liczba pierwsza to 2.
  • Łączenie cech dla liczb, które nie są względnie pierwsze. Podzielność przez 4 i przez 6 nie daje podzielności przez 24 (kontrprzykład: 12). Przez 24 sprawdzaj cechy przez 3 i przez 8.
  • Cecha przez 4 z ostatniej cyfry. Liczba 314 kończy się czwórką, ale 14 nie dzieli się przez 4, więc 314 też nie. Liczy się liczba utworzona z dwóch ostatnich cyfr.
  • Suma cyfr użyta tam, gdzie nie działa. Suma cyfr rozstrzyga tylko podzielność przez 3 i 9. Liczba 33 ma sumę cyfr 6, ale nie dzieli się przez 6, bo jest nieparzysta.
  • Pomylenie NWD z NWW. NWD jest nie większy od mniejszej z liczb, NWW nie mniejsza od większej. Jeśli w zadaniu o płytkach bok płytki wyszedł większy niż wymiar podłogi — policzyłeś NWW zamiast NWD.
  • Złe wykładniki w rozkładzie. NWD bierze tylko czynniki wspólne i mniejsze potęgi, NWW — wszystkie czynniki i większe potęgi. Częsty błąd to wpisanie do NWD czynnika, który występuje tylko w jednej liczbie.
  • Wzór NWD · NWW = a · b dla trzech liczb. Dla 2, 4, 8 mamy NWD równy 2 i NWW równą 8, czyli iloczyn 16, a \(2 \cdot 4 \cdot 8 = 64\).
  • Reszta spoza zakresu. Reszta z dzielenia przez \(d\) jest zawsze liczbą od 0 do \(d - 1\). Wynik 19 przy dzieleniu przez 7 trzeba jeszcze zredukować, jak w przykładzie 7.
  • Test pierwszości przerwany za wcześnie. Dla 391 trzeba dojść aż do 17; sprawdzenie samych 2, 3, 5 i 7 niczego nie rozstrzyga.

Ściąga — podzielność, NWD i NWW w pigułce

  • \(d \mid a\) oznacza \(a = d \cdot k\) dla pewnej całkowitej \(k\); dzielenie z resztą: \(a = dq + r\), \(0 \leq r < d\).
  • Przez 2, 5, 10 decyduje ostatnia cyfra; przez 4 i 25 — dwie ostatnie; przez 8 — trzy ostatnie.
  • Przez 3 i 9 decyduje suma cyfr (bo \(10 = 9 + 1\)); przez 11 — naprzemienna suma cyfr od prawej (bo \(10 = 11 - 1\)).
  • Przez 6 to przez 2 i przez 3; łącz tylko cechy dla liczb względnie pierwszych.
  • Liczba pierwsza ma dokładnie dwa dzielniki; 1 nie jest pierwsza; 2 to jedyna parzysta liczba pierwsza; liczb pierwszych mniejszych od 100 jest 25.
  • Test pierwszości: dziel przez liczby pierwsze nie większe niż \(\sqrt{n}\).
  • \(n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}\) ma \((a_1 + 1) \cdot \ldots \cdot (a_k + 1)\) dzielników.
  • NWD: czynniki wspólne w mniejszych potęgach albo algorytm Euklidesa \(\text{NWD}(a, b) = \text{NWD}(b, r)\).
  • NWW: wszystkie czynniki w większych potęgach; \(\text{NWD}(a, b) \cdot \text{NWW}(a, b) = a \cdot b\).
  • Zadania tekstowe: „największe jednakowe części” to NWD, „kiedy znów razem” to NWW.
  • \(n^3 - n = (n - 1)n(n + 1)\) dzieli się przez 6; suma trzech kolejnych liczb całkowitych to \(3n\).

Sprawdź się

Najpierw kilka szybkich zadań (odpowiedzi w nawiasach):

  1. Czy liczba 123 456 jest podzielna przez 3, 4, 8, 9 i 11? (przez 3, 4 i 8 tak; przez 9 i 11 nie)
  2. Czy 221 jest liczbą pierwszą? (nie, \(221 = 13 \cdot 17\))
  3. Oblicz \(\text{NWD}(1071, 462)\) algorytmem Euklidesa. (21)
  4. Oblicz \(\text{NWW}(28, 42)\). (84)
  5. Wykaż, że dla liczby pierwszej \(p > 3\) liczba \(p^2 - 1\) jest podzielna przez 24. (\(p^2 - 1 = (p - 1)(p + 1)\), a \(p\) jest nieparzysta i niepodzielna przez 3 — rozumuj jak w przykładzie 9)

Potem zadania z bazy, od prostszych do trudniejszych:

Więcej zadań znajdziesz w dziale teoria liczb, a pełne arkusze egzaminacyjne w sekcji matura.

Dzisiejszy zestaw zadań → Trening liczenia w pamięci · 2 min