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 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 2 iracionalan broj

Dokaz da je koren iz prostog broja iracionalan broj

Algebarski dokaz Pitagorine teoreme