Državno natjecanje 2018., 2. razred SŠ, A varijanta, 4. Zadatak
Odredi sve parove prostih brojeva za koje je kvadrat prirodnog broja.
Rješenje
Neka je prirodni broj čiji je kvadrat jednak izrazu iz zadatka, tj.
Podijelit ćemo zadatak na odvojene slučajeve prema parnosti brojeva i .
Ako su oba broja parna, jedina mogućnost je da su oba . Tada dobivamo rješenje za .
Ako su oba broja neparna, tada gledajući ostatak pri dijeljenju s zaključujemo da nema rješenja. Doista, kako su neparni, brojevi su parni, pa su brojevi kvadrati neparnih brojeva, za koje znamo da uvijek daju ostatak pri dijeljenju s . Stoga lijeva strana daje ostatak pri dijeljenju s , dok daje ostatak ili pri dijeljenju sa .
Jedini preostali slučaj je da je jedan od brojeva paran, a drugi neparan. Budući da je jednadžba simetrična, bez smanjenja općenitosti možemo pretpostaviti da je neparan, oblika za prirodni broj , a . Sada imamo jednadžbu
tj.
Desna strana jednakosti sastoji se od dva faktora kojima je umnožak prost broj. To je jedino moguće ako je jedan od faktora jednak , a drugi . Također, uočimo da je , te da je , pa nužno mora biti
Oduzimanjem zadnjih dviju jednadžbi dobivamo
Dokažimo da ova jednadžba nema rješenja. Broj , pa onda i broj , daje ostatak pri dijeljenju s , odakle je nužno paran broj, tj. , za neki nenegativan cijeli broj . No, u tom slučaju, broj
je djeljiv s (jer daje ostatak pri dijeljenju s ). Dakle, je djeljiv s , tj. . Uvrštavanjem u početnu jednadžbu, vidimo da u i nije rješenje.
Stoga, jedino rješenje je
Napomena. Drugi način dokaza da jednadžba
nema rješenja je da se pokaže da vrijedi nejednakost , tj. za sve prirodne brojeve . To možemo pokazati matematičkom indukcijom ili višestrukom upotrebom nejednakosti :
Nejednakost se može dokazati i kombinatornim argumentom, uočavajući da je ukupan broj podskupova uvijek veći od broja jednočlanih podskupova -članog skupa.
Slučaj kad su oba prosta broja neparna, možemo riješiti tako da uočimo da su brojevi kvadrati, pa je
Pitagorina trojka u kojoj su prva dva broja neparna, što je nemoguće.
Alternativno, možemo pisati
Budući da možemo pokazati da su faktori na desnoj strani relativno prosti, sličnim argumentima kao u rješenju zaključujemo da je . Mijenjajući uloge za i , možemo zaključiti i da je , pa dobivamo jednakost
Iz toga slijedi , pa uvrštavajući to u originalnu jednadžbu dobivamo , što nema rješenja za neparan .