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]    [162]    [163]    [164]    [165]    [166]    [167]    [168]    [169]    [170]    [171]    [172]    [173]    [174]    [175]    [176]    [177]    [178]    [179]    [180]    [181]    [182]    [183]    [184]    [185]    [186]    [187]    [188]    [189]    [190]    [191]    [192]    [193]    [194]    [195]    [196]    [197]    [198]    [199]    [200]    [201]    [202]    [203]    [204]    [205]    [206]    [207]    [208]    [209]    [210]    [211]    [212]    [213]    [214]    [215]    [216]    [217]    [218]    [219]    [220]    [221]    [222]    [223]    [224]    [225]    [226]    [227]    [228]    [229]    [230]    [231]    [232]    [233]    [234]    [235]    [236]    [237]    [238]    [239]    [240]    [241]    [242]    [243]    [244]    [245]    [246]    [247]    [248]    [249]    [250]    [251]    [252]    [253]    [254]    [255]    [256]    [257]    [258]    [259]    [260]    [261]    [262]    [263]    [264]    [265]    [266]    [267]    [268]    [269]    [270]    [271]    [272]    [273]    [274]    [275]    [276]    [277]    [278]    [279]    [280]    [281]    [282]    [283]    [284]    [285]    [286]    [287]    [288]    [289]    [290]    [291]    [292]    [293]    [294]    [295]    [296]    [297]    [298]    [299]    [300]    [301]    [302]    [303]    [304]    [305]    [306]    [307]    [308]    [309]    [310]    [311]    [312]    [313]    [314]    [315]    [316]    [317]    [318]    [319]    [320]    [321]    [322]    [323]    [324]    [325]    [326]    [327]    [328]    [329]    [330]    [331]    [332]    [333]    [334]    [335]    [336]    [337]    [338]    [339]    [340]    [341]    [342]    [343]    [344]    [345]    [346]    [347]    [348]    [349]    [350]    [351]    [352]    [353]    [354]    [355]    [356]    [357]    [358]    [359]    [360]    [361]    [362]    [363]    [364]    [365]    [366]    [367]    [368]    [369]    [370]    [371]    [372]    [373]    [374]    [375]    [376]    [377]    [378]    [379]    [380]    [381]    [382]    [383]    [384]    [385]    [386]    [387]    [388]    [389]    [390]    [391]    [392]    [393]    [394]    [395]    [396]    [397]    [398]    [399]    [400]    [401]    [402]  

Szeretnél hozzászólni? Jelentkezz be.
[3182] Róbert Gida2010-02-01 11:43:16

Halál ismert példa, k=n-1 jelöléssel és osztással azt állítja a feladat, hogy \binom {p-1}{k} \equiv {(-1)}^k (\mod p). Ami például Graham Konkrét matematika című könyvében az 5. fejezet 5. példája. És szerinte ez k=0-ra spec. esete a Wilson tételnek. Egy túróst.

Előzmény: [3179] Maga Péter, 2010-02-01 08:11:25
[3183] Róbert Gida2010-02-01 11:46:39

Akarom mondani szerinte speciális esete a Wilson tétel, ha k=0. No comment.

Előzmény: [3182] Róbert Gida, 2010-02-01 11:43:16
[3184] Fálesz Mihály2010-02-01 12:04:48

Úgy látom, kezdenek forrósodni a kedélyek...

Szóval,

(p-1)!=(p-n)!.(p-n+1)(p-n+2)...(p-1)\equiv(p-n)!.(-n+1)(-n+2)...(-1)=(p-n)!.(-1)n-1(n-1)! (mod  p),

és persze egyszerűsíthetünk bármivel, ami nem osztható p-vel.

De hol van ebben a Wilson-tétel?

[3185] bily712010-02-01 15:41:23

Wilson szerint (p-1)!\equivp-1(mod p), ha p prím.

Tekintsük a p számrendszerbeli szorzótáblát. Ha a 0-át kihagyjuk, azaz a számokat csak 1-től p-1-ig szorozzuk össze, akkor a táblázat i-edik oszlopának j-edik eleme aij\equivi.j(mod p).

Ebből következik, hogy i!\equivaij(mod p), ahol j\equiv(i-1)!(mod p).

A táblázat, mivel p prím, egy latin négyzet, amely nem tartalmazza a 0-át és középpontosan szimmetrikus, azaz aij\equiva(p-i)(p-j)(mod p), továbbá tengelyesen is szimmetrikus oly módon, hogy aij\equivp-a(p-i)j(mod p). Az előbb felsorolt tulajdonságok ismertek, bizonyításukat most mellőzhetjük.

A fenti szimmetriákból és a (p-n)!\equiv\frac{(p-1)!}{(n-1)!}(-1)^{n-1}(\mod{p}) összefüggésből adódik, hogy (p-1)!\equivp-1(mod p), tehát ez egy speciális eset.

Előzmény: [3184] Fálesz Mihály, 2010-02-01 12:04:48
[3186] Róbert Gida2010-02-01 17:11:09

"Az előbb felsorolt tulajdonságok ismertek, bizonyításukat most mellőzhetjük."

Életemben nem hallottam, hogy valaki is latin négyzetekkel próbálná bebizonyítani a Wilson tételt. Ne tartsd magadban!

Előzmény: [3185] bily71, 2010-02-01 15:41:23
[3187] bily712010-02-01 20:03:10

Bármely n számrendszerbeli szorzótábla, (tehát nemcsak prím) ha elhagyjuk a 0-át, mint szorzótényezőt, középontosan szimmetrikus, hiszen

ab\equiv(n-a)(n-b)\equiv(mod n).

Ugyanezen táblázat tengelyesen is szimmetrikus, a maradékok abszolútértékére tekintettel, hiszen

