Teorija brojeva - deljivost i prosti brojevi - zadaci sa rešenjima

Rešenje:
Za [tex]n\ge 5[/tex] proizvod [tex]n!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot \ldots\cdot n[/tex] sadrži činioce [tex]2[/tex] i [tex]5[/tex], pa je deljiv sa [tex]10[/tex] i završava se cifrom [tex]0[/tex]. Zato sabirci od [tex]5![/tex] do [tex]2018![/tex] ne utiču na poslednju cifru broja [tex]P[/tex], i ona je jednaka poslednjoj cifri zbira
[tex]1!+2!+3!+4!=1+2+6+24=33[/tex]
Dakle, poslednja cifra broja [tex]P[/tex] je [tex]3[/tex].

Rešenje:
Poslednja cifra proizvoda zavisi samo od poslednjih cifara činilaca, pa se [tex]237^{127}[/tex] završava istom cifrom kao [tex]7^{127}[/tex]. Prvi stepeni broja [tex]7[/tex] su
[tex]7^1=7,\quad 7^2=49,\quad 7^3=343,\quad 7^4=2401[/tex]
Njihove poslednje cifre su [tex]7[/tex], [tex]9[/tex], [tex]3[/tex], [tex]1[/tex], a zatim se ponavljaju s periodom [tex]4[/tex], jer se množenjem broja koji se završava cifrom [tex]1[/tex] brojem [tex]7[/tex] ponovo dobija broj koji se završava cifrom [tex]7[/tex]. Pošto je [tex]127=4\cdot 31+3[/tex], važi
[tex]7^{127}=\left(7^4\right)^{31}\cdot 7^3[/tex]
Činilac [tex]\left(7^4\right)^{31}[/tex] se završava cifrom [tex]1[/tex], a [tex]7^3=343[/tex] cifrom [tex]3[/tex], pa se [tex]7^{127}[/tex] završava cifrom [tex]3[/tex]. Dakle, poslednja cifra broja [tex]237^{127}[/tex] je [tex]3[/tex].

Rešenje:
Neka je [tex]k[/tex] traženi broj godina. Sada uzrast [tex]1[/tex] nije prost broj, pa je [tex]k\ge 1[/tex]. Svi sadašnji uzrasti su neparni. Ako je [tex]k[/tex] neparno, svi novi uzrasti su parni, a [tex]3+k\ge 4[/tex] je paran broj veći od [tex]2[/tex], pa nije prost. Dakle, [tex]k[/tex] je parno.
Za [tex]k=2[/tex] uzrasti su [tex]3; 5; 9; 11; 15; 17[/tex], a [tex]9=3\cdot 3[/tex] nije prost broj.
Za [tex]k=4[/tex] uzrasti su [tex]5; 7; 11; 13; 17; 19[/tex], i svi su prosti brojevi.
Prema tome, najmanji broj godina je [tex]4[/tex].

Rešenje:
Izvucimo ispred zagrade najmanji stepen broja [tex]3[/tex]:
[tex]3^{2016}+3^{2017}+3^{2019}=3^{2016}\left(1+3+3^{3}\right)=31\cdot 3^{2016}[/tex]
Pošto je [tex]31[/tex] prost broj, svaki delilac datog broja ima oblik [tex]3^{k}[/tex] ili [tex]31\cdot 3^{k}[/tex], gde je [tex]0\le k\le 2016[/tex]. Dvocifreni delioci oblika [tex]3^{k}[/tex] su [tex]27[/tex] i [tex]81[/tex]. Dvocifreni delioci oblika [tex]31\cdot 3^{k}[/tex] su [tex]31[/tex] i [tex]93[/tex], jer je već [tex]31\cdot 9=279[/tex] trocifren broj.
Najveći od njih je [tex]93[/tex].

Rešenje:
Stranice su numerisane od [tex]1[/tex], pa svaki list ima neparnu stranicu s prednje strane i sledeću parnu stranicu s poleđine. Iscepani deo počinje stranicom [tex]387[/tex] (neparnom, tj. prednjom stranom lista) i završava se poleđinom lista, pa poslednja iscepana stranica ima paran broj veći od [tex]387[/tex].
Ostali brojevi zapisani ciframa [tex]3[/tex], [tex]8[/tex] i [tex]7[/tex] su [tex]378; 738; 783; 837; 873[/tex]. Broj [tex]378[/tex] je manji od [tex]387[/tex], a [tex]783[/tex], [tex]837[/tex], [tex]873[/tex] su neparni, pa je poslednja iscepana stranica [tex]738[/tex]. Petar je iscepao sve stranice od [tex]387[/tex] do [tex]738[/tex] uključno, a njihov broj je
[tex]738-387+1=352[/tex]

Rešenje:
Zapišimo broj u obliku [tex]a=2007q+99[/tex], gde je [tex]q\ge 0[/tex] ceo broj. Brojevi [tex]a[/tex] i [tex]99[/tex] su neparni, pa je [tex]2007q=a-99[/tex] paran; pošto je [tex]2007[/tex] neparan, [tex]q[/tex] je paran, [tex]q=2s[/tex]. Tada je
[tex]a=4014s+99=18\cdot 223s+18\cdot 5+9=18\left(223s+5\right)+9[/tex]
Pošto je [tex]0\le 9\lt 18[/tex], ostatak pri deljenju broja [tex]a[/tex] sa [tex]18[/tex] je [tex]9[/tex].

