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 su susedni Fibonačijevi brojevi uzajamno prosti

Pozdrav svima. Danas ćemo dokazati da su susedni Fibonačijevi brojevi uzajamno prosti. Kao dokazni metod koristićemo metod matematičke indukcije.

Teorema: Neka \(F_n\) predstavlja n-ti Fibonačijev broj. Tada važi: \[\forall n \ge 2 , \quad \operatorname{NZD}\left(F_n,F_{n+1}\right)=1\]

Dokaz:

1. Baza indukcije (n=2)

\[\operatorname{NZD}\left(F_2,F_{3}\right)=\operatorname{NZD}(1,2)=1\]

2. Induktivna hipoteza (n=m)

Pretpostavimo da važi:

\[\operatorname{NZD}\left(F_m,F_{m+1}\right)=1\]

3. Induktivni korak (n=m+1)

Koristeći pretpostavku iz drugog koraka dokažimo da važi:

\[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=1\]

Kako je najveći zajednički delilac bilo kojih prirodnih brojeva \(a\) i \(b\) jednak najvećem zajedničkom deliocu bilo koje linearne kombinacije brojeva \(a\) i \(b\) imamo da je \(\operatorname{NZD}(a,b)=\operatorname{NZD}(a,b-a)\) . Imajući ovo u vidu možemo zapisati sledeću jednakost: \[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=\operatorname{NZD}\left(F_{m+1},F_{m+2}-F_{m+1}\right)\]

Dalje, kako je po definiciji Fibonačijevog niza \(F_{m+2}=F_{m}+F_{m+1}\) imamo da je: \[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=\operatorname{NZD}\left(F_{m+1},F_{m}\right)\]\[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=\operatorname{NZD}\left(F_{m},F_{m+1}\right)=1\]

\(\blacksquare\)

Коментари

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

Dokaz da je koren iz prostog broja iracionalan broj

Dokaz da je koren iz 2 iracionalan broj

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