Jedan zadatak iz teorije brojeva

Jedan zadatak iz teorije brojeva 10.07.2005. u 15:06 · pre 259 meseci #1

Sa svaki prirodan broj $k$ postoji prirodan broj $n$ takav da je $n\cdot 2^k+17$ potpun kvadrat. Dokazati.

Nikako ne uspevam da ga resim. Pomozite!

Re: Jedan zadatak iz teorije brojeva 13.07.2005. u 08:11 · pre 259 meseci #2

Primetimo prvo da ako za neko $y$ važi $n\cdot 2^k+17=y^2$ , onda je $y$ neparno (jer je $k>0$ ).
Posmatrajmo sada niz $a_n=(2n+1)^2$ , za $n=0,1,2,\ldots$
Pogledajmo razliku $a_d-a_0=(2d+1)^2-1=4d(d+1)$ .
Traženu jednačinu možemo zapisati kao $4(m\cdot2^k+4)=y^2-1^2$ , gde smo uzeli da je $n:=4m$ . Pošto je desna strana jednaka razlici dva neparna kvadrata, dobijamo da za neko $d$ važi $4(m\cdot2^k+4)=4d(d+1)$ , tj. $m\cdot2^k+4=d(d+1)$ , dakle dovoljno je dokazati da jednačina $d(d+1)\equiv 4\pmod {2^k}$ ima rešenja po $d$ .

Dokazaćemo da jednačina $d(d+1)\equiv a\pmod {2^k}$ ima rešenja za svako $a\in P:=\{a\quad |\quad 0\leq a <2^k\quad\wedge\quad a\equiv 0\pmod 2\}$ .

Neka je $f(x):=x(x+1)\pmod {2^k}$ i neka je $S:=\{0,1,\ldots,2^{k-1}-1\}$ . Pokazaćemo da je $f(S)=P$ .

Pre svega, jasno je da važi $f(S)\subseteq P$ , jer je $f$ proizvod jednog parnog i jednog neparnog broja.

Dokažimo još i injektivnost f-je $f$ na skupu $S$ .

Neka za neke $x_1,x_2\in S$ važi $f(x_1)=f(x_2)$ , tj. $x_1(x_1+1)\equiv x_2(x_2+1)\pmod {2^k}$ , odnosno $(x_1-x_2)(x_1+x_2+1)\equiv 0\pmod {2^k}$ .

Ako su $x_1$ i $x_2$ iste parnosti, onda je broj $1+x_1+x_2$ neparan, pa mora biti da $2^k\vert (x_1-x_2)$ , ali pošto je $x_1,x_2\in S$ , važi procena $0\leq\left|x_1-x_2\right|<2^{k-1}$ , pa mora biti $x_1=x_2$ .

Ako $x_1$ i $x_2$ nisu iste parnosti, onda je $x_1-x_2$ neparan, pa mora biti $2^k | x_1+x_2+1$ , a to je nemoguće zbog procene $x_1+x_2+1\leq 2^{k-1}-1+2^{k-1}-2+1=2^k-2$ (različita parnost je uzeta u obzir u ovoj proceni).

Pošto je $f$ injektivna to je $\left|f(S)\right|=\left|S\right|=2^{k-1}$ , pa iz $\left|P\right|=2^{k-1}$ i $f(S)\subseteq P$ sledi $f(S)=P$ a time i samo tvrđenje.

Možemo primetiti još i to da je sada lako pokazati da za dato $k$ postoji beskonačno mnogo prirodnih $n$ za koje važi tvrđenje.

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Jedan zadatak iz teorije brojeva 14.07.2005. u 21:21 · pre 259 meseci #3

Hvala ti puno, pogledacu resenje detaljnije ovih dana.

Forum kao aplikacija na telefonu

Srodne teme