Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Érdekes matekfeladatok

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]  

Szeretnél hozzászólni? Jelentkezz be.
[3260] bily712010-02-25 11:50:28

Sajnos a párosítgatás módszerével nem, de más úton sikerült belátnom, hogy ha p=3k-1 és a\inZ és 1\lea\lep-1, akkor minden a-hoz létezik x egész, hogy a\equivx3 (mod p), ha pedig p=3k+1, a akkor, és csak akkor kubikus maradék, ha a(p-1)/3\equiv1 (mod p).

Előzmény: [3259] Fálesz Mihály, 2010-02-19 12:51:14
[3259] Fálesz Mihály2010-02-19 12:51:14

Újabb gondolkodnivaló. Legyen p egy 3k+1 alakú prím.

Használhatjuk-e a párosítgatás módszerét annak bizonyítására, hogy 1\lea\lep-1 akkor és csak akkor teljes köb -- kubikus maradék :-) --, azaz létezik olyan x egész, amire a\equivx3 (mod p), ha a(p-1)/3\equiv1 (mod p)?

Előzmény: [3258] Fálesz Mihály, 2010-02-19 12:41:32
[3258] Fálesz Mihály2010-02-19 12:41:32

Számomra inkább az érdekes, hogy ezzel a módszerrel primitív gyökök felhasználása nélkül is ilyen röviden be lehet bizonyítani azt, hogy a akkor és csak akkor kvadradikus maradék mod p, ha a(p-1)/2\equiv1(mod p), különben a(p-1)/2\equiv-1.

(A kis Fermat-tétel párosítgatás és Wilson-tétel nélkül is kijön a szokásos bizonyítással: összeszorozzuk az a,2a,...,(p-1)a maradékokat.)

Előzmény: [3256] bily71, 2010-02-17 23:30:28
[3257] bily712010-02-18 21:45:01

Én arra jutottam, hogy a le nem fedett számok halmaza végtelen. Gondoltmenetem a következő:

Vonjuk össze az egy modulushoz tartozó számtani sorozatokat, így minden 3-nál nagyobb prímhez kapunk egy olyan számsorozatot, amelyben két differencia váltja egymást. Írjuk fel a sorokat egymás után képzeletben. A sorok táblázatba rendezhetőek, a táblázatban a számok a prímek szorzata egyhatodának alsó, vagy felső egészrészének felelnek meg. Ezt a táblázatot azt hiszem már jól ismerjük.

Ha a le nem fedett számok halmaza véges lenne, akkor létezne k természetes szám, hogy e szám nem, de minden nála nagyobb fedett. Ez csak úgy lehetséges, ha minden új sorozat legkisebb olyan tagja, amely eddig egyik sorozatnak sem volt tagja fedi a k után következő olyan számot, amelyet az előző sorozatok nem fedtek le, (remélem eddig érthetően fogalmaztam).

Jelölje an az n-edik le nem fedett számot, bn pedig az n-edik sorozat azon legkisebb tagját, amely nem szerepelt egyik eddigi sorozatban sem. Mivel a táblázat a főátlóra szimmetrikus, ezért a_n<\left[\frac{p_n^2}{6}\right]\le{b_n}, ebből következik, hogy an<bn, így soha nem fedheti, mert az an=bn soha nem teljesül.

Jól következtettem? Eléggé tömören fogalmaztam, ha nem érthető, bővebben kifejtem.

A nem fedett számok egy nevezetes számsorozat tagjaival egyértelműen megfeleltethetőek .

Előzmény: [3253] bily71, 2010-02-16 20:04:32
[3256] bily712010-02-17 23:30:28

Két eset lehetséges:

1. a nem kvadratikus maradék modulo p. Ekkor a Wilson-tétel miatt

a^{\frac{p-1}{2}}\equiv-1~(\mod{p}),

ebből

ap-1\equiv1 (mod p),

ebből

ap\equiva (mod p).

2. a kvadratikus maradék modulo p. Ekkor a Wilson-tétel miatt

a^{\frac{p-3}{2}}(-a)\equiv-1~(\mod{p}),

ebből

a^{\frac{p-1}{2}}\equiv1~(\mod{p}),

ebből ugyancsak a kis Fermat-tételt kapjuk.

(Az előző megoldásom második része részben hibás).

Előzmény: [3252] Fálesz Mihály, 2010-02-15 10:16:52
[3255] jonas2010-02-16 20:54:36

Nem, én azt állítom, hogy a következő egy lefedő rendszer:

x0\equiv0(mod p0)

x1\equiv1(mod p1)

x2\equiv-1(mod p2)

x3\equiv2(mod p3)

x4\equiv-2(mod p4)

