Podstawowe twierdzenie arytmetyki - Wikipedia, wolna encyklopedia

Wolna encyklopedia

Podstawowe twierdzenie arytmetyki – stwierdzenie, że każdą liczbę naturalną można rozłożyć na czynniki pierwsze. Dokładniejsze sformułowanie twierdzenia brzmi jak następuje:

Każdą liczbę całkowitą dodatnią można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.

Rozkład ten dotyczy każdej liczby całkowitej dodatniej. W szczególności, liczbę pierwszą można przedstawić jako iloczyn zawierający jeden czynnik, a liczbę 1 można przedstawić jako iloczyn zawierający zero czynników.

Jednoznaczność rozkładu

Rozkład każdej liczby na czynniki pierwsze jest jednoznaczny. Należy to rozumieć w ten sposób, że jeśli liczba n jest przedstawiona jako iloczyn pewnych liczb pierwszych na dwa sposoby, to oba iloczyny zawierają te same czynniki i w tej samej liczbie, a różnią się jedynie ich kolejnością. Na przykład:

$180 = 3\cdot 2\cdot 3\cdot 2\cdot 5 = 2\cdot 3\cdot 5\cdot 3\cdot 2.$

Zwykle czynniki pierwsze danej liczby grupuje się od najmniejszych do największych, czyli:

$180 = 2\cdot 2\cdot 3\cdot 3\cdot 5 = 2^2\cdot 3^2\cdot 5$ .

Dowód^[1]

Lemat I

Każda liczba naturalna większa od jednego posiada przynajmniej jeden dzielnik będący liczbą pierwszą.

Oznaczmy liczbę przez $n$ , $n > 1$ . Każda liczba naturalna większa od jednego ma przynajmniej jeden dzielnik różny od jednego, zatem liczba $n$ też ma dzielniki. Oznaczmy najmniejszy z nich przez $d$ . Należy teraz udowodnić, że $d$ jest liczbą pierwszą. Otóż gdyby nie był, to istniałaby taka liczba $k < d$ będąca dzielnikiem liczby $d$ , a co za tym idzie, również liczby $n$ , co przeczy założeniu, że $d$ jest najmniejszym dzielnikiem liczby $n$ .

Lemat II

Każda liczba naturalna większa od jednego daje się przedstawić jako iloczyn samych liczb pierwszych.

Każda liczba pierwsza daje się przedstawić jako iloczyn jednego czynnika, tej właśnie liczby. Wystarczy zatem rozpatrywać liczby złożone.

Oznaczmy pewną liczbę złożoną przez $n$ , $n > 1$ i . Na mocy lematu I, $n$ ma dzielnik pierwszy, który oznaczmy przez $p$ . Można zatem zapisać:

n = p n'

Ponieważ $n' = n / p$ , zachodzi nierówność $1 < n' < n$ . Jeżeli $n'$ jest liczbą pierwszą, to mamy już gotowy rozkład, jeżeli nie, to powyższe rozumowanie można powtarzać aż otrzyma się liczbę pierwszą.

Ciąg równości

$n=pn' , n'=p'n'' , n''=p''n''', \ldots$

nie jest nieskończony, gdyż liczby $n', n'', n'''$ są wyrazami ciągu malejącego zawartymi w przedziale między 1 a n. Oznaczmy ostatnią (r-tą) równość jako

n (r - 1) = p (r - 1) n (r)

Mając powyższy ciąg równości możemy wywnioskować, że

$n=p p' p'' p''' \ldots p^{(r-1)} n^{(r)}$

gdzie

$p, p', p'', \ldots, p^{(r-1)}$

są liczbamy pierwszymi. Wystarczy tylko udowodnić, że $n (r)$ jest liczbą pierwszą. Otóż gdyby nie było, to można by zapisać

n (r) = p (r) n (r + 1)

co oznaczałoby, że r-ta równość nie jest ostatnia. Dochodzimy do sprzeczności.

Lemat III

Jeżeli $a$ jest liczbą całkowitą, a $p$ liczbą pierwszą, to albo $a$ jest podzielne przez $p$ , albo $a$ i $p$ są względnie pierwsze

$p$ , jako liczba pierwsza, posiada tylko dwa dzielniki naturalne - $1$ i $p$ . Zatem albo $\operatorname{NWD}(a, p) = 1$ , albo $\operatorname{NWD}(a, p) = p$ . W pierwszym wypadku $a$ i $p$ są względnie pierwsze, w drugim $a$ dzieli $p$ .

