2^-1 mod 7 az mennyi és miért?

A 7 az prímszám, és ha PRÍMSZÁM szerinti maradékosztályokat nézek, akkor az ezekre értelmezett ,,szorzás''nak valóban lehet inverz műveletet megfeleltetni. Azt hiszem, ez az, amit úgy mondanak, hogy a prímszám szerinti maradékosztályok testek alkotnak.

Konkrétan: itt ugye a 2-vel való szorzáshoz keresek olyan számot, amellyel való szorzás éppen ,,lerontja'' a 2-vel való szorzást. Vagyis azt a számot jelölném 2⁻¹-gyel (ha van ilyen egyáltalán), amelyik az alábbi dologra képes:

(a · 2) · 2⁻¹ ≡ a (mod 7)

itt úgy értem, hogy a dolognak tetszőleges a-ra kell teljesülnie. Vagyis, ha tetszőleges a-t megszorzok 2-vel, akkor ugye az a az megváltozik, de ezt a változást bizton invertálhatom azáltal, hogy ezzel a bizonyos 2⁻¹-gyel újra megszorzom az eredményt, és akkor íme visszakapom az eredeti a-t. És ez mindig bizton igaz, függetlenül attól, mi is volt ez az eredeti a. Ez a lényeg, hogy ez az egyenlet az eredeti a konkrét értékétől függetlenül mondig stimmeljen.

Nohát az a kérdés, hogy van-e egyáltalán ilyen alkalmas 2⁻¹ szám.

Persze ahogy írtad is, a 4 az tényleg ilyen. A bizonyítást azonban nem merem vállalni, mert már rég volt nekem ez a tárgy. Én egyelőre ennyire jutottam:

Ugyehát olyan x számot tekintenék méltónak arra, hogy a 2⁻¹ megtisztelő címet adjam neki, ami képes arra, hogy tetszőleges a esetén kielégítse az alábbi kongruneciát:

(a · 2) · x ≡ a (mod 7)

most ezt írjuk át úgy, hogy mit is jelent, most kongruenciák nélkül, szóval csak az oszthatóság nyelvén megfogalmazva:

7 | (a · 2) · x - a

7 | 2a · x - a

A jobboldalon álló különbséget felírhatjuk szorzat lakban is (,,kiemeljük'' az a-t):

7 | a · (2x - 1)

Most használhatjuk ki azt, hogy a 7 az éppen prímszám. A prímtulajdonság épp azt jelenti, hogy prímszám csak úgy lehet osztója valamilyen szorzatnak, hogy ha egyúttal a szorzat legalább egyik tényezőjét is osztja. (Tehát egy prímszám nem tud ,,ravasz'' módon ,,megoszlani'' a szorzat két tényezője ,,között'', mint mondjuk a 6-os, amely képes úgy osztója lenni a 10·3-nak, hogy sem a 10-nek, sem a 3-nak ő maga nem osztója.)

[link]

fontos, hogy itt tényleg csak éppen a ,,prímtulajdonságot'' használom ki 7-re, a felbonthatatlanság fogalmába most nem érdemes belemenni.

Ez alapján:

7 | a · (2x - 1)

egyúttal azt is jelenti, hogy

7 | a, VAGY 7 | (2x - 1)

Most ezt újra visszaírom a kongruenciák nyelvére:

a ≡ 0 (mod 7), VAGY 2x ≡ 1 (mod 7)

Ez azt jelenti, hogy ha az a történetesen épp 0 (modulo 7), akkor az feladat által kívánt egyenlet meglehetősen unalmas módon úgyis magától teljesül (a 0 maradékosztályt bármivel szorozva egyöntetűen a 0 maradékosztályt kapjuk, vagyis, 7-tel osztható számot bármivel szorozva 7-tel osztható számot kapunk). A kérdés tehát igazából csak a nem-0 maradékosztályokra érdekes (nem mintha épp a 0-ra ne lenne igaz, de az eléggé triválisan úgyis igaz).

Az a lényeg, hogy az x értékét megmondhatjuk anélkül is, hogy a értékét tudnánk, szóval a-tól függetlenül is. Ha az a az épp 0, akkor úgyis triviálisan összejön a dolog, akkor akármit is vehetnék x-nek.

Ha az a pedig nem a 0 maradékosztály, akkor persze már nem mindegy az x megválasztása, de a lényeg akkor is igaz marad: vagyis hogy x-et ekkor is meg tudom mondani az a-től függetlenül is.

Szóval itt tartottunk:

a ≡ 0 (mod 7), VAGY 2x ≡ 1 (mod 7)

nézzük a nemtriviális esetet

2x ≡ 1 (mod 7)

vagy ha úgy jobban átlátható

7 | 2x - 1

próbálgatással is kijön, hogy az x := 4 választás esetén valóban stimmel az egyenlet. És ez minden a-ra stimmel:

0 · 2 · 4 ≡ 0 (mod 7)

1 · 2 · 4 ≡ 1 (mod 7)

2 · 2 · 4 ≡ 2 (mod 7)

3 · 2 · 4 ≡ 3 (mod 7)

4 · 2 · 4 ≡ 4 (mod 7)

5 · 2 · 4 ≡ 5 (mod 7)

6 · 2 · 4 ≡ 6 (mod 7)

látszik, hogy a 4 tényleg képes arra, hogy ,,pont visszacsinálja'' a 2-vel szorzás hatását, TELJESEN FÜGGETLENÜL ATTÓL, HOGY MI IS VOLT AZ EREDETI SZÁM, amit vissza kell csinálni.

Az a lényeg, hogy a

2⁻¹ := 4 (mod 7)

megállapodás ugyan valóban megigazolható, de ennek mély algebrai és számelméleti okai vannak. Ezekre nem emlékszem pontosan, szinte biztos, hogy kihagytam egy csomó fontos dolgot.

Ilyesmikre emlékszem halványan, hogy ,,a modulo prím p maradékosztályok a rájuk értelmszerűen átvitt szorzás és összeadás műveletekre nézve testek alkotnak''.

[link]

Ezt igazolni nem nehéz, de elég terjedelmes. Valószínűleg a legérdekesebb rész a nemnulla elemmel való szorzás invertálhatósága, ennél pedig szerintem lényegében éppen a p prímtulajdonságát használjuk ki, ahogy föntebb a 7-esre vonatkozóan tettem.