[Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu)

Odgovori Nova tema

8 odgovora
10.437 pregleda

[Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 30.05.2005. u 18:52 · pre 261 mesec #1

Dokazati da se za svaki prost broj $p\geq5$ i ceo broj $a$ , $p\not| a$ , mogu naći celi brojevi $x,y,z$ takvi da nijedan od njih nije deljiv sa $p$ i da je $a\equiv x^2+y^2+z^2\ (\hbox{mod }p)$ .

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 18.08.2005. u 03:39 · pre 258 meseci #2

Dokazaću malo opštije tvrđenje, zbog čega mi i treba ovoliki uvod.

Definicija 1. Neka je $p$ prost broj i $a\in \textbf{Z}$ uzajamno prost sa $p$ , onda za $a$ kažemo da je kvadratni ostatak po modulu $p$ akko postoji $x\in \textbf{Z}$ za koje važi $x^2\equiv a\pmod p$ .

Definicija 2. Neka je $p$ prost broj i $a\in \textbf{Z}$ uzajamno prost sa $p$ , onda za $a$ kažemo da je ne-kvadratni ostatak po modulu $p$ akko nije kvadratni ostatak po modulu $p$ .
(ne znam kako bih preveo quadratic non-residue)

Nadalje, $p$ će uvek označavati neki neparan prost broj, a $Z_p^*:=Z_p\setminus\{0\}$ .

Lema 1. Ako je $Z_p^*=A \cup B$ , gde je $A$ skup svih kvadratnih ostataka po modulu $p$ a $B$ skup svih ne-kvadratnih ostataka po modulu $p$ , onda je $|A|=|B|=\frac{p-1}{2}$ .

Dokaz.

Na osnovu prethodnih definicija jasno je da važi $A\cap B=\emptyset$ .
Ako je $f(x):=x^2 \pmod p$ , i ako je $S:=\{1,\ldots,\frac{p-1}{2}\}$ , onda je $f(S)=A$ .
Naime, $A=f(Z_p^*)=f(S\cup -S)=f(S)$ , jer je $(-x)^2\equiv x^2\pmod p$ .
Pokazaćemo da je $f$ i injekcija na $S$ .
Ako bi za neke $x_1,x_2\in S$ bilo $x_1^2\equiv x_2^2\pmod p$ , onda sledi $p|x_1-x_2$ ili $p|x_1+x_2$ .
Budući da $x_1,x_2\in S$ , u prvom slučaju sledi da je $0\leq |x_1-x_2|<\frac{p-1}{2}<p$ pa mora biti $|x_1-x_2|=0$ tj. $x_1=x_2$ , a drugi je nemoguć zbog procene $2\leq x_1+x_2\leq p-1<p$ .

Sada imamo da je $\frac{p-1}{2}=|S|=|f(S)|=|A|$ , odakle i sledi tvrđenje. $\diamondsuit$

Lema 2. Ako je $Z_p^*=A \cup B$ , gde je $A$ skup svih kvadratnih ostataka po modulu $p$ a $B$ skup svih ne-kvadratnih ostataka po modulu $p$ , onda:

1. $x,y\in A\Rightarrow x\cdot y\in A$
2. $x\in A\wedge y\in B\Rightarrow x\cdot y\in B$
3. $x,y\in B\Rightarrow x\cdot y\in A$

Dokaz.

Primetimo prvo da je, za svako fiksirano $x\in Z_p^*$ , f-ja $f_x(t):=x\cdot t\pmod p$ bijekcija na $Z_p^*$ .

Ako je $x,y\in A$ , onda na osnovu definicije 1. sledi da postoje brojevi $\alpha,\beta\in Z_p^*$ takvi da važi $\alpha^2\equiv x\pmod p$ i $\beta^2\equiv y\pmod p$ , pa dobijamo $(\alpha\cdot\beta)^2\equiv x\cdot y\pmod p$ , tj. $x\cdot y\in A$ .

Ako je $x\in A$ a $y\in B$ , onda, budući da je $x$ fiksirano, možemo posmatrati f-ju $f_x$ na skupu $A$ . Iz dela pod 1. sledi $f_x(A)\subseteq A$ a iz injektivnosti sledi $|f_x(A)|=|A|$ , pa imamo da je $f_x(A)=A$ .
Sada je jasno da ne može biti $x\cdot y=f_x(y)$ element skupa $A$ , jer bi u protivnom ispalo da za neko $a\in A$ važi $x\cdot a=x\cdot y$ , pa bi, posle skraćivanja sa $x$ ispalo da je $y\in A$ (što je kontradikcija).

Ako je $x,y\in B$ , onda možemo posmatrati f-ju $f_x$ na skupu $A$ , pa koristeći dokazani deo pod 2. kao i injektivnost f-je, na analogan način kao i prethodnom delu, uz korišćnje rezultata $|A|=|B|$ iz Leme 1, dobiti $f_x(A)=B$ . Sada, na isti način kao i u delu pod 2, sledi da $x\cdot y$ mora biti element skupa $A$ . $\heartsuit$

(Inače, ove dve leme još lakše slede ako znamo da je za svako prosto p, grupa $Z_p^*$ ciklična, ili, što je isto: da za svako prosto $p$ postoji "primitive root modulo $p$ ").

Lema 3. Ako je $Z_p^*=A \cup B$ , gde je $A$ skup svih kvadratnih ostataka po modulu $p$ a $B$ skup svih ne-kvadratnih ostataka po modulu $p$ , onda važi:

1. za $p>5$ , postoje $x,y\in A$ za koje važi $x+y\pmod p\in A$ .
2. za $p>2$ , postoje $x,y\in A$ za koje važi $x+y\pmod p\in B$ .

Dokaz.

1. Možemo iskoristi identitet: $(x^2-y^2)^2+(2xy)^2=(x^2+y^2)^2$ , pazeći pri tom da $x^2,y^2\in A$ budu takvi da nije ni $x^2-y^2\equiv 0\pmod p$ , ni $x^2+y^2\equiv 0\pmod p$ , a to je uvek moguće za $|A|=\frac{p-1}{2}>2$ tj. za $p>5$ .

2. Budući da je $1\in A$ , možemo posmatrati f-ju $f(x):=1+x\pmod p$ , $x\in A$ .
Uzmimo da je $A=\{x_1,\ldots,x_{\frac{p-1}{2}}\}$ , pri čemu je $x_i<x_{i+1}$ za svako $i$ .
Ako bi za neko $i$ bilo $x_i<x_i+1<x_{i+1}$ , onda bi moralo biti $1+x_i\in B$ , pa bi to bio kraj dokaza.
A ako bi za svako $i$ bilo $x_{i+1}=x_i+1$ , onda bi imali da je $A=\{1,\ldots,\frac{p-1}{2}\}$ , pa bi moralo biti $\frac{p-1}{2}+1\in B$ . $\spadesuit$

Lema 4. Svaki element skupa $Z_p^*$ , gde je $p>5$ , može se predstaviti kao zbir:

1. Dva kvadratna ostatka, za $p>5$
2. Dva ne-kvadratna ostatka, za $p>5$
3. Jednog kvadratnog ostatka i jednog ne-kvadratnog ostatka, za $p>3$

Dokaz:
Ako je $a\in Z_p^*$ , onda postoji jedinstveno $b\in Z_p^*$ za koje važi $a\equiv 2b\pmod p$ , (jer je 2 inverzibilno po modulu $p$ ),
pa ako stavimo da je $f_\alpha(x):=\alpha+x\pmod p$ , onda se sve particije broja $a$ u grupi $Z_p$ mogu predstaviti kao $a\equiv f_b(x)+f_b(-x)\pmod p$ pri čemu se $x$ "šeta" kroz $T:=\{0,1,\ldots,\frac{p-1}{2}\}$ .

Budući da je f-ja $f_b$ bijekcija i da je $x\in T\Longleftrightarrow -x\in -T=\{\frac{p-1}{2}+1,\ldots,p-1,0\}$ , dobijamo da se svi elementi skupa $Z_p$ pojavljuju tačno jedanput kao sabirci, u pomenutim razlaganjima, osim što se element $b$ javlja i kao $f_b(0)$ i kao $f_b(-0)$ , a što je u stvari jedno te isto. Primetimo i to da su parovi jedinstveno određeni, tj. za dato $f_b(x)$ , jedini broj (po modulu p) koji sa njim pravi razlaganje broja $a$ (po modulu p) je upravo $f_b(-x)$ .

Neka su nadalje, $A$ i $B$ skupovi kvadratnih, odnosno ne-kvadratnih ostataka po modulu $p$ .
Neka je $D_{a,A}$ broj razlaganja broja $a$ po modulu $p$ , u kojima su oba sabirka iz skupa $A$ , (analogan smisao ima i oznaka $D_{a,B}$ ) i neka je $D_a$ broj "mešovitih" razlaganja broja $a$ po modulu $p$ , u kojima je jedan sabirak iz $A$ a drugi iz $B$ .

Pokazaćemo sada da važi:

a) Ako su $a_1,a_2\in A$ , onda je $D_{a_1,A}=D_{a_2,A}$ , $D_{a_1,B}=D_{a_2,B}$ i $D_{a_1}=D_{a_2}$
b) Ako su $b_1,b_2\in B$ , onda je $D_{b_1,A}=D_{b_2,A}$ , $D_{b_1,B}=D_{b_2,B}$ i $D_{b_1}=D_{b_2}$
c) Ako je $a\in A$ i $b\in B$ , onda je $D_{a,A}=D_{b,B}$ , $D_{a,B}=D_{b,A}$ i $D_a=D_b$