Z tego lematu bezpośrednio wynika inne twierdzenie:

Jeżeli $p$ i $q$ są liczbami pierwszymi, to albo $\operatorname{NWD}(a, p) = 1$ , albo $p = q$ .

Twierdzenie

Każdą liczbę naturalną większą od jednego da się rozłożyć na czynniki pierwsze tylko w jeden sposób (jeśli nie uważamy za różne rozwinięć, które różnią się jedynie kolejnością czynników).

Niech $n$ będzie liczbą naturalną większą od jednego. Na mocy lematu II da się rozłożyć na czynniki pierwsze. Niech

$n=p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} ,\quad n=q_1^{\beta_1} q_2^{\beta_2} q_3^{\beta_3} \cdots q_l^{\beta_l}$

Gdyby żadna z liczb $q_1, q_2, \ldots, q_l$ nie była równa $p 1$ , to, ze względu na lemat III, wszystkie byłyby pierwsze względem $p 1$ . Liczba $n$ byłaby zatem iloczynem samych liczb pierwszych względem $p 1$ , więc sama była by pierwsza względem $p 1$ , co jest niemożliwe, gdyż $p 1$ dzieli $n$ w związku z pierwszym z wypisanych rozwinięć. Wynika z tego fakt, iż wśród liczb $q$ znajduje się liczba $p 1$ . Analogicznie można udowodnić, że wśród liczb $q$ znajduje się każda liczba ze zbioru $p$ i na odwrót.

Zbiory liczb $p$ i $q$ są zatem identyczne i jeżeli uporządkujemy je na przykład rosnąco, to będziemy mieli

$p_1=q_1, p_2=q_2, \ldots, p_k=p_l$

przy czym $k = l$ . Na koniec wystarczy udowodnić, że dla każdego $n \le k$ , $α n = β n$ . Otóż niech na przykład $α 1 < β 1$ . Wtedy $β 1 = α 1 + δ 1$ . Zatem:

$p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} = p_1^{\beta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_l^{\beta_l}$

$p_1^{\beta_1} = p_1^{\alpha_1 + \delta_1} = p_1^{\alpha_1} p_1^{\delta_1}$

$p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} = p_1^{\alpha_1} p_1^{\delta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_l^{\beta_l}$

Dzieląc obydwie strony równości przez $p_1^{\alpha_1}$ , otrzymujemy:

$p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} = p_1^{\delta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_l^{\beta_l}$

Prawa strona zawiera czynnik $p 1$ , więc jest przez niego podzielna, prawa strona z kolei, jako iloczyn liczb pierwszych różnych od $p 1$ , jest względnie pierwsza z $p 1$ , co jest sprzecznością. Niemożliwe jest zatem by $α 1 < β 1$ . W ten sam sposób można udowodnić, że niemożliwe jest również $β 1 < α 1$ , jak również $α n < β n$ dla każdego $n \le k$ .

Ciągi $p$ i $q$ są równe, jak również ciągi $α$ i $β$ , co znaczy, że obydwa rozkłady są identyczne, co było do okazania.

Uogólnienia

Zbiór liczb całkowitych tworzy pierścień przemienny. Podstawowe twierdzenie arytmetyki wyraża fakt, że pierścień ten jest pierścieniem z jednoznacznością rozkładu (pierścieniem Gaussa). Własność tę posiadają także pierścienie wielomianów – tam rolę elementów pierwszych odgrywają wielomiany nierozkładalne. Dla pierścienia $\mathbb C[x]$ jedynymi takimi wielomianami są wielomiany stopnia pierwszego – jest to treść zasadniczego twierdzenia algebry.

Twierdzenie o jednoznaczności rozkładu jest podstawą wielu metod matematyki i kryptografii.

Zobacz też

przegląd zagadnień z zakresu matematyki.

Przypisy

↑ I. W: Wacław Sierpiński: Teoria liczb. Wyd. trzecie. Warszawa: Wydawnictwo Uniwersytetu Wrocławskiego, 1950, ss. 8-10. (pl)

Źródło: „haslo,Podstawowe_twierdzenie_arytmetyki”

Kategorie: Arytmetyka • Teoria liczb