Oszthatósági szabályok

Az oszthatósági szabályok olyan eszközök a matematikában, amik segítségével egy adott számmal való oszthatóság eldönthető az osztás elvégzése nélkül is. Minden osztóra található oszthatósági szabály, azonban az elvárásainkkal nem feltétlenül egyeznek. Egy oszthatósági szabálytól elvárjuk ugyanis, hogy könnyen alkalmazható legyen, és kevesebb lépéssel érjünk célt, mint az osztás maga. Példának okáért ha egy szabály csak az egymilliónál nagyobb számokra működik, akkor, habár elméleti jelentősége van, a mindennapokban kevés hasznát vesszük. Ugyanígy ha a számjegyeket hármasával csoportosítva és alternálva kell összeadni egy szabály szerint, megint csak elméleti jelentősége lesz a szabálynak, a mindennapokban felesleges mennyiségű számítást igényel.

Oszthatóság meghatározása

Bármely két a és b egész szám esetén azt mondjuk, hogy b osztója a-nak, ha van olyan c egész szám, hogy

$a=b\cdot c$.

Tehát egy számnak az osztói párosával fordulnak elő. Ha a négyzetszám, akkor van olyan osztója, jelesül a négyzetgyöke, aminek önmaga a párja, ezért az osztók valódi száma lehet páratlan is.

Valódi osztónak nevezzük azokat az osztókat, amik nem a ±1 számok, és amiknek a párja nem ±1.

A későbbiek szempontjából fontos a maradék fogalma is. Ha ugyanis b nem osztója a-nak, akkor is találhatunk olyan r számot, hogy

$a=b\cdot c+r$,

és |r|<|b|. Ekkor r az a-nak b-vel való osztási maradéka.

Oszthatósági tételek

Az oszthatóság folytatása

Ha a|b és b|c, akkor a|c

Bizonyítás

Definíció szerint a|b azt jelenti, hogy van olyan x, hogy a•x=b, és hasonlóan van olyan y, hogy b•y=c. A kettőt összevetve kapjuk, hogy a•x•y=c. QED

Az oszthatóság háló-jellege

Egy szám bármely két osztójának legkisebb közös többszöröse is osztója a számnak:

$(a|x)\&(b|x)\implies (\mathop {\text{lkkt}} (a,b)|x)$.

Bizonyítás

A legkisebb közös többszörös osztója az összes közös többszörösnek. Mivel x a feltétel szerint közös többszörös, ezért ennek is osztója kell legyen. QED

Következmény

Az oszthatósági szabályokat elegendő prímhatványokra felírni és vizsgálni.

Oszthatósági szabályok az egész számok körében

Az alábbiakban olvashatóak az egyes számokra az oszthatósági szabályok (tételek) a bizonyításaikkal együtt.

A 2 és hatványai

Egy szám akkor osztható 2-vel, ha az utolsó számjegye osztható 2-vel. Egy szám akkor osztható 4-gyel, ha a 100-as osztási maradéka osztható 4-gyel. Egy szám akkor osztható 2ⁿ-nel, ha a 10ⁿ-es osztási maradéka osztható 2ⁿ-nel.

Bizonyítás

1. 10=2•5, és minden szám felírható 10•x+y alakban, ezért az összeg első tagja osztható 2-vel.
2. 100=4•25, és minden szám felírható 100•x+y alakban, aminek első tagja osztható 4-gyel.
3. 10ⁿ=(2•5)ⁿ=2ⁿ•5ⁿ, és minden szám felírható 10ⁿ•x+y alakban, aminek első tagja osztható 2ⁿ-nel.

QED

Az 5 és hatványai

Egy szám akkor osztható 5-tel, ha utolsó számjegye osztható 5-tel. Egy szám akkor osztható 25-tel, ha a százas osztási maradéka osztható 25-tel. Egy szám akkor osztható 5ⁿ-nel, ha a 10ⁿ szerinti osztási maradéka osztható vele.

Bizonyítás

1. Mivel 10=2•5, és minden szám felírható 10•x+y alakban, elegendő csak az utolsó számjegyet vizsgálni.
2. Mivel 100=25•4, és minden szám felírható 100•x+y alakban, ahol y a százas maradék, az állítás már következik.
3. Hasonlóan az eddigiekhez, 10ⁿ=(2•5)ⁿ=2ⁿ•5ⁿ, a számnak elegendő a megfelelő tízhatvány szerinti maradékát vizsgálni.

