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: Valaki mondja meg!

  [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]  

Szeretnél hozzászólni? Jelentkezz be.
[882] Euler2009-03-27 21:09:46

Az n=4-re végtelen leszállással lehet bizonyitani pl., ami eleminek mondható.

Előzmény: [874] Gábor1905, 2009-03-26 22:14:46
[881] jonas2009-03-27 16:37:56

Most már otthon vagyok és megnéztem a Szalay: Számelmélet könyvet. Az n=4 esetre leír egy nem túl nehéz elemi megoldást. Az n=3 esetet nem bizonyítja, de megemlíti, hogy az Euler-egészek segítségével látták be.

Előzmény: [877] jonas, 2009-03-27 10:59:51
[880] R.R King2009-03-27 14:38:17

és n=3-ra van elemi bizonyítása...rossz napom van

Előzmény: [879] R.R King, 2009-03-27 14:36:49
[879] R.R King2009-03-27 14:36:49

n=3 van az Euler egészekkel. bocsánat

[878] R.R King2009-03-27 14:36:01

Freud: Számelmélet könyvében benne van az n=4 és az n=3 eset is, de az n=4 Euler-egészekkel (ha jól emlékszem). Gábor azt állította, h az előbbire van középiskolás módszerekkel megoldása. Én szkeptikus vagyok, de ne legyen igazam:) Szerintem egyszer mindenki megkísérli bizonyítani az n=3,4-et aki olvasott gimiben Fermat sejtésről...(aztán az esetek többségében besül a próbálkozás)

Előzmény: [877] jonas, 2009-03-27 10:59:51
[877] jonas2009-03-27 10:59:51

Most nem otthon vagyok, úgyhogy nem tudom ellenőrizni, de a Szalay: Számelmélet könyvben nincs benne az n=3 és az n=4 esetek bizonyítása?

Előzmény: [874] Gábor1905, 2009-03-26 22:14:46
[876] Euler2009-03-27 00:18:01

Szerintem nincs kizárva, hogy bizonyitható, n=4 esetre pl. elég "könnyű" a bizonyitás, én is kiváncsian várom a bizonyitásodat.

Előzmény: [874] Gábor1905, 2009-03-26 22:14:46
[875] jenei.attila2009-03-26 23:36:09

Könnyen meglehet. Írd be, szívesen átrágjuk rajta magunkat.

Előzmény: [874] Gábor1905, 2009-03-26 22:14:46
[874] Gábor19052009-03-26 22:14:46

Üdv! Csak azt szeretném kérdezni hogy szerintetek gimis matekkal bizonyítható-e a Fermat sejtés n=3 esete?Szerintem sikerült csak még nem írtam le!:D:D:D

[873] jenei.attila2009-03-23 17:11:37

Továbbra is úgy értelmezem a kérdést, hogy "Hány olyan elem van 64 elemű testben, amely nincs benne valódi résztestben?" Ennek a testnek valóban csak 2,4 és 8 elemű résztestei lehetnek mivel minden test vektortér bármelyik részteste felett, ahogy Fálesz Mihály is írta. Ilyen résztestei pedig valóban vannak is, mégpedig mindegyikből csak 1-1. Ez a test (GF(64)) a x64-x polinomnak felbontási teste (e testben lineáris gyöktényezők szorzatára bomlik), sőt pontosan a x64-x polinom gyökei alkotják a test elemeit. Az, hogy ennek a testnek van 2, 4 és 8 elemű részteste abból következik, hogy a x2-x, x4-x és x8-x polinomok osztói a x64-x polinomnak, amelyek gyökei így szintén GF(64) elemei. Ezek a gyökök könnyen bizonyíthatóan résztesteket alkotnak, mert (x+y)2=x+y,(xy)2=xy,(-x)2=-x,(x-1)2=x-1 (itt kihasználtuk, hogy a test 2 karakterisztikájú). Hasonlóan 4 és 8 kitevővel. Más 2, 4 és 8 elemű résztestei GF(64)-nek nincsenek, mint a most felsorolt polinomok gyökeiből álló testek, mert az azt jelentené hogy a x2-x, x4-x és x8-x polinomoknak 2,4 illetve 8-nál több gyökük lenne ami lehetetlen. A 2 elemű (0,1 -et tartalmazó) résztest részteste a 4 és 8 elemű testeknek is, azonban a 4 elemű résztest nem részteste a 8 eleműnek (mivel a 8 elemű test nem lehet vektortér a 4 elemű felett). Vagyis e résztestek uniója 10 elemet tartalmaz, a maradék 54 elem pedig egyik résztestnek sem eleme.

Előzmény: [862] Bubcsi, 2009-03-17 11:01:41
[872] lgdt2009-03-20 02:17:01

A Wikipedia szerint ez egy ismert probléma, amelyre eddig nem találtak polinom futásidejű algoritmust, és azt sem tudják, hogy van-e; viszont az inverzét, a hatványozást könnyű hatékonyan elvégezni. Ha jól tudom, az sem ismert, hogy léteznek-e bizonyítottan ilyen tulajdonságú ún. csapóajtófüggvények.

The existence of one-way functions

Előzmény: [867] Borel, 2009-03-18 19:25:53
[871] jonas2009-03-18 21:55:16

Nézzük. A 7-1 prímfelbontása 2.3, úgyhogy elég a második és harmadik hatványt megnézni, ha egyik sem 1, akkor a rend 6. Mármost 32=9\equiv2mod 7 az nem 1, és 33\equiv2*3=6 szintén nem 1, tehát a 3 rendje 6.

