6. Rozkład liczby na czynniki pierwsze

REJGDQQ59HJC2

REZMNCPZH2UCM1

Na ilustracji znajduje się starszy, elegancko ubrany mężczyzna w okularach. — Paul Erdős (1992)
Źródło: Kmhkmh, dostępny w internecie: https:\\wikimedia.commons.org, licencja: CC BY 3.0.

Można śmiało zaryzykować twierdzenie, że wśród liczb naturalnych najciekawsze i najważniejsze są liczby pierwsze. Badał je już Euklides na przełomie IV i III wieku przed naszą erą. To od niego pochodzi dowód na to, że liczb pierwszych jest nieskończenie wiele, przez wielu uznawany za dowód z Księgi. Określenie to pochodzi od Paula Erdősa – jednego z najwybitniejszych matematyków XX wieku. Mawiał on, że wszystkie najelegantsze dowody Bóg trzyma spisane w Księdze i tylko czasami pozwala do niej zajrzeć jakiemuś człowiekowi.

Z liczb pierwszych możemy budować inne liczby wykorzystując do tego mnożenie. Przypomnimy teraz algorytm rozkładania liczby na czynniki pierwsze.

Twoje cele

Zastosujesz algorytm rozkładania liczby na czynniki pierwsze.
Wykorzystasz rozkład liczby na czynniki pierwsze do wyznaczania liczby dzielników danej liczby.

Przypomnijmy algorytm rozkładania liczby naturalnej na czynniki pierwsze:

Po prawej stronie rozważanej liczby naturalnej $n$ stawiamy pionową kreskę.
Szukamy jakiejkolwiek liczby pierwszej $p_{1}$ , która dzieli daną liczbę – zapisujemy ją po prawej stronie kreski na wysokości liczby $n$ .
Dzielimy liczbę $n$ przez liczbę $p_{1}$ – wynik $n_{1}$ tego dzielenia zapisujemy po lewej stronie kreski pod liczbą $n$ .
Czynności 2) i 3) powtarzamy dla liczby $n_{1}$ – liczbę pierwszą $p_{2}$ dzielącą liczbę $n_{1}$ zapisujemy pod liczbą $p_{1}$ . Wynik $n_{2}$ tego dzielenia zapisujemy pod liczbą $n_{1}$ .
Algorytm kontynuujemy, aż po lewej stronie kreski pojawi się liczba $1$ .

R1U7TAGXTTTOT

Na ilustracji przedstawiono dwa pionowe rzędy czynników oddzielone prostą. Po lewej stronie prostej zapisano, kolejno od góry n, n indeks dolny, jeden, koniec indeksu dolnego, n indeks dolny, dwa, koniec indeksu dolnego. Po prawej stronie prostej, równolegle do n, czynnik p indeks dolny, jeden, koniec indeksu dolnego oraz równoległe do n indeks dolny, jeden, koniec indeksu dolnego czynnik p indeks dolny, dwa, koniec indeksu dolnego. Najbardziej po lewej umieszczono następujące napisy. Wynik dzielenia n ÷ p indeks dolny, jeden, koniec indeksu dolnego, od którego poprowadzono strzałkę do n indeks dolny, jeden, koniec indeksu dolnego oraz wynik dzielenia n indeks dolny, jeden, koniec indeksu dolnego, ÷ p indeks dolny, dwa, koniec indeksu dolnego, od którego poprowadzono strzałkę do n indeks dolny, dwa, koniec indeksu dolnego. Najbardziej po prawej umieszczono napisy. p indeks dolny, jeden, koniec indeksu dolnego dzieli n, od którego poprowadzono strzałkę do p indeks dolny, jeden, koniec indeksu dolnego oraz p indeks dolny, dwa, koniec indeksu dolnego dzieli n indeks dolny, jeden, koniec indeksu dolnego od którego poprowadzono strzałkę do p indeks dolny, dwa, koniec indeksu dolnego.

Wobec powyższego $n = p_{1} \cdot p_{2} \cdot \dots \cdot p_{k}$ .

Przykład 1

Przedstawimy liczbę $360$ w postaci iloczynu czynników pierwszych.

Zauważmy przy okazji, że kolejność znajdowania czynników pierwszych nie ma znaczenia – efekt jest taki sam, chociaż przyjęło się, że zaczynamy dzielenie od najmniejszych liczb pierwszych.

R1JR8OD49KNM4

