Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
5. lecke: Moduláris aritmetika- Mi a moduláris aritmetika?
- Modulo művelet
- Játék a modulóval
- Maradékosztály
- Kongruencia reláció
- Ekvivalence reláció
- Maradékos osztásra vonatkozó tétel
- Moduláris összeadás és kivonás
- Moduláris összeadás
- Moduláris kihívás (összeadás és kivonás)
- Moduláris szorzás
- Moduláris szorzás
- Moduláris hatványozás
- Gyors moduláris hatványozás
- Gyors moduláris hatványozás
- Moduláris inverz
- Az euklideszi algoritmus
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Moduláris összeadás és kivonás
Vizsgáljuk meg közelebbről a moduláris aritmetikában az additivitási (összeadásra vonatkozó) szabályt:
(A + B) mod C = (A mod C + B mod C) mod C
Példa:
Legyen A=14, B=17, C=5!
Bizonyítsuk be: (A + B) mod C = (A mod C + B mod C) mod C!
Jelölje BO az egyenlet bal oldalát,
JO az egyenlet jobb oldalát!
Jelölje BO az egyenlet bal oldalát,
JO az egyenlet jobb oldalát!
BO = (A + B) mod C
BO = (14 + 17) mod 5
BO = 31 mod 5
BO = 1
BO = (14 + 17) mod 5
BO = 31 mod 5
BO = 1
JO = (A mod C + B mod C) mod C
JO = (14 mod 5 + 17 mod 5) mod 5
JO = (4 + 2) mod 5
JO = 1
JO = (14 mod 5 + 17 mod 5) mod 5
JO = (4 + 2) mod 5
JO = 1
BO = JO = 1
A moduláris összeadás szemléltetése
Nézd meg a lenti képet! Ha ki akarjuk számolni 12+9 mod 7 értékét, akkor egyszerűen körbejárhatjuk a moduláris kört 12+9 lépésben az óramutató járásának irányában (ezt rajzoltuk fel a bal alsó ábrán).
Lerövidíthetjük az eljárást, mivel tudjuk, hogy minden 7. lépés ugyanarra a helyre visz vissza a moduláris körön. Ezek a teljes körök nem befolyásolják a végső helyzetünket. Ezeket a teljes köröket figyelmen kívül hagyhatjuk úgy, hogy kiszámoljuk mindkét szám mod 7 értékét (ami a felső két ábrán látható). Ez megadja mindkét szám esetén, hány lépést kellett megtenni a 0-tól a moduláris körön az óramutató járásával megegyező irányban, hogy eljussunk a végső pozícióba.
Ezután már csak annyi lépést kell megtenni az óramutató járásával megegyező irányban, ami a két szám végső pozíciójának meghatározásában szerepet játszott (ami a jobb alsó moduláris körön látszik). Ez a módszer általánosan érvényes bármely két egész számra, tetszőleges moduláris kör esetén.
A moduláris összeadás bizonyítása
Be fogjuk bizonyítani, hogy (A + B) mod C = (A mod C + B mod C) mod C.
Meg kell mutatnunk, hogy BO=JO.
Meg kell mutatnunk, hogy BO=JO.
A maradékos osztásra vonatkozó tétel alapján A-t és B-t felírhatjuk ilyen alakban:
A = C · Q1 + R1, ahol 0 ≤ R1 < C és Q1 egész. A mod C = R1
B = C · Q2 + R2, ahol 0 ≤ R2 < C és Q2 egész. B mod C = R2
(A + B) = C · (Q1 + Q2) + R1+R2
B = C · Q2 + R2, ahol 0 ≤ R2 < C és Q2 egész. B mod C = R2
(A + B) = C · (Q1 + Q2) + R1+R2
BO = (A + B) mod C
BO = (C · (Q1 + Q2) + R1+ R2) mod C
C többszöröse elhagyható a mod C művelet alkalmazásakor.
BO = (R1 + R2) mod C
BO = (C · (Q1 + Q2) + R1+ R2) mod C
C többszöröse elhagyható a mod C művelet alkalmazásakor.
BO = (R1 + R2) mod C
JO = (A mod C + B mod C) mod C
JO = (R1 + R2) mod C
JO = (R1 + R2) mod C
BO=JO= (R1 + R2) mod C
Moduláris kivonás
Hasonló módon bizonyítható a moduláris kivonás.
(A - B) mod C = (A mod C - B mod C) mod C
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.