Rešenje:
Broj sa [tex]k[/tex] cifara ima zbir cifara najviše [tex]9k[/tex], a [tex]9\cdot 223=2007\lt 2015[/tex], pa traženi broj ima bar [tex]224[/tex] cifre. Brojevi sa [tex]224[/tex] cifre i zbirom cifara [tex]2015[/tex] postoje (jedan je naveden niže), a svaki broj sa više cifara je veći, pa najmanji takav broj ima tačno [tex]224[/tex] cifre.
Od dva broja sa istim brojem cifara manji je onaj čija je prva cifra manja. Preostale [tex]223[/tex] cifre imaju zbir najviše [tex]2007[/tex], pa je prva cifra bar [tex]2015-2007=8[/tex]. Prva cifra je [tex]8[/tex] samo ako su sve preostale [tex]223[/tex] cifre jednake [tex]9[/tex], što daje tačno jedan broj:
[tex]8\underbrace{99\ldots 9}_{223}[/tex]
Njegova cifra jedinica je [tex]9[/tex].

Rešenje:
Pretpostavimo suprotno: svaka od deset cifara [tex]0; 1; \ldots; 9[/tex] javlja se najviše [tex]10[/tex] puta. Tada [tex]A[/tex] ima najviše [tex]10\cdot 10=100[/tex] cifara. Pošto [tex]A[/tex] ima tačno [tex]100[/tex] cifara, važi jednakost, tj. svaka cifra se javlja tačno [tex]10[/tex] puta. Tada je zbir cifara broja [tex]A[/tex]
[tex]10\cdot \left(0+1+2+\ldots+9\right)=10\cdot 45=450[/tex]
Ovaj zbir je deljiv sa [tex]3[/tex], pa je prema pravilu deljivosti sa [tex]3[/tex] i broj [tex]A[/tex] deljiv sa [tex]3[/tex]. Ali [tex]A=2^{332}[/tex] nema prostih delilaca osim [tex]2[/tex], što je kontradikcija. Dakle, bar jedna cifra se javlja bar [tex]11[/tex] puta.

Rešenje:
Neka je [tex]p[/tex] takav prost broj. Pošto je [tex]p[/tex] zbir dva prosta broja, [tex]p\ge 2+2=4[/tex], pa je [tex]p[/tex] neparan i [tex]p\ge 5[/tex]. Zbir dva prosta broja je neparan samo ako je jedan od njih paran prost broj [tex]2[/tex]; zato je [tex]p=q+2[/tex], gde je [tex]q[/tex] prost, tj. [tex]p-2[/tex] je prost broj.
Iz [tex]p=s-t[/tex], gde su [tex]s[/tex] i [tex]t[/tex] prosti, dobijamo [tex]s=p+t\gt p\ge 5[/tex], pa je [tex]s[/tex] neparan; tada je [tex]t=s-p[/tex] paran, tj. [tex]t=2[/tex], i [tex]p+2=s[/tex] je prost broj.
Dakle, [tex]p-2[/tex], [tex]p[/tex] i [tex]p+2[/tex] su prosti brojevi. Pošto je [tex]p-2\equiv p+1\pmod 3[/tex], ova tri broja pri deljenju sa [tex]3[/tex] daju iste ostatke kao uzastopni brojevi [tex]p[/tex], [tex]p+1[/tex], [tex]p+2[/tex], tj. ostatke [tex]0[/tex], [tex]1[/tex] i [tex]2[/tex]. Zato je jedan od njih deljiv sa [tex]3[/tex] i, kao prost broj, jednak je [tex]3[/tex]. Pošto je [tex]p\ge 5[/tex], jedina mogućnost je [tex]p-2=3[/tex], tj. [tex]p=5[/tex]. Provera:
[tex]5=2+3,\quad 5=7-2[/tex]
Prema tome, [tex]5[/tex] je jedini takav prost broj.

Rešenje:
Svaki razlomak je oblika [tex]\frac{k}{n+k+2}[/tex], gde je [tex]k=19; 20; \ldots; 91[/tex]. Svaki zajednički delilac brojeva [tex]k[/tex] i [tex]n+k+2[/tex] deli i njihovu razliku [tex]n+2[/tex], i obrnuto, pa je
[tex]\text{NZD}(k; n+k+2)=\text{NZD}(k; n+2)[/tex]
Dakle, svi razlomci su nesvodljivi tačno onda kada je [tex]n+2[/tex] uzajamno prost sa svakim od brojeva [tex]19; 20; \ldots; 91[/tex].
Neka je [tex]p[/tex] prost delilac broja [tex]n+2[/tex] (postoji, jer je [tex]n+2\ge 3[/tex]). Ako je [tex]19\le p\le 91[/tex], onda je sam broj [tex]p[/tex] jedan od brojilaca. Ako je [tex]p\lt 19[/tex], onda među [tex]73[/tex] uzastopna broja [tex]19; 20; \ldots; 91[/tex] postoji sadržalac broja [tex]p[/tex]. U oba slučaja neki od razlomaka može se skratiti sa [tex]p[/tex].
Prema tome, svaki prost delilac broja [tex]n+2[/tex] veći je od [tex]91[/tex], a najmanji prost broj veći od [tex]91[/tex] je [tex]97[/tex]. Zato je
[tex]n+2\ge 97\Rightarrow n\ge 95[/tex]
Za [tex]n=95[/tex] imamo [tex]n+2=97[/tex], prost broj koji ne deli nijedan od brojeva [tex]19; 20; \ldots; 91[/tex], pa su svi razlomci nesvodljivi. Odgovor: [tex]n=95[/tex].