x5\equiv3(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
[3254] bily712010-02-16 20:06:05

Erre majd később válaszolok, most nincs időm.

Előzmény: [3252] Fálesz Mihály, 2010-02-15 10:16:52
[3253] bily712010-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 x_n\equiv\left[\frac{p_n}{6}\right]~(\mod{p_n}) kongruenciáknak megfelelő számtani sorozatok első eleme p_n+\left[\frac{p_n}{6}\right], az x_m\equiv-\left[\frac{p_m}{6}\right]~(\mod{p_m}) kongruenciáknak megfelelőeknek pedig változatlanul -\left[\frac{p_m}{6}\right].

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
[3252] Fálesz Mihály2010-02-15 10:16:52

Következő gondolkodnivaló: Legyen most a egy 0-tól különböző maradék modulo p, és párosítsuk össze a modulo p maradékokat úgy, hogy minden párban a legyen a szorzat.

Előzmény: [3251] Fálesz Mihály, 2010-02-15 10:16:11
[3251] Fálesz Mihály2010-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 \equiv (p-1)! = 
\bigg(1\cdot(p-1)\bigg)\cdot\bigg(2\cdot\frac{p-1}2\bigg)\cdot\dots
\equiv (-1)^{(p-1)/2}.~ ~(\mod p)
(1)

Mivel p>2, a +1 és -1 maradékok különbözőek, a -1\equiv(-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\equiv-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\equiv+1(mod p)):

-1\equiv(p-1)!=(a.(-a)).(1.(p-1))....\equiv(-1)(p-3)/2.  (mod p)(2)

A -1\equiv(-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
[3250] bily712010-02-14 23:27:08

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

akkor (p-a)2\equiv-1(mod p).

Előzmény: [3247] bily71, 2010-02-14 22:12:36
[3249] bily712010-02-14 23:19:10

Ez megoldható, legyen x1\equiv0(mod p1).

Előzmény: [3245] Róbert Gida, 2010-02-14 16:09:01
[3248] bily712010-02-14 23:10:38

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

x1\equivm(mod p1)

x2\equivm(mod p2)

...

xn\equivm(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\equiv1(mod 5)

x2\equiv-1(mod 5)

x3\equiv1(mod 7)

x4\equiv-1(mod 7)

x5\equiv2(mod 11)

...

x_n\equiv\left[\frac{p_n}{6}\right](\mod{p_n})

x_{n+1}\equiv-\left[\frac{p_n}{6}\right](\mod{p_n}),

ahol ha pn=6k+1, akkor \left[\frac{p_n}{6}\right] 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] bily712010-02-14 22:12:36

Ezt kapjuk:

(p-1)\equiv2\frac{p-1}{2}\equiv3\frac{p-1}{2}\equiv...\equiv\frac{p-1}{2}\frac{p-1}{\frac{p-1}{2}}\equiv-1(\mod{p}

.

Két eset lehetséges, első:

2 | \frac{p-1}{2}, ekkor van \frac{p-1}{2} darab számpárunk, amelyek szorzata ab\equiv-1(mod p), ha behelyettesítünk, akkor ezt kapjuk:

(p-1)!\equiv(-1)^{\frac{p-1}{2}}\equiv-1(\mod{p})

.

Második:

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

(p-1)!\equiv(-1)^{\frac{p-1}{2}+1}\equiv-1(\mod{p})

.

Előzmény: [3243] Fálesz Mihály, 2010-02-13 12:38:17
[3246] jonas2010-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
[3245] Róbert Gida2010-02-14 16:09:01

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

Előzmény: [3244] bily71, 2010-02-13 12:46:49
[3244] bily712010-02-13 12:46:49

Triviális megoldás az

x1\equiv1(mod p1)

x2\equiv2(mod p2)

...

xn\equivn(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:

x1\equiva1(mod p1)

x2\equiva2(mod p2)

x3\equiva3(mod p3)

...

xm\equivam(mod pm)

xm+1\equivb1(mod pm+1)

...

xm+n\equivbn(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
[3243] Fálesz Mihály2010-02-13 12:38:17

Ú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:


1 \cdot (p-1) \equiv 2 \cdot \frac{p-1}{2} \equiv ... \equiv -1 ~ (\mod p).

Milyen eredményt kapunk ebből?

Előzmény: [3234] bily71, 2010-02-11 17:28:19
[3242] Fálesz Mihály2010-02-13 12:12:33

Írjuk inkább így:


a = \frac{(x-z)y^\alpha + (y-x)z^\alpha + (z-y)x^\alpha}{
(y-x)(z-x)(z-y)}.

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

Ha \alpha\le0 vagy \alpha\ge0, akkor az x^\alpha függvény konvex, a három pontra illesztett parabola felfelé áll, tehát a\ge0.

Ha pedig 0\le\alpha\le1, akkor x^\alpha konkáv, a parabola lefelé áll, tehát a\le0.

Előzmény: [3240] Lóczi Lajos, 2010-02-12 22:03:59
[3241] bily712010-02-12 22:53:59

És ha végtelen sok kongruenciából álló rendszerről van szó ugyanezen feltételekkel?

Előzmény: [3239] jonas, 2010-02-12 21:57:23
[3240] Lóczi Lajos2010-02-12 22:03:59

a=-\frac{-y x^{\alpha }+z x^{\alpha }+x y^{\alpha }-x z^{\alpha }-z y^{\alpha }+y z^{\alpha }}{(x-y) (x-z) (y-z)}

Előzmény: [3237] Fálesz Mihály, 2010-02-12 11:31:26
[3239] jonas2010-02-12 21:57:23

Nyilván nem, mert a modulusok relatív prímek, így mindegyik sorozat tagjaihoz egyet hozzáadva a kapott sorozatoknak van metszetük, és az ebben lévő számok egyik eredeti sorozatban sincs benne.

Előzmény: [3238] bily71, 2010-02-12 21:01:37
[3238] bily712010-02-12 21:01:37

Konstruálható-e inkongruens lefedőrendszer csak prím modulusú tagokból?

[3237] Fálesz Mihály2010-02-12 11:31:26

Sikerült valakinek kifejezni az a együtthatót az x,y,z,\alpha számokkal?

Előzmény: [3226] Fálesz Mihály, 2010-02-10 10:41:39
[3236] Róbert Gida2010-02-12 00:44:36

De, halálismert. Specmatos gimnáziumban is ugyanezt a bizonyítást mondják el, latinnégyzetes rizsa nélkül.

Előzmény: [3231] bily71, 2010-02-11 12:49:08

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]