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
Maradékosztály
Maradékosztály
Ha ehhez hasonló kifejezést találsz:
ez azt jelenti, hogy A kongruens B-vel modulo C.
A maradékosztály jelentését egy gondolatkísérleten keresztül a szokásos modulo művelet segítségével fogjuk bemutatni.
Tegyük fel, hogy ki akarjuk számolni az összes egész szám mod 5 értékét:
Tegyük fel, hogy felcímkéztünk 5 szeletet: 0, 1, 2, 3, 4. Minden egész számot berakunk abba a szeletbe, aminek a címkéje megegyezik a szám mod 5 értékével.
Gondolhatsz úgy is a szeletekre, mint számokat tartalmazó csoportokra. Például a 26 az 1 címkéjű szeletbe fog kerülni, mert 26, start text, space, m, o, d, space, end text, 5, equals, 1.
A fenti ábrán olyan egész számokat tüntettünk fel, melyek az egyes szeletekbe tartoznak.
Gondolhatsz úgy is a szeletekre, mint számokat tartalmazó csoportokra. Például a 26 az 1 címkéjű szeletbe fog kerülni, mert 26, start text, space, m, o, d, space, end text, 5, equals, 1.
A fenti ábrán olyan egész számokat tüntettünk fel, melyek az egyes szeletekbe tartoznak.
Hasznos lenne egy olyan jelölés, amivel kifejezhetjük, hogy adott számok ugyanahhoz a szelethez tartoznak. (Megfigyelheted, hogy a fenti példában a 26 ugyanabban a szeletben van, mint az 1, 6, 11, 16, 21).
Úgy is szokták mondani, hogy ha két érték azonos szelethez tartozik, akkor azok ugyanabba az ekvivalenciaosztályba (maradékosztályba) tartoznak.
Ez matematikai jelöléssel így néz ki mod C esetére: A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Ez matematikai jelöléssel így néz ki mod C esetére: A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
A fenti kifejezés olvasata: A kongruens B-vel modulo C.
Vizsgáljuk meg részletesen az alábbi kifejezést!
- \equiv a kongruencia jele, ami azt jelenti, hogy A és B ugyanahoz az maradékosztályhoz tartozik.
- left parenthesis, start text, m, o, d, space, end text, C, right parenthesis mutatja meg az A-val és B-vel elvégzett műveletet.
- Ha fenti kettő szerepel, akkor ezt „\equiv”: kongruens modulo C-nek mondjuk.
Például 26, \equiv, 11, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis
26, start text, space, m, o, d, space, end text, 5, equals, 1, ezért a 26 az 1 maradékosztályban van,
11, start text, space, m, o, d, space, end text, 5, equals, 1, ezért a 11 is az 1 maradékosztályban van.
11, start text, space, m, o, d, space, end text, 5, equals, 1, ezért a 11 is az 1 maradékosztályban van.
Figyeld meg, hogy ez más, mint A, start text, space, m, o, d, space, end text, C: 26, does not equal, 11, start text, space, m, o, d, space, end text, 5.
Maradékosztályok közelebbről
További részleteket fedezhetünk fel a maradékosztályokkal kapcsolatban, ha követjük ugyanezt a gondolatmenetet egy C pozitív egész számmal.
Először megjelölünk C szeletet: 0, comma, 1, comma, 2, comma, dots, comma, C, minus, 2, comma, C, minus, 1.
Ezután minden egész számot beteszünk abba a szeletbe, amelyik megfelel a start text, m, o, d, space, end text, C értékének.
Az alábbi ábrán az egyes szeletekre jellemző értékek közül látható néhány.
Először megjelölünk C szeletet: 0, comma, 1, comma, 2, comma, dots, comma, C, minus, 2, comma, C, minus, 1.
Ezután minden egész számot beteszünk abba a szeletbe, amelyik megfelel a start text, m, o, d, space, end text, C értékének.
Az alábbi ábrán az egyes szeletekre jellemző értékek közül látható néhány.
Ha megnézzük a 0-val jelölt szeletet, ezt látjuk:
Ha megnézzük az 1-gyel jelölt szeletet, ezt látjuk:
Ha megnézzük a 2-vel jelölt szeletet, ezt látjuk:
Ha megnézzük a C, minus, 1-el jelölt szeletet, ezt látjuk:
Ebből a kísérletből az alábbi fő következtetést vonhatjuk le:
Az egyes szeletekhez tartozó értékek megegyeznek a szelet címkéje plusz-mínusz C valamilyen többszörösével.
Ez azt jelenti, hogy az egy szelethez tartozó tetszőleges két érték közötti különbség C valamilyen többszöröse.
Ez a megfigyelés segíteni fog abban, hogy megértsük az ekvivalencia kifejezéseket és a maradékosztályokat a későbbi fejezetekben.
Az egyes szeletekhez tartozó értékek megegyeznek a szelet címkéje plusz-mínusz C valamilyen többszörösével.
Ez azt jelenti, hogy az egy szelethez tartozó tetszőleges két érték közötti különbség C valamilyen többszöröse.
Ez a megfigyelés segíteni fog abban, hogy megértsük az ekvivalencia kifejezéseket és a maradékosztályokat a későbbi fejezetekben.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.