Na ilustracji przedstawiono dwa sposoby przedstawienia liczby 360 w postaci iloczynu czynników pierwszych. Sposób 1. Przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie prostej zapisano kolejno od góry 360, 180, 90, 30, 10, 5 oraz jeden. Po prawej stronie zapisano kolejno od góry 2, 2, 3, 3, 2 oraz pięć. Sposób 2. Przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie zapisano kolejno od góry 360, 120, 60, 30, 10, 2 oraz jeden. Po prawej stronie zapisano kolejno od góry 3, 2, 2, 3, 5 oraz 2.

Zatem możemy zapisać $360 = 2^{3} \cdot 3^{2} \cdot 5$ .

Zauważmy, że każdy dzielnik liczby 360 jest pewną kombinacją jego dzielników pierwszych.

Na przykład liczba $360$ dzieli się przez $8$ (bo $8 = 2 \cdot 2 \cdot 2$ ), ale nie przez $16$ (bo $16 = 2 \cdot 2 \cdot 2 \cdot 2$ ), $360$ dzieli się przez $45$ (bo $45 = 3 \cdot 3 \cdot 5$ ), ale nie przez $135$ (bo $135 = 3 \cdot 3 \cdot 3 \cdot 5$ ). Liczba $360$ nie dzieli się też przez $13$ , ani przez $26$ (bo $26 = 2 \cdot 13$ ).

Zatem każdy dzielnik $d$ liczby $360$ jest postaci $d = 2^{w_{1}} \cdot 3^{w_{2}} \cdot 5^{w_{3}}$ , przy czym $w_{1} \in \{0, 1, 2, 3\}$ , $w_{2} \in \{0, 1, 2\}$ , $w_{3} \in \{0, 1\}$ .

RQM3AJL8E1HKM

Na ilustracji przedstawiono tabelę składającą się z trzech kolumn. Pierwszą kolumnę od lewej zatytułowano potęga liczby dwa. Kolejno od góry wypisano liczby dwa do potęgi zerowej, dwa do potęgi pierwszej, dwa do potęgi drugiej oraz dwa do potęgi trzeciej. Środkową kolumnę zatytułowano potęga liczby trzy. Kolejno od góry wypisano liczby, trzy do potęgi zerowej, trzy do potęgi pierwszej oraz trzy do potęgi drugiej. Trzecią kolumnę zatytułowano potęga liczby pięć. Kolejno od góry wypisano liczby, pięć do potęgi zerowej oraz pięć do potęgi pierwszej. Liczby w poszczególnych kolumnach połączono strzałkami w odpowiedniej kolejności, z których powstały następujące równości dwa indeks górny, dwa, koniec indeksu górnego, × trzy indeks górny, dwa, koniec indeksu górnego, × pięć indeks górny, zero, koniec indeksu górnego, równa się, trzydzieści sześć, dwa indeks górny, zero, koniec indeksu górnego, × trzy indeks górny, jeden, koniec indeksu górnego, × pięć indeks górny, jeden, koniec indeksu górnego, równa się, piętnaście, dwa indeks górny, trzy, koniec indeksu górnego, × trzy indeks górny, zero, koniec indeksu górnego, × pięć indeks górny, jeden, koniec indeksu górnego, równa się, czterdzieści.

Ponieważ tworząc dzielnik $d$ liczby $360$ możemy użyć dowolnej spośród potęg liczby $2$ o wykładniku $0$ , $1$ , $2$ , $3$ (co daje $4$ możliwości), dowolnej spośród potęg liczby $3$ o wykładniku $0$ , $1$ , $2$ (co daje $3$ możliwości) oraz dowolnej spośród potęg liczby $5$ o wykładniku $0$ , $1$ (co daje $2$ możliwości), to wszystkich dzielników liczby $360$ jest $4 \cdot 3 \cdot 2 = 24$ . Zauważmy jeszcze, że $1 = 2^{0} \cdot 3^{0} \cdot 5^{0}$ .

Ogólnie jeśli liczba naturalna $x$ przedstawia się jako iloczyn liczb pierwszych w następujący sposób

{p_{1}}^{k_{1}} \cdot {p_{2}}^{k_{2}} \cdot {p_{3}}^{k_{3}} \cdot . . . \cdot {p_{n}}^{k_{n}}

to każdy jej dzielnik $d$ jest postaci:

{p_{1}}^{w_{1}} \cdot {p_{2}}^{w_{2}} \cdot {p_{3}}^{w_{3}} \cdot . . . \cdot {p_{n}}^{w_{n}}

gdzie:
$w_{1} \in \{0, 1, 2, . . ., k_{1}\}$ , $w_{2} \in \{0, 1, 2, . . ., k_{2}\}$ , $w_{3} \in \{0, 1, 2, . . ., k_{3}\}$ , $. . .$ , $w_{n} \in \{0, 1, 2, . . ., k_{n}\}$ .

