Дељивост

Дељивост (ијек. дјељивост) алгебарска је особина целих бројева. Један цели број је дељив другим целим бројем, ако је остатак дељења једнак нули. Тако на пример, је број 8 дељив са 4, зато што $8\div 4$ износи 2 без остатка, док број 9 није дељив са 4, зато што $9\div 4$ износи 2 са остатком 1.

Дељивост је централни појам теорије природних бројева (аритметика). Један од највећих математичара свих времена, који је и данас познат као краљ математике, Карл Фридрих Гаус (1777-1855), једном је приликом рекао: "Математика је краљица наука, а теорија бројева је краљица математике." Гаус је можда више него било који други математичар у историји допринео развоју аритметике, оне исте за коју је на крају написао: „Аритметика је ипак претешка за мене!"

Дељивост

Дефиниција

Природан број $a$ дељив је природним бројем $b$ ако постоји природан број $m$ такав да је $a=mb$. Ако је број $a$ дељив бројем $b$ писаћемо $b|a$ (чита се: „б дели а").

На пример 3|24 јер је 24 = 3х8; слично је 7|28 јер 28 = 7x4; такође 10|10 јер је 10 = 10х1. Број b зовемо делитељ или фактор броја a; број b зовемо садржалац, вишекратник, или умножак броја a.

Кажемо да је b прави делитељ од a ако b|a и a ≠ b.

Једноставни критеријуми

Постоји неколико једноставних правила за проверу дељивости конкретних бројева са којима радимо често.

• Број је дељив са 10, 100, 1000, ... ако су му једна, две, три, ... последње цифре нуле.
• Број је дељив са 2, 4, 8, ... ако су му последње 1, 2, 3, ... цифре дељиве датим бројем.
• Број је дељив са 5, 25, 125, ... ако су му последње 1, 2, 3, ... цифре дељиве датим бројем.
• Број је дељив са 3 и 9 ако му је збир цифара дељив датим бројем.
• Број је дељив са 7 ако занемарите његову последњу цифру (јединицу) и од остатка одузмете двоструку вредност занемарене цифре, нпр. број 231 занемаримо `1` и од 23 одузмемо 2 што износи 21 које је дељиво са 7, уколико имамо многоцифрен број поступак можемо да поновимо више пута.

На пример, број 12300 је дељив са 100 јер су му последње две цифре дељиве са 100; број 12345612345632 је дељив са 4 јер су му последње две цифре дељиве са 4; број ...7125 је дељив са 125 јер су му задње три цифре дељиве са 125; број 5886 је дељив са 9 јер му је збир цифара дељив са 9.

Постоји још неколико „једноставних“ правила која не користимо дневно. Записани број, ако је довољно дугачак, можемо раздвојити на класе (групе узастопних цифара) са једнаким бројем цифара. Бројећи са лева удесно те класе ће се налазити на парним и непарним позицијама.

• Број је дељив са 11 када је разлика између збира цифара (једноцифрених класа) које стоје на непарним и оних које стоје на парним местима дељива са 11. На пример, број 8684016 на непарним местима има цифре 8,8,0,6 чији је збир 22, а на парним 6,4,1 збира 11. Разлика ових збирова је 11, тј. број дељив са 11; почетни број 8684016 је дељив са 11.
• Број је дељив са 101 када је разлика збира двоцифрених класа које у броју стоје на непарним и парним местима дељива са 101. На пример, број 7 96 89 има збирове класа, на непарним местима 7+89=96, и на парним 96, чија је разлика нула, тј. дељива је са 101. Зато је почетни број 79689 дељив са 101.
• Број је дељив са 7, 11, 13, 77, 91, 143 и 1001 када је разлика између збира троцифрених класа које у броју стоје на непарним местима и збира троцифрених класа које стоје на парним местима дељива са датим од бројева. На пример, број 539 693 385 има разлику ових класа 539-693+385=231, па је дељив са 7, 11 и 77, а није дељив са 13, 91, 143 и 1001.

Лакши задаци

У неким случајевима не користимо „велику“ теорију да би установили дељивост, јер је у решавању задатка довољно елементарно познавање математике, или је ситуација изван домашаја наше теорије.

1. Задатак

Доказати да је број $117^{4}-93^{4}$ дељив свим природним бројевима до броја 10 закључно.

Решење

Растављањем на факторе, добијамо: $117^{4}-93^{4}=(117^{2}-93^{2})(117^{2}+93^{2})=(117-93)(117+93)(117^{2}+93^{2}).$

Вредности прве две заграде лако израчунавамо и множимо 24х210=(6х4)х(5х42)=2х3х... х9х10.

2. Задатак

Доказати да је за сваки број n број $n^{3}-n$ дељив бројем 6.

Решење

На пример, за n = 1, дати број је нула, дељив је са шест;

за n = 2, дати број је 8 - 2 = 6, такође;

за n = 3 имамо $3^{3}-3=27-3=24$, а 24 је број дељив са шест.

У општем случају, растављамо на факторе и дати израз постаје n(n-1)(n+1). Фактори су три узастопна броја n-1, n, n+1. Међутим, у низу од три узастопна природна броја тачно један је дељив са три (у низу од k узастопних бројева тачно један је дељив са k). Према томе, дати израз је за свако n дељив са 3; али је дељив и са 2, јер сваки низ од 3 члана има подниз од 2 члана. Отуда је дати израз дељив са 6.

3. Задатак

Доказати да је за свако n израз $n^{3}+23n$ дељив са 6.

Решење

Трансформишимо дати израз у облик $(n^{3}-n)+24n$. Први сабирак, разлика у загради, је према претходном задатку дељива са 6, али је и други сабирак, због фактора 24 дељив са 6. Њихов збир мора бити дељив са 6.

Провера

за n = 1, израз има вредност 1+23 + 24, дакле дељив је са шест;

за n = 2, израз даје резултат 8+46 + 54, дељив са шест;

за n = 3, израз је 27+23х3=96, тј. 6х16.

Међутим, у општем случају претпостављали смо да су тачна следећа тврђења:

• ако је сваки од сабирака дељив са 6, онда је и збир дељив са 6;
• ако је један од фактора дељив са 6, онда је и производ дељив са 6.

Ова тврђења су многима јасна и без доказа, али у теорији бројева постоје и тежа.

Алгоритам дељења

Следећа теорема садржи неке од најважнијих особина дељивости.

Теорема 1

Нека су a, b, c произвољни (природни) бројеви. Тада:

(а) ако a|b и b|c онда a|c;

(б) ако a|b, онда је a ≤ b;

(в) ако a|b и a|c, онда, за произвољне целе бројеве x, y важи a|(bx+cy);

(г) ако a|b и b|a, онда је a = b.

Доказ

(а) ако је a|b и b|c, онда постоје бројеви m и n такви да је b = ma, c = nb. То значи да је c = mna, па а|c.

(б) Ако a|b, постоји број m такав да је b = ma. Непосредно следи b = am ≥ ax1 = a.

(в) Ако је a|b и a|c, онда постоје бројеви m, n тако да је b = ma, c = na. Отуда, bx + cy = max + nay = a(mx +ny). Дакле, a|(bx+cy).

(г) Из претпоставке a|b, b|a и из (б) следи да је a = b.

Последица 1

(а) Ако су a, b, c произвољни (природни) бројеви такви да је a|b и a|c, тада a|(b+c) и a|(b-c).

(б) Ако су у једнакости $a_{1}+a_{2}+...+a_{n}=b_{1}+b_{2}+...+b_{n},$ сви сабирци изузев једног дељиви са c, онда је и тај један дељив са c.

Алгоритам дељења, или теорема о дељењу са остатком, која следи, је једна од важнијих у теорији бројева:

Теорема 2

За дате (природне!) бројеве $a$ и $b$, једнозначно су одређени бројеви $q$ и $r$, такви да је $a=bq+r,\;0\leq r<b.$

Доказ

Постоји бар један такав начин представљања броја $a$, рецимо када изаберемо $bq$ као највећи садржалац броја $b$ који није већи од $a$. Претпоставимо да постоји још један начин, да је $a=bq_{1}+r_{1},\;0\leq r_{1}<b.$ Тада одузимањем добијамо $b(q-q_{1})+r-r_{1}=0,$ што значи да $b|(r-r_{1})$ (последица 1а). Како је $|r-r_{1}|<b,$ следи $r-r_{1}=0,$ тј. $r=r_{1}.$ Затим да је $q=q_{1}.$

Број q назива се количник а број r остатак при дељењу a са b.

Алгоритам дељења се користи у класификацији бројева. На пример, када b = 2 за број ($a=2q+1$) кажемо да је непаран ако r = 1, односно да је паран ако r = 0. Прост број p је онај коме су једини делитељи 1 и p. За природан број који није прост кажемо да је сложен.

НЗД

• Заједнички делитељ бројева a и b је (природан) број k ако је k|a и k|b.
• Највећи заједнички делитељ бројева a и b је највећи од бројева заједничких делитеља. Означава се са (a,b), или NZD(a,b), али може и НЗД.
• Узајамно прости бројеви а, б су они за које је НЗД(а, б)=1. Узајамно просте бројеве називамо и релативно прости бројеви.

На пример, NZD(8,15)=1, NZD(4,40)=4, NZD(40,210)=10, NZD(697,816)=17, NZD(1326,7315)=1.

Теорема 3

Највећи заједнички делитељ два (природна) броја је јединствен.

Доказ

Ако је $c_{1}=NZD(a,b)$ и $c_{2}=NZD(a,b)$ тада је $c_{1}|c_{2}\wedge c_{2}|c_{1}$ дакле $c_{1}=c_{2}$.

Теорема 4

Ако је $c$ највећи заједнички делилац природних бројева $a$ и $b$, онда постоје цели бројеви $x$ и $y$ такви да је $xa+yb=c.$

Доказ

Посматрајмо скуп целих бројева облика $xa+yb$, где $x,y\in \mathbb {Z} .$ Изаберимо у њему најмањи природан број, рецимо $n=xa+yb$.

Докажимо да $n|a$ и $n|b$:

Претпоставимо да $n$ не дели $a$. Онда би постојали такви бројеви $q$ и $r$ да је $r<n,a=nq+r.$

Па би било $r=a-nq=a-q(xa+yb)=(1-xq)a-yqb$, тј. природан број $r$ био би мањи од $n$ и припадао би скупу бројева $xa+yb$, што је у контрадикцији са претпоставком да је $n$ најмањи.

Докажимо сада да је $n$ највећи заједнички делилац бројева $a$ и $b$, тј. да је $n=c.$ Како је $c=NZD(a,b),$ можемо писати $a=pc,b=qc,$ па имамо да је $n=xpc+yqc=c(xp+yq).$ Следи да $c|n,$ па $c\leq n.$ Зато што је $c$ највећи заједнични делилац, биће $c=n,$ тј. $c=xa+yb.$

На пример, највећи заједнички делиоци из претходног примера

НЗД(8,15)=1 и имамо 2х8-1х15=1; NZD(4,40)=4 и 11х4-1х40=4; (40,210)=40 и -5х40+1х210=10.

Најмањи заједнички делилац бројева $a,b$ можемо дефинисати и као најмањи природан број облика $xa+yb=c;\;x,y\in Z.$ Погледајмо на крају још једну теорему која се често користи приликом решавања (тежих) задатака аритметике.

Теорема 5

(а) Ако је k>0, онда је NZD(ka,kb)=kNZD(a,b).

(б) Ако је a=bq и b ≥ 0, онда је NZD(a,b)=b.

(в) Ако q|ab и при томе су q и b узајамно прости бројеви, тј. NZD(b,q)=1, онда q|a.

(г) Ако је a=bq+r, онда је NZD(a,b)=NZD(b,r).

Доказ

(в) Претпоставићемо да је a>0; за a<0 радили би једнако. Прво приметимо да NZD(b,q)=1 повлачи NZD(ab,q)=NZD(a,q). Наиме, број NZD(ab,q) дели бројеве ab и aq, па дели и број NZD(ab,aq)=aNZD(b,q)=a. Како NZD(ab,q) дели q следи да NZD(ab,q) да NZD(a,q). Међутим, број NZD(a,q) дели оба ab и q, па NZD(a,q) дели NZD(ab,q), дакле NZD(ab,q)=NZD(a,q). Како из претпоставке q|ab произилази NZD(ab,q)=q, то из последње доказане једнакости излази q|a.

(г) Нека је c=NZD(a,b). Тада c дели оба броја a и b, па је a=xc, b=yc, односно r =c(x-yq), па c|r, тј. c је заједнички делилац бројева b и r. Отуда NZD(a,b) дели NZD(b,r). Ставимо c₁=NZD(b,r), па имамо b=y₁c₁, r = zc₁, a=c₁(y₁q+z), tj. c₁ deli а. Дакле NZD(b,r)|NZD(a,b), те је NZD(a,b)=NZD(b,r).

Теорема 6

$NZD(a_{1},a_{2},...,a_{n})=NZD(NZD(a_{1},a_{2},...,a_{n-1}),a_{n}).$

Доказ

Први, односно други са лева најмањи заједнички делилац назовимо c, односно d. Како је $d|a_{i},\;i=1,2,...,n,$ добијамо да $c|NZD(a_{1},a_{2},...,a_{n-1})$ и $c|a_{n}$. Дакле, c|d. Обратно, како $d|NZD(a_{1},a_{2},...,a_{n-1}),\;d|a_{n}$ то је $d|a_{i},\;i=1,2,...,n,$ па је d|c. Према томе c|d.

Еуклидов алгоритам

Еуклидов алгоритам служи за одређивање највећег заједничког делитеља природних бројева a > b:

Према алгоритму дељења, једнозначно су одређени бројеви $q_{i},r_{i},\;i\leq k+1,$ такви да је

$a=q_{1}b+r_{1},\;r_{1}<b;$

$b=q_{2}r_{1}+r_{2},\;r_{2}<r_{1};$

$r_{1}=q_{3}r_{2}+r_{3},\;r_{3}<r_{2};$

...

$r_{k-3}=q_{k-1}r_{k-2}+r_{k-1},\;r_{k-1}<r_{k-2}$

$r_{k-2}=q_{k}r_{k-1}+r_{k},\;r_{k}<r_{k-1}$

$r_{k-1}=q_{k+1}r_{k}+0,\;(r_{k+1}=0).$

Низ $r_{1},r_{2},r_{3},...,r_{k-1},r_{k}$ је опадајући низ природних бројева мањих од b, што значи да горе описани поступак мора завршити после коначно много дељења.

Теорема 7

$NZD(a,b)=r_{k}$ где је $r_{k}$ последњи позитиван остатак добијен применом Еуклидовог алгоритма на природне бројеве $a,b;\;a>b.$

Доказ

Доказаћемо да важе следећа два тврђења:

(а) $r_{k}|a,\;r_{k}|b;$

(б) $d|a\wedge d|b\Rightarrow d|r_{k}.$

(а) Заиста, из последње једнакости Еуклидовог алгоритма добијамо да је $r_{k}|r_{k-1}.$ На основу тога и претпоследње једнакости, закључујемо да је $r_{k}|r_{k-2}.$ Настављајући тај поступак добија се да је $r_{k}|r_{k-3},\;r_{k}|r{k-4},\;...,r_{k}|b,\;$ а онда из прве једнакости следи да је $r_{k}|a.$

(б) Нека је d природан број такав да је d|a и d|b. Тада, из прве једнакости Еуклидовог алгоритма добијамо да је d|r₁, из друге да је d|r₂, ..., и коначно, из претпоследње, да је d|r_k. Тиме је доказано (б). Дакле $r_{k}=NZD(a,b).$

Пример

Одредићемо НЗД(936,588). По Еуклидовом алгоритму имамо:

936 = 1·588 + 348,

588 = 1·348 + 240,

348 = 1·240 + 108,

240 = 2·108 + 24,

108 = 4·24 + 12,

24 = 2·12.

Дакле, НЗД(936,588)=12.

На основу теореме 6, закључујемо да се вишеструком применом Еуклидовог алгоритма може добити највећи заједнички делитељ више бројева.

Литература

• Владимир Мићић, Зоран Каделбург: „Увод у теорију бројева“, Друштво математичара СР Србије, Београд, 1989.
• Ратко Тошић, Вања Вукославчевић: „Елементи теорије бројева“, Алеф, Нови Сад, 1995.