|ab|\equiv|(n-a)b|\equiv|a(n-b)|(mod n).

Ez nem fontos, de, ha már szóba került: ha a szorzótábla p, azaz prím számrendszerbeli, akkor az a szám csak egyszer fordulhat elő soronként, ugyanis, ha többször szerepelne, akkor vagy a|p, vagy (a,p)\ne1, egyik sem lehetséges, hiszen p prím, tehát a táblázat latin négyzet.

Ezen tulajdonságokat immáron bizonyítottnak tekinthetjük.

Most már nincs több teendőnk, csak a behelyettesítéseket kell végrehajtani a

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

képletbe, és az eredmény a Wilson-tétel.

Egyébként szó sincs arról, hogy ki kellene számolni (n-1)! értékét, vagyis, hogy n-2 darab szorzást kellene eszközölni egy szám Wilson-féle tesztelése során. Legyen n=p_1^{\alpha_1}p_2^{\alpha_2}...p_m^{\alpha_m}. Legyen k=pi\alphai, azaz a prímek kitevőjükkel vett szorzatok közül a legnagyobb. Ekkor

k!\equiv0(mod n).

Tehát elég k darab szorzást és k darab osztást, azaz 2k darab műveletet végrehajtani.

De az is lehet, hogy szokás szerint tévedtem, ez esetben elnézést kérek mindenkitől.

Előzmény: [3186] Róbert Gida, 2010-02-01 17:11:09
[3188] m2mm2010-02-01 21:13:36

Képletedből nem következik a Wilson-tétel. n=1-et behelyettesítve pontosan azt kapod, hogy (p-1)!\equiv(p-1)! (mod p).

Előzmény: [3187] bily71, 2010-02-01 20:03:10
[3189] m2mm2010-02-01 21:32:17

Remélem még nem volt, és igaz(saját alkotás): a,b,c valós számokra abc=1. Bizonyítsuk be, hogy a4+b4+c4+a+b+c\gea3b+b3c+c3a+ab3+bc3+ca3. Ha közismert lenne, akkor elnézést.

[3190] Maga Péter2010-02-01 21:37:30

1. Sokat téptem a számat a Goldbach-topikon (meg hát mások is), most bily testhezálló dolgot csinált, végre rendesen. Amikor hülyeséget csinált, leszóltuk érte. Most nem csinál hülyeséget, ha ezért is leszóljuk, akkor azt fogja gondolni, hogy igazából mindegy, hogy mit csinál.

2. Amikor te a Goldbach-topikban megtetted a hozzászólást, ami szerint a Dirichletben nem a végtelen sok, hanem a legalább 1 prím a nehéz, akkor arra nem azt írtam, hogy ez halálismert. Nem ugattalak le, pedig én utána érdemben(!) hozzá tudtam szólni a dologhoz (ez most rólad nem mondható el).

3. Ha a gyereked beszélni tanul, gügyögésért ne vágd szájon. Valóban nem gügyögve kell beszélni, de didaktikailag messze nem optimális megoldás a szájonvágás.

Előzmény: [3182] Róbert Gida, 2010-02-01 11:43:16
[3191] Maga Péter2010-02-01 21:51:45

Nem baj, ha egy feladat közismert, biztosan sokan vannak, akik nem ismerik.

Előzmény: [3189] m2mm, 2010-02-01 21:32:17

  [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]    [162]    [163]    [164]    [165]    [166]    [167]    [168]    [169]    [170]    [171]    [172]    [173]    [174]    [175]    [176]    [177]    [178]    [179]    [180]    [181]    [182]    [183]    [184]    [185]    [186]    [187]    [188]    [189]    [190]    [191]    [192]    [193]    [194]    [195]    [196]    [197]    [198]    [199]    [200]    [201]    [202]    [203]    [204]    [205]    [206]    [207]    [208]    [209]    [210]    [211]    [212]    [213]    [214]    [215]    [216]    [217]    [218]    [219]    [220]    [221]    [222]    [223]    [224]    [225]    [226]    [227]    [228]    [229]    [230]    [231]    [232]    [233]    [234]    [235]    [236]    [237]    [238]    [239]    [240]    [241]    [242]    [243]    [244]    [245]    [246]    [247]    [248]    [249]    [250]    [251]    [252]    [253]    [254]    [255]    [256]    [257]    [258]    [259]    [260]    [261]    [262]    [263]    [264]    [265]    [266]    [267]    [268]    [269]    [270]    [271]    [272]    [273]    [274]    [275]    [276]    [277]    [278]    [279]    [280]    [281]    [282]    [283]    [284]    [285]    [286]    [287]    [288]    [289]    [290]    [291]    [292]    [293]    [294]    [295]    [296]    [297]    [298]    [299]    [300]    [301]    [302]    [303]    [304]    [305]    [306]    [307]    [308]    [309]    [310]    [311]    [312]    [313]    [314]    [315]    [316]    [317]    [318]    [319]    [320]    [321]    [322]    [323]    [324]    [325]    [326]    [327]    [328]    [329]    [330]    [331]    [332]    [333]    [334]    [335]    [336]    [337]    [338]    [339]    [340]    [341]    [342]    [343]    [344]    [345]    [346]    [347]    [348]    [349]    [350]    [351]    [352]    [353]    [354]    [355]    [356]    [357]    [358]    [359]    [360]    [361]    [362]    [363]    [364]    [365]    [366]    [367]    [368]    [369]    [370]    [371]    [372]    [373]    [374]    [375]    [376]    [377]    [378]    [379]    [380]    [381]    [382]    [383]    [384]    [385]    [386]    [387]    [388]    [389]    [390]    [391]    [392]    [393]    [394]    [395]    [396]    [397]    [398]    [399]    [400]    [401]    [402]