[3255] jonas | 2010-02-16 20:54:36 |
 Nem, én azt állítom, hogy a következő egy lefedő rendszer:
x0 0(mod p0)
x1 1(mod p1)
x2 -1(mod p2)
x3 2(mod p3)
x4 -2(mod p4)
x5 3(mod p5)
stb, ahol pi mondjuk a prímszámok sorozata.
Ez akkor is működik, ha mondjuk pi=10i+1: ilyenkor a kongruenciák közül bármelyik véges sok együtt csak a természetes számok legfeljebb egy kilenced részét fedi le, mégis az összes kongruencia együtt már lefedi az összes egész számot.
|
Előzmény: [3248] bily71, 2010-02-14 23:10:38 |
|
|
[3253] bily71 | 2010-02-16 20:04:32 |
 Ez a kongruenciarendszer minden természetes számot lefed a 0-án kívül, tehát részleges lefedőrendszer. Változtassunk egy kicsit a szabályokon. Legyen az kongruenciáknak megfelelő számtani sorozatok első eleme , az kongruenciáknak megfelelőeknek pedig változatlanul .
Nevezzük az ilyen rendszereket, ahol a kongruenciáknak megfelelő számok sorozata nem a maradékosztályt reprezentáló legkisebb elemtől indul, számtani sorozatok lefedőrendszerének, ha minden természetes szám tagja legalább egy sorozatnak. Számtani sorozatok részleges lefedőrendszerének pedig akkor, ha létezik k>0 természetes szám, úgy, hogy a rendszer minden k-nál nagyobb számot lefed.
Utolsó kérdésem e témában: 1. Az így kapott számtani sorozatok rendszere részleges lefedőrendszer-e, vagyis a le nem fedett számok halmaza véges, avagy végtelen?
Mégegyszer elnézést kérek a témakör érdektelenségéért.
|
Előzmény: [3248] bily71, 2010-02-14 23:10:38 |
|
|
[3251] Fálesz Mihály | 2010-02-15 10:16:11 |
 Én pontosan fordítva szervezném a számolást:
1. eset: a -1 nem kvadradikus maradék mod p, azaz minden pár két különböző maradékból áll. A párok száma (p-1)/2. A Wilson-tételt is alkalmazva,
 | (1) |
Mivel p>2, a +1 és -1 maradékok különbözőek, a -1 (-1)(p-1)/2 (mod p) kongruencia akkor teljesül, ha (p-1)/2 páratlan, azaz p 4k+3 alakú.
2. eset: a -1 kvadradikus maradék mod p, azaz létezik egy a maradék, amire a2 -1(mod p). Ilyen maradék a -a is, a két maradék külöböző, mert p páratlan, és több nincs.
Az (1)-beli szorzatból hagyjuk el a (a,a) és a (-a,-a) párokat, és helyettük vegyük hozzá a szorzathoz az (a,-a) párt (ahol a.(-a)=-a2 +1(mod p)):
-1 (p-1)!=(a.(-a)).(1.(p-1)).... (-1)(p-3)/2. (mod p) | (2) |
A -1 (-1)(p-3)/2 (mod p) kongruencia akkor teljesül, ha (p-3)/2 páratlan, azaz p 4k+1 alakú.
Összességében az derült ki, hogy a -1 akkor és csak akkor kvadradikus maradék mod p, ha p 4k+1 alakú.
|
Előzmény: [3250] bily71, 2010-02-14 23:27:08 |
|
|
|
[3248] bily71 | 2010-02-14 23:10:38 |
 Tehát, ha jól értem azt állítod, hogy az
x1 m(mod p1)
x2 m(mod p2)
...
xn m(mod pn)
végtelen kongruenciarendszer lefedőrendszer?
Szerintem nem.
Bármelyik számot fedem le az összes kongruenciával, az ugyanaz, mintha a 0-át fedném le. Az eratoszthenészi szita működik akkor is, ha nem a 0-ról indítjuk a lépéseket, hanem m-ről, hiszen minden modulus prím, csak ebben az esetben nem a pl. 5-tel osztható számokat húzzuk le, hanem m-től minden 5k-adik számot.
Ha pedig arra gondoltál, hogy minden kongruenciával másik számot fedünk le, azt egy esetként írtam le, vagyis a végtelen sok megoldást egy típusba soroltam.
De mi a helyzet akkor, ha minden 3-nál nagyobb prímet kétszer használunk fel, és ha a lefedett szám függ a modulustól, mint a következő rendszerben:
x1 1(mod 5)
x2 -1(mod 5)
x3 1(mod 7)
x4 -1(mod 7)
x5 2(mod 11)
...
](keplet.cgi?k=31B7602D9EBE3CC4)
,](keplet.cgi?k=65AD1F2195D695B8)
ahol ha pn=6k+1, akkor az alsó egészrészt jelöli, ha pn=6k-1, akkor pedig a felsőt? Lehet-e ez a rendszer részleges lefedőrendszer, tehát létezik-e olyan természetes szám, hogy minden nála nagyobbat lefed a rendszer?
|
Előzmény: [3246] jonas, 2010-02-14 17:18:58 |
|
[3247] bily71 | 2010-02-14 22:12:36 |
 Ezt kapjuk:

.
Két eset lehetséges, első:
2 | , ekkor van darab számpárunk, amelyek szorzata ab -1(mod p), ha behelyettesítünk, akkor ezt kapjuk:

.
Második:
, ekkor létezik a, hogy a2 -1(mod p), de akkor (p-1)2 -1(mod p). Így kapunk darab számpárt, amelyek szorzata ab -1(mod p), és mivel 2 | , ezért, ha behelyettesítünk, ezt kapjuk:

.
|
Előzmény: [3243] Fálesz Mihály, 2010-02-13 12:38:17 |
|
[3246] jonas | 2010-02-14 17:18:58 |
 Ne viccelj már. Ha végtelen sok kongruenciát használhatsz, és csak a modulusokra van megkötés, akkor nagyon sok megoldás van, mert akár minden kongruenciával elég egy egész számot lefedned.
|
Előzmény: [3244] bily71, 2010-02-13 12:46:49 |
|