3386. Deljivost celih brojeva

TEKST ZADATKA

Da li je broj $2^{100} - 1$ prost ili složen?

REŠENJE ZADATKA

Prirodan broj veći od 1 je složen ako se može zapisati kao proizvod dva prirodna broja koja su veća od 1. Pokušaćemo da rastavimo dati izraz na činioce.

Broj $2^{100}$ možemo zapisati kao kvadrat broja $2^{50} ,$ koristeći pravilo za stepenovanje $(x^m)^n = x^{m \cdot n} .$

2^{100} = (2^{50})^2

Sada dati izraz možemo zapisati kao razliku kvadrata.

2^{100} - 1 = (2^{50})^2 - 1^2

Primenjujemo formulu za razliku kvadrata: $a^2 - b^2 = (a - b)(a + b) .$

(2^{50})^2 - 1^2 = (2^{50} - 1)(2^{50} + 1)

Analizirajmo dobijene činioce. Pošto je $2^{50}$ broj koji je znatno veći od 2, važi da su oba činioca strogo veća od 1.

2^{50} - 1 > 1 \quad \text{i} \quad 2^{50} + 1 > 1

Pošto se broj $2^{100} - 1$ može predstaviti kao proizvod dva prirodna broja koja su veća od 1, zaključujemo da je on složen broj.

176