Hárommal és kilenccel való oszthatóság

Egy szám akkor osztható 3-mal, ha a számjegyeinek összege osztható 3-mal. Egy szám akkor osztható 9-cel, ha a számjegyeinek összege osztható 9-cel.

Bizonyítás

• Vegyük észre, hogy a 10 hatványainak hármas osztási maradéka 1:

${\begin{aligned}10&=3\cdot 3+1\\100&=3\cdot 33+1\\1000&=3\cdot 333+1\\&\vdots \end{aligned}}$

A helyiértékes rendszer alapján egy szám felírható

$\sum a_{n}\cdot 10^{n}$

alakban, ahol az a_n az n. számjegy.. Mivel a tíz hatványainak 3-as maradékai rendre 1-ek, ezért a fenti összeg átírható:

$\sum a_{n}\cdot 10^{n}=\sum a_{n}\cdot \left(3\cdot x_{n}+1\right)=\sum a_{n}\cdot x_{n}\cdot 3+\sum a_{n}$

Itt az első tag definíció szerint osztható 3-mal, tehát elegendő csak a második tagot vizsgálni, ami éppen a tétel állítása.

• Hasonló módon kaphatjuk a kilences szabályt is, mivel a 10 hatványai 9-cel osztva is 1-et adnak maradékul. Ez akár direkt is belátható, mivel a 10 hatványai 1-essel kezdődnek, majd 0-k sorozatával folytatódnak. Ha ebből 1-et elveszünk, akkor az eredmény csupa 9-es számjegyből áll, ami viszont muszáj, hogy kilenccel osztható legyen.
• A fentiek röviden felírhatóak a maradékokra vonatkozó tételek alapján, ugyanis egy szám valamelyik hatványának maradéka a szám hatványának maradéka. Mivel pedig a 10 maradéka 3-ra és 9-re vonatkozóan is 1, annak hatványai pedig mindig 1-ek, a tétel állítása nyilvánvalóvá válik.

Héttel oszthatóság

1. Héttel akkor, és csak akkor osztható egy szám, ha a számjegyeiből képzett hármas csoportokat alternálva összeadva az eredmény osztható héttel.
2. Héttel pontosan akkor osztható egy szám, ha a százzal való osztási maradékához hozzáadva a hányados kétszeresét, az eredmény osztható héttel.

Példa

1. A 193 472 476 szám osztható-e héttel? Csoportosítsuk a számjegyeit hármasával hátulról! 476, 472 és 193 lesz. Felváltva összeadva őket kapjuk:

$476-472+193=197$, ami nem osztható 7-tel. Érdemes viszont felfigyelni arra, hogy az így kapott szám maradéka az eredeti szám maradékával lesz egyenlő.

1. A 7683 szám osztható-e héttel? Osszuk el 100-zal!

$7683=76\cdot 100+83$, és a szabály alapján elegendő a

$2\cdot 76+83=235$ számot ellenőrizni. Ez pedig nem osztható 7-tel. Tovább is léptethetjük a szabály alapján:

$2\cdot 2+35=39$, ami szintén nem osztható 7-tel. Az egyenértékűség miatt pedig az eredeti szám sem osztható 7-tel.

Bizonyítás

1. Vegyük észre, hogy 1000 hetes osztási maradéka 6=7-1, azaz -1. Emiatt az 1.000.000 hetes maradéka 1, stb... Emiatt ezresével, azaz hármasával csoportosítva a számjegyeket, azokat +1 és -1 szorzótényezőkkel felváltva láthatjuk el, majd összegezhetünk.
2. Minden 100-nál nagyobb szám felírható a helyiértékek alapján:

$x=100a+b$.

A felbontás esetén a 100-ast elegendő figyelembe vennünk, ugyanis

$100=98+2=7\cdot 14+2$, azaz felbontható egy 7-tel osztható részre és maradékra. Az eredeti felbontás szerint tehát

