Oszthatóság

Az oszthatóság egy matematikai reláció, melynek tulajdonságait a számelmélet vizsgálja.

1. Hagyományos értelemben akkor mondjuk, hogy az a és b egész számok között (ebben a sorrendben) fennáll az oszthatósági reláció; röviden a b szám osztója az a számnak, vagy az a szám osztható a b-vel, ha van olyan egész szám, melyet b-vel szorozva a-t kapunk, vagy más szóval, ha az a szám többszöröse a b-nek. A b osztó valódi osztó, ha nem azonos a-val vagy 1-gyel és triviális osztó, ha igen.)^[1]
2. Egész számok helyett gyűrűk elemei között értelmezett oszthatóságról is beszélhetünk. A definíció hasonló: az a gyűrűelem osztható a b gyűrűelemmel (az a többszöröse b-nek, vagy a b osztója a-nak), ha van olyan c gyűrűelem, amellyel b-t szorozva a-t kapunk.

Az elnevezés egy kicsit félrevezető, mivel szorzás helyett osztást sugall. A definíció szorzásos megfogalmazására a nulla miatt van szükség: Így megoldható, hogy a nulla osztható legyen nullával.

Oszthatóság

Oszthatósági hálódiagram a 400-nál nem nagyobb reguláris számokra

Egy a egész szám osztója egy b egész számnak, ha van olyan n egész szám, melyre ${\displaystyle a\cdot n=b}$. Jele: ${\displaystyle a|b}$ (a osztója b-nek). Ennek tagadását ${\displaystyle a\nmid b}$ jelöli.

Az oszthatóság tulajdonságai (bármely a,b,c egész szám esetén):