Wszystkich dzielników liczby

{p_{1}}^{k_{1}} \cdot {p_{2}}^{k_{2}} \cdot {p_{3}}^{k_{3}} \cdot . . . \cdot {p_{n}}^{k_{n}}

jest

(k_{1} + 1) \cdot (k_{2} + 1) \cdot (k_{3} + 1) \cdot . . . \cdot (k_{n} + 1)

Przykład 2

Wyznaczymy liczbę wszystkich dzielników liczb

a) $100$

b) $600$

a) Każdy dzielnik liczby $100 = 2^{2} \cdot 5^{2}$ ma swoim rozkładzie na czynniki pierwszerozkład na czynniki pierwszerozkładzie na czynniki pierwsze tylko i wyłącznie zerową, pierwszą lub drugą potęgę liczby $2$ oraz zerową, pierwszą lub drugą potęgę liczby $5$ . Czyli dzielnik liczby $100$ może zawierać jedynie jedną z trzech potęg liczby $2$ ( $1$ , $2$ lub $4$ ) oraz jedną z trzech potęg liczby $5$ ( $1$ , $5$ lub $25$ ). Zatem wszystkich dzielników liczby $100$ jest $3 \cdot 3 = 9$ . Wypiszmy je wszystkie:

R1SAZH92C62DM

Na ilustracji przedstawiono przykład, zobrazowany za pomocą diagramu drzewa. W rzędzie pierwszym umieszczono, kolejno od góry liczby 2 do potęgi zerowej, 2 do potęgi pierwszej oraz 2 do potęgi drugiej. Od każdej liczby odchodzą trzy strzałki do cyfr 5 do potęgi zerowej, 5 do potęgi pierwszej oraz 5 do potęgi drugiej. Od każdej potęgi liczby pięć, dla odpowiadającej jej potęgi liczby dwa, poprowadzono strzałki oraz zapisano równości. Dla potęgi 2 do zerowej dwa indeks górny, zero, koniec indeksu górnego, × pięć indeks górny, zero, koniec indeksu górnego, równa się, jeden, dwa indeks górny, zero, koniec indeksu górnego, × pięć indeks górny, jeden, koniec indeksu górnego, równa się, pięć oraz dwa indeks górny, zero, koniec indeksu górnego, × pięć indeks górny, dwa, koniec indeksu górnego, równa się, dwadzieścia pięć. Następnie dla potęgi liczby 2 do pierwszej. dwa indeks górny, jeden, koniec indeksu górnego, × pięć indeks górny, zero, koniec indeksu górnego, równa się, dwa, dwa indeks górny, jeden, koniec indeksu górnego, × pięć indeks górny, jeden, koniec indeksu górnego, równa się, dziesięć oraz dwa indeks górny, jeden, koniec indeksu górnego, × pięć indeks górny, dwa, koniec indeksu górnego, równa się, pięćdziesiąt. Dla potęgi liczby 2 do drugiej. dwa indeks górny, dwa, koniec indeksu górnego, × pięć indeks górny, zero, koniec indeksu górnego, równa się, pięćdziesiąt, dwa indeks górny, dwa, koniec indeksu górnego, × pięć indeks górny, jeden, koniec indeksu górnego, równa się, dwadzieścia oraz dwa indeks górny, dwa, koniec indeksu górnego, × pięć indeks górny, dwa, koniec indeksu górnego, równa się, sto.

b) Dzielniki $d$ liczby $600 = 2^{3} \cdot 5^{2} \cdot 3$ są postaci

$d = 2^{w_{1}} \cdot 5^{w_{2}} \cdot 3^{w_{3}}$

gdzie:
$w_{1} \in \{0, 1, 2, 3\}$ , $w_{2} \in \{0, 1, 2\}$ , $w_{3} \in \{0, 1\}$ .

Zatem tworząc dzielnik liczby $600$ możemy użyć jednej z czterech potęg liczby $2$ , jednej z trzech potęg liczby $5$ oraz jednej z dwóch potęg liczby $3$ , co daje $4 \cdot 3 \cdot 2 = 24$ dzielniki.

Podsumujmy dotychczasowe rozważania w postaci twierdzenia.

Zasadnicze twierdzenie arytmetyki

Twierdzenie: Zasadnicze twierdzenie arytmetyki

Każda liczba naturalna większa od $1$ albo jest liczbą pierwszą, albo można ją jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.

Jednoznaczność oznacza, że jeśli dana liczba jest przedstawiona jako iloczyn pewnych liczb pierwszych na dwa sposoby, to oba te iloczyny zawierają te same czynniki, a różnią się jedynie ich kolejnością.

