6. Rozkład liczby na czynniki pierwsze

RUNT3STrNQevb

RltBnhF2OzsxK1

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. W tej lekcji przypomnimy 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$ .

RrCj0La98O2r4

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

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

Przykład 1

Przedstawmy 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.

RQYTXAmD84UdV

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\}$ .

R19X2EX56TNPL

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 22×32×50=36, 20×31×51=15, 23×30×51=40.

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:

R1BHL6QJDLD1J

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 20×50=1, 20×51=5 oraz 20×52=25. Następnie dla potęgi liczby 2 do pierwszej. 21×50=2, 21×51=10 oraz 21×52=50. Dla potęgi liczby 2 do drugiej. 22×50=50, 22×51=20 oraz 22×52=100.

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.

Polecenie 1

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

R1VdznIVxNWRW

Polecenie 2

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

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

R34cTfS48ZLnd

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$ :

R1MjDcrETt1FK

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$ :

RmNpwPiFJxfBw

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$ :

R1DV8JNA9LBQL

Ilustracja przedstawia drzewko matematyczne ukazujące rozkład liczby 4950 na dzielniki. Pierwszy wiersz ukazuje liczbę 4950, drugi wiersz 10 razy 495. Trzeci wiersz od strony 10 to 2 razy 5, od strony 495 5razy 99. Od liczby 99 kolejny wiersz ukazuje mnożenie 9 razy 11, od liczby 9 strzałki ukazują mnożenie liczb 3 i 3.

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

Pokaż ćwiczenia:

RiTtqeeVEDcL11

Ćwiczenie 1

Ćwiczenie 2

Rozłóż podane liczby na czynniki pierwsze:

a) $936$

b) $528$

c) $1575$

RkPENCn9ZfdpZ

Na ilustracji przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie prostej zapisano kolejno od góry 936, 312, 156, 78, 39, 13 oraz jeden. Po prawej stronie zapisano kolejno od góry 3, 2, 2, 2, 3 oraz trzynaście. Poniżej zapisano równanie. 936=23×33×13.

R1SHhIxdhmOec

Na ilustracji przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie prostej zapisano kolejno od góry 528, 264, 132, 66, 33, 11 oraz jeden. Po prawej stronie zapisano kolejno od góry 2, 2, 2, 2, 3 oraz jedenaście. Poniżej zapisano równanie 528=24×3×11.

R1IgXiDoqH1Wa

Na ilustracji przedstawiono dwa pionowe rzędy liczb oddzielone prostą. Po lewej stronie prostej zapisano kolejno od góry 1575, 315, 63, 21, 7 oraz jeden. Po prawej stronie zapisano kolejno od góry 5, 5, 3, 3 oraz siedem. Poniżej zapisano równanie 1575=52×32×7.

R1NIsfDSSr43W2

Ć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

R4WlXF5YrJtCV2

Ćwiczenie 4

R17uOKNCrZkjH2

Ćwiczenie 5

RzXmReYwn2Iki2

Ćwiczenie 6

R15pe5ivPBx2T3

Ć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.

RnYt0oFKpiobB

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

6. Rozkład liczby na czynniki pierwsze

Słownik