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
Mi a moduláris aritmetika?
Bevezetés a moduláris aritmetikába
Amikor két egész számot elosztunk, akkor valami ehhez hasonló egyenletet kapunk:
A a számláló
B a nevező
Q a hányados
R a maradék
B a nevező
Q a hányados
R a maradék
Van úgy, hogy csak az érdekel bennünket, mi lesz a maradék, amikor elosztjuk A-t B-vel.
Erre szolgál a modulo nevű művelet (rövidítése mod).
Erre szolgál a modulo nevű művelet (rövidítése mod).
A fenti A, B, Q és R jelölést alkalmazva: A, start text, space, m, o, d, space, end text, B, equals, R
A fenti kifejezést így olvassuk A modulo B egyenlő R, ahol a B-t modulusnak hívják.
Például:
Maradékos osztás bemutatása órával
Figyeld meg, mi történik, ha egy számot egyesével növelünk, majd elosztjuk 3-mal.
A maradék 0-val kezdődik, és minaddig 1-gyel nő, amig a nevezőnél eggyel kisebb számhoz nem érünk. Ezután megismétlődik a sorozat.
Ennek alapján a modulo műveletet körökkel illusztrálhatjuk.
A 0-t írjuk a kör tetejére, és az óramutató járásával megegyező irányban beírjuk az egész számokat, 1, 2, ... amíg el nem érjük a nevező (vagy modulus) mínusz 1-et.
Például vehetünk egy órát, ahol a 12-t 0-val helyettesítjük a modulo 12 ábrázolásához.
Az A, start text, space, m, o, d, space, end text, B kiszámításához az alábbi lépésekre van szükség:
- Készítsd el az órát a B méretéhez igazítva!
- Kezdd 0-val és haladj körbe az órán A lépést!
- Ahová megérkezünk, az adja meg a megoldást.
(Ha a szám pozitív, akkor az óramutató járásának irányában haladunk, ha negatív, akkor az óramutató járásával ellentétes irányba megyünk.)
Példák
8, start text, space, m, o, d, space, end text, 4, equals, question mark
Ha 4 a modulus, készítünk egy órát a 0, 1, 2, 3 számokkal.
0-nál indulunk, és az óramutató járásával megegyező irányba haladva sorban 8-at lépünk a számokon: 1, 2, 3, 0, 1, 2, 3, 0.
0-nál indulunk, és az óramutató járásával megegyező irányba haladva sorban 8-at lépünk a számokon: 1, 2, 3, 0, 1, 2, 3, 0.
0-hoz értünk, úgyhogy 8, start text, space, m, o, d, space, end text, 4, equals, 0.
7, start text, space, m, o, d, space, end text, 2, equals, question mark
Ha 2 a modulus, készítünk egy órát a 0, 1 számokkal.
0-nál indulunk, és az óramutató járásával megegyező irányba haladva sorban 7-et lépünk a számokon: 1, 0, 1, 0, 1, 0, 1.
0-nál indulunk, és az óramutató járásával megegyező irányba haladva sorban 7-et lépünk a számokon: 1, 0, 1, 0, 1, 0, 1.
1-hez értünk, úgyhogy 7, start text, space, m, o, d, space, end text, 2, equals, 1.
minus, 5, start text, space, m, o, d, space, end text, 3, equals, question mark
Ha 3 a modulus, készítünk egy órát a 0, 1, 2 számokkal.
0-nál indulunk, és az óramutató járásával ellenkező irányba haladva (mert az 5 negatív) sorban 5-öt lépünk a számokon: 2, 1, 0, 2, 1.
0-nál indulunk, és az óramutató járásával ellenkező irányba haladva (mert az 5 negatív) sorban 5-öt lépünk a számokon: 2, 1, 0, 2, 1.
1-hez értünk, úgyhogy minus, 5, start text, space, m, o, d, space, end text, 3, equals, 1.
Összefoglalás
A, start text, space, m, o, d, space, end text, B esetén ha A-t a B többszörösével megnöveljük, akkor ugyanoda jutunk, azaz:
A, start text, space, m, o, d, space, end text, B, equals, left parenthesis, A, plus, K, dot, B, right parenthesis, start text, space, m, o, d, space, end text, B tetszőleges K egész szám esetén.
Például:
Megjegyzés az olvasónak
mod a programozási nyelvekben és számológépeken
Sok programozási nyelvben és számológépen megtalálható a mod művelet. Ezt legtöbbször a % szimbólummal jelölik. Negatív szám esetén vannak olyan programozási nyelvek, ahol az eredményt negatív számmal adják meg.
Például:
Például:
-5 % 3 = -2.
Kongruencia a maradékos osztásnál
Ha ehhez hasonló kifejezést találsz:
A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Ez azt jelenti, hogy A kongruens B-vel modulo C. Ez hasonlít a mi általunk használt kifejezésekhez, de nem egészen ugyanazt jelenti.
A következő leckében elmagyarázzuk, ez mit jelent, és hogyan kapcsolódik a fenti kifejezésekhez.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.