Označimo jedan (bilo koji) od skupova $A$ i $B$ sa $X$ .
Ako su $x,y\in X$ , onda, na osnovu Leme 2. postoji $z\in A$ , tako da važi $y\equiv z\cdot x\pmod p$ , pa svakom razlaganju broja $x\equiv\alpha+\beta\pmod p$ odgovara jedinstveno razlaganje broja $y\equiv z\cdot x\equiv z\cdot\alpha+z\cdot\beta\pmod p$ , a pošto je $z\in A$ , na osnovu Leme 2. sledi da će i $z\cdot\alpha\pmod p$ pripadati istom skupu ( $A$ ili $B$ ) kao i $\alpha$ i analogno, $z\cdot\beta\pmod p$ pripadaće istom skupu ( $A$ ili $B$ ) kao i $\beta$ . Dakle, vidimo da se "struktura" tih razlaganja ne menja. Pošto možemo napraviti i analogan prelaz sa razlaganja broja $y$ na razlaganja broja $x$ , slede tvrđenja pod a) i b). (Koja u stvari pokušavaju da kažu da prilikom razmatranja broja razlaganja elemenata iz $A$ ili $B$ , nije bitno kog "predstavnika" tih skupova posmatramo.)

Dokaz tvrđenja pod c) je potpuno analogan prethodnom, uz jedinu razliku da $z\in B$ , pa prema Lemi 2, "struktura" razlaganja se "invertuje" tj. ako je $x\equiv\alpha+\beta\pmod p$ , (neka je npr. $\alpha\in A$ ) onda će sabirci u pridruženom razlaganju broja $y\equiv z\cdot x\equiv z\cdot\alpha+z\cdot\beta\pmod p$ pripadati "suprotnom" skupu (onda je npr. $z\cdot\alpha\pmod p\in B$ ).

