Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

4. A feladatok megoldásai

4. A feladatok megoldásai

1. Ha csak annyit kell Biankának bizonyítania, hogy ki tudja nyitni a C kaput, akkor elég, ha Elemér elkíséri a B elágazásig, ott megáll, míg Bianka besétál a barlangba az egyik elágazáson, majd kijön a másikon. Ha azonban nem szeretnék, hogy az Elemért kísérő Fidél is megtudja, hogy Bianka tudja-e a titkot vagy nem, akkor a következőképp járnak el: az A bejáratnál Elemér (és Fidél) vár, míg Bianka bemegy a barlang C kapujáig. Ekkor Elemér bemegy a B pontig, és ott kihívja Biankát a barlang valamelyik ágán. Ha nem azon jön ki, Bianka nem tudja a titkot. Ha ott jön ki, megismétlik az eljárást néhányszor. Fidél számára semmi sem bizonyítja, hogy amit lát, nemcsak egy előre megbeszélt színjáték.

2. Az eredmény

242 424 242 - 1 mod 12 121 212 121 = 1 154 401 152 .

Megadjuk a számításokhoz használt táblázatot:

12 121 212 121 0 242 424 242 1 ( ? 12 121 212 121 242 424 242 ? = 50 ) 21 - 50 ( ? 242 424 242 21 ? = 11 544 011 ) 11 577 200 551 10 - 577 200 601 1 1 154 401 152

3. Először a korábban tanult módszerrel meghatározzuk a 7 - 1 mod 11 és a 11 - 1 mod 7 inverzeket. Igen rövid számolás után – de akár fejben próbálgatással is – kapjuk, hogy 7 - 1 mod 11 = 8 és 11 - 1 mod 7 = 4 - 1 mod 7 = 2 . Az x = a q q ¯ p + b p p ¯ q képletbe helyettesítve kapjuk, hogy x = 2 · 11 · 2 + 3 · 7 · 8 = 212 , de 212 ? 58 ( mod 77 ) , így a kongruenciarendszer összes megoldása leírható az x ? 58 ( mod 77 ) kongruenciával, illetve felírható x = 58 + 77 k alakban, ahol k tetszőleges egész. A másik kongruenciarendszer megoldása hasonló számítás után x = - 2 · 11 · 2 - 3 · 7 · 8 = - 212 , de - 212 ? 19 ( mod 77 ) miatt az összes megoldása x ? 19 ( mod 77 ) alakba, illetve x = 19 + 77 k alakba írható, ahol k tetszőleges egész.

4. Mivel 31 + 1 4 = 8 , ezért a négyzetgyökök ± 2 8 mod 31 , illetve ± 5 8 mod 31 . A 8-dik hatvány kiszámítható 3 négyzetreemeléssel. Ezek eredményi 4, 16, 8, illetve 5, 15, 5, tehát 2 négyzetgyökei 8 és 23 ( 23 ? - 8 ( mod 31 ) ), míg 5 négyzetgyökei 25 és 6 ( 6 ? - 25 ( mod 31 ) ).

5. Tekintsük először az x 2 ? 53 ( mod 7 ) és az x 2 ? 53 ( mod 11 ) , illetve a velük ekvivalens x 2 ? 4 ( mod 7 ) és x 2 ? 9 ( mod 11 ) kongruenciákat! Ezek megoldásai ± 2 , illetve ± 3 , amit fejben számolva is azonnal látunk, de megkaphatjuk a ± 4 7 + 1 4 mod 7 , illetve a ± 9 11 + 1 4 mod 11 hatványok kiszámolásával is. Ezek után tehát az alábbi négy kongruenciarendszert kell megoldanunk:

x ? 2 ( mod 7 ) x ? 3 ( mod 11 ) (6) x ? 2 ( mod 7 ) x ? - 3 ( mod 11 ) (7) x ? - 2 ( mod 7 ) x ? 3 ( mod 11 ) (8) x ? - 2 ( mod 7 ) x ? - 3 ( mod 11 ) (9)

Az (1) és a (4) kongruenciarendszert már megoldottuk a 3. feladatban, a megoldás 58, illetve 19. A másik két rendszer hasonlóan oldható meg, a megoldások 30 és 47. Tehát 53 négyzetgyökei modulo 77 számolva: 19, 30, 47, 58.