$x=98a+(2a+b)$, ahol az első tag 7-tel osztható, tehát elegendő a zárójelbe tett résszel foglalkozni. A szám maradéka is eme tagban lesz megtalálható. Ha pedig eme rész 100-nál nagyobb, akkor természetesen léphetünk tovább.

11-gyel való oszthatóság

Egy szám pontosan akkor osztható 11-gyel, ha a számjegyeit váltakozva pozitív és negatív előjellel összeadva eredményül 11-gyel osztható számot kapunk.

Bizonyítás

A számokat tízes számrendszerben

$a_{0}\cdot 10^{0}+a_{1}\cdot 10^{1}+a_{2}\cdot 10^{2}+\dots +a_{n}\cdot 10^{n}$

alakban írhatjuk fel.

A 10=11-1 alakból következően a 10 hatványai átalakíthatóak:

$10^{2}=(11-1)^{2}=11^{2}-2\cdot 11+1$

$10^{3}=(11-1)^{2}=11^{3}-3\cdot 11^{2}+3\cdot 11-1$

általában

$10^{n}=(11-1)^{n}=11^{n}+{\binom {n}{1}}\cdot (-1)^{1}\cdot 11^{n-1}+{\binom {n}{2}}\cdot (-1)^{2}\cdot 11^{n-2}+\dots +{\binom {n}{n-2}}\cdot (-1)^{n-2}\cdot 11^{2}+{\binom {n}{n-1}}\cdot (-1)^{n-1}\cdot 11^{1}+(-1)^{n}$

Látható, hogy az utolsó tag kivételével mindegyik osztható 11-gyel, azaz a hatványok átírhatóak 11•k±1 alakra. A szám helyiértékes felírása eszerint

$\sum _{i=0}^{n}a_{i}\cdot 11\cdot k_{i}+(-1)^{i}\cdot a_{i}$

Itt az első tag mindig osztható 11-gyel, így az összegük is, az oszthatóság feltétele tehát, hogy a második tagok összege is osztható legyen tizeneggyel, ami pedig az állítás.

13-mal való oszthatóság

Ha egy szám számjegyeit hármasával csoportosítjuk, és azok közé a végéről kezdve felváltva - és + jeleket teszünk, az így kapott összeg értéke pontosan akkor osztható 13-mal, ha az eredeti szám is.

Például

$13|9281363467?$

$9-281+363-467=-376$

-376 : 13 = -28 és 12 a maradék. A 9281363467 tehát nem osztható 13-mal, mi több, az osztás maradéka 12 lesz.

Bizonyítás

A 10 hatványait 13-mal osztva a következőt látjuk:

$10^{n}$	13-as maradék
0	1
1	-3
2	9
3	-1
4	3
5	-9
6	1

Láthatóan minden harmadik hatvány maradéka felváltva 1 vagy -1. Ha tehát a számot 1000 hatványai szerint írjuk fel, akkor kapjuk:

$x=\sum _{i=1}^{n}a_{i}\cdot 13\cdot k_{i}+(-1)^{i}\cdot a_{i}$

Itt az első tagok biztosan oszthatóak hárommal, tehát az oszthatóság meghatározásához elegendő a második tagok összegét vizsgálni. Ez pedig éppen a tétel állítása.

17-tel való oszthatóság

Egy szám pontosan akkor osztható 17-tel, ha a 100-as osztási maradékából kivonva a hányados kétszeresét 17-tel osztható számot kapunk. A két szám osztási maradéka is megegyezik.

Például

$17|64897?$

$64897=648\cdot 100+97\rightarrow 17|(97-2\cdot 648)?$

$97-2\cdot 648=-1199\rightarrow 17|(99-2\cdot 11)?$

$99-2\cdot 11=77$

$17\not |77\Rightarrow 17\not |64897$

Bizonyítás

A 100-nál nagyobb számok felírhatóak 100•a+b alakban. Mivel 6•17=102, ezért írhatjuk:

$100\cdot a+b=102\cdot a-2\cdot a+b$

Az első tag biztosan osztható 17-tel, tehát elegendő a b-2•a kifejezéssel foglalkoznunk. Ez pedig éppen a tétel állítása.

19-cel való oszthatóság

19-cel pontosan akkor osztható egy szám, ha a 100-as osztási maradékához a hányados ötszörösét hozzáadva 19-cel osztható számot kapunk.

