3360446516

Liczby pierwsze 19

to stosując indukcję. Dla n = 2 fakt jest prawdziwy. Załóżmy, że fakt jest prawdziwy dla wszystkich liczb naturalnych mniejszych od k . Jeżeli k jest liczbą pierwszą, to fakt jest prawdziwy. Jeśli k jest liczbą złożoną, to k = bc, gdzie b oraz c są liczbami mniejszymi od k . Z założenia indukcyjnego b = P1P2 ■ • • p_s oraz c = p_s+1p_s+2 ...pt. Stąd

k =PlP2---PsPs+l---Pt-

2. Teraz wykażemy jednoznaczność przedstawienia. Uczynimy to znowu stosując indukcję. Dla n = 2 twierdzenie jest prawdziwe. Załóżmy, że twierdzenie jest prawdziwe dla liczb naturalnych mniejszych od k . Przypuśćmy, że

k = PlPl ■ ■ - Pr = <7l?2 • • ■<?»>    (1)

gdzie pi , p2 , ..., p_r , q\ , q2 , ... , q_s są liczbami pierwszymi, takimi że

Pl < P2 < • • • < Pr, qi < 92 < • • • < q_S-

Ponieważ Pi\qiq2 • • • qs , więc pi\qi lub Pi\q2 , lub ... , lub pi\q_s (wynika to z zasadniczego twierdzenia arytmetyki). Niech na przykład pi\qi . Ponieważ p\ oraz q\ są liczbami pierwszymi, więc Pi = q\ . Dzieląc (1) przez pi mamy

k

— =P2P3---Pr =q2q3---Qs-Pl

Ponieważ ^ < k, więc z założenia indukcyjnego wynika, że r = s oraz

P2=q2, P3=q3, •••, Pr=q_r-

2.3.1. Pokaż, że każdą liczbę naturalną n > 2 można przedstawić w postaci

n = P?P? ...pf,    (2)

gdzie Pi , P2 , • ■ • i Ps są różnymi liczbami pierwszymi, takimi że pi < p2 < • • • < p_s , natomiast ai , (*2 , ... , a_s są liczbami całkowitymi dodatnimi. (Rozkład (2) liczby naturalnej n nazywamy rozkładem kanonicznym liczby n na czynniki pierwsze).