A számrendszerek világa izgalmas és sokszínű, tele logikával és eleganciával. Gyakran a tízes számrendszer rabjai vagyunk, hiszen ez a mindennapjainkban legelterjedtebb. Azonban érdemes kilépni ebből a megszokásból, és felfedezni más rendszereket is. Gondoljunk csak bele, hogy a számítógépek világa a kettes számrendszerre épül, de más területeken is találkozunk például a tizenkettes vagy a tizenhatos számrendszerrel. Ezek a rendszerek nem csupán elméleti érdekességek; megértésük segíthet mélyebben átlátni a számok közötti összefüggéseket és fejlesztheti logikai készségeinket.
Egy ilyen felfedezőút során találkozunk a négyes számrendszerrel. Ez a rendszer, bár kevésbé ismert, mint a tízes vagy a kettes, számos tanulságot tartogat a számok oszthatóságával kapcsolatban. Megvizsgálva, hogyan működik a négyes számrendszerben az oszthatóság, új perspektívákat nyithatunk meg a számelméletben, és láthatjuk, hogy bizonyos elvek hogyan általánosíthatók különböző számrendszerekben. Különböző nézőpontokból közelítjük meg a témát, hogy teljes képet kapjunk.
Ez a most következő írás egy utazás lesz a négyes számrendszer oszthatósági szabályai felé. Megismerjük az alapokat, felfedezzük a lényeges összefüggéseket, és praktikus példákon keresztül szemléltetjük, hogyan alkalmazhatjuk ezeket az ismereteket. Célunk, hogy a lehető legérthetőbben, legáttekinthetőbben mutassuk be ezt a különleges témát, hogy Ön is kedvet kapjon a számrendszerek rejtelmeinek további felfedezéséhez.
A négyes számrendszer alapjai
Mielőtt belemerülnénk az oszthatósági szabályokba, fontos, hogy tisztában legyünk a négyes számrendszer működésével. Ez egy helyiértékes számrendszer, akárcsak a tízes, de ebben az esetben a számokat csak a $0, 1, 2, 3$ számjegyekkel tudjuk felírni. A számok értékét a számjegyek helyiértéke határozza meg, ahol a helyiértékek a $4$ hatványai.
Egy $N$ számot a négyes számrendszerben így írhatunk fel:
$$ N = d_k \cdot 4^k + d_{k-1} \cdot 4^{k-1} + \dots + d_1 \cdot 4^1 + d_0 \cdot 4^0 $$
ahol $d_i$ a számjegyek egyike ($0, 1, 2, 3$), és $k$ a legnagyobb kitevő.
Például, vegyünk egy számot: $(1230)_4$. Ennek a tízes számrendszerben vett értéke:
$$ 1 \cdot 4^3 + 2 \cdot 4^2 + 3 \cdot 4^1 + 0 \cdot 4^0 = 1 \cdot 64 + 2 \cdot 16 + 3 \cdot 4 + 0 \cdot 1 = 64 + 32 + 12 + 0 = 108 $$
Tehát a $(1230)_4$ szám egyenlő a $108$-cal a tízes számrendszerben.
Miért pont a négyes?
Az, hogy egy adott számrendszer oszthatósági szabályait vizsgáljuk, sokszor kapcsolódik magának a számrendszer alapjának tulajdonságaihoz. A négyes számrendszer esetében különösen érdekes lehet, hogy az alapja ($4$) maga is egy négyzetszám ($2^2$). Ez a tulajdonság fogja majd befolyásolni az oszthatósági szabályokat, különösen a $4$-gyel való oszthatóság esetében. Más számrendszerekben is megfigyelhető, hogy az alap vagy annak tényezői jelentős szerepet játszanak az oszthatósági szabályok megalkotásában.
"A számrendszerek titka abban rejlik, hogy megmutatják, miként rendezhetjük el ugyanazokat a mennyiségeket különböző logikai struktúrák mentén."
Oszthatóság négyes számrendszerben
Most, hogy már ismerjük a négyes számrendszer alapjait, nézzük meg, hogyan működik az oszthatóság ebben a rendszerben. Vizsgáljuk meg az oszthatóságot a számrendszer alapjával, a $4$-gyel, illetve annak tényezőivel és hatványaival.
Oszthatóság 4-gyel
A tízes számrendszerben az oszthatóság 10-zel, 100-zal, stb. rendkívül egyszerű: a szám végén lévő nullák számától függ. A négyes számrendszerben hasonló logikával működik az oszthatóság $4$-gyel.
Egy szám akkor osztható $4$-gyel a négyes számrendszerben, ha a legkisebb helyiértékű számjegye $0$. Ez azért van, mert a legkisebb helyiérték a $4^0 = 1$, a következő helyiérték pedig a $4^1 = 4$.
Ha egy számot $N = d_k \cdot 4^k + \dots + d_1 \cdot 4^1 + d_0 \cdot 4^0$ alakban írunk fel, akkor azt láthatjuk, hogy minden tag, amelyik $4^1$ vagy annál magasabb hatványt tartalmaz, osztható $4$-gyel. Tehát a szám oszthatósága $4$-gyel csak a legkisebb helyiértékű számjegytől, $d_0$-tól függ. Ha $d_0 = 0$, akkor a teljes szám osztható $4$-gyel.
Példa:
Tekintsük a $(1230)_4$ számot. A legkisebb helyiértékű számjegye $0$. Ahogy fent kiszámoltuk, ez a szám $108$ a tízes számrendszerben. $108$ osztható $4$-gyel ($108 / 4 = 27$), ami megerősíti a szabályt.
Tekintsük a $(2313)_4$ számot. A legkisebb helyiértékű számjegye $3$, ami nem $0$. Ez a szám nem osztható $4$-gyel. A tízes számrendszerben ez $2 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 3 \cdot 1 = 128 + 48 + 4 + 3 = 183$. $183$ nem osztható $4$-gyel.
"A legegyszerűbb oszthatósági szabályok gyakran közvetlenül magából a számrendszer alapjából fakadnak, mint egy logikai következmény."
Oszthatóság 16-tal (és általában $4^n$-nel)
Mivel $16 = 4^2$, az oszthatóság $16$-tal hasonló elven működik, mint az oszthatóság $4$-gyel, csak most a két legkisebb helyiértéket kell figyelembe vennünk.
Egy szám akkor osztható $16$-tal a négyes számrendszerben, ha az utolsó két számjegye által alkotott szám osztható $16$-tal. A négyes számrendszerben ez azt jelenti, hogy az utolsó két számjegy $d_1 d_0$ által alkotott szám ($d_1 \cdot 4^1 + d_0 \cdot 4^0$) osztható $16$-tal.
Nézzük meg ezt részletesebben. Ha $N = d_k \cdot 4^k + \dots + d_2 \cdot 4^2 + d_1 \cdot 4^1 + d_0 \cdot 4^0$, akkor minden tag, amelyik $4^2=16$ vagy annál magasabb hatványt tartalmaz, osztható $16$-tal. Tehát a szám oszthatósága $16$-tal csak az utolsó két számjegytől, $d_1 d_0$-tól függ.
Példa:
Tekintsük a $(1312)_4$ számot. Az utolsó két számjegye $12_4$. Ennek értéke tízes számrendszerben $1 \cdot 4^1 + 2 \cdot 4^0 = 4 + 2 = 6$. Mivel $6$ nem osztható $16$-tal, az egész szám sem osztható $16$-tal.
A szám értéke tízes számrendszerben: $1 \cdot 4^3 + 3 \cdot 4^2 + 1 \cdot 4^1 + 2 \cdot 4^0 = 64 + 3 \cdot 16 + 4 + 2 = 64 + 48 + 4 + 2 = 118$. $118$ nem osztható $16$-tal.
Tekintsük a $(2300)_4$ számot. Az utolsó két számjegye $00_4$. Ez egyenlő $0$-val, ami osztható $16$-tal. Tehát a $(2300)_4$ osztható $16$-tal.
A szám értéke tízes számrendszerben: $2 \cdot 4^3 + 3 \cdot 4^2 + 0 \cdot 4^1 + 0 \cdot 4^0 = 2 \cdot 64 + 3 \cdot 16 = 128 + 48 = 176$. $176 / 16 = 11$. Valóban osztható.
Általánosan, egy szám osztható $4^n$-nel a négyes számrendszerben, ha az utolsó $n$ számjegye $0$.
Oszthatóság 2-vel
Mivel $2$ a $4$ egyik tényezője ($4 = 2 \cdot 2$), az oszthatóság $2$-vel is megvizsgálható.
Egy szám akkor osztható $2$-vel a négyes számrendszerben, ha az utolsó számjegye páros. Mivel a megengedett számjegyek $0, 1, 2, 3$, a páros számjegyek a $0$ és a $2$.
Ha $N = d_k \cdot 4^k + \dots + d_1 \cdot 4^1 + d_0 \cdot 4^0$, akkor minden tag, amelyik $4^1=4$ vagy annál magasabb hatványt tartalmaz, osztható $2$-vel (mivel $4$ osztható $2$-vel). Tehát a szám oszthatósága $2$-vel csak az utolsó számjegytől, $d_0$-tól függ. Ha $d_0$ páros ($0$ vagy $2$), akkor a szám osztható $2$-vel.
Példa:
Tekintsük a $(1230)_4$ számot. Az utolsó számjegye $0$, ami páros. Tehát a szám osztható $2$-vel. Tízes számrendszerben $108$, ami osztható $2$-vel.
Tekintsük a $(2313)_4$ számot. Az utolsó számjegye $3$, ami páratlan. Tehát a szám nem osztható $2$-vel. Tízes számrendszerben $183$, ami nem osztható $2$-vel.
Oszthatósági szabályok más számokkal
A négyes számrendszerben nem csak az alap tényezői vagy hatványai alapján vizsgálhatunk oszthatóságot. Általánosabb szabályokat is megfogalmazhatunk, amelyek hasonlítanak a tízes számrendszerben megismert elvekhez, csak éppen a $4$ hatványait használjuk.
Oszthatóság $3$-mal
Az oszthatóság $3$-mal a négyes számrendszerben hasonlóan működik, mint a tízes számrendszerben az oszthatóság $3$-mal vagy $9$-cel. A kulcs itt az, hogy $4 \equiv 1 \pmod 3$.
Vizsgáljuk meg újra az általános alakot: $N = d_k \cdot 4^k + d_{k-1} \cdot 4^{k-1} + \dots + d_1 \cdot 4^1 + d_0 \cdot 4^0$.
Mivel $4 \equiv 1 \pmod 3$, következik, hogy $4^m \equiv 1^m \equiv 1 \pmod 3$ minden $m \ge 0$ egész számra.
Tehát:
$N \equiv d_k \cdot 1 + d_{k-1} \cdot 1 + \dots + d_1 \cdot 1 + d_0 \cdot 1 \pmod 3$
$N \equiv d_k + d_{k-1} + \dots + d_1 + d_0 \pmod 3$
Ez azt jelenti, hogy egy szám osztható $3$-mal a négyes számrendszerben, ha számjegyeinek összege osztható $3$-mal.
Példa:
Tekintsük a $(1230)_4$ számot. Számjegyeinek összege: $1 + 2 + 3 + 0 = 6$. Mivel $6$ osztható $3$-mal, az egész szám osztható $3$-mal.
A szám értéke tízes számrendszerben $108$. $108 / 3 = 36$. Valóban osztható.
Tekintsük a $(2311)_4$ számot. Számjegyeinek összege: $2 + 3 + 1 + 1 = 7$. Mivel $7$ nem osztható $3$-mal, az egész szám nem osztható $3$-mal.
A szám értéke tízes számrendszerben: $2 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 1 \cdot 1 = 128 + 48 + 4 + 1 = 181$. $181$ nem osztható $3$-mal.
"Az oszthatósági szabályok nem specifikusak egyetlen számrendszerre; sokkal inkább a számok közötti alapvető aritmetikai kapcsolatok tükröződnek bennük, csupán más 'nyelven'."
Oszthatóság 5-tel
Az oszthatóság $5$-tel már egy kicsit bonyolultabb a négyes számrendszerben, mivel $5$ és $4$ nem állnak olyan egyszerű kapcsolatban, mint például $3$ és $4$. A $4 \equiv -1 \pmod 5$ kapcsolat hasznos lehet.
Írjuk fel újra az általános alakot: $N = d_k \cdot 4^k + d_{k-1} \cdot 4^{k-1} + \dots + d_1 \cdot 4^1 + d_0 \cdot 4^0$.
Használjuk a $4 \equiv -1 \pmod 5$ kongruenciát:
$N \equiv d_k \cdot (-1)^k + d_{k-1} \cdot (-1)^{k-1} + \dots + d_1 \cdot (-1)^1 + d_0 \cdot (-1)^0 \pmod 5$
Ez egy alternáló összeghez vezet a számjegyeiből és a helyiértékeik paritásából.
Példa:
Tekintsük a $(1230)_4$ számot.
$N \equiv 1 \cdot (-1)^3 + 2 \cdot (-1)^2 + 3 \cdot (-1)^1 + 0 \cdot (-1)^0 \pmod 5$
$N \equiv 1 \cdot (-1) + 2 \cdot 1 + 3 \cdot (-1) + 0 \cdot 1 \pmod 5$
$N \equiv -1 + 2 – 3 + 0 \pmod 5$
$N \equiv -2 \pmod 5$
$N \equiv 3 \pmod 5$
Tehát a $(1230)_4$ szám (ami $108$ tízes számrendszerben) nem osztható $5$-tel, és $108 \div 5$ maradéka $3$.
Tekintsük a $(3121)_4$ számot.
$N \equiv 3 \cdot (-1)^3 + 1 \cdot (-1)^2 + 2 \cdot (-1)^1 + 1 \cdot (-1)^0 \pmod 5$
$N \equiv 3 \cdot (-1) + 1 \cdot 1 + 2 \cdot (-1) + 1 \cdot 1 \pmod 5$
$N \equiv -3 + 1 – 2 + 1 \pmod 5$
$N \equiv -3 \pmod 5$
$N \equiv 2 \pmod 5$
A szám értéke tízes számrendszerben: $3 \cdot 64 + 1 \cdot 16 + 2 \cdot 4 + 1 \cdot 1 = 192 + 16 + 8 + 1 = 217$. $217 / 5 = 43$ maradék $2$.
Oszthatóság $13$-mal
A $13$ szám oszthatósága a négyes számrendszerben is megvizsgálható. Itt is keresünk egy olyan tulajdonságot, ami megkönnyíti a számítást. Mivel $4^3 = 64$, és $64 = 5 \cdot 13 – 1$, így $64 \equiv -1 \pmod{13}$. Ez ad egy lehetőséget az oszthatóság vizsgálatára.
Egy számot csoportosíthatunk a legkisebből kezdve 3-3 számjegyre, ha nem lenne a $4^3$ hatvány. Mivel $4^3 \equiv -1 \pmod{13}$, ez nem lesz olyan egyszerű, mint a tízes számrendszerben a 13-mal való oszthatóság (ahol $1000 = 77 \cdot 13 – 1$, azaz $1000 \equiv -1 \pmod{13}$).
A négyes számrendszerben $4^1=4$, $4^2=16$, $4^3=64$.
Vizsgáljuk meg a maradékokat $13$-mal osztva:
$4^0 \equiv 1 \pmod{13}$
$4^1 \equiv 4 \pmod{13}$
$4^2 \equiv 16 \equiv 3 \pmod{13}$
$4^3 \equiv 4 \cdot 3 = 12 \equiv -1 \pmod{13}$
$4^4 \equiv 4 \cdot (-1) = -4 \equiv 9 \pmod{13}$
$4^5 \equiv 4 \cdot 9 = 36 \equiv 10 \pmod{13}$
$4^6 \equiv 4 \cdot 10 = 40 \equiv 1 \pmod{13}$
A maradékok $1, 4, 3, 12, 9, 10$ ciklikusan ismétlődnek $6$ hosszúságú ciklusokban.
Ezt felhasználva, egy $N$ számot felírhatunk a következő alakban, ha hatos csoportokba rendezzük a számjegyeket (vagyis $4^6$ hatványaival):
$N = (d_5 d_4 d_3 d_2 d_1 d_0)4 + (d{11} d_{10} d_9 d_8 d_7 d_6)_4 \cdot 4^6 + \dots$
Mivel $4^6 \equiv 1 \pmod{13}$, az oszthatóság $13$-mal ugyanazt jelenti, mint a tízes számrendszerben: a számot 6-os csoportokra bontjuk balról, és az alternáló összeget vesszük.
Példa:
Tekintsük a $(12345671)_4$ számot. Írjuk fel $6$-os csoportokra bontva:
$(12345671)_4 = (12)(345671)_4$
Ez nem teljesen triviális, mivel a számjegyek nem $0, 1, 2, 3$.
Nézzük meg az utolsó 6 számjegyet: $(345671)_4$.
Most nézzük meg a számot, mint $(a_m \dots a_1 a_0)_4$ ahol $a_i$ most már egy-egy számjegy.
Az oszthatóság $13$-mal a $4^6 \equiv 1 \pmod{13}$ tulajdonság miatt a tízes számrendszerben látotthoz hasonlóan, 6-os számjegyes blokkok alternáló összegével vizsgálható.
$(12345671)_4 = (12)(345671)_4$.
A $345671_4$ értéke tízes számrendszerben:
$3 \cdot 4^5 + 4 \cdot 4^4 + 5 \cdot 4^3 + 6 \cdot 4^2 + 7 \cdot 4^1 + 1 \cdot 4^0$
Itt meg kell jegyeznünk, hogy a $4, 5, 6, 7$ nem számjegyek a négyes számrendszerben. Tehát az eredeti számot írjuk fel újra: $(12303231)_4$ (ez egy kitalált szám, hogy a számjegyek helyesek legyenek).
$(12303231)_4 = (12)(303231)_4$.
Vizsgáljuk a $303231_4$ számot:
$3 \cdot 4^5 + 0 \cdot 4^4 + 3 \cdot 4^3 + 2 \cdot 4^2 + 3 \cdot 4^1 + 1 \cdot 4^0$
Használjuk a kongruenciákat:
$3 \cdot 4^5 \equiv 3 \cdot 10 \equiv 30 \equiv 4 \pmod{13}$
$0 \cdot 4^4 \equiv 0 \pmod{13}$
$3 \cdot 4^3 \equiv 3 \cdot (-1) = -3 \equiv 10 \pmod{13}$
$2 \cdot 4^2 \equiv 2 \cdot 3 = 6 \pmod{13}$
$3 \cdot 4^1 \equiv 3 \cdot 4 = 12 \pmod{13}$
$1 \cdot 4^0 \equiv 1 \pmod{13}$
Összeg: $4 + 0 + 10 + 6 + 12 + 1 = 33$.
$33 \equiv 7 \pmod{13}$.
Tehát a $(303231)_4$ szám nem osztható $13$-mal, és $7$ a maradéka.
A $(12)_4$ szám értéke $1 \cdot 4 + 2 = 6$.
A teljes szám $N = (12)_4 \cdot 4^6 + (303231)_4$.
$N \equiv (6) \cdot 1 + 7 \pmod{13}$
$N \equiv 13 \equiv 0 \pmod{13}$.
Tehát a $(12303231)_4$ szám osztható $13$-mal.
Táblázatok a négyes számrendszerben
Hogy jobban átláthassuk a különbségeket és hasonlóságokat, készítsünk néhány táblázatot.
Táblázat: Számok átváltása és oszthatósági szabályok (négyes vs. tízes)
| Tízes Számrendszer | Négyes Számrendszer | Osztható 4-gyel (négyes) | Osztható 2-vel (négyes) | Osztható 3-mal (négyes) |
|---|---|---|---|---|
| 0 | $(0)_4$ | Igen | Igen | Igen |
| 1 | $(1)_4$ | Nem | Nem | Nem |
| 2 | $(2)_4$ | Nem | Igen | Nem |
| 3 | $(3)_4$ | Nem | Nem | Igen |
| 4 | $(10)_4$ | Igen | Igen | Nem |
| 5 | $(11)_4$ | Nem | Nem | Igen |
| 6 | $(12)_4$ | Nem | Igen | Igen |
| 7 | $(13)_4$ | Nem | Nem | Nem |
| 8 | $(20)_4$ | Igen | Igen | Nem |
| 9 | $(21)_4$ | Nem | Nem | Igen |
| 10 | $(22)_4$ | Nem | Igen | Nem |
| 11 | $(23)_4$ | Nem | Nem | Igen |
| 12 | $(30)_4$ | Igen | Igen | Igen |
| 13 | $(31)_4$ | Nem | Nem | Nem |
| 14 | $(32)_4$ | Nem | Igen | Nem |
| 15 | $(33)_4$ | Nem | Nem | Igen |
| 16 | $(100)_4$ | Igen | Igen | Nem |
A táblázatból jól látszik, hogy az oszthatóság $4$-gyel a négyes számrendszerben az utolsó számjegy $0$-ra végződésen alapul. Az oszthatóság $2$-vel az utolsó számjegy párosságán. Az oszthatóság $3$-mal pedig a számjegyek összegén.
Táblázat: A négyes számrendszer helyiértékei és oszthatósági képességei
| Helyiérték (négyes számrendszerben) | Értéke (tízes számrendszerben) | Osztható vele (tízes számrendszerben) | Megjegyzés a négyes számrendszerben |
|---|---|---|---|
| $4^0$ | $1$ | Minden szám | Ez a legkisebb helyiérték. |
| $4^1$ | $4$ | $4, 8, 12, 16, \dots$ | Az oszthatóság $4$-gyel az utolsó számjegyen múlik. |
| $4^2$ | $16$ | $16, 32, 48, 64, \dots$ | Az oszthatóság $16$-tal az utolsó két számjegyen múlik. |
| $4^3$ | $64$ | $64, 128, 192, \dots$ | Az oszthatóság $64$-gyel az utolsó három számjegyen múlik. |
| $4^n$ | $4^n$ | $4^n, 2 \cdot 4^n, \dots$ | Egy szám osztható $4^n$-nel, ha az utolsó $n$ számjegye $0$. |
Ez a táblázat jól szemlélteti, hogy miért olyan egyszerű az oszthatóság $4$ hatványaival a négyes számrendszerben.
"A rendszerek megértése nem csak a 'hogyan'-ra, hanem a 'miért'-re is választ ad, feltárva az alapul szolgáló logikát."
Algoritmusok és módszerek
A fent említett szabályok alapján konkrét algoritmusokat dolgozhatunk ki annak eldöntésére, hogy egy, a négyes számrendszerben felírt szám osztható-e egy adott számmal.
Algoritmus az oszthatóság ellenőrzésére $4^n$-nel
- Bemenet: Egy $N$ szám a négyes számrendszerben (pl. $(d_k d_{k-1} \dots d_1 d_0)_4$) és egy $n$ pozitív egész szám.
- Ellenőrzés: Nézd meg az $N$ szám utolsó $n$ számjegyét ($d_{n-1} \dots d_1 d_0$).
- Feltétel: Ha az utolsó $n$ számjegy mind $0$, akkor az $N$ szám osztható $4^n$-nel.
- Kimenet: Igen vagy Nem.
Ez az algoritmus rendkívül hatékony, mivel csak a szám végén lévő számjegyek számát kell ellenőrizni, ami független a szám hosszától (csak az $n$ értékétől függ).
Algoritmus az oszthatóság ellenőrzésére $3$-mal
- Bemenet: Egy $N$ szám a négyes számrendszerben (pl. $(d_k d_{k-1} \dots d_1 d_0)_4$).
- Számítás: Számítsd ki a számjegyeinek összegét: $S = d_k + d_{k-1} + \dots + d_1 + d_0$.
- Rekurzív (vagy iteratív) ellenőrzés: Ha az $S$ összeg nagyobb, mint $3$, alkalmazd újra az algoritmust az $S$ összegre (négyes számrendszerben írva, ha szükséges, vagy egyszerűen csak a számjegyek összegét számolva tízes számrendszerben). Ha $S$ kisebb vagy egyenlő $3$-mal, akkor nézd meg, hogy $S=0$ vagy $S=3$.
- Feltétel: Ha az összeg végső értéke $0$ vagy $3$, akkor az $N$ szám osztható $3$-mal.
- Kimenet: Igen vagy Nem.
A gyakorlatban az $S$ összeget elég csak tízes számrendszerben kiszámolni, és azt ellenőrizni $3$-mal.
Algoritmus az oszthatóság ellenőrzésére $5$-tel
- Bemenet: Egy $N$ szám a négyes számrendszerben (pl. $(d_k d_{k-1} \dots d_1 d_0)_4$).
- Számítás: Számítsd ki az alternáló összeget a kongruencia alapján: $R = d_0 – d_1 + d_2 – d_3 + \dots + (-1)^k d_k$.
- Moduló 5: Számítsd ki $R \pmod 5$.
- Feltétel: Ha $R \pmod 5 = 0$, akkor az $N$ szám osztható $5$-tel.
- Kimenet: Igen vagy Nem.
Ez az algoritmus is hatékony, mivel csak a számjegyeinek egy lineáris kombinációját kell kiszámolni.
"Az algoritmusok nyelvére lefordított matematikai szabályok teszik lehetővé a gépek számára is az elmélkedést és a döntéshozatalt."
Példák és gyakorlati alkalmazások
Bár a négyes számrendszer nem elterjedt a mindennapi életben, az általa bemutatott elvek sok más területen is hasznosíthatók. A gondolatmenet, ami az oszthatósági szabályokat megalkotja, univerzális.
Feladat: Ellenőrizzük, hogy a $(21303)_4$ szám osztható-e 12-vel.
-
Lebontás tényezőkre: $12 = 4 \cdot 3$. Mivel $4$ és $3$ relatív prímek, a szám akkor osztható $12$-vel, ha külön-külön osztható $4$-gyel és $3$-mal.
-
Oszthatóság 4-gyel: A $(21303)_4$ szám utolsó számjegye $3$, ami nem $0$. Tehát a szám nem osztható $4$-gyel.
-
Következtetés: Mivel a szám nem osztható $4$-gyel, így nem lehet osztható $12$-vel sem. Nem szükséges tovább vizsgálni a $3$-mal való oszthatóságot.
Ha mégis megvizsgálnánk a $3$-mal való oszthatóságot:
Számjegyek összege: $2 + 1 + 3 + 0 + 3 = 9$.
Mivel $9$ osztható $3$-mal, a $(21303)_4$ szám osztható $3$-mal.
Tízes számrendszerben: $2 \cdot 4^4 + 1 \cdot 4^3 + 3 \cdot 4^2 + 0 \cdot 4^1 + 3 \cdot 4^0 = 2 \cdot 256 + 1 \cdot 64 + 3 \cdot 16 + 0 + 3 = 512 + 64 + 48 + 3 = 627$.
$627 / 3 = 209$. Tényleg osztható $3$-mal.
$627 / 4 = 156$ maradék $3$. Tényleg nem osztható $4$-gyel.
$627 / 12 = 52$ maradék $3$.
Feladat: Oszthatóság $17$-tel a $(103213)_4$ szám esetén.
$17$ nem a $4$ hatványa, sem tényezője. A $4 \pmod{17}$ maradékot kell vizsgálni.
$4^0 \equiv 1 \pmod{17}$
$4^1 \equiv 4 \pmod{17}$
$4^2 \equiv 16 \equiv -1 \pmod{17}$
$4^3 \equiv 4 \cdot (-1) = -4 \equiv 13 \pmod{17}$
$4^4 \equiv 4 \cdot 13 = 52 \equiv 1 \pmod{17}$
A ciklus hossza $4$. Tehát a számjegyeket 4-es csoportokba rendezhetjük balról.
$(103213)_4 = (10)(3213)_4$
A $3213_4$ szám értéke $4$-es csoportban:
$3 \cdot 4^3 + 2 \cdot 4^2 + 1 \cdot 4^1 + 3 \cdot 4^0$
Használjuk a kongruenciákat:
$3 \cdot 4^3 \equiv 3 \cdot 13 = 39 \equiv 5 \pmod{17}$
$2 \cdot 4^2 \equiv 2 \cdot (-1) = -2 \equiv 15 \pmod{17}$
$1 \cdot 4^1 \equiv 1 \cdot 4 = 4 \pmod{17}$
$3 \cdot 4^0 \equiv 3 \cdot 1 = 3 \pmod{17}$
Összeg: $5 + 15 + 4 + 3 = 27$.
$27 \equiv 10 \pmod{17}$.
A $(10)_4$ szám értéke $1 \cdot 4 + 0 = 4$.
A teljes szám $N = (10)_4 \cdot 4^4 + (3213)_4$.
$N \equiv 4 \cdot 1 + 10 \pmod{17}$
$N \equiv 4 + 10 \pmod{17}$
$N \equiv 14 \pmod{17}$.
Tehát a $(103213)_4$ szám nem osztható $17$-tel, és $14$ a maradéka.
A szám értéke tízes számrendszerben: $1 \cdot 256 + 0 \cdot 64 + 3 \cdot 16 + 2 \cdot 4 + 1 \cdot 4 + 3 \cdot 1 = 256 + 48 + 8 + 4 + 3 = 319$.
$319 / 17 = 18$ maradék $13$.
$N = (103213)_4 = 1 \cdot 4^5 + 0 \cdot 4^4 + 3 \cdot 4^3 + 2 \cdot 4^2 + 1 \cdot 4^1 + 3 \cdot 4^0$
$N = 1 \cdot 1024 + 0 + 3 \cdot 64 + 2 \cdot 16 + 1 \cdot 4 + 3 \cdot 1 = 1024 + 192 + 32 + 4 + 3 = 1255$.
$1255 / 17 = 73$ maradék $14$. A számítás helyes.
Ez a példa jól mutatja, hogy a ciklikus maradékok felfedezése kulcsfontosságú lehet bonyolultabb oszthatósági vizsgálatoknál.
Gyakran Ismételt Kérdések
Mi az a négyes számrendszer?
A négyes számrendszer egy helyiértékes számrendszer, amelyben a számokat a $0, 1, 2, 3$ számjegyekkel írjuk fel. A helyiértékek a $4$ hatványai ($4^0, 4^1, 4^2, \dots$).
Miért fontosak az oszthatósági szabályok?
Az oszthatósági szabályok segítenek gyorsan eldönteni, hogy egy szám osztható-e egy másikkal, anélkül, hogy elvégeznénk a teljes osztást. Ez időt takarít meg és fejleszti a matematikai intuíciót.
Hogyan ellenőrizhető az oszthatóság 4-gyel a négyes számrendszerben?
Egy szám akkor osztható $4$-gyel a négyes számrendszerben, ha az utolsó számjegye $0$.
Mi a helyzet az oszthatósággal a számrendszer alapjának hatványaival?
Ha egy számrendszer alapja $b$, akkor egy $b^n$ számmal való oszthatóság általában az utolsó $n$ számjegy vizsgálatával ellenőrizhető. A négyes számrendszerben ez azt jelenti, hogy $4^n$-nel osztható, ha az utolsó $n$ számjegye $0$.
Milyen elv alapján működik az oszthatóság 3-mal a négyes számrendszerben?
A négyes számrendszerben az oszthatóság $3$-mal úgy ellenőrizhető, hogy összeadjuk a számjegyeket. Ha az összeg osztható $3$-mal, akkor az eredeti szám is osztható $3$-mal. Ez azért van, mert $4 \equiv 1 \pmod 3$.
Használhatók ezek a szabályok valós problémák megoldására?
Bár a négyes számrendszer nem mindennapi, a szabályok mögötti logika (mint pl. a modulo aritmetika, helyiértékek vizsgálata) rendkívül hasznos a számelméletben, kriptográfiában és informatikában, ahol különböző számrendszereket használnak.
Miben különbözik ez a tízes számrendszerbeli szabályoktól?
A lényegi különbség az alapban rejlik. A tízes számrendszerben a $10$ hatványai (mint $10, 100$) könnyen kezelhetők, a négyes számrendszerben pedig a $4$ hatványai. Más számokkal való oszthatóságnál az alap és a vizsgált szám közötti relatív prímesség vagy konkrét kongruenciaviszonyok határozzák meg a szabályok hasonlóságát vagy eltérését.