Przedstawienie liczby w postaci iloczynu nazywamy rozkładem na czynniki lub faktoryzacją. Często pod pojęciem faktoryzacjifaktoryzacjafaktoryzacji rozumiemy rozkład na czynnikirozkład na czynniki pierwszerozkład na czynniki nierozkładalne, czyli w przypadku liczb – na czynniki będące liczbami pierwszymi, czasami jednak nazywamy tak dowolne przedstawienie danego obiektu matematycznego w postaci iloczynu. Znaczenie rozpoznajemy na podstawie kontekstu.

Animacja interaktywna

Przeanalizuj zaprezentowane w animacji sposoby rozkładania liczb naturalnych na czynniki pierwsze.

R1C999KND4217

Polecenie 1

Każdą z liczb $3480$ i $4950$ rozłóż na czynniki pierwsze korzystając z obu przedstawionych metod.

Rozkład “z kreską” liczby $3480$ :

R1DB22GJZUPXJ

Na ilustracji przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie prostej zapisano kolejno od góry liczby 3480, 1740, 870, 435, 87, 29 oraz jeden. Po prawej stronie zapisano kolejno od góry liczby 2, 2, 2, 5, 3 oraz dwadzieścia dziewięć.

3480 = 2^{3} \cdot 3 \cdot 5 \cdot 29

“Drzewko” dla liczby $3480$ :

R1MBPK6LV3KBE

Na ilustracji przedstawiono rozkład liczby 3480 na czynniki pierwsze, zobrazowany za pomocą diagramu drzewa. Rozgałęzienia następują w dół a gałęzie zaznaczono za pomocą strzałek. Drzewo wygląda następująco. Liczba 3480 rozgałęzia się w dół na 10 i trzysta czterdzieści osiem. Liczby te leżą równolegle, a pomiędzy nimi umieszczono znak mnożenia. Liczba dziesięć rozgałęzia się na liczby dwa i pięć, między którymi analogicznie znajduje się znak mnożenia. Liczba 348 rozgałęzia się na 4 i osiemdziesiąt siedem. Liczba 4 rozgałęzia się na 2 i 2, natomiast liczba 87 rozgałęzia się na 3 i dwadzieścia dziewięć.

3480 = 2^{3} \cdot 3 \cdot 5 \cdot 29

Rozkład “z kreską” liczby $4950$ :

R966PSTTR7V7V

Na ilustracji przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie prostej zapisano kolejno od góry liczby 4950, 2475, 495, 99, 33, 11 oraz jeden. Po prawej stronie zapisano kolejno od góry liczby 2, 5, 5, 3, 3 oraz jedenaście.

4950 = 2 \cdot 3^{2} \cdot 5^{2} \cdot 11

“Drzewko” dla liczby $4950$ :

R1PS592ZV4AQE

Ilustracja przedstawia drzewko matematyczne ukazujące rozkład liczby cztery tysiące dziewięćset pięćdziesiąt na dzielniki. Pierwszy wiersz ukazuje liczbę cztery tysiące dziewięćset pięćdziesiąt, drugi wiersz dziesięć razy czterysta dziewięćdziesiąt pięć. Trzeci wiersz od strony dziesięć to dwa razy pięć, od strony czterysta dziewięćdziesiąt pięć pięćrazy dziewięćdziesiąt dziewięć. Od liczby dziewięćdziesiąt dziewięć kolejny wiersz ukazuje mnożenie dziewięć razy jedenaście, od liczby dziewięć strzałki ukazują mnożenie liczb trzy i trzy.

4950 = 2 \cdot 3^{2} \cdot 5^{2} \cdot 11

Zestaw ćwiczeń interaktywnych

Pokaż ćwiczenia:

R1GJZHNBT55QR1

Ćwiczenie 1

Ćwiczenie 2

Rozłóż podane liczby na czynniki pierwsze:

a) $936$

b) $528$

c) $1575$

R1G4LEOKDX82V2

Ćwiczenie 3