• ${\displaystyle a|a}$ (ez a reflexív tulajdonság)
• ${\displaystyle 1|a}$
• ${\displaystyle a|0}$
• ${\displaystyle a|b\Rightarrow a|b\cdot c}$
• ${\displaystyle a|b\Rightarrow a\cdot c|b\cdot c}$
• ${\displaystyle a\mid b}$, ${\displaystyle c\mid d}$ ⇒ ${\displaystyle ac\mid bd}$.
• ${\displaystyle (a|b)\wedge (b|c)\Rightarrow (a|c)}$ (ez a tranzitív tulajdonság)
• ${\displaystyle (a|b)\wedge (a|c)\Rightarrow (a|b+c)}$
• ${\displaystyle (a|b)\wedge (a|c)(\Rightarrow (a|b-c)}$
• ${\displaystyle (a\mid b)\wedge (a\mid c)\Rightarrow (a\mid kb+lc)}$, ahol minden szám egész.
• Ha ${\displaystyle a\mid b}$ és ${\displaystyle b\mid a}$, akkor ${\displaystyle a=b}$ vagy ${\displaystyle a=-b}$.
• Ha ${\displaystyle a\mid b}$, akkor ${\displaystyle -a\mid b}$ és ${\displaystyle a\mid -b}$. :Úgy is mondják, hogy ${\displaystyle a}$ és ${\displaystyle -a}$ nem különböznek egymástól lényegesen, és mivel a -1 egység, asszociáltak.
• Mivel ${\displaystyle 0\cdot n=0}$ minden ${\displaystyle n}$ egész számra, azért 0|0 és ${\displaystyle 0\nmid b}$, minden ${\displaystyle b\neq 0}$ egészre.
• A legkisebb pozitív nem triviális osztó prímszám.

Az oszthatósági reláció reflexív és tranzitív, a pozitív egész számok körében antiszimmetrikus.

Az egységek olyan számok, melyek osztói minden egész számnak. Ha ${\displaystyle e=\pm 1}$, akkor van inverze az egész számok körében. Azokat a számokat, melyek egymás egységszeresei, egymás asszociáltjainak nevezzük. A számelméletben nem tekintjük lényegesen különbözőeknek őket. Egy egész asszociáltjait és az egységeket nem tekintjük valódi osztóknak; triviálisnak nevezzük őket. Ha egy szám nem egység, de nincsenek valódi osztói, akkor prímszám. Egy szám prím volta másként is megfogalmazható: ha bármely két szám szorzata akkor és csak akkor osztható a számmal, ha valamelyik tényező osztható a számmal.

Egy természetes szám természetes szám osztóinak halmaza a szám osztóhalmaza. Az oszthatósággal, mint részben rendezéssel az osztóhalmaz hálót alkot. Ez az oszthatósági háló.

Egy egész szám többszörösei alkotják a többszöröshalmazt, ami megszámlálhatóan végtelen.

Két szám legnagyobb közös osztója az a közös osztó, mely a két szám osztóhalmazainak metszetében az oszthatóságra nézve maximális elem, azaz az a közös osztó, aminek minden közös osztó osztója. Hasonlóan definiálható a legkisebb közös többszörös is. Például a nulla és egy tetszőleges egész szám legnagyobb közös osztója a másik szám, legkisebb közös többszöröse a nulla. Ha két szám legnagyobb közös osztója 1, akkor a számok relatív prímek. A legnagyobb közös osztó meghatározható euklideszi algoritmussal. Mivel a két szám szorzata megegyezik legnagyobb közös osztójuk és legkisebb közös többszörösük szorzatával, azért ez segít kiszámítani a legkisebb közös többszöröst is.

Az ${\displaystyle \mathbb {N} _{0}}$ halmaz az oszthatósággal mint relációval részben rendezett halmaz, teljes háló, ahol a legnagyobb alsó korlát a legnagyobb közös osztó, és a legkisebb felső korlát a legkisebb felső többszörös. A legkisebb elem az 1, és a legnagyobb a 0.

Oszthatósági tesztek a tízes számrendszerben felírt természetes számok körében

• 2-vel osztható az a szám, melynek utolsó számjegye 0, 2, 4, 6 vagy 8, tehát páros.
• 3-mal osztható az a szám, melynek számjegyeinek összege 3-mal osztható. (Úgy is meg lehet fogalmazni, hogy 3-mal osztható az a szám, amelynek a 3-mal nem osztható számjegyeinek (vagyis a 0, 3, 6, 9 számjegyeket nem számolva) összege osztható hárommal (például a 3694692306 szám osztható 3-mal, mert hárommal nem osztható számjegyeinek összege 4+2=6 osztható 3-mal).)
• 4-gyel osztható az a szám, melynek a két utolsó jegyéből alkotott szám osztható 4-gyel. (Azaz ez a szám 00, 04, 08, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92 vagy 96.)
• 5-tel osztható az a szám, melynek utolsó számjegye 0 vagy 5.
• 7-tel osztható az a szám, melynek számjegyeit hátulról hármasával csoportosítva és váltakozó előjellel összeadva a kapott szám osztható 7-tel. A 7-tel való oszthatóság ellenőrzéséhez az egyesek, tízesek stb. helyén álló számjegyeket sorra 3-mal, 2-vel, (-1)-gyel, (-3)-mal, (-2)-vel és 1-gyel (majd ugyanilyen sorrendben folytatva tovább ismét 3-mal, 2-vel stb.) kell szorozni, s a kapott számokat összeadni: az eredeti szám osztható 7-tel, ha az ekként kapott súlyozott összeg is osztható héttel.
• 7-tel osztható az a szám, aminek az utolsó két számjegyéből álló számhoz hozzáadva a többi számjegyből alkotott szám kétszeresét 7-tel osztható számot kapunk.
• 8-cal osztható az a szám, melynek utolsó három jegyéből alkotott szám osztható nyolccal.
• 9-cel osztható az a szám, melynek számjegyeinek összege 9-cel osztható.
• 10-zel osztható az a szám, melynek utolsó jegye 0.
• 11-gyel osztható az a szám, melynek páros helyiértéken álló számjegyeinek összege megegyezik a páratlan helyiértéken álló számjegyek összegével, vagy a kettő különbsége 11-nek a többszöröse.
• 13-mal osztható az a szám, amely utolsó három számjegyéből álló számnak és a maradék számjegyekből álló számnak a különbsége osztható 13-mal.
• 16-tal osztható az a szám, melynek utolsó négy jegyéből alkotott szám osztható 16-tal.
• 25-tel osztható az a szám, melynek a két utolsó jegyéből alkotott szám osztható 25-tel, vagyis ha a szám 00-ra, 25-re, 50-re vagy 75-re végződik.
• 50-nel osztható az a szám, melynek az utolsó két jegyéből alkotott szám osztható 50-nel. (00 vagy 50)
• 100-zal osztható az a szám, melynek az utolsó két számjegye 00.
• 125-tel azok a számok oszthatók, melyek utolsó 3 számjegyéből alkotott szám osztható 125-tel. (000, 125, 250, 375, 500, 625, 750 vagy 875.)
• A 0-val való osztást ugyan nem értelmezzük, azonban a 0 minden számmal osztható, a definíció szerint még önmagával is. Más szám nem lehet nullával osztható, hiszen a 0 minden többszöröse 0.
• A 2 és 5 hatványai esetén az oszthatósági szabály általánosan is megfogalmazható: 2ⁿ-nel (5ⁿ-nel) akkor osztható egy szám, ha az utolsó n számjegyéből álló szám osztható 2ⁿ-nel (5ⁿ-nel).

Az egyes szabályok bizonyítása itt: Oszthatósági szabályok.

Oszthatósági szabályok más számrendszerekben

Nem kell egy a alapú számrendszerben felírt egész számot csak azért átváltani, hogy megállapíthassunk bizonyos oszthatóságokat.

• Az a-val és hatványaival való oszthatóság: n osztható a^h-nal, ha utolsó h jegye 0.
• Osztható a^h egy osztójával, ha az utolsó h jegyből álló szám osztható az adott osztóval.
• Osztható (a-1)-gyel vagy annak egy osztójával, ha számjegyeinek összege osztható (a-1)-gyel vagy az adott osztóval.
• Osztható (a+1)-gyel vagy annak egy osztójával, ha a páros helyiértékű jegyeit és a páratlan helyiértékű jegyeit külön-külön összeadva olyan számokat kapunk, amik különbsége osztható (a+1)-gyel vagy az adott osztóval.

Fejszámolás szempontjából csak azoknak a szabályoknak van nagyobb jelentősége, ahol a szeletek hosszúsága legfeljebb négy. Lehet hosszabb szeletekkel is számolni, de az az átlagosnál jobb számemlékezetet igényel.

A fentiek alapján vizsgálható számok néhány számrendszerben:

${\displaystyle a=2}$: 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 21, 31, 32, 33, 63, 64, 65, … osztói

${\displaystyle a=3}$: 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 16, 20, 26, 27, 28, 40, 41, 80, 81, 82, … osztói

${\displaystyle a=4}$: lásd ${\displaystyle a=2}$

${\displaystyle a=5}$: 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 18, 24, 25, 26, 31, 39, 62, 63, 78, 124, 125, 126, 156, 312, 313, 624, 625, 626, … osztói.

Egy szám osztható egy ${\displaystyle 2^{n}-1}$ alakú számmal, ha egy ${\displaystyle 2^{n}}$ alapú számrendszerben a számjegyek összege osztható ${\displaystyle 2^{n}-1}$-gyel. A kettes és az ${\displaystyle 2^{n}}$ alapú számrendszerek között egyszerű az átváltás: a kettes számrendszerbeli alak jegyeit jobbról kezdve ${\displaystyle n}$ jegyenként csoportosítjuk, és ezeket a csoportokat váltjuk át. Például ${\displaystyle 91_{10}}$ osztható ${\displaystyle 7_{10}=2^{3}-1}$-gyel, mivel ${\displaystyle 91_{10}=001011011_{2}=133_{8}}$ számjegyeinek összege ${\displaystyle 1_{8}+3_{8}+3_{8}=7_{10}}$.

Ha az alap ezer, akkor a 27-tel való oszthatóság meghatározható a számjegyek összegeként. Ez tízes számrendszerben azt jelenti, hogy hármas csoportokat képezünk, és ezeket adjuk össze. Az így kapott szám akkor és csak akkor osztható 27-tel, ha az eredeti is.

Egy nullától, egytől és mínusz egytől különböző ${\displaystyle n}$ számmal akkor és csak akkor osztható egy másik szám, ha annak ${\displaystyle n}$-es számrendszerbeli ábrázolása nullára végződik.

Oszthatóság az egész számok körében

Ha az egész számok halmazát a szokásos összeadás és szorzás művelettel integritástartománynak tekintjük, és a fenti módon értelmezzük rajta az oszthatóság fogalmát, akkor például a 6-nak nemcsak az 1, 2, 3 és a 6 lesz osztója, hanem a -1, -2, -3 és a -6 is, mert ezekhez is lehet olyan alkalmas egész számot találni, amivel megszorozva őket mind 6-ot adnak. Ekkor a prímszámoknak 4 osztójuk van, amiből 2 pozitív; így a prímszámok ellentettje is prímszám, de nem lényegesen különböző az eredeti prímtől. A számelmélet alaptételében a különböző szó helyét a lényegesen különböző kifejezés veszi át.

Oszthatóság gyűrűkben és integritástartományokban

Definíció:

Tetszőleges ${\displaystyle D}$ integritástartomány (kommutatív, zérusosztómentes és egységelemes, általában legalább két elemet tartalmazó gyűrű) esetén ${\displaystyle a,b\in D}$ elemeire akkor mondjuk, hogy ${\displaystyle a}$ osztója ${\displaystyle b}$-nek, ha van olyan ${\displaystyle c\in D}$ elem, melyre ${\displaystyle ac=b}$.

Jelölés: ${\displaystyle a|b}$

Ahogyan a gyűrű tekinthető az egész számok halmazán értelmezett négy alapművelet által meghatározott struktúra általánosításának, úgy az itt bevezetett oszthatósági fogalom is tekinthető az egész számokon értelmezett oszthatóság általánosításának.

Valóban, tetszőleges ${\displaystyle D}$ integritástartomány tetszőleges ${\displaystyle a,b,c,d}$ elemeire teljesülnek a következő tulajdonságok, (melyek az egész számok esetén is teljesülnek az oszthatóságra):

• ${\displaystyle a|a}$ (reflexivitás)
• ${\displaystyle a|b}$ és ${\displaystyle b|c}$ esetén ${\displaystyle a|c}$ (tranzitivitás)
• ${\displaystyle a|b}$ és ${\displaystyle a|c}$ esetén ${\displaystyle a|b+c}$ és ${\displaystyle a|b-c}$
• ${\displaystyle a|b}$ és ${\displaystyle c|d}$ esetén ${\displaystyle ac|bd}$
• ${\displaystyle 1|a}$ és ${\displaystyle a|0}$ a ${\displaystyle D}$ bármely ${\displaystyle a}$ elemére
• ${\displaystyle ac|bc}$ és ${\displaystyle c\neq 0}$ esetén ${\displaystyle a|b}$

• Tetszőleges integritástartományokban is érvényes (a nullosztómentesség miatt), hogy (0-val jelölve a gyűrű nullelemét) ${\displaystyle 0|a}$ akkor és csak akkor teljesül, ha ${\displaystyle a=0}$.

Ahogyan az egész számok példája is mutatja, egy integritástartományon az osztást műveletként bevezetni nem feltétlenül egyszerű (a struktúra bővítése nélkül), mert előfordulhat, hogy az ${\displaystyle a\mathbf {x} =b}$-nek nincs is megoldása, vagy több megoldása is van ${\displaystyle x}$-re (rögzített ${\displaystyle a}$ és ${\displaystyle b}$ mellett), így az esetleges ${\displaystyle a/b}$ jel nem jelölné az integritástartomány egy egyértelmű elemét.

Gyűrűkben is definiálhatjuk az egységeket és asszociáltakat. Ha van egységelem, akkor vannak egységek is, melyek csoportot alkotnak. Az invertálható elemek egységek, így nem érdemes a testeket számelméleti szempontból vizsgálni, hiszen a nullelem kivételével minden egység.

Gyűrűk esetén a prímszámokra vonatkozó ekvivalens definíciók nem ekvivalensek. Ha egy elem nem egység, de nincsenek valódi osztói, akkor felbonthatatlan. Egy elem prímelem, bármely két elem szorzata akkor és csak akkor osztható az elemmel, ha valamelyik tényező osztható az elemmel. Gyűrűkben a prímszámok szerepét a felbonthatatlan elemek töltik be.

Az egész számokhoz hasonlóan bevezetik a közös osztók, legnagyobb közös osztó, közös többszörösök, legkisebb közös többszörös, relatív prím elemek fogalmát. Ezzel együtt eljutnak az ideálelméletig. Euklideszi gyűrűkben a legnagyobb közös osztó euklideszi algoritmussal kiszámítható.

Az oszthatóság és az ideálok kapcsolata: Ha az ${\displaystyle a}$ elem osztja a ${\displaystyle b}$ elemet, akkor ${\displaystyle a\mid b\Leftrightarrow (a)\supseteq (b)}$, és megfordítva. Például az egész számok gyűrűjében a ${\displaystyle (2)}$ ideál a páros számokból áll, míg a ${\displaystyle (4)}$ a néggyel oszthatókból. A 2 osztója a 4-nek, és ennek megfelelően, a ${\displaystyle (2)\supseteq (4)}$. Ha a gyűrű nem kommutatív, akkor az oszthatóság sem szimmetrikus, így beszélhetünk bal- és jobb oldali, kétoldali osztókról, amelyek a jobb-, bal-, illetve kétoldali ideálokkal állnak ugyanolyan kapcsolatban, mint kommutatív esetben az osztók és az ideálok.

Jegyzetek

1. Archivált másolat. [2021. október 17-i dátummal az eredetiből archiválva]. (Hozzáférés: 2021. február 10.)

Fordítás

• Ez a szócikk részben vagy egészben a Teilbarkeit című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Fritz Reinhardt: dtv-Atlas Schulmathematik. Deutscher Taschenbuch-Verlag, München 2002, ISBN 3-423-03099-2.
• Eric W. Weisstein: Divisibility tests auf Mathworld (engl.)
• http://www.olympiade-mathematik.de/pdf/saetze/teilb.pdf

További információk

• Alice és Bob – 16. rész: Alice és Bob alaptétele
• Alice és Bob – 19. rész: Alice és Bob ideáljai
• https://kobak.org/oszthatosagi-szabalyok-tablazat/