Sada, na osnovu Leme 3. i tvrđenja pod a) i b) mora da važi $D_{a,A}\geq 1$ , $D_{b,A}\geq 1$ za svako $a\in A$ i svako $b\in B$ , pa, na osnovu tvrđenja c), dobijamo da je i $D_{b,B}\geq 1$ i $D_{a,B}\geq 1$ , odakle slede tvrđenja pod 1. i 2.

Da bi važilo i tvrđenje pod 3. dovoljno je pokazati da je za neko $a\in Z_p^*$ važi $D_a\geq 1$ , jer bi na osnovu a), b) i c) odmah sledilo da $D_x\geq 1$ važi i za svako $x\in Z_p^*$ .

Budući da elemenata iz $A$ , odnosno $B$ , ima sasvim dovoljno (za $p>3$ ), uvek možemo pronaći $a\in A$ i $b\in B$ tako da ne bude $a+b\equiv 0\pmod p$ , pa na osnovu prethodne primedbe, važi i tvrđenje pod c). $\clubsuit$

Tvrđenje 1. Ako je $p$ bilo koji prost broj i $k$ bilo koji ceo broj, onda, ako je $p>5\wedge k\geq 2$ ili $p=5\wedge k>2$ , za svako celo $a$ , uzajamno prosto sa $p$ , postoje celi brojevi $x_1,\ldots ,x_k$ , uzajamno prosti sa $p$ , za koje važi: $a\equiv x_1^2+\ldots +x_k^2\pmod p$ .