Poniżej wypisane liczby naturalne przedstawiono w postaci iloczynu potęg liczb pierwszych. Przyporządkuj potęgi liczbom, z rozkładów których pochodzą.
Przeciągnij i upuść. dwieście czterdzieści Możliwe odpowiedzi: 1. trzy indeks górny, dwa, koniec indeksu górnego, 2. pięć indeks górny, dwa, koniec indeksu górnego, 3. trzy indeks górny, trzy, koniec indeksu górnego, 4. pięć indeks górny, dwa, koniec indeksu górnego, 5. dwa, 6. pięć, 7. dwa indeks górny, trzy, koniec indeksu górnego, 8. trzy, 9. dwa indeks górny, dwa, koniec indeksu górnego, 10. trzy indeks górny, dwa, koniec indeksu górnego, 11. pięć, 12. dwa indeks górny, cztery, koniec indeksu górnego trzysta sześćdziesiąt Możliwe odpowiedzi: 1. trzy indeks górny, dwa, koniec indeksu górnego, 2. pięć indeks górny, dwa, koniec indeksu górnego, 3. trzy indeks górny, trzy, koniec indeksu górnego, 4. pięć indeks górny, dwa, koniec indeksu górnego, 5. dwa, 6. pięć, 7. dwa indeks górny, trzy, koniec indeksu górnego, 8. trzy, 9. dwa indeks górny, dwa, koniec indeksu górnego, 10. trzy indeks górny, dwa, koniec indeksu górnego, 11. pięć, 12. dwa indeks górny, cztery, koniec indeksu górnego dziewięćset Możliwe odpowiedzi: 1. trzy indeks górny, dwa, koniec indeksu górnego, 2. pięć indeks górny, dwa, koniec indeksu górnego, 3. trzy indeks górny, trzy, koniec indeksu górnego, 4. pięć indeks górny, dwa, koniec indeksu górnego, 5. dwa, 6. pięć, 7. dwa indeks górny, trzy, koniec indeksu górnego, 8. trzy, 9. dwa indeks górny, dwa, koniec indeksu górnego, 10. trzy indeks górny, dwa, koniec indeksu górnego, 11. pięć, 12. dwa indeks górny, cztery, koniec indeksu górnego tysiąc trzysta pięćdziesiąt Możliwe odpowiedzi: 1. trzy indeks górny, dwa, koniec indeksu górnego, 2. pięć indeks górny, dwa, koniec indeksu górnego, 3. trzy indeks górny, trzy, koniec indeksu górnego, 4. pięć indeks górny, dwa, koniec indeksu górnego, 5. dwa, 6. pięć, 7. dwa indeks górny, trzy, koniec indeksu górnego, 8. trzy, 9. dwa indeks górny, dwa, koniec indeksu górnego, 10. trzy indeks górny, dwa, koniec indeksu górnego, 11. pięć, 12. dwa indeks górny, cztery, koniec indeksu górnego

R1X2NC8N8ZSLV2

Ćwiczenie 4

R1Z3AMDHS4MLJ2

Ćwiczenie 5

R1TZ47U5UVV332

Ćwiczenie 6

RK1GEKEL2NPHL3

Ćwiczenie 7

Ćwiczenie 8

Znana jest cecha podzielności przez $7$ .

Liczba $n$ dzieli się przez $7$ , dokładnie wtedy, gdy przez $7$ dzieli się suma iloczynów kolejnych cyfr liczby $n$ (licząc od rzędu jedności) przez kolejne naturalne potęgi liczby $3$ (licząc od potęgi zerowej).

Sprawdzimy, czy liczba $52647$ dzieli się przez $7$ . Rozważmy sumę iloczynów kolejnych cyfr tej liczby przez kolejne naturalne potęgi liczby $3$ :

$7 \cdot 3^{0} + 4 \cdot 3^{1} + 6 \cdot 3^{2} + 2 \cdot 3^{3} + 5 \cdot 3^{4} = 7 + 12 + 54 + 54 + 405 = 532$

Aby stwierdzić, czy liczba $532$ dzieli się przez $7$ , możemy ponownie zastosować cechę podzielności:

$2 \cdot 3^{0} + 3 \cdot 3^{1} + 5 \cdot 3^{2} = 2 + 9 + 45 = 56$

Ponieważ $56$ dzieli się przez $7$ , więc $532$ dzieli się przez $7$ , a z tego wynika, że liczba $52647$ również dzieli się przez $7$ .

Stosując cechę podzielności przez $7$ zbadaj, czy liczba $7$ występuje w rozkładzie na czynniki pierwsze następujących liczb.

R197HFXVHKEC2

Słownik

rozkład na czynniki pierwsze

przedstawienie liczby naturalnej w postaci iloczynu liczb pierwszych; zapis zwykle zawiera naturalne potęgi liczb pierwszych

faktoryzacja

1) czynność prowadząca do przedstawienia liczby lub wyrażenia algebraicznego w postaci nietrywialnych (w przypadku liczb – różnych od $1$ ) czynników;
2) przedstawienie liczby lub wyrażenia w postaci iloczynu nietrywialnych (w przypadku liczb – różnych od $1$ ) czynników

5. Podzielność w zbiorze liczb naturalnych – dzielenie z resztą i bez reszty

7. NWD, NWW