3374. Prosti brojevi i rastavljanje na proste činioce

TEKST ZADATKA

Neka je $p$ prost broj, $p > 3 .$ Odrediti ostatak koji broj $p^2$ daje pri deljenju sa 3.

REŠENJE ZADATKA

Pošto je $p$ prost broj veći od 3, on ne može biti deljiv sa 3 (jedini prost broj deljiv sa 3 je sam broj 3).

Prema teoremi o deljenju sa ostatkom, svaki prirodan broj se pri deljenju sa 3 može zapisati u obliku $3k ,$ $3k+1$ ili $3k+2 ,$ gde je $k$ ceo broj.

Kako $p$ nije deljiv sa 3, on mora davati ostatak 1 ili 2 pri deljenju sa 3.

p \in \{3k+1, 3k+2\}

Razmotrimo prvi slučaj, kada je $p = 3k+1 .$ Kvadriramo ovaj izraz.

p^2 = (3k+1)^2

Primenjujemo formulu za kvadrat binoma i izdvajamo 3 ispred zagrade iz prva dva člana.

p^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1

Neka je $q_1 = 3k^2 + 2k .$ Vidimo da se $p^2$ može zapisati u obliku $3q_1 + 1 ,$ što znači da daje ostatak 1 pri deljenju sa 3.

p^2 = 3q_1 + 1

Razmotrimo sada drugi slučaj, kada je $p = 3k+2 .$ Kvadriramo izraz.

p^2 = (3k+2)^2

Primenjujemo kvadrat binoma. Broj 4 možemo zapisati kao $3 + 1$ kako bismo izdvojili 3 ispred zagrade.

p^2 = 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 = 3(3k^2 + 4k + 1) + 1

Neka je $q_2 = 3k^2 + 4k + 1 .$ Vidimo da se i u ovom slučaju $p^2$ može zapisati u obliku $3q_2 + 1 ,$ pa je ostatak ponovo 1.

p^2 = 3q_2 + 1

Zaključujemo da u oba moguća slučaja broj $p^2$ daje isti ostatak pri deljenju sa 3.

r = 1

181.a