Dokaz.

Neka je $p>5\wedge k\geq 2$ . Dovoljno je dokazati slučaj kada je $k\in \{2,\ldots,p+1\}$ , jer se slučaj $k=p\cdot q+r$ , za $2\leq r\leq p+1$ , i $q>0$ svodi na prethodni tako što uzmemo da $x_{r+1}=\ldots =x_{r+p\cdot q}=1$ .

Broj $k$ ima $\frac{p-1}{2}+1$ particija u $Z_p$ , tj. $\frac{p-1}{2}$ particija u $Z_p^*$ . Izaberimo zato bilo koju particiju, $k=m+n$ , gde je $1\leq m\leq n<k$ . Sada, za dato celo $a$ , uzajamno prosto sa $p$ , uzmimo da je $\alpha:=a\pmod p$ .
Budući da je $p>5$ , na osnovu Leme 4, sledi da je $D_{k,A}\geq 1$ , $D_{k,B}\geq 1$ , $D_k\geq 1$ kao i $D_{\alpha,A}\geq 1$ , $D_{\alpha, B}\geq 1$ , $D_\alpha\geq 1$ , pa odatle i na osnovu Leme 2, imamo da jednačina $\alpha\equiv m\cdot x^2+n\cdot y^2$ ima rešenja za neke $x,y\in Z_p^*$ , bez obzira na to kom od skupova $A$ ili $B$ pripadali $m$ i $n$ .
Sada možemo uzeti da je $x_1=\ldots=x_m=x$ i $x_{m+1}=\ldots=x_{m+n}=y$ , pa je jasno da mora biti $\alpha\equiv x_1^2+\ldots +x_m^2+x_{m+1}^2+\ldots\+x_{m+n}^2\pmod p$ .

Ostao je još slučaj $p=5\wedge k>2$ , koji je specifičan po tome što nije za svako $a\in Z_5$ $D_{a,A}>0$ ni $D_{a,B}>0$ , pa ćemo zato koristiti činjenicu da za svako $a\in Z_5^*$ , jeste $D_a=1$ .
Na isti način kao i ranije, vidimo da je dovoljno dokazati tvrđenje u slučaju kad $k\in \{3,4,5,6,7\}$ .
Ako $k\neq 5$ , onda se, zbog $D_k=1$ , broj $k$ može razložiti na zbir jednog kvadratnog i jednog ne-kvadratnog ostatka $k=m+n$ , (3=1+2, 4=1+3, 6=4+2, 7=4+3), pa vidimo da jednačina $\alpha\equiv m\cdot x^2+n\cdot y^2\pmod p$ ima rešenja po $x$ i $y$ za svako $\alpha\in Z_5^*$ , tako da je, za dato celo $a\equiv \alpha\pmod p$ , dovoljno uzeti da je $x_1=\ldots=x_m=x$ i $x_{m+1}=\ldots=x_{m+n}=y$ .

Ako je $k=5$ , imamo da je :

$1\equiv 2\cdot 2^2+3\cdot 1^2\equiv 2^2+2^2+1^2+1^2+1^2\pmod 5$
$4\equiv 2\cdot 1^2+3\cdot 2^2\equiv 1^2+1^2+2^2+2^2+2^2\pmod 5$

$2\equiv 1\cdot 1^2+4\cdot 2^2\equiv 1^2+2^2+2^2+2^2+2^2\pmod 5$
$3\equiv 1\cdot 2^2+4\cdot 1^2\equiv 2^2+1^2+1^2+1^2+1^2\pmod 5$

Potpis

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

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 25.08.2005. u 23:03 · pre 258 meseci #3

Bio sam odsutan neko vreme pa sam tek sada stigao da malo detaljnije analiziram ovo tvoje rešenje i sve što mogu da kažem je svaka čast, zaista je odlično i nemam zamerki.

Ovu temu sam zapravo postavio da bih "promovisao" nešto što se zove Cauchy-Davenport inequality (Koši-Davenportova nejednakost) koja ume da bude veoma moćno sredstvo iako na prvi pogled ne izgleda tako. Formulacija same nejednakosti glasi ovako:

Neka su $A,B\in Z_p$ . Tada važi
$|A+B|\geq\min(|A|+|B|-1,p)$

(Napomena: $A+B=\{a+b\mid a\in A,\ b\in B\}$ )