Előzmény: [870] Borel, 2009-03-18 21:47:08
[870] Borel2009-03-18 21:47:08

Köszönöm a válaszokat. Én is így számoltam eddig, csakhát reméltem van valami hatékonyabb megoldás is... n=7-re a 3 rendjéért már meg kell szenvedni (szg. nélkül).

Előzmény: [869] Tibixe, 2009-03-18 21:03:47
[869] Tibixe2009-03-18 21:03:47

Végignézheted szép sorban bd-t minden szóba jöhető d-re, azaz amikor d poz. egész és osztja \varphi(n)-t, aztán ha 1 maradékot ad, akkor az aktuális d lesz a válasz. Kis n-re ez is jó.

Előzmény: [867] Borel, 2009-03-18 19:25:53
[868] R.R King2009-03-18 20:26:50

Üdv. Freud: Számelmélet című könyvében pl. utána lehet nézni, de a google is segíthet:) a rend emlékeim szerint a legkisebb ,,jó'' kitevő és osztója minden jó kitevőnek pl. fi(n)-nek is. fi(n) n-ig az n hez relatív prímek száma. Konkrét b és n esetén tehát a rend a fi(n) osztói közül kerül ki. Régen tanultam ezekről talán diszkrét logaritmus(index) címszóval keresd a problémát.

Előzmény: [867] Borel, 2009-03-18 19:25:53
[867] Borel2009-03-18 19:25:53

Sziasztok!

Egy kis segítségre lenne szükségem: Rn redukált maradékosztályok csoportjában hogy kell elem rendjét kiszámolni? Vagy ami ezzel ekvivalens, b a k-adikon kongruens 1 modulo n egyenletet hogy kell megoldani? (b és n ismert)

Üdv: Borel

[866] jenei.attila2009-03-17 21:09:20

Igaz. Ezen még gondolkozok.

Előzmény: [864] Fálesz Mihály, 2009-03-17 13:25:03
[865] gubanc2009-03-17 18:32:01

Köszönöm szépen!

Előzmény: [861] nadorp, 2009-03-16 18:20:13
[864] Fálesz Mihály2009-03-17 13:25:03

A 64-elemű testnek csak 2-, 4- és 8-elemű résztestei vannak.

A bővebb test vektortér a résztest felett, ezért az elemszáma csak hatványa lehet a résztest elemszámának.

Előzmény: [863] jenei.attila, 2009-03-17 12:15:43
[863] jenei.attila2009-03-17 12:15:43

"Hány olyan elem van 64 elemű test felett...", ezt úgy érted, hogy "Hány olyan elem van 64 elemű testben..."? Ha igen, akkor szerintem 32. Mivel a 64 elemű test legbővebb valódi részteste 32 elemű és a többi résztest ennek részteste, a maradék 32 elem nem eleme egyetlen résztestnek sem.

Előzmény: [862] Bubcsi, 2009-03-17 11:01:41
[862] Bubcsi2009-03-17 11:01:41

Valki segítene ebben a feladatban? Hány olyan elem van 64 elemű test felett amely nincs benne valódi résztestben?

Elöre is köszönöm!

[861] nadorp2009-03-16 18:20:13

Biztos van egyszerűbb megoldás is ( maradékosztályokat felhasználó vagy gráfelméleti), de ezt nem találtam.

Jelölje Ai azon függvények halmazát,melyek maximuma i. Ekkor ha 0\leqi\leqk ,akkor

Ai elemszáma (k+1)n-kn,mert

f\inAi esetén i-k\leqf(j)\leqi, tehát f k+1 féle értéket vehet fel, így azokat a k+1 elemből képezhető n hosszú sorozatokat kell leszámolni, melyek legalább egyszer tartalmazzák az i-t.

Ha pedig -k\leqi\leq-1, akkor a fentihez hasonlóan

Ai elemszáma (i+k+1)n-(i+k)n

A fenti módszerrel minden függvényt pontosan egyszer számoltuk, hiszen egy Ai-n belül a függvények különböznek és i\neqj esetén minden Ai-ben szereplő függvény eltér minden Aj-ben szereplő függvénytől, mert a maximumuk különböző. Az összes függvény száma

(1n-0n)+(2n-1n)+...+(kn-(k-1)n)+(k+1)((k+1)n-kn)=(k+1)n+1-kn+1

Előzmény: [860] gubanc, 2009-03-13 12:41:36
[860] gubanc2009-03-13 12:41:36

Nagyrabecsült FÓRUMOSOK! Sehogy sem bírok ezzel a feladattalÿ:( segítenétek?

Legyenek n és k adott pozitív egészek és tekintsük azon f: {1; 2; 3; ...; n} \to {-k; -k+1; ...; k-1; k} függvényeket, amelyekre |f(i) - f(j)|\lek bármely i, j\in {1; 2; 3; ...; n} esetén. Hány ilyen f függvény van?

Üdv: gubanc

[859] sakkmath2009-03-10 10:01:07

Talán ez is segít (a részleteket a könyv mellőzi):

Előzmény: [855] plac, 2009-03-07 16:12:53
[858] plac2009-03-09 15:57:15

Ez is hatalmas segítség volt köszönöm szépen!

Előzmény: [857] Lóczi Lajos, 2009-03-08 20:49:07

  [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]