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

Dokazati da se za svaki prost broj i ceo broj , , mogu naći celi brojevi takvi da nijedan od njih nije deljiv sa i da je .

---

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

Definicija 1. Neka je prost broj i uzajamno prost sa , onda za kažemo da je kvadratni ostatak po modulu akko postoji za koje važi .

Definicija 2. Neka je prost broj i uzajamno prost sa , onda za kažemo da je ne-kvadratni ostatak po modulu akko nije kvadratni ostatak po modulu .
(ne znam kako bih preveo quadratic non-residue)

Nadalje, će uvek označavati neki neparan prost broj, a .




Lema 1. Ako je , gde je skup svih kvadratnih ostataka po modulu a skup svih ne-kvadratnih ostataka po modulu , onda je .

Dokaz.

Na osnovu prethodnih definicija jasno je da važi .
Ako je , i ako je , onda je .
Naime, , jer je .
Pokazaćemo da je i injekcija na .
Ako bi za neke bilo , onda sledi ili .
Budući da , u prvom slučaju sledi da je pa mora biti tj. , a drugi je nemoguć zbog procene .

Sada imamo da je , odakle i sledi tvrđenje.




Lema 2. Ako je , gde je skup svih kvadratnih ostataka po modulu a skup svih ne-kvadratnih ostataka po modulu , onda:

1.
2.
3.

Dokaz.

Primetimo prvo da je, za svako fiksirano , f-ja bijekcija na .

Ako je , onda na osnovu definicije 1. sledi da postoje brojevi takvi da važi i , pa dobijamo , tj. .

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

Ako je , onda možemo posmatrati f-ju na skupu , pa koristeći dokazani deo pod 2. kao i injektivnost f-je, na analogan način kao i prethodnom delu, uz korišćnje rezultata iz Leme 1, dobiti . Sada, na isti način kao i u delu pod 2, sledi da mora biti element skupa .

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




Lema 3. Ako je , gde je skup svih kvadratnih ostataka po modulu a skup svih ne-kvadratnih ostataka po modulu , onda važi:

1. za , postoje za koje važi .
2. za , postoje za koje važi .

Dokaz.


1. Možemo iskoristi identitet: , pazeći pri tom da budu takvi da nije ni , ni , a to je uvek moguće za tj. za .

2. Budući da je , možemo posmatrati f-ju , .
Uzmimo da je , pri čemu je za svako .
Ako bi za neko bilo , onda bi moralo biti , pa bi to bio kraj dokaza.
A ako bi za svako bilo , onda bi imali da je , pa bi moralo biti .




Lema 4. Svaki element skupa , gde je , može se predstaviti kao zbir:

1. Dva kvadratna ostatka, za
2. Dva ne-kvadratna ostatka, za
3. Jednog kvadratnog ostatka i jednog ne-kvadratnog ostatka, za

Dokaz:
Ako je , onda postoji jedinstveno za koje važi , (jer je 2 inverzibilno po modulu ),
pa ako stavimo da je , onda se sve particije broja u grupi mogu predstaviti kao pri čemu se "šeta" kroz .

Budući da je f-ja bijekcija i da je , dobijamo da se svi elementi skupa pojavljuju tačno jedanput kao sabirci, u pomenutim razlaganjima, osim što se element javlja i kao i kao , a što je u stvari jedno te isto. Primetimo i to da su parovi jedinstveno određeni, tj. za dato , jedini broj (po modulu p) koji sa njim pravi razlaganje broja (po modulu p) je upravo .

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

Pokazaćemo sada da važi:

a) Ako su , onda je , i
b) Ako su , onda je , i
c) Ako je i , onda je , i

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

Dokaz tvrđenja pod c) je potpuno analogan prethodnom, uz jedinu razliku da , pa prema Lemi 2, "struktura" razlaganja se "invertuje" tj. ako je , (neka je npr. ) onda će sabirci u pridruženom razlaganju broja pripadati "suprotnom" skupu (onda je npr. ).

Sada, na osnovu Leme 3. i tvrđenja pod a) i b) mora da važi , za svako i svako , pa, na osnovu tvrđenja c), dobijamo da je i i , odakle slede tvrđenja pod 1. i 2.

Da bi važilo i tvrđenje pod 3. dovoljno je pokazati da je za neko važi , jer bi na osnovu a), b) i c) odmah sledilo da važi i za svako .

Budući da elemenata iz , odnosno , ima sasvim dovoljno (za ), uvek možemo pronaći i tako da ne bude , pa na osnovu prethodne primedbe, važi i tvrđenje pod c).




Tvrđenje 1. Ako je bilo koji prost broj i bilo koji ceo broj, onda, ako je ili , za svako celo , uzajamno prosto sa , postoje celi brojevi , uzajamno prosti sa , za koje važi: .

Dokaz.

Neka je . Dovoljno je dokazati slučaj kada je , jer se slučaj , za , i svodi na prethodni tako što uzmemo da .

