|
[3244] bily71 | 2010-02-13 12:46:49 |
Triviális megoldás az
x11(mod p1)
x22(mod p2)
...
xnn(mod pn),
kongruenciarendszer, ahol n végig fut a természetes számokon, pn>n és a prímek páronkét különböznek.
A p1<p2<...<pn nem szükséges feltétel, pn itt nem az n-edik prímet jelöli és nem szükséges minden prímet felhasználni, akár végtelen sok is kimaradhat.
Egy másik:
x1a1(mod p1)
x2a2(mod p2)
x3a3(mod p3)
...
xmam(mod pm)
xm+1b1(mod pm+1)
...
xm+nbn(mod pm+n),
ahol bi pi valamely maradékosztálya, bi és bj nem feltétlenül különböző számok, bn<pm+n és bn az n-edik olyan természetes szám, amely nem elégít ki p1-től pm-ig egy kongruenciát sem, pm nem az m-edik prím és p1<p2<...<pm+n itt sem szükséges feltétel, és itt sem szükséges minden prímet felhasználni.
1. Van-e több megoldás?
(Szerintem nincs a jonas által [3239]-ben ismertetett okok miatt.)
Nevezzünk részleges lefedőrendszernek egy olyan kongruenciarendszert, ahol létezik k természetes szám, hogy a k-nál nagyobb természetes számok mindegyike kielégít valamely kongruenciát, azaz k fölött a rendszer minden számot lefed.
2. Konstruálható-e véges, vagy végtelen részleges inkongruens lefedőrendszer, ha minden modulus prím?
3. Konstruálható-e véges, vagy végtelen részleges lefedőrendszer, ha minden modulus prím, és minden prímet kétszer használunk fel?
Elnézést, ha bárkit is untatok.
|
Előzmény: [3241] bily71, 2010-02-12 22:53:59 |
|
|
[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 |
|
[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 |
|
[3248] bily71 | 2010-02-14 23:10:38 |
Tehát, ha jól értem azt állítod, hogy az
x1m(mod p1)
x2m(mod p2)
...
xnm(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:
x11(mod 5)
x2-1(mod 5)
x31(mod 7)
x4-1(mod 7)
x52(mod 11)
...
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 |
|
|
|
[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 |
|
|