Például:

$19|87653?$

$87653=876\cdot 100+53\rightarrow 19|(53+5\cdot 76)?$

$53+5\cdot 876=4433=44\cdot 100+33\rightarrow 19|(33+5\cdot 44)?$

$33+5\cdot 44=253=2\cdot 100+53\rightarrow 19|(53+5\cdot 2)?$

$53+5\cdot 2=63$, ami nem osztható 19-cel, tehát az eredeti szám sem.

Bizonyítás

Minden 100-nál nagyobb szám felírható 100•a+b alakban. Figyelembe véve, hogy 100=5•19+5, átalakíthatjuk

$100\cdot a+b=95\cdot a+5\cdot a+b$,

mely összeg első tagja biztosan osztható 19-cel, ezért az oszthatóságot a többi tag szabja meg. Az pedig a tétel állítása.

Általános szabályok

Oszthatósági szabályok általánosan is megfogalmazhatóak.

A kis Fermat-tétel alapján

A kis Fermat-tétel szerint legyen a és b relatív prím, ekkor

$a^{b-1}\equiv 1{\pmod {b}}$.

mivel 10-hez csak a 2 és az 5 nem relatív prím, ezért bármely p prím esetén

$10^{p-1}\equiv 1{\pmod {p}}$,

ami azt jelenti, hogy egy szám számjegyeit (p-1)-es csoportokba osztva, és a csoportokat összeadva az eredmény ha osztható p-vel, akkor az eredeti szám is.

Ennek lényegében csak elméleti jelentősége van, hiszen például a 19-cel való oszthatóság esetén tizennyolc jegyű számszörnyeket kell összeadnunk, majd az eredményt osztani 19-cel. Ugyanakkor azonban a tétel mintát ad egyes oszthatósági szabályokra, ugyanis ha a maradék nem is egy ugyan, de abszolútértékben "kicsi" szám, akkor van lehetőségünk viszonylag egyszerűen eldönteni oszthatóságot.

Más számrendszerbe áttérve

Legyen a számrendszer alapja f! Ekkor a következő tételek jelenthetőek ki:

Az alapszám osztóival való oszthatóság

Ha g|f, akkor egy tetszőleges ${\overline {n_{k}n_{k-1}\dots n_{2}n_{1}n_{0}}}_{f}$ szám akkor osztható g-vel, ha az utolsó számjegye (n₀) osztható g-vel.

g hatványainak oszthatósági szabálya hasonló: a kitevőnek megfelelő darab utolsó számjegyet kell vizsgálnunk.

Szomszédos számokkal való oszthatóság

Egy f alapú számrendszerben az f-1 szám oszthatósági feltétele hasonló a 9-es oszthatósághoz: Ha a szám f alapú szám jegyeinek összege osztható f-1-gyel akkor az eredeti szám is osztható f-1-gyel.

Egy f alapú számrendszerben az f+1 szám oszthatósági feltétele hasonló a 11-es oszthatósághoz: ha a szám f alapú számjegyeinek váltakozó előjelű összege (hátulról +-szal kezdve) osztható f+1-gyel akkor az eredeti szám is osztható f+1-gyel.

Bizonyítás

Ez a tétel meglehetős egyszerűséggel belátható, ugyanis két szám szorzatának osztási maradéka a két szám osztási maradékának szorzata (illetve annak osztási maradéka):

$a\cdot b{\pmod {c}}=(a{\pmod {c}})\cdot (b{\pmod {c}})$

Ennek következménye, hogy egy szám hatványainak maradékai a szám maradékának hatványai. Mivel

$f\equiv 1{\pmod {f-1}}$

ezért kapjuk, hogy

$f^{n}\equiv 1{\pmod {f-1}}$.

A kongruenciák tulajdonságai alapján pedig már következik az állítás.

Források

• Bronstejn-Szemengyajev-Musiol-Mühlig: Matematikai kézikönyv
• Kiss Péter-Mátyás Ferenc: A számelmélet alapjai
• Szendrei: Algebra és számelmélet

Kapcsolódó szócikkek

• Osztás
• Oszthatóság
• Kongruencia
• Kis Fermat-tétel