3. Zadatak
Marijan je na ploču napisao niz od prostih brojeva tako da je svaki sljedeći broj za veći od prethodnog.
Dokaži da postoji najveći prirodan broj za koji je to moguće. Koji je to najveći i koje je sve nizove Marijan mogao napisati na ploču za taj najveći ?
Dokažimo da je najveći takav jednak , te da postoji samo jedan niz duljine :
Promotrimo prvih brojeva bilo kojeg takvog niza s barem elemenata.
Promotrimo ostatke koje ti brojevi daju pri dijeljenju s .
Kako je svaki sljedeći za veći od prethodnog, ostatak koji sljedeći član niza daje pri dijeljenju s za jedan je veći od prethodnog, ili je taj broj djeljiv s (ako prethodni daje ostatak pri dijeljenju s ).
Zato zaključujemo da je jedan od prvih brojeva niza nužno djeljiv s : ili se takav nalazi među prva broja, ili prva broja daju redom ostatke , , , pri dijeljenju s , pa je peti član djeljiv s .
Broj jedini je prost broj djeljiv s , te se mora naći među prvih brojeva. No, kako broj nije prost, broj nužno je prvi član tog niza.
Zato su prvih članova svakog Marijanovog niza od barem elemenata redom brojevi
Svi brojevi su prosti, pa zaključujemo da je to jedini niz od elemenata.
Kada bi niz imao ili više elemenata, šesti član niza morao bi biti jednak , što nije prost broj. Zato je najveći takav jednak .