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.

[3222] Fernando

2010-02-08 11:27:47

Kedves Bily71!

A Fermat-álprímekről (341 Fermat-álprím 2-es alapra nézve), Carmichael számokról (pl. 561) és a Fermat-tétel megfordításának lehetőségiről olvashatsz: "Megyesi László: Bevezetés a számelméletbe" című könyvében (Polygon, Szeged 1997)

Előzmény: [3212] bily71, 2010-02-07 19:23:42

[3221] Sirpi	2010-02-08 10:52:51
Miért kell oda a $\varphi$ (n) ? A p kitevőjét bármilyen pozitívra állítod, a számláló akkor is -1 lesz a jobb oldalon. Igazából ha már általánosítás (és itt nem is kell, hogy p prím, csak hogy 2-nél nagyobb páratlan, valamint p és n relatív prímek): $(p-n)^{\varphi(n)-1} \equiv \frac{p-1}n (\mod p)$ , de ez megintcsak ekvivalens a kis Fermat-tétellel.
Előzmény: [3220] bily71, 2010-02-08 10:03:21

[3220] bily71

2010-02-08 10:03:21

Nem RG bosszantásául, csak, mert érdekesnek találtam, ugyanez általánosan:

$(p-n)^{p-2}\equiv\frac{p^{\varphi(n)}-1}{n}(\mod{p}),$

ahol p $\in$ P, n $\in$ N, p>2, 0<n<p.

Előzmény: [3219] Sirpi, 2010-02-08 09:15:16

[3219] Sirpi

2010-02-08 09:15:16

RG sajátságos stílusával azt próbálta sugallni, hogy ez az összefüggés prímekre pl. ekvivalens a kis-Fermat tétellel (sőt, a következő átalakításnál csak azt használom ki, hogy p páratlan poz. egész):

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

2^.(p-2)^p-2 $\equiv$ p-1

-2^.(p-2)^p-2 $\equiv$ -(p-1)

(p-2)^.(p-2)^p-2 $\equiv$ 1

(p-2)^p-1 $\equiv$ 1

Ez meg tényleg a kis-Fermat a=p-2-es alapra. Már ez az alap is nagyon sok nem-prímet lebuktat, de ha további alapokat is nézünk, akkor egyre biztosabban eldönthető, hogy p prím-e. Egyébként ez a prímteszt erősíthető (Rabin-Miller-féle prímteszt):

Legyen p-1=2^m^.k, és vegyünk egy 1<a<p-1 alapot. Számítsuk ki az a^k,a^2k,a^4k,...,a^{2^mk}=a^p-1 számokat (az elsőt "bináris" hatványozással, a többit mindig az előzőből sima négyzetre emeléssel).

Ha az utolsó nem 1 maradékot ad p-vel osztva, akkor p biztosan összetett. Ha már a^k $\equiv$ 1, akkor a teszt nem tud semmit mondani. Ellenkező esetben viszont van néhány 1-től különböző elem a sorozatban, aztán a végén néhány 1-es. Van tehát egy utolsó, 1-től különböző elem. Ha ez nem -1, akkor p összetett, ez a teszt lényege (ha p prím, akkor az x² $\equiv$ 1-nek csak 2 megoldása lehet, az 1 és a -1).

Bizonyítható, hogy adott p összetett számra a szóba jöhető a-k legfeljebb negyede nem buktatja le p összetettségét, vagyis pl. 20 véletlen a-t választva 1/4²⁰ esélye lesz annak, hogy p összetett és ez mégse derült ki. A teszt viszont hiába buktatja le p-t, semmilyen támpontot nem ad p osztóira.

Előzmény: [3218] Róbert Gida, 2010-02-07 22:48:06

[3218] Róbert Gida	2010-02-07 22:48:06
Újra felfedezted(?) a Fermat-féle prímtesztet.
Előzmény: [3217] bily71, 2010-02-07 22:42:34

[3217] bily71	2010-02-07 22:42:34
Sajnos van, ellenkező esetben lenne egy viszonylag gyors prímtesztünk, ha (p-2)^p-2 értékét a gyorshatványozás módszerével számoljuk ki.
Előzmény: [3213] R.R King, 2010-02-07 19:35:45

[3216] bily71	2010-02-07 22:31:14
Igazad van, hiányzik a p>2 feltétel.
Előzmény: [3215] Róbert Gida, 2010-02-07 20:29:02

[3215] Róbert Gida

2010-02-07 20:29:02

p=2-re 0⁰ nincs értelmezve.

(A hozzászólás egy részét töröltem. Moderátor)

Előzmény: [3212] bily71, 2010-02-07 19:23:42

[3214] Lóczi Lajos	2010-02-07 19:53:57
Ez 1000 alatt pontosan az alábbi 3 számra igaz: 341, (a hasonló kontextusból jól ismert) 561 és a 645.
Előzmény: [3213] R.R King, 2010-02-07 19:35:45

[3213] R.R King	2010-02-07 19:35:45
Igaz, és kis Fermat tétellel elég könnyen kihozható! Ami érdekes lehet, hogy van-e olyan páratlan összetett szám, amelyre még igaz ez a kongruencia..
Előzmény: [3212] bily71, 2010-02-07 19:23:42

Már regisztráltál?
Új vendég vagy?