P R E S E K List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 26 (1998/1999) Številka 6 Strani 328-337 Jože Grasselli: O FROBENIUSOVEM ŠTEVILU Ključne besede: matematika, teorija števil, diofantske enačbe. Elektronska verzija: http://www.presek.si/26/1384-Grasselli.pdf © 1999 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo O FROBENIUSOVEM ŠTEVILU 1 V daljnji deželi plačujejo le s kovanci po 7 in 10 denarnih enot. Katere zneske lahko poravnajo? Zastavljeno vprašanje zahteva dopolnitev. Sprašujemo seveda le po zneskih, ki se povedo v naravnih številih (saj zneska, ki je necelo število, ni mogoče poravnati). Upoštevati pa je potrebno še nekaj. Recimo, da hočemo v Sloveniji v kovancih izplačati 18 SIT. Odštejemo npr. tri kovance po 5 SIT in tri po 1 SIT; lahko pa damo npr, štiri kovance po 5 SIT in dobimo nazaj kovanec 2 SIT. Znesek 18 SIT je bil prvič poravnan brez vračila, drugič z vračilom. Katere zneske je mogoče v daljnji deželi izplačati z vračilom? Ker je 7 ■ 3 + 10 - (-2) = 1, (1) je možno izplačati znesek 1. (Plačnik da tri kovance po 7 enot in vrnejo mu dva kovanca po 10 enot.) Po množenju z naravnim številom n iz (1) dobimo 7(3n) + 10 (—2n) = n (2) in vidimo, da je mogoče poravnati znesek n. (Za 3ti kovancev po 7 enot vrnejo 2n kovancev po 10 enot.) Označimo z x število kovancev po 7 enot, z y število kovancev po 10 enot in vsebino enakosti (2) povejmo takole: A. Vsako naravno število n izrazimo lahko v obliki 7x + 10y s ceiima številoma x in y. Aii: Pri vsakem naravnem številu n je enačba 7x +10 y = n rešljiva v celih številih x, y. Kako je v daljnji deželi s plačevanjem zneskov brez vračila? Ker ni vračanja, nobeno od celih števil x, y ne sme biti negativno. Gre torej za natančno tiste zneske, ki jih lahko izrazimo v obliki 7x + 10y , (3) ko se x, y spreminjata po nenegativnih celih številih 0, 1, 2, 3, (4) Moremo izplačati npr. vsote 7 = 7 • 1 + 10 ■ 0, 10 = 7 • 0 + 10 ■ 1, 17 = 7* 1 + ltf-lj ne pa npr. 1, 8, 23. Pokažimo, da je naravno število n, večje od 53, izrazljivo v obliki (3) pri x, y iz (4) in da 53 take izrazitve nima. Iz ugotovitve A vemo, da obstajata celi števili xq, yo> ko je 7x0 + 10yu = n . (5) Delitev yo s 7 daje količnik k in nenegativen ostanek r; števili k, r sta celi in yQ = 7k + r, 0 < r < 7. (6) Z najdenim k in znanim xq naredimo celo število = + lUfc; od tod sledi x0 = ri - 10k, (7) Ko zapisa (6), (7) za yo in x0 vnesemo v (5), dobimo 7n + lOr = n. (8) Po privzetku je n > 53, zaradi (6) pa 0 < r < 7; zato iz (8) izhaja ocena 7rj = n ~ lOr > 53 - 60 = -7. Torej je 7r\ > —7 in tako rx > — 1; to pove, da je celo Število ri iz množice (4); ker velja to tudi za r, imamo v (8) želeno izrazitev za n. Ali je lahko 7x + 10y = 53 (9) pri x, y iz (4)? Ker je 10 ■ 6 > 53 in x ni negativen, more y v (9) biti le 0, 1, 2, 3, 4, 5. Ko te vrednosti za y postavimo v (9), dobimo za 7x po vrsti 53, 43, 33, 23, 13, 3; nobeno teh števil ni deljivo s 7 in tako x v (9) ni celo število. Dognali smo: D rez vračila morejo v dalj nji deželi poravnati vsak znesek 54, 55, 56,...; zneska 53 brez vračila ne morejo izplačati; od zneskov 1,2,..., 52 lahko brez povračila plačajo le nekatere. Povejmo to ugotovitev še drugače. B. Vsako naravno število n > 53 lahko zapišemo v obliki 7x + lOj/ z nenegativnima celima, številoma x, y; za Število 53 to ni mogoče. Ali: Za vsako naravno števjJo n > 53 ima enačba 7x + 10 y~n rešitev v ncnegativnih cclih številih x, y; pri n — 53 enačba take rešitve nima. Lahko se zgodi, da pri plačevanju brez vračila plačnik enega od obeh kovancev za 7 ali 10 enot ne uporabi; ker ni vračanja, more npr. znesek 56 enot poravnati le tako, da našteje osem kovancev po 7 enot. Pa vzemimo, da v daljnji deželi poostrijo pogoje izplačevanja. Dovoljeno je le še plačevanje brez vračila in pri vsakem plačilu je potrebno uporabiti oboje kovance. Katere zneske je sedaj mogoče poravnati? Ravno tiste, ki jih opiše izraz 7x+U)y, ko tečeta x, y po naravnih številih 1,2,3,____ Natančnejši odgovor vsebuje trditev C. Vsako naravno število n > 70 lahko izrazimo v obliki 7x + 10y pri naravnih x, y; za n = 70 to ne velja. Ali: Za, vsako naravno število n. večje od 70 ima enačba 7x + 10y = n rešitev v naravnih številih xt y; pri n = 70 enačba take rešitve nima. Enakosti 7 ■ 3 + 10 ■ 5 = 71 7-8 + 10-2 = 76 7-6 + 10-3 = 72 7 - 1 + 10-7 = 77 7 -9+ 10- 1 = 73 7-4+ 10-5 = 78 (10) 7 • 2 + 10 ■ 6 = 74 7 • 7 + 10 ■ 3 = 79 7 ■ 5 + 10 ■ 4 = 75 7 ■ 10 + 10 ■ 1 = 80 kažejo, da za naravna, števila, od 71 do 80 drži, kar pravi trditev C. Naj bo sedaj naravno število n > 81 in števka njegovih enic j. Med števili (10) je ravno eno, ki itna enico j; zaznamujmo ga a3 (npr. a2 — 72, «n = 80). Ker je n > 81 in 71 > aj > 80, je razlika n — aj naravno število; ker se n in a.j končujeta z enako števko, je n — a j večkratnik od 10; torej je n — a.j = lOfc pri naravnem k. Iz (10) je a} — 7x + 10y z naravnima x, y in n = 7x + 10(fc + y) je želena izrazitev. Če bi bilo lx + 10y = 70 (11) pri naravnih x, y, bi 7 delil lOj/ in potem 7 delil y; torej bi bilo y = 78 pri naravnem s. Prav tako bi po (11) bil x deljiv z 10 in x = 10i pri naravnem t. Najdena x: y, postavljena v (11), pripeljeta do 70(s + t) = — 70 in po krajšanju do a +1 = Si. Za naravni števili s, t to ne more veljati (vsota dveh naravnih števil je 2 ali več). Z naravnima x, y se torej enačba (11) ne da izpolniti. Trditev C je dognana. Povzemimo: Ko morajo v daljnji deželi pri plačevanju brez vračanja uporabiti oboje kovance, lahko plačajo vsak znesek 71,72,73,...; zneska 70 ne morejo poravnati; od zneskov 1,2,3,..., 69 nekatere da, druge ne. 2 Zapustimo daljnjo deželo in se pomudimo pri nekaterih posplošitvah ugotovitev iz razdelka 1. Namesto 7 in 10 vzamemo tuji naravni števili a in b, večji od 1. Č. Ce sta, a, b tuji naravni Števili, je vsako naravno število izrazljivo v obliki ax + by s celoštevilskima x, y. Ali: Naj bosta a, b tuji naravni števili; pri naravnem številu n je enačba ax + by = n rešljiva v celili številih x, y. Trditve Č ne bomo dokazovali. Povejmo samo. da npr. z Evklidovim algoritmom na a, b pridemo do celih števil Xi, ji, takih, da velja a^i + byi = 1. Pri celih številih — nxi, yo = ny\ je potem ax o + byo = n . D. Naj bosta a, b tuji naravni števili, večji od J, in č>) = ab — a — b. (12) Vsako naravno število n > g(a, b) je izrazi ji vo v obliki ax + by z nenegativnima celoštevilskima X, y; za n = g(a, b) to ne drži. Ali: Pri tujih naravnih Številih a, b, večjih od 1, ima enačba ax + by = n (13) za vsako naravno števiio n > g(a, b) rešitev v nenegativnih ceiiii številih x, y; za n — g(a, b) take rešitve nima. Trditev D do ženemo podobno kot B. Po C obstajata celi števili xo, j/o, ko je aio + by0 ~ ti . (14) Ko delimo yo z o, dobimo količnik k in ostanek r ter imamo yo = ka + r, 0 , k določajo celo število n = xq + kb in od tod je xq = r% — kb. (16) Postavimo (16) in (15) v (14) pa smo pri enačbi ari + br = n . (17) Zaradi (15) je r največ a — 1; zato iz (17) izhaja ocena a?'i -I- b(a — 1) > n . Upoštevamo privzetek n > ab — a — b in dobimo ari > ab — a — b — b(a — 1) ali arj > a. Torej je celo število rj > — 1 in tako ri > 0; po (15) je tudi r >0 in (17) predstavlja rešitev enačbe (13) v nenegativnih celih številih x — ri, y — r. Ali je lahko ax + by ~ ab ~ a — b (18) pri ne negativnih celoštevilykih i, yl Potem je a(x + 1) = f>(a — 1 — y) in b deli a(x + 1); ker je b tuj a, mora b deliti x + ] in je zato x- -l t-«6. (19) Tu je s naravno število, saj je x nenegativno celo število in b naravno število. Iz (18) sledi tudi b(y+ 1) = a(& — 1 — i). Od tod vidimo, da a deli y + 1 in je potem y = —l + ta (20) pri naravnem številu t. Zapisa (19), (20) sledita iz predpostavke, da x, y ustrezata enačbi (18). Ko ju vanjo vnesemo, po skrčenju dobimo (s + t)ab = ab. Ker je ab / 0, je s + i = 1. V naravnih številih pa to ne gre. Trditev D je dognana. Naravni števili a, b sta po privzetkn večji od 1 in tuji, zato različni. Kadar sta najmanjši, je eno 2, drugo 3; torej je ab — a — b= (a — 1)(6 — 1) — 1 >2-1 = 1. Z (12) podano celo število g(a, b) je tako pozitivno in liho, saj sta o,, b tuja. Imenuje se flrobeniusovo število za a, b. Zaznamnjmo s h.(a, b) število naravnih števil, ki jih ne moremo izraziti v obliki ax 4- by, kjer sta y celi nenegativni števili. Največje naravno število te vrste je po trditvi D Frobeniusovo število g(a,b). Zato je h(a,b) > l. Do boljše ocene privede kratek razmislek. Ce sta naravni števili rij, n? izrazljivi, obstajajo nenegativni celošte-vilski ari, Vi, X2> lfe> daje axi + by\ = ni t ax2 + by2 = n2 . Po seštetju dobimo a(£i 4- x2) + b(y i + y2) = ni + n2 in vidimo, da je obenem z nj, n2 tudi vsota ni + n2 izrazljiva (saj sta Xi + x2, y\ +y2 nenegativni celi števili). Vse možnosti, kako zapisati M)>(^(sM) + l). (22) Zgled. V skladu z (12) smo že v B našli g(7, 10) = 53; po (22) je h(7,10) > 27. Izpeljimo še trditev: E. Pri tujih naravnih številih a, b, večjih od 1, vsako naravno število n > ab lahko izrazimo v obliki ax + by z naravnima x, y; za ti = ab take izrazitve ni. Ali: Pri tujih naravnih števihh a, b, ki sta nad 1, je za vsako naravno število n > ab enačba ax + by = n rešljiva v naravnih številih x, y; za n ~ ab take rešitve ni. Vsako naravno število n > ab lahko zapišemo n = ab + j, kjer je j naravno število. Po ugotovitvi D obstajata nenegativni celi Števili yo-ko je ax0 + byo = ab — a — b + j Seveda velja a ■ 1 + &■ 1 = o. + č>. Iz vsote teh enačb a(i0 + 1) + b(yo + 1) - ab + j že sledi zahtevna izrazitev za n > ab\ od celih števil y0 namreč nobeno ni negativno, zato sta + 1, yo + 1 naravni števili. Če bi pri naravnih številih x, y imeli ax + by-ab, (23) bi iz tujosti a, b izhajalo, da je x ~ sb, y = ta pri naravnih s, t; to bi v (23) pripeljalo do nemogoče enačbe s + t = 1. Trditev E je dognana. 3 V razdelku 2 smo si ogledali, katera naravna števila zavzame izraz ax 4- by. če sta a, b tuji naravni števili nad 1 in se x, y spreminjata po celih, nenegativnih celih ali le po pozitivnih celili številih. Povejmo še nekaj besed o tem v splošnem primeru. Naj bodo ci,cj,... ,q tuja naravna števila, ustrezajoča pogoju 1 < c\ < c2 < ... < 3, Vsako naravno število n lahko izrazimo v obliki cix\ + C2%2 H-----h Ct^t — n , kjer so , x2, ■ ■ -, cela števila. Največje naravno število, ki ga ne moremo zapisati v obliki c\Xi + + c-iXi + ■ ■ ■ + ctxt z nenegativnimi celimi Xi,X2,. ..,Xt, se imenuje Fro-beniusovo število za ci,c2l- ■ ■ ,ct in ga označujemo 3(^,02,...,ct). Zanj velja Čl —1 < 5(C],02, ■ • • ,ct) < C1C2 + C1C3-I-----hCiCi — ci -C2-----ct . (24) V razdelku 2 smo našli g{ci,cz) — C1C2 — c\ — C2- Za g(a,C2, ■. ■ ,ct) pri i > 3 tak obrazec ni poznan. Je pa mogoče včasih 5(01,02,... ,C() določiti, če imajo C], cj, - - - ,ct poleg zgornjih še kakšne dodatne lastnosti. Navedimo dva takšna primera. Če sta od števil c\,02,03 vsaki dve tuji, je <7(cic2l c2c3, C3C1) = 2C!C2C3 - Cie2 — c2C3 - C3C1 . Za zaporedna naravna števila c,c + l,c+2,...,c + t — 1 in c večji od 1 je g(c,c+ l,c+2,... ,c+t — l) = c + t2 - 3 t2-t~ 2 (2c + t-l)t c+---------~ t-l (25) Oglati oklepaj v (25) pomeni, daje treba vzeli največje celo število, ki ne presega števila (c + t2 - 3)/(i — 1). Npr. za c = 100, t = 3 iz (25) najdemo ^(lOO, 101,102) = 53 ■ 100 + 2 - 101 • 3 = 4999 . Naj pomeni h(c\,02, ■ ■ ■ ,c*) število naravnih števil, ki jih ni mogoče izraziti v obliki C\X\ + 02X2 + * • ■ + C-tXt pri nenegativnih celoštevilskih Xi,X2, ■ ■ ■ ,xt- Podobno kot v (23) ugotovimo h(ci,c2,...,ct) > -(gf(cj,c2,---,ci) + l). Največje naravno število, ki ga ne moremo izraziti kot vsoto c%x 1 + +c2X2-\-----\-CfXt pri naravnih xi,W2, ■ ■ ■ ,xt, zaznamujemo f(c\, 02,... ,ct); s Frobeniusovim številom je takole povezano f(ci,c2, ...,ct) = g(cuc2,.. .,ct) + c1 + c2 + --- + ct. (26) Iz <7(100,101,102) = 4999 sledi po (26) /(100,101,102) = 4999 + 303 = 5302 . Za vsako naravno število n > 5302 obstajajo naravna števila 1, a'2, £3, daje 100xi + 101x2 + 102x3 — n- Ni pa mogoče v tej obliki zapisati 5302 (in nekaterih manjših naravnih števil). Pripis. Ferdinand Georg Frobenius se je rodil leta 1849 v Berlinu in tam umrl leta 1917. Po končanem študiju v rojstnem mestu je bil profesor najprej na politehniki v Ziirichu, nato na univerzi v Berlinu. Deloval je na raznih področjih matematike, zlasti pomembni so njegovi prispevki v algebri. Naloge. L Trditvi D, E držita tudi tedaj, če izpustimo zahtevo, da sta a, h nad 1; ni pa g{a>b) več naravno število. Prepričaj se o tem. 2. Katera naravna števila lahko izrazimo v obliki ax + by z nenegativ-nima celoštevilskiina x, če naravni števili a, b nista tuji? 3. Preveri, da je /i(7,10) - 27, h{7,11) = 33. 4. Število 140 lahko le na en način izrazimo v obliki 7x 4- 10če naj bosta x, y naravni števili (namreč x = 10, y = 7). Toda 141 je mogoče v taki obliki izraziti na dva, 211 na tri načine. Poišči izrazitve! 5. Vse celoštevilske rešitve enačbe 100xi + 101x2 + 102x3 = 5302 so zajete z obrazcema xi = 51 + x3 + lOlu , x2 = 2 - 2x3 - 100tJ, ko X3t v tečeta po celih številih. Od tod takoj vidimo, da enačbe ni mogoče izpolniti v naravnih številih. (Da bo X2 naravno število, mora biti = 0, v = 0.) 6. Poštne pristojbine so 40, 41, 42, 43,... denarnih enot, poravnati jih je mogoče le z leplenjem znamk. Uprava se odloči, da bo izdala znamke le dveh različnih vrednosti, ne bo pa med njima znamke z vrednostjo L Ugotovi, da sta samo dve izbiri; znamki za 2 in 41 ali pa za 5 in 11 denarnih enot. Jože Grasselli