Fő tartalom

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:

$\frac{A}{B} = Q marad R$ ‍

A

a számláló

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).

A fenti

A

B

Q

és

R

jelölést alkalmazva:

A mod B = R

A fenti kifejezést így olvassuk

A

modulo

B

egyenlő

R

, ahol a

B

-t modulusnak hívják.

Például:

$\begin{array}{rcl} \frac{13}{5} & = & 2 marad 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

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.

$\begin{array}{rcl} \frac{0}{3} & = & 0 marad 0 \\ \frac{1}{3} & = & 0 marad 1 \\ \frac{2}{3} & = & 0 marad 2 \\ \frac{3}{3} & = & 1 marad 0 \\ \frac{4}{3} & = & 1 marad 1 \\ \frac{5}{3} & = & 1 marad 2 \\ \frac{6}{3} & = & 2 marad 0 \end{array}$ ‍

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.

A mod 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 mod 4 = ?$ ‍

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-hoz értünk, úgyhogy

8 mod 4 = 0

$7 mod 2 = ?$ ‍

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.

1-hez értünk, úgyhogy

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

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.

1-hez értünk, úgyhogy

- 5 mod 3 = 1

Összefoglalás

A mod B

esetén ha

A

-t a $B$ ‍ többszörösével megnöveljük, akkor ugyanoda jutunk, azaz:

$A mod B = (A + K \cdot B) mod B$ ‍ tetszőleges $K$ ‍ egész szám esetén.

Például:

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

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:

-5 % 3 = -2.

Kongruencia a maradékos osztásnál

Ha ehhez hasonló kifejezést találsz:

$A \equiv B (mod C)$ ‍

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?

Jelentkezz be

Rendezés:

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.

Számítástudomány

Tantárgy/kurzus: Számítástudomány > 2. témakör