Sada da vidimo kako se ovo može lepo iskoristiti u postavljenom zadatku.

Neka je $Q$ skup svih kvadratnih ostataka po modulu $p$ . Poznata je stvar da je $|Q|=\frac{p-1}2$ (koga interesuje dokaz može pogledati Lemu 1 u prethodnom postu), pa primenom navedene nejednakosti za $A=B=Q$ dobijamo $|Q+Q|\geq p-2$ . Stavljajući sada $A=Q+Q$ i $B=Q$ dalje sledi $|Q+Q+Q|\geq\min\left(p+\frac{p-1}2-3,p\right)$ . Slučaj $p=5$ proveravamo direktno, dok za $p\geq 7$ važi $p+\frac{p-1}2-3\geq p$ pa je $|Q+Q+Q|\geq p$ odnosno mora biti $|Q+Q+Q|=p$ , iz čega očigledno sledi tvrđenje zadatka.

Možemo konstatovati još i to da se ova ideja u neznatno izmenjenom obliku može primeniti i za dokaz uopštenja koje je dao uranium.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 26.08.2005. u 17:25 · pre 258 meseci #4

Svaka čast!! Ovo je baš bilo moćno!

Dosad nisam ništa čitao od Aditivne teorije brojeva, ali sad kad si me već nagnao u tom pravcu

, mogu da kažem da je dokaz Cauchy-Davenport-ove nejednakosti, koji sam pročitao, sasvim jednostavan za razumevanje, ne baš naročito kratak i koristi vrlo zanimljivu tehniku...

Ako je od interesa, čisto da pomenem da je A.G.Vosper dokazao da u pomenutoj nejednakosti važi jednakost akko važi jedno od sledećih tvrđenja:

1. $|A|+|B|>p$

2. $\min\{|A|,|B|\}=1$

3. postoji $\alpha\in Z_p$ tako da je $A=\{\alpha-\beta :\beta\in B^c\}$ , gde je $B^c$ komplement skupa $B$ u odnosu na $Z_p$ .

4. elementi skupova $A$ i $B$ su aritmetički nizovi sa istom diferencijom (razlikom).

Potpis

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

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 27.08.2005. u 13:24 · pre 258 meseci #5

Nisam siguran na koji dokaz misliš pošto znam da ih ima više. Sećam se da se može isterati indukcijom po $|B|$ (i vrlo brzo se dođe do kraja) ali trenutno ne mogu da rekonstruišem kako tačno ide. U svakom slučaju, sad ću napisati jedan dokaz koji zaista koristi zanimljivu tehniku a nije previše dugačak tako da ne znam da li je to taj na koji si ti mislio.

Prvo ćemo dokazati dve leme.

Lema 1:
Neka su $A$ i $B$ neprazni podskupi nekog polja $F$ , i neka je $f(x,y)$ polinom stepena najviše $|A|-1$ po $x$ i $|B|-1$ po $y$ takav da njegovi koeficijenti pripadaju polju $F$ . Ako je $f(a,b)=0$ za svako $a\in A$ i $b\in B$ onda je $f(x,y)\equiv 0$ .

Dokaz:
Možemo zapisati $f(x,y)=\sum_{i=0}^{|A|-1}\sum_{j=0}^{|B|-1}f_{i,j}x^iy^j=\sum_{i=0}^{k-1}v_i(y)x^i$ . Fiksirajmo sada $b\in B$ . Polinom $u(x)=\sum_{i=0}^{|A|-1}v_i(b)x^i$ je stepena najviše $|A|-1$ , ali s druge strane je $u(x)=0$ za sve $x\in A$ . Sledi da je $u(x)\equiv 0$ pa je i $v_i(b)=0$ za svako $i$ . Međutim, kako je $b$ proizvoljno odabran element iz skupa $B$ , a kako je stepen polinoma $v_i(y)$ najviše $|B|-1$ sledi da je i $v_i(y)\equiv 0$ , a samim tim i $f(x,y)\equiv 0$ .

Lema 2:
Neka je $A$ konačan podskup polja $F$ . Za svako $m$ postoji polinom $g_m(x)\in F[x]$ stepena najviše $|A|-1$ takav da je $g_m(a)=a^m$ za svako $a\in A$ .

