4. Zadatak

Neka je $n$ prirodan broj čiji je kvadrat jednak izrazu iz zadatka, tj.

$$p^{q-1}+q^{p-1}=n^2.$$

Podijelit ćemo zadatak na odvojene slučajeve prema parnosti brojeva $p$ i $q$.

Ako su oba broja parna, jedina je mogućnost da su oba jednaka $2$. Tada dobivamo rješenje $(p,q)=(2,2)$ za $n=2$.

Ako su oba broja $p$ i $q$ neparna, tada gledajući ostatak pri dijeljenju s $4$ zaključujemo da nema rješenja. Doista, kako su $p$ i $q$ neparni, brojevi $p-1$ i $q-1$ su parni, pa su brojevi $p^{q-1}$ i $q^{p-1}$ kvadrati neparnih brojeva, za koje znamo da uvijek daju ostatak $1$ pri dijeljenju s $4$. Stoga lijeva strana daje ostatak $2$ pri dijeljenju s $4$, dok $n^2$ daje ostatak $1$ ili $0$ pri dijeljenju s $4$.

Preostaje slučaj da je jedan od brojeva $p,q$ paran, a drugi neparan. Budući da je jednadžba simetrična, bez smanjenja općenitosti možemo pretpostaviti da je $p$ neparan, oblika $p=2k+1$ za prirodan broj $k$, a $q=2$. Sada imamo

$$p+2^{2k}=n^2,$$

odnosno

$$p=n^2-2^{2k}=(n-2^k)(n+2^k).$$

Desna strana jednakosti sastoji se od dva faktora kojima je umnožak prost broj. To je moguće samo ako je jedan faktor jednak $\pm1$, a drugi $\pm p$. Budući da je $n+2^k>0$ i $n+2^k>n-2^k$, nužno je

$$n-2^k=1\quad\text{i}\quad n+2^k=p.$$

Oduzimanjem tih dviju jednakosti dobivamo

$$2^{k+1}+1=p=2k+1.$$

Dokažimo da ova jednadžba nema rješenja. Broj $2^{k+1}+1$, pa onda i broj $2k+1$, daje ostatak $1$ pri dijeljenju s $4$, odakle je nužno $k$ paran broj, tj. $k=2l$ za neki nenegativan cijeli broj $l$. No tada je

$$p=2^{k+1}+1=2^{2l+1}+1=2\cdot4^l+1$$

djeljiv s $3$, jer $4^l$ daje ostatak $1$ pri dijeljenju s $3$. Dakle, $p$ je djeljiv s $3$, pa je $p=3$. Uvrštavanjem u početnu jednadžbu vidimo da $(p,q)=(3,2)$ nije rješenje.

Stoga je jedino rješenje

$$(p,q)=(2,2).$$

Napomena. Drugi način dokaza da jednadžba

$$2^{k+1}+1=p=2k+1$$

nema rješenja jest pokazati nejednakost $2^{k+1}+1>2k+1$, tj. $2^k>k$ za sve prirodne brojeve $k$. To možemo pokazati matematičkom indukcijom ili višestrukom uporabom nejednakosti $2^a\ge a+1$:

$$\begin{aligned} 2^k&=2\cdot2^{k-1}\ge2^{k-1}+1=2\cdot2^{k-2}+1\\ &\ge2^{k-2}+2\ge\cdots\ge2^1+k-1=k+1>k. \end{aligned}$$

Nejednakost $2^k>k$ može se dokazati i kombinatornim argumentom, uočavajući da je ukupan broj podskupova uvijek veći od broja jednočlanih podskupova $k$-članog skupa.

Slučaj kada su oba prosta broja $p,q$ neparna možemo riješiti i tako da uočimo da su brojevi $p^{q-1}$ i $q^{p-1}$ kvadrati, pa je

$$\left(p^{\frac{q-1}{2}},q^{\frac{p-1}{2}},n\right)$$

Pitagorina trojka u kojoj su prva dva broja neparna, što je nemoguće.

Alternativno, možemo pisati

$$p^{q-1}=\left(n-q^{\frac{p-1}{2}}\right)\left(n+q^{\frac{p-1}{2}}\right).$$

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 $n=q^{\frac{p-1}{2}}+1$. Mijenjajući uloge za $p$ i $q$, zaključujemo i da je $n=p^{\frac{q-1}{2}}+1$, pa dobivamo

$$p^{\frac{q-1}{2}}=n-1=q^{\frac{p-1}{2}}.$$

Iz toga slijedi $p=q$, a uvrštavanjem u početnu jednadžbu dobivamo $2p^{p-1}=n^2$, što nema rješenja za neparan $p$.