If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

Moduláris inverz

Mit jelent egy művelet inverze?

Emlékszel? Ha egy számot megszorzol az inverzével, akkor 1-et kapsz eredményül. Az algebrából tudjuk, hogy:
  • Egy A szám inverze 1/A, mivel A · 1/A = 1 (például 5 inverze 1/5)
  • A 0-n kívül minden valós számnak van inverze
  • Ha egy számot megszorzunk A inverzével, az ugyanazt jelenti, mintha elosztanánk A-val (például 10/5 megegyezik 10 · 1/5-tel)

Mi a modulo művelet inverze?

A moduláris aritmetikában nem létezik az osztás művelete. De létezik a multiplikatív inverz modulo C (a továbbiakban moduláris inverz).
  • Az A (mod C) moduláris inverzét A^-1-el jelöljük.
  • (A · A^-1) ≡ 1 (mod C), ami egyenértékű ezzel: (A · A^-1) mod C = 1.
  • Csak a C-hez viszonyított relatív prímszámoknak (olyan számok, amelyeknek nincs C-vel közös prím osztója) van moduláris inverze (mod C).

Hogyan lehet megkeresni egy moduláris inverzet?

Az A (mod C) moduláris inverz megkeresésének egy egyszerű módja:
1. lépés: számold ki A · B mod C-t minden B értékre 0-tól C-1-ig.
2. lépés: A mod C moduláris inverze az a B érték lesz, ahol A · B mod C = 1.
Vedd figyelembe, hogy B mod C csak 0 és C-1 közötti egész értékeket vehet fel, úgyhogy nem érdemes nagyobb értékekkel próbálkozni, mert redundáns lenne a számítás.

Példa: A=3, C=7

1. lépés: számold ki A · B mod C-t minden B értékre 0-tól C-1-ig .

3 · 0 ≡ 0 (mod 7)
3 · 1 ≡ 3 (mod 7)
3 · 2 ≡ 6 (mod 7)
3 · 3 ≡ 9 ≡ 2 (mod 7)
3 · 4 ≡ 12 ≡ 5 (mod 7)
3 · 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <------ ​MEGVAN AZ INVERZ!
3 · 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

2. lépés: A mod C moduláris inverze az a B érték lesz, ahol A · B mod C = 1

A 3 mod 7-nek a moduláris inverze 5, mivel 5 · 3 mod 7 = 1
Egyszerű!
Nézzünk még egy példát, ahol nem találunk inverzet!

Példa: A=2 C=6

1. lépés: számold ki A · B mod C-t minden B értékre 0-tól C-1-ig.

2 · 0 ≡ 0 (mod 6)
2 · 1 ≡ 2 (mod 6)
2 · 2 ≡ 4 (mod 6)
2 · 3 ≡ 6 ≡ 0 (mod 6)
2 · 4 ≡ 8 ≡ 2 (mod 6)
2 · 5 ≡ 10 ≡ 4 (mod 6)

2. lépés: A mod C moduláris inverze az a B érték lesz, ahol A · B mod C = 1

Nincs olyan B érték, ahol A · B mod C = 1. Ezért A-nak nincs moduláris inverze (mod 6) esetén.
Ez azért van így, mert 2 és 6 nem relatív prímszámok (a 2 mindkettőnek osztója).

Ez a módszer lassúnak tűnik...

Ennél van egy sokkal gyorsabb módszer az A (mod C) megkeresésére, amit a következő, az euklideszi algoritmusról szóló fejezetben fogunk tárgyalni.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.