Dokaz:
Neka je $A=\{a_0,a_1,\dots,a_{k-1}\}$ . Potrebno je pokazati da postoji polinom $u(x)=u_0+u_1x+\cdots+u_{k-1}x^{k-1}\in F[x]$ takav da je $u(a_i)=u_0+u_1a_i+u_2a_i^2+\cdots+u_{k-1}a_i^{k-1}=a_i^m$ za $i=0,1,\dots,k-1$ . Primetimo da ovo zapravo predstavlja sistem od $k$ linearnih jednačina sa $k$ nepoznatih, a znamo da takav sistem ima rešenje ako je njegova determinanta različita od nule. Determinanta ovog sistema je ništa drugo do Vandermondova determinanta
$\left|\begin{array}{ccccc} 1&a_0&a_0^2&\cdots&a_0^{k-1}\\ 1&a_1&a_1^2&\cdots&a_1^{k-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&a_{k-1}&a_{k-1}^2&\dots&a_{k-1}^{k-1}\end{array}\right|=\prod_{0\leq i<j\leq k-1}(a_j-a_i)$
a ovo je očigledno različito od nule čime je dokaz leme završen.

Dokaz:
Neka je $|A|=k, |B|=l$ i $|A+B|=n$ , i neka je

$f(x,y)=\prod_{c\in A+B}(x+y-c)=\sum_{i,j}f_{i,j}x^iy^j$

Primetimo da je $i+j\leq n$ jer se u formiranom proizvodu nalazi tačno $n$ članova.

Sada, na osnovu Leme 2, u polju $Z_p$ odaberimo polinome $g_i(x)$ stepena manjeg od $k$ i $h_j(y)$ stepena manjeg od $l$ takve da je $g_i(x)=x^i$ i $h_j(y)=y^j$ za sve $x\in A$ odnosno $y\in B$ . Definišimo sledeći polinom:

$p(x,y)=\sum_{\tiny{\begin{array}{c}i<k\\j<l\end{array}}}f_{i,j}x^iy^j+\sum_{\tiny{\begin{array}{c}i\geq k\\j\leq n-i\end{array}}}f_{i,j}g_i(x)y^j+\sum_{\tiny{\begin{array}{c}j\geq l\\i\leq n-j\end{array}}}f_{i,j}x^ih_j(y)\quad(*)$

Primetimo da se za $x\in A$ i $y\in B$ vrednosti polinoma $f(x,y)$ i $p(x,y)$ poklapaju. S druge strane, za tako odabrane $x,y$ važi $f(x,y)=0$ pa mora biti i $p(x,y)=0$ . Pošto je polinom $p(x,y)$ stepena manjeg od $k$ po $x$ i stepena manjeg od $l$ po $y$ na osnovu Leme 1 sledi da mora biti $p(x,y)\equiv 0$ . Ako zapišemo $p(x,y)=\sum_{i,j}p_{i,j}x^iy^j$ onda je $p_{i,j}=0$ za svako $i,j$ .

Ako je $n\geq p$ nejednakost koju dokazujemo je očigledna, pa uzmimo da je $n<p$ . Potrebno je dokazati $n\geq k+l-1$ . Pretpostavimo suprotno, tj. $n<k+l-1$ , odnosno $k+l\geq n+2$ . U tom slučaju postoje brojevi $u<k$ i $v<l$ takvi da je $u+v=n$ . Primetimo da se član $x^uy^v$ ne pojavljuje u drugoj i trećoj sumi izraza $(*)$ jer za $j=v$ važi $i\leq n-j=u<k$ i slično za $i=u$ važi $j\leq n-i=v<l$ . Sledi da je $p_{u,v}=f_{u,v}$ . Međutim, $p_{u,v}=0$ dok je $f_{u,v}={n\choose u}$ što za $n<p$ ne može biti deljivo sa $p$ . Kontradikcija, čime je tvrđenje dokazano.

Pošto smo se toliko raspričali o ovoj nejednakosti red bi bio da vidimo još jednu njenu lepu primenu.

Zadatak:
Dokazati da se između datih $2n-1$ brojeva uvek mogu izabrati $n$ takvih da je njihova suma deljiva sa $n$ .

Rešenje:
Posle, prvo malo probajte sami :)

Toliko od mene za sada, imam još ponešto da kažem na ovu temu ali najpre malo pauze i da rešimo ovaj zadatak.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 28.08.2005. u 12:17 · pre 258 meseci #6

