Dokaz da je skup prostih brojeva beskonačan

 Pozdrav svima. Danas ćemo dokazati da je skup prostih brojeva beskonačan. Kao dokazni metod koristićemo metod kontradikcije. Takođe ćemo upotrebiti teoremu francuskog matematičara Eduarda Lukasa. Teorema (Lukas): Svaki prost faktor Fermaovog broja \(F_n=2^{2^n}+1\) ; (\(n>1\)) je oblika \(k2^{n+2}+1\) . Teorema: Skup prostih brojeva je beskonačan. Dokaz: Pretpostavimo suprotno, da postoji samo konačno mnogo prostih brojeva i označimo najveći prosti broj sa \(p\) . Tada je \(F_p\) sigurno složen broj jer je \(F_p > p\) . Na osnovu Lukasove teoreme znamo da postoji prost broj \(q\) koji je oblika   \(k2^{p+2}+1\)  i koji deli broj \(F_p\). Ali \(q > p\) što je u kontradikciji sa polaznom pretpostavkom. Dakle, skup prostih brojeva je beskonačan . \(\blacksquare\)

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 kao proizvod jednog prostog broja i jedinice ili kao proizvod više prostih brojeva. 

Za sve \(k\)-ove manje od \(m+1\) istinitost tvrdnje automatski sledi iz induktivne hipoteze. Razmotrimo sada slučal kada je \(k=m+1\). Ukoliko je \(m+1\) prost broj tvrdnja je automatski dokazana. U suprotnom \(m+1\) je složen broj i može da se izrazi u obliku \(m+1=pq\) , gde su \(p\) i \(q\) prirodni brojevi takvi da \(2 \le p <m+1\) i \(2 \le q <m+1\) , tj. \(2 \le p \le m\) i \(2 \le q \le m\) . Kako prema induktivnoj hipotezi oba broja \(p\) i \(q\) mogu da se izraze kao proizvodi prostih brojeva ili proizvodi prostog broja i jedinice to isto važi i za broj \(m+1\) .

\(\blacksquare\)

Коментари

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

Dokaz da je koren iz prostog broja iracionalan broj

Dokaz da je koren iz 2 iracionalan broj