104314

Zasadnicze twierdzenie arytmetyki

Dla każdej liczby naturalnej n > 1 istnieje dokładnie jeden ciąg liczb pierwszych qi,..., oraz ciąg liczb większych od 0 ai,..., a* taki, że qi < ... < q_m oraz n = q** •... • q_m^J,“

Vn Vm (n | m <=><» 3k k • n = m)

n | m jeśli dzielenie m przez n jest wykonalne w świecie liczb naturalnych.

Lemat 1. Vn [n > 1 => 3p (p jest liczbą pierwszą a p | n)] l emat 2. Vn Vm [(n | m a m * 0) => n < m]

Lemat 3. Va Vb Vp [(a > 1 a b > 1 a p jest liczbą pierwszą a p | a • b) => (p | a v p | b)] Dowód lematu 3. Przypuśćmy niewprost, że tak nie jest Zatem istnieją liczby naturalne a, b > 1 i liczba pierwsza p takie, że p | a • b, ~ p | a oraz ~ p | b. Na mocy zasady minimum istnieje najmniejsza liczba pierwsza taka, że p | a ■ b, ~ p | a oraz ~ p | b. Niech p będzie tą liczbą.

Zał. ind.: Na mocy zasady minimum istnieje najmniejszy iloczyn a • b taki, że p | a • b, ~ p | a i ~ p | b. Niech a • b będzie tym iloczynem.

Uwaga: a • b < p²

Dow ód Uwagi. Przypuśćmy niewprost, że a • b > p². Wówczas a > p lub b > p. Bez utraty ogólności można przyjąć, że a £ p. Istnieją zatem liczby całkowite k, r takie, że a = k • p + r, gdzie k > 1 oraz 0 < r < p. Wówczas a • b = (k • p + r) • b = (k • p) • b + r • b. Tymczasem p | r • b oraz r • b < a • b, stąd p | r lub p | b. Wiadomo, że ~ p | b, więc p | r, co jest niemożliwe, gdyż p>r.

Skoro p | a - b, to istnieje liczba całkowita d > 1 taka, że a • b = p • d. Zatem istnieje liczba pierwsza q taka, że q | d. Stąd q | a • b. Z Uwagi wynika, że q < p, czyli q | a lub q | b. Bez utraty ogólności (ze względu na symetrię) można przyjąć, że q | a. Zatem istnieje liczba całkowita a’ taka, że a = q • a'. Wówczas a' ■ b < a • b. Zatem p | a’ • b, gdyż a • b = p • d = p • k • q, gdzie k jest pewną liczbą całkowitą. Stąd a • b = a’ • b • q, więc a' • b = p • k. To dowodzi, że p | a’ • b. Zatem (z zał. ind.) p | a' lub p | b, czyli p | a lub p | b, co jest sprzeczne z założeniem.

Dowód tw ierdzenia.

1.    Istnienie. Niech n > 1 będzie liczbą taką, że dla każdego k < n teza twierdzenia zachodzi (k ma jednoznaczną reprezentację jako iloczyn potęg liczb pierwszych). Na mocy lematu 1 istnieje liczba pierwsza p taka, że p | n. Wówczas niech k będzie liczbą taką, że p • k = n. Albo k = 1, wtedy n = p¹, albo k > 1, wówczas k < n i na mocy założenia indukcyjnego k ma reprezentację postaci qi^ł| •... • q_m*". Wówczas n = p • qi⁴' •... • q_n⁴". Wynika stąd istnienie.

2.    Jednoznaczność. Przypuśćmy, że liczba n ma dwie różne interpretacje: qi < ... < q_m oraz n <... < r,,, są ciągami liczb pierwszych takimi, że q_t^ł| •... • q_m^ = n = ri^b| •... • r^b'. Zauważmy, że qi | n, więc na mocy lematu 3 istnieje i = 1, 2,..., / takie, że qi | ri^b‘, co więcej qi | r_u czyli qi = r„ ponieważ qi i r, są pierwsze. Zatem k = qi'^rl •... • q_m^4- = ri^b| •... • r/*"¹ •... • r^b' < n. Teza twierdzenia prawdziwa dla k, więc obie reprezentacje muszą być identyczne, i = 1, m = / oraz dla j = 1,..., m mamy qj = Tj oraz aj = b,, skąd wynika jednoznaczność.