Dokaz da se prirodan broj može izraziti kao proizvod prostih brojeva

Pozdrav svima. Danas ćemo dokazati da se svaki prirodan broj veći od \(1\) može izraziti kao proizvod prostog broja i jedinice ili kao proizvod više prostih brojeva. Kao dokazni metod koristićemo metod matematičke indukcije. Teorema: Neka je \(n\) prirodan broj veći od \(1\). Tada \(n\) može da se izrazi kao proizvod jednog prostog broja i jedinice ili kao proizvod više prostih brojeva.  Dokaz: Primetimo da ukoliko je \(n\) prost broj tvrdnja je automatski dokazana jer svaki broj može da se zapiše kao proizvod tog broja i jedinice. 1. Baza indukcije (n=2) Kako je \(2\) prost broj tvrdnja je automatski dokazana. 2. Induktivna hipoteza (n=m) Pretpostavimo da važi:  \(\forall k \in \mathbb{N} , \quad 2 \le k \le m \) , \(k\) se može izraziti kao proizvod jednog prostog broja i jedinice ili kao proizvod više prostih brojeva.  3. Induktivni korak (n=m+1) Na osnovu pretpostavke iz drugog koraka dokažimo da važi: \(\forall k \in \mathbb{N} , \quad 2 \le k \le m+1 \) , \(k\) se može izraziti

Dokaz teoreme u vezi prostih Fibonačijevih brojeva

Pozdrav svima. Danas ćemo dokazati teoremu u vezi prostih Fibonačijevih brojeva. Kao dokazni metod koristićemo metod kontradikcije.

Teorema: Neka je \(F_n\) n-ti Fibonačijev broj i neka je \(F_n\) prost broj. Tada je \(n\) takođe prost broj, osim u slučaju \(F_4=3\) .

Dokaz:

Za slučaj kada je \(n=2\) imamo da je \(F_2=1\), a kao što znamo broj \(1\) nije ni prost ni složen, pa ovaj slučaj ne opovrgava istinitost teoreme.

Za slučaj kada je \(n=3\) imamo da je \(F_3=2\), pa je ovaj slučaj u skladu sa tvrđenjem.

Sada, pretpostavimo da je za \(n>4\) , \(F_n\) prost broj i da je \(n=rs\) za neke prirodne brojeve \(r,s\) veće od \(1\), odnosno da je \(n\) složen broj.

Kako je \(n>4\) to je bar jedan od brojeva \(r\) i \(s\) veći od \(2\). Tada na osnovu teoreme o deljivosti Fibonačijevih brojeva koja kaže: \[\forall m,n \in \mathbb{Z}_{>2} \quad m \mid n \Leftrightarrow F_m \mid F_n\] imamo da je bar jedan od izraza \(F_r \mid F_n\) i \(F_s \mid F_n\) tačan . Dalje, kako je bar jedan od brojeva \(r\) i \(s\) veći od \(2\), to je bar jedan od Fibonačijevih brojeva \(F_r\) i \(F_s\) veći od \(1\). Dakle, pokazali smo da broj \(F_n\) ima bar jedan delilac veći od \(1\) a manji od \(F_n\),odnosno pokazali smo da je \(F_n\) složen broj, tj. došli smo do kontradikcije. Odavde zaključujemo da \(n\) mora biti prost broj.

\(\blacksquare\)

Коментари

Популарни постови са овог блога

Dokaz da je koren iz 2 iracionalan broj

Dokaz da je koren iz prostog broja iracionalan broj

Algebarski dokaz Pitagorine teoreme