6. Válasszunk egy véletlen v ? Z n * elemet, és legyen a = v 2 mod n . Az f eljárás segítségével határozzuk meg egyik gyökét. Annak valószínűsége, hogy f nem ad új gyököt, azaz hogy f ( a ) = v vagy f ( a ) = - v épp 1 / 2 , míg 1 / 2 annak a valószínűsége is, hogy f ( a ) ? ± v , tehát a négy gyöke: ± v , ± f ( a ) . Így a fenti eljárás k -szori megismétlése után 1 / 2 k annak az esélye, hogy sikertelenül járunk.

7. Álnégyzetelem, hisz 19 ? 5 ( mod 7 ) , míg 19 ? 8 ( mod 11 ) , és az Euler-feltétellel azonnal látható, de fejben is könnyen ellenőrizhető az összes lehetőség végigszámolásával, hogy 5 nem négyzetelem modulo 7, és 8 nem négyzetelem modulo 11. Z 77 * négyzetelemeinek listája: 1, 4, 9, 15, 16, 23, 25, 36, 37, 53, 58, 60, 64, 67, 71. Az álnégyzetek listája: 6, 10, 13, 17, 19, 24, 40, 41, 52, 54, 61, 62, 68, 73, 76.

8. Az 58 négyzetelem, a többi nem. Ennek bizonyítását az Euler-feltétel is elvégezhetjük (ld. (3)), de egyszerűbb számítás is elég. Ha x 0 az egyik gyök, és x 0 négyzetelem, akkor kielégíti az x 2 ? x 0 ( mod 77 ) kongruenciát, de akkor kielégíti a x 2 ? x 0 ( mod 7 ) és a x 2 ? x 0 ( mod 11 ) kongruenciákat is. Ezek szerint az előző feladat megoldásában megadott négy kongruenciarendszer közül azt kell kiválasztani, melynek mindkét kongruenciájában négyzetelem áll a jobb oldalon. Könnyű ellenőrizni, hogy ez csak az (1) kongruenciarendszerre áll, tehát ennek megoldása, vagyis 58 az egyetlen négyzetelem modulo 77.

9. Ha a ? S , akkor a négyzetelem modulo p és modulo q is, azaz az Euler-feltétel szerint a ( p - 1 ) / 2 ? 0 vagy 1 ( mod p ) és a ( q - 1 ) / 2 ? 0 vagy 1 ( mod q ) . Eszerint

a ( p - 1 ) ( q - 1 ) + 4 8 2 = a p - 1 2 q - 1 2 a ? a ( mod p )

és hasonlóképpen

a ( p - 1 ) ( q - 1 ) + 4 8 2 = a q - 1 2 p - 1 2 a ? a ( mod q ) .

Ezekből következik, hogy

a ( p - 1 ) ( q - 1 ) + 4 8 2 ? a ( mod n ) ,

ami bizonyítja, hogy az x ? S ? x 2 mod n leképezés S egy permutációja, és hogy inverze az x ? S ? x ( p - 1 ) ( q - 1 ) + 4 8 mod n leképezés.

10. Az alábbi lépéseket elegendően sokszor – legalább k 2 -szer – megismétlik:

  1. Bianka véletlen sorrendbe állítja a színeket, és e színkiosztás mellett előállítja a b 1 b 1 ' b 2 b 2 ' b v b v ' bitsorozatot (ilyenből összesen 6 létezik, veszi tehát ezek egyikét). A fenti bitsorozat minden b bitjéhez választ egy véletlen x b ? Z n * elemet, és a már ismert módon, az m b x b 2 mod n képlettel borítékolja. Végül a borítékolt bitek sorozatát elküldi Elemérnek.

  2. Elemér választ egy ( i , j ) élt, ahol i és j egy-egy csúcs sorszáma.

  3. Bianka visszaküldi a kiválasztott két csúcs borítékolt bitjei kibontásához szükséges információkat, azaz a ( b i , x b i ) , ( b i ' , x b i ' ) , ( b j , x b j ) , ( b j ' , x b j ' ) számpárokat.

  4. Elemér ellenőrzi, hogy a két csúcs helyesen van-e kódolva, és hogy valóban különböző színűek-e.