Fórum: Érdekes matekfeladatok

É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 a²-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)=-a²+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ú.

Bocsánat, elírtam a második esetnél, tehát mégegyszer, helyesen: ha a²-1(mod p),

akkor (p-a)²-1(mod p).

Ez megoldható, legyen x₁0(mod p₁).

Tehát, ha jól értem azt állítod, hogy az

x₁m(mod p₁)

x₂m(mod p₂)

...

x_nm(mod p_n)

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:

x₁1(mod 5)

x₂-1(mod 5)

x₃1(mod 7)

x₄-1(mod 7)

x₅2(mod 11)

...

ahol ha p_n=6k+1, akkor az alsó egészrészt jelöli, ha p_n=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?

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 a²-1(mod p), de akkor (p-1)²-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:

.

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.

A 0-t nem fedted le, ha p(n) az n-edik prím.

Triviális megoldás az

x₁1(mod p₁)

x₂2(mod p₂)

...

x_nn(mod p_n),

kongruenciarendszer, ahol n végig fut a természetes számokon, p_n>n és a prímek páronkét különböznek.

A p₁<p₂<...<p_n nem szükséges feltétel, p_n 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:

x₁a₁(mod p₁)

x₂a₂(mod p₂)

x₃a₃(mod p₃)

...

x_ma_m(mod p_m)

x_m+1b₁(mod p_m+1)

...

x_m+nb_n(mod p_m+n),

ahol b_i p_i valamely maradékosztálya, b_i és b_j nem feltétlenül különböző számok, b_n<p_m+n és b_n az n-edik olyan természetes szám, amely nem elégít ki p₁-től p_m-ig egy kongruenciát sem, p_m nem az m-edik prím és p₁<p₂<...<p_m+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.

Új gondolkodnivaló.

Legyen ismét p prím. A Wilson-tétel mintájára, párosítsuk össze azokat a modulo p maradékokat, amelyek szorzata -1:

Milyen eredményt kapunk ebből?

Írjuk inkább így:

Ha 0<x<y<z, akkor a nevező pozitív.

Ha 0 vagy 0, akkor az függvény konvex, a három pontra illesztett parabola felfelé áll, tehát a0.

Ha pedig 01, akkor konkáv, a parabola lefelé áll, tehát a0.