Ja sam našao dokaz u knjizi Not always buried deep (Paul Pollack) i u suštini ne razlikuje se mnogo od dokaza koji si ti dao, sve ključne ideje su upotrebljene. Jedino je dokaz Leme 2. za nijansu simpatičniji:

Neka je $\displaystyle t(x)=\prod_{a\in A}(x-a)$ i neka je $g_m(x)$ jedinstven polinom stepena najviše $|A|-1$ , takav da $x^m\equiv g_m(x)\pmod {t(x)}$ . Kraj dokaza

Potpis

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

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 06.10.2007. u 12:42 · pre 232 meseca #7

Dovoljno pokazati datu teoremu za proste brojeve, jer ako je tacna za m,n onda je tacna i za mn, sto se lako dokazuje. Znaci imamo brojeve $a_1,a_2,...a_{2p-1}$ i pretpostavimo da je zbir brojeva u svakom podskupu ciji je broj elemenata p nije deljiv sa p, tj. da je uzajamno prost sa p. Izracunajmo vrednost zbira p-1 stepena svih zbirova elemenata podskupova od p elemenata.

Kako je $x^{p-1}\equiv_p 1$ za (x,p)=1 to je data vrednost jednaka ${2p-1\choose p}\not \equiv_p 0$ .

Sa druge strane dati broj je $(a_1+a_2+...+a_{p})^{p-1}+...+(a_p+...+a_{2p-1})^{p-1}$ . Posmatrajmo koeficijent uz $a_1^{k_1}a_2^{k_2}...a_x^{k_x}$ u datom broju ( $1\leq x\leq p-1$ ), gde je $k_1+...+k_x=p-1$ . Taj broj je jednak ${2p-1-x \choose p-x}\frac{(p-1)!}{k_1! k_2!...k_x!}$ . Kako je ${2p-1-x \choose p-x}=\frac{(2p-1-x)!}{(p-x)!(p-1)!}\equiv_p 0$ dobijamo kontradikciju.

Secam se da sam negde video dokaz i preko Kosi-Davenportove teoreme, ali se ne secam kako ide. :)

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 08.10.2007. u 13:38 · pre 232 meseca #8

Dobro je rešenje, samo na kraju treba da posmatramo koeficijent uz $a_{i_1}^{k_1}a_{i_2}^{k_2}\cdots a_{i_x}^{k_x}$ (tvoj zapis sasvim ignoriše članove u kojima se pojavljuje $a_p$ i brojevi s većim indeksom).

Evo kako bi išlo preko Koši—Davenportove nejednakosti.

Poređamo $2p-2$ od datih brojeva (sve sem nekog izostavljenog broja $t$ ) redom u sledeću tabelu (posmatramo samo ostatke po modulu $p$ ):
$\begin{array}{ccccccccc} 0,&0,&\dots,&0,&1,&1,&\dots,&a,&a,\\ a,&a,&&&\dots&&&&p-1\end{array}$
Ukoliko postoji kolona u kojoj su dva ista broja, taj broj očito se pojavljuje kao ostatak bar $p$ puta (vrste imaju po $p-1$ članova), pa je tvrđenje dokazano: uzmemo dotičnih $p$ brojeva. U suprotnom, po Koši—Davenportovoj nejednakosti (primenjenoj više puta) važi $|A_1+A_2+\cdots+A_{p-1}|\geq p$ (gde su $A_1,\dots,A_{p-1}$ dvočlani skupovi — kolone gornje tabele). Dakle, svi ostaci su zastupljeni, pa postoji $p-1$ brojeva koji u zbiru daju ostatak $-t$ ; zajedno s brojem $t$ činiće zbir deljiv sa $p$ .

Lista ovdašnjih nerešenih zadataka sve se više prazni.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Malo teorije brojeva (zbir kvadrata, kongruencija po modulu) 10.10.2007. u 20:40 · pre 232 meseca #9

Citat:

Bojan Basic: Dobro je rešenje, samo na kraju treba da posmatramo koeficijent uz $a_{i_1}^{k_1}a_{i_2}^{k_2}\cdots a_{i_x}^{k_x}$ (tvoj zapis sasvim ignoriše članove u kojima se pojavljuje $a_p$ i brojevi s većim indeksom).

Pa isti je koeficijent, to je samo prenumeracija promenljivih.

Prijavite se da biste odgovorili u ovoj temi.Prijava Registracija

Forum kao aplikacija na telefonu

Srodne teme