section_heading: Konstrukcija
paragraph_text: Pretpostavimo zato da se <math>n</math> može prikazati kao <math> n = k \cdot l </math> gdje je <math> k \in \mathbb{N} </math> moguće potpuno faktorizirati kao u iskazu, a <math> l \in \mathbb{N} </math> barem jedan djelitelj broja <math>n</math> koji se ne može potpuno faktorizirati. Zbog pretpostavke mora vrijediti da je <math> l </math> složen, tj. <math> l </math> sadrži barem 2 faktora veća od <math> 1 </math>: <math> l = ab</math> za <math>a, b \in \{2, 3, ...\}. </math> No sada se, slično, <math>a</math> i <math>b </math> ne mogu prikazati kao u iskazu pa su složeni, tj. možemo pisati <math> l = a_1 \cdot a_2 \cdot b_1 \cdot b_2 </math> (vrijedi <math> a = a_1a_2</math>, <math>b = b_1b_2 </math>). No, taj proces bismo onda mogli ponoviti za <math> a_1</math>, <math>a_2</math>, <math>b_1</math> i <math>b_2</math>. Prema tome, da pretpostavka vrijedi ovaj algoritam ne bi imao kraja, što znači da bi <math> n </math> bio beskonačno velik. To je u kontradikciji s činjenicom da je <math> n </math> prirodan broj. Prema tome u nekom trenutku se mora dogoditi da se neki faktor <math> x </math> broja <math> n </math> ne može dodatno rastavljati (osim na trivijalan način, <math> x = x \cdot 1 </math>), a to je jedino moguće ako je taj posljednji faktor <math> x </math> u algoritmu prost broj. Naravno neki faktori se mogu i ponavljati. Poredak faktora je proizvoljan zbog komutativnosti množenja. Time smo konstruirali navedeni rastav broja <math> n </math>.