Broj ima particija u , tj. particija u . Izaberimo zato bilo koju particiju, , gde je . Sada, za dato celo , uzajamno prosto sa , uzmimo da je .
Budući da je , na osnovu Leme 4, sledi da je , , kao i , , , pa odatle i na osnovu Leme 2, imamo da jednačina ima rešenja za neke , bez obzira na to kom od skupova ili pripadali i .
Sada možemo uzeti da je i , pa je jasno da mora biti .

Ostao je još slučaj , koji je specifičan po tome što nije za svako ni , pa ćemo zato koristiti činjenicu da za svako , jeste .
Na isti način kao i ranije, vidimo da je dovoljno dokazati tvrđenje u slučaju kad .
Ako , onda se, zbog , broj može razložiti na zbir jednog kvadratnog i jednog ne-kvadratnog ostatka , (3=1+2, 4=1+3, 6=4+2, 7=4+3), pa vidimo da jednačina ima rešenja po i za svako , tako da je, za dato celo , dovoljno uzeti da je i .

Ako je , imamo da je :













_{[Ovu poruku je menjao uranium dana 18.08.2005. u 03:50 GMT+1]}

---

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 . Tada važi


(Napomena: )

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

Neka je skup svih kvadratnih ostataka po modulu . Poznata je stvar da je (koga interesuje dokaz može pogledati Lemu 1 u prethodnom postu), pa primenom navedene nejednakosti za dobijamo . Stavljajući sada i dalje sledi . Slučaj proveravamo direktno, dok za važi pa je odnosno mora biti , 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.

_{[Ovu poruku je menjao Bojan Basic dana 26.08.2005. u 19:05 GMT+1]}

---

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.

2.

3. postoji tako da je , gde je komplement skupa u odnosu na .

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

---

Nisam siguran na koji dokaz misliš pošto znam da ih ima više. Sećam se da se može isterati indukcijom po (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 i neprazni podskupi nekog polja , i neka je polinom stepena najviše po i po takav da njegovi koeficijenti pripadaju polju . Ako je za svako i onda je .

Dokaz:
Možemo zapisati . Fiksirajmo sada . Polinom je stepena najviše , ali s druge strane je za sve . Sledi da je pa je i za svako . Međutim, kako je proizvoljno odabran element iz skupa , a kako je stepen polinoma najviše sledi da je i , a samim tim i .

Lema 2:
Neka je konačan podskup polja . Za svako postoji polinom stepena najviše takav da je za svako .

Dokaz:
Neka je . Potrebno je pokazati da postoji polinom takav da je za . Primetimo da ovo zapravo predstavlja sistem od linearnih jednačina sa 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

a ovo je očigledno različito od nule čime je dokaz leme završen.

Dokaz:
Neka je i , i neka je



Primetimo da je jer se u formiranom proizvodu nalazi tačno članova.

Sada, na osnovu Leme 2, u polju odaberimo polinome stepena manjeg od i stepena manjeg od takve da je i za sve odnosno . Definišimo sledeći polinom:



Primetimo da se za i vrednosti polinoma i poklapaju. S druge strane, za tako odabrane važi pa mora biti i . Pošto je polinom stepena manjeg od po i stepena manjeg od po na osnovu Leme 1 sledi da mora biti . Ako zapišemo onda je za svako .

Ako je nejednakost koju dokazujemo je očigledna, pa uzmimo da je . Potrebno je dokazati . Pretpostavimo suprotno, tj. , odnosno . U tom slučaju postoje brojevi i takvi da je . Primetimo da se član ne pojavljuje u drugoj i trećoj sumi izraza jer za važi i slično za važi . Sledi da je . Međutim, dok je što za ne može biti deljivo sa . 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 brojeva uvek mogu izabrati takvih da je njihova suma deljiva sa .

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.

_{[Ovu poruku je menjao Bojan Basic dana 13.09.2005. u 11:35 GMT+1]}

---

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 i neka je jedinstven polinom stepena najviše , takav da . Kraj dokaza

---

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 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 za (x,p)=1 to je data vrednost jednaka .

Sa druge strane dati broj je . Posmatrajmo koeficijent uz u datom broju (), gde je . Taj broj je jednak . Kako je dobijamo kontradikciju.



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

Dobro je rešenje, samo na kraju treba da posmatramo koeficijent uz (tvoj zapis sasvim ignoriše članove u kojima se pojavljuje i brojevi s većim indeksom).

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

Poređamo od datih brojeva (sve sem nekog izostavljenog broja ) redom u sledeću tabelu (posmatramo samo ostatke po modulu ):

Ukoliko postoji kolona u kojoj su dva ista broja, taj broj očito se pojavljuje kao ostatak bar puta (vrste imaju po članova), pa je tvrđenje dokazano: uzmemo dotičnih brojeva. U suprotnom, po Koši—Davenportovoj nejednakosti (primenjenoj više puta) važi (gde su dvočlani skupovi — kolone gornje tabele). Dakle, svi ostaci su zastupljeni, pa postoji brojeva koji u zbiru daju ostatak ; zajedno s brojem činiće zbir deljiv sa .

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

_{[Ovu poruku je menjao Bojan Basic dana 08.10.2007. u 15:22 GMT+1]}

---

Pa isti je koeficijent, to je samo prenumeracija promenljivih.