P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 28 (2000/2001) Številka 1 Strani 34-41
Jože Grasselli:
O NAJMANJŠEM ŠTEVILU S PREDPISANIM ŠTEVILOM DELITELJEV
Ključne besede: matematika, teorija števil, delitelji, faktorizacija. Elektronska verzija: http://www.presek.si/28/1430-Grasselli.pdf
© 2000 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
O NAJMANJŠEM ŠTEVILU S PREDPISANIM ŠTEVILOM DELITELJEV
Katero je najmanjše naravno število, ki ima 81 deliteljev? Aii obstaja od njega manjše naravno število, ki premore več kot SI deliteljev?
1. Z delitedji mislimo na pozitivne delitelje. Število vseh deliteljev naravnega števila n označimo z d(n). Ker ima 1 le delitelj 1, je d(l) = = 1. Vsi delitelji števila 10 so 1. 2, -5, 10, zato je d( 10) — 4. Pri majhnih n delitelje hitro poiščemo, in ko jih preštejemo, imamo d(n). Navcdimo obrazec, po katerem lahko d(n) izračunamo:
Naj bo p praštevilo, a naravno število. Število pa nima drugih deliteljev kot l,p,... ,pa; ker jih je a + 1, velja
d(pa) = a +1.	(1)
Cc sta p, q različni praštevili in a, b naravni števili, so vsi delitelji števila paqb zajeti v seznamu
1, p, ...rpa~\ p" & M.....Pa Pa<l
q\pqb, ...,pa-1qb,paqb
V vsaki vrstici je a + 1 števil, vrstic pa je b + 1, vseh deliteljev za paqh je torej (a + l)(i> + 1) ah
d(pY) = (tt+ !){& +1).	(2)
Ko na podoben način nadaljujemo, ugotovimo: Število,
tff ,	(3)
kjer so pi,p2,- - ■ ,pj različna praštevila in a\, «2,..., ti, naravna števila, premore («i + J )(u2 + 1).., (a, 4- 1) deliteljev; tako je
d {pVP? ■ ■ -Pj') = («i + «te + !)■■• + 1) ■	(4)
Po (4) število 3000 23 • 3 ■ 53 premore 4 ■ 2 ■ 4 = 32 deliteljev.
Vsako naravno število, ki je večje od 1, ima. en sam zapis (3) s produktom potenc praštevil (če zapišemo praštevila po velikosti). Pri velikih naravnih številih pa navadno ni preprosto to izrazitev (3) poiskati.
2. V razdelku 1 smo vpraševali, koliko deliteljev ima dano naravno število. Sedaj vprašanje obrnimo: Katera naravna števila imajo predpisano število deliteljev? Pri danem naravnem številu m iščemo torej vsa naravna števila x, za katere je
d(x) = m.	(5)
Pri m — 1 premore enačba (5) eno samo rešitev x = 1; edino naravno število z enim d elit eljem je namreč 1.
Ko v (5) vzamemo m — 2, iščemo vsa naravna števila z dvema deliteljema. To so ravno vsa praštevila in enačba d(x) = 2 ima za rešitev vsako od praštevil. Rešitev je neskončno, saj je praštevil neskončno.
V enačbi (5) naj bo sedaj m ~ 3. Po (1) je za x mogoče vzeti p2, kjer je p praštevilo. Drugih rešitev pa enačba d(x) = 3 nima. Naj bo namreč x tretja ali višja potenca praštevila p ali pa x deljiv vsaj z dvema različnima prašteviloma p. q. Po (1) in (4) je za tak x vedno d(x) > 4, Vse rešitve enačbe d(x) = 3 so tako p1. kjeT je p praštevilo; rešitev je spet neskončno.
Kako je pri m = 4? Iz (1) dobimo rešitev x = p'\ p praštevilo, iz (2) rešitev x — pq, p in q različni praštevili; drugih rešitev enačba d(x) — 4 nima. Za p3 je neskončno možnosti, prav tako jih je za pq.
Obravnavajmo sedaj primer m = 8. Iščemo x v obliki (3); zaradi (4) preide enačba d(x) = 8 v enačbo
(«i + l)(az + 1) • ■ ■ («j + 1) = 2 ■ 2 ■ 2 ,	(6)
Ker desne strani ne moremo bolj razstaviti, so tudi na levi lahko največ trije faktorji, torej je j < 3. Poiskati moramo rešitev enačbe (6), ko je j =3 1,2,3. Za j = 1 dobimo
ai + 1 = 8 .
Torej je a^ = 7 in x ~ p'. p praštevilo. Ko je j = 2, se (6) glasi (ni + l)(û2 + 1) =4-2.
Dobimo a\ = 3, «2 = 1 in x = pfp2, kjer sta P2 različni praštevili. R.ešitev a\ = î, «2 = 3 izpustimo, saj pripelje do istega x. Pri 7 = 3 je (6) oblike
(01 + 1)(«2 + l)(û3 + 1) = 2 ■ 2 ■ 2 .
Torej je rii = «2 = ûg = 1 in £ = ptpzps, kjer so p\, P2, P3 različna praštevila. Vse rešitve enačbe d(x) = 8 ko tako zajete v številih
Pli P1P2, P1P2P3 : kjer so praštevila P1,P2,P3 različna. (T)
Rešitve razpadejo na tri množice, vsaka vsebuje neskončno števil; v prvi množici je najmanjše število 2', v drugi 23 * 3, najmanjše število tretje množice je 2 ■ 3 ■ 5.
Podobno ugotovimo za m = 16, da so vse rešitve enačbe d(x) = 16 zajete z množicami
Pi5, P1P2, p\p\, P1P2P3, P1P2P3P4,	(8)
kjer so pi, p2, p;i, p4 različna praštevila.
V splošnem primeru ravnamo enako kot, zgoraj za m — 2,3,4,8. Naravno število m > i izrazimo v ohliki
m = </i<j2 ... qs ; qi > q2 > ... > qs,	(9)
kjer su qi,q2, ■ ■ ■, qs praštevila, ne nujno med sabo različna. Enakost (5) se potem glasi:
(QI + 1)... + 1 ) = ... g, .	(10)
Ker je na desni s praštevilskih faktorjev, mora biti j < s. Za vsak jf = 1,2,3,..-,s iz (10) izhaja ena ali več rešitev «!,..., a_,; vsaka taka rešitev daje x = p"1 ■ ... ■ p"*; t.u je za različna praštevila pi....,pj neskončno možnosti in tako že vsaka rešitev a\za (10) pripelje do neskončno rešitev x za (5). Za m = 16 je s = 4 in v (8) nastopa pet oblik za x. Ce je s velik, ima enačba (10) veliko rešitev in je za x potem na razpolago veliko oblik.
3. Iz razdelka 2 vemo: Pri danem naravnem številu m > 1 obstaja neskončno naravnih števil, ki imajo m deliteljev; najmanjše med števili, ki premorejo natanko m deliteljev, označimo z A(m). Število m si mislimo zapisano v obliki (9).
Če je s = 1, je m = q\; ker je q\ praštevllo, ima. enačba ( 10) le rešitev ai ¿= çi — 1. Vse rešitve enačbe d(x) = so tako x — pqi kjer je p praštevilo; najmanjše število med temi x je 2Çl "1 in velja
Â{§\) — 2<n 1 ; gje praštevilo.
(11)
Ce je s = 2, je m = §igi ali pa. m — <]irjo pri praštevilih qi, q2 in <ji > <i2- Za 'in = (/1 r/i dobimo iz (10), da je ai = gf — 1 ali pa a\ = qt — 1. «2 = h ~ 1- Enačba (5) ima tedaj rešitve
2 — 1 — 1 — 1 p\ ' pV~ p2~ i pup2 sta različni praštevili.	(12)
Za m = q\q2, qi > je v (10) ali a\ — (/¡r/2 — I ali pa «i = q\ — 1, 62 - (¡2 ~ 1- To daje za enačbo (5) rešitve
p«-1 ^	-1 , j(jei, gta jj1p2 različni praštevili. (13)
Najmanjši med števili (12) sta 2"'"1 m 2^ 1 ■ S51 Ker je qy > 2, je
_2111 —* - ^iiiii-l) > —1 ■ 491-1 > —1 ■ 31"-1
in število na koncu je najmanjše med števili (12). Zato je
A(qlq2) = 2">-}	(14)
Najmanjši števili v (13) sta 2«1''2-1 in 2®1~1-391-1. Zaradi qx > q2 > 2
je
27H2-1 _ 2f/i . 271 — 1) > -1 • 49=-1 > 2<iL_1 ■
in tako
^(71^2) = 29l_1 ■ 352- 1 .	(15)
Ko primerjamo (14) in (15), vidimo, daje
¿(«1®)	•39s_1;	praštevili > q2 .	(16)
Na podalgi obrazcev (11) in (16) je sestavljena preglednica
4(2) = 2	A(6) = 4(3-2) = 22-3 = 12
4(3) = 22 = 4	4(7) =2° = 64
(17)
4(4) = 4(2 ■ 2) = 3 ■ 2 = 6 4(9) = 4(3 ■ 3) = 22 - 32 = 36 4(5) = 24 = 16	4(10) = 4(5 • 2) = 2J • 3 = 48
Najmanjše od števil v množicah (7) je 23 ■ 3 in zato
4(8) = 4(2 ■ 2 ■ 2) = 23 - 3 = 24 .	(18)
Dodajmo še dva zgleda. Po kratkem računu najdemo
A(16) = A(2 ■ 2 • 2 - 2) - 23 • 3 • 5 = 120,	(19)
po nekoliko daljšem pa
A(60) = A(5 • 3 ■ 2 • 2) = 24 ■ 3a • 5 ■ 7 = 5 040.	(20)
Najmanjše naravno število s 16 delitelji je torej 120, s 60 delitelji 5 040.
4, Zaznamujmo s p\ = 2, p'2 = 3, p'z = 5, p'4 = 7,.,. ,p's,,., zaporedna praštevila. S številom m = qiq-2 • ■ ■ qs- kjer so gi.92,..., qs praštevila in je qi > 32 > ... > <j5, je določeno število
JB(qm ...q,) = ■ 3«-1 -... ■ p'*'-1 .	(21)
Iz (21) najdemo
B(2) =2	ii(6) = .6(3 ■ 2) = 22 - 3 = 12
B(3) = 22=4	B{ 7) = 26 = 64
B(4) = 5(2 ■ 2) = 2 ■ 3 - 6	B{9) - 5(3 ■ 3) - 22 ■ 32 = 36
5(5) = 24 = 16	6(10) = B{5 ■ 2) = 24 ■ 3 = 48
Dobili smo enake rezultate kot v (17); za m = 2. 3, 4. 5, 6, 7. 9,10 je torej B(m) = A(m).
V splošnem pa števili B(m) in A (m) nista enaki. Po (18) je .4(8) == = 24, toda B(8) = B(2-2-2) = 2- 3- 5 = 30. Število B{m) ima m deliteljev; to pove opredelitev (21). Ker je A(m) najmanjše naravno število z m delitelji, je zmeraj
B(m) > A(m).	(22)
Ni težko pokazati, da obstaja neskončno takih m, za katere v (22) velja enačaj.
Za vsako praštevilo q je zaradi (21) in (11)
B(q) = A(q); q je praštevilo.	(23)
Pri praštevilih q\, qi, kjer je q\ > <72. Je po (21) in (IG)
— A{qiq2), kjer sta quq2 praštevili in qx > q2 . (24)
Ker je praštevil neskončno, imamo v (23) in (24) neskončno naravnih števil, ko v (22) velja enačaj. Niso pa s tem opisani vsi takšni m.
Naravno število, pri katerem v (22) velja neenaeaj in je torej B(m) večji od .4(m), se imenuje izjemno. Daje tudi izjemnih števil neskončno, kažejo naslednji primeri. Iz ocene
3-5-711 = 1155 > 33 ■ 5-7 = 945 dobimo pri praštevilu q po (21)
B{q- 2-2 - 2- 2} = 2q~l -3*5-7- 11 > 2«"1 • 33 • 5 • 7 . (25)
Števili na obeh straneh ueenačaja imata enako mnogo deliteljev, namreč 16c/. Ker je A(q -2-2-2-2) najmanjše naravno število s I67 delitelji, iz (25) izhaja
B(q ■ 2 ■ 2 ■ 2 ■ 2) > A(q • 2 • 2 ■ 2 ■ 2); g praštevilo.	(26)
Naj bo q izbrano praštevilo in p', najmanjše praštevilo z lastnostjo
¿>2«.	(27)
Ker je praštevil neskončno, je med njimi neskončno takih, ki so večja od 2q. Pri vsakem danem q zato obstaja p't. Po (21) upoštevaje (27) izračunamo
B{q') = 2q~1 • 39_1 •... • p'i~i -p't~l > 2""1 .39-1 ■•..■p'tt-1	.
Število je na koncu enako
in ima q' deliteljev tako kot B(q' ). Zato je
B[ql) > A{qt), kjer je p, > 2'' in sta p[,q praštevili. (28)
Tako v (26) kakor v (28) je zajetih neskončno izjemnih naravnih števil tn, ko v (22) velja neenaeaj. Seveda so še izjemna števila drugačnih oblik.
5. Rekli smo, da je A(m) najmanjše naravno število z m delitelji. Zato je
¿(^(m)) - m.
Nara vno število m, pri katerem je izpolnjena enakost
A(d(ni)) = m,	(29)
se imenuje minimalno. Ker pomeni d(m) število deliteljev za m, lahko (29) preberemo: Naravno število tri je minimalno, če ni manjšega naravnega števila s toliko delit.elji, kot jih ima m.
Za praštevilo q je d{2l,~l) = q; po (11) je potem
/l(f/(2CJ-1}) = A(q) — 2q~x .
Pogoj (29) je izpolnjen in število
2q~ , kjer je q praštevilo,	(30)
je minimalno.
Pri praštevilu q > 3 iz (2) in (15) najdemo
A(d(2q-1 ■ 3)) = A{q • 2) = 2*"1 ■ 3	(31)
in število
2"_1 ■ 3 ; q liho praštevilo,	(32)
je minimalno.
Minimalnih števil oblika. (30) je neskončno, prav tako minimalnih števil oblike (32); niso pa. s tem izčrpana vsa minimalna števila,
Navedimo še dve neskončni množici, katerih vsaka vsebuje le končno mnogo minimalnih števil.
Produkt vseli naravnih števil od 1 do n se imenuje n fakulteta in se označuje n!; za naraven n je torej
n! = 1 ■ 2 - 3-... • (n - 1) -n.
Ugotovili so: Število »! je minimalno za n = 1,2,3,4,5,6,7, pri n > 7 pa število nI ni minimalno:
Zaznamujmo z v (n) najmanjši skupni večkratnik števil 1.2,..., n. Dognano je: v(n) je minimalno število za n = 1, 2,3, 4, 5, 6, 8,9, 10. i 1, 12, 16,27,28; za vsak drugačen n pa v(n) ni minimalno število.
6. Dolžni smo še odgovor na vprašanje, zastavljeno na začetku. Ker je 81 = 3 ■ 3 ■ 3 ■ 3, v enačbi (1) velja s = 4; iz rešitev te enačbe najdemo .4(81) = ,4(3 ■ 3 ■ 3 ■ 3) = 22 ■ 32 ■ 52 ■ 72 = 44 1 00. Najmanjše naravno število z 81 delit.elji je tako 44 100; vsako od njega manjše naravno število
ima torej manj ali več deliteljev kot 81. Število 25 200 = 2J • 32 • 52 • 7 je manjše od 44 100 in premore 5 ■ 3 ■ 3 - 2 = 90 deliteljev. Čeprav je 44 100 najmanjše naravno število z 81 delitelji, obstaja vsaj eno od njega manjše naravno število, ki ima več kot 81 deliteljev.
Naloge
1.	Med števili m = qiq-2q3- kjer so q\, q2, praštevila in q\ > q2 > q3. je izjemno le število 2 ■ 2 ■ 2 = 8. Razen za qi = = q:i = 2 velja zmeraj B(q\q-2q;i) = >4C<3i<7a)■ Preveri to trditev.
2.	Izpelji, da je ,4(16) = 120, yt(60) = 5 040.
3.	Pokaži, da je A{26) = 23 ■ 33 • 5 ■ 7.
4.	S. Ramanujan (1887-1920) imenuje naravno število m > 1 zelo sestavljeno, če je d(n) < d(m) za vsak naraven n < m. To pomeni, da je zelo sestavljeno število m najmanjše naravno število z d(rn) delitelji. Ker je tako A(d(m) ) = m, je zelo sestavljeno Število obenem minimalno število. Minimalno število pa ni zmeraj zelo sestavljeno; po (30) je 2'1 = 10 minimalno število, ni pa zelo sestavljeno, saj je 12 < 16, toda
d{ 12) = d(22 ■ 3) = C > 5 = d{24) = d(16).
Poišči še kakšno minimalno število, ki ni zelo sestavljeno.
5.	Pri praštevilu q je po (30) število 2f'_1 minimalno. Ker za q > 5 drži ocena
,	q- J o-l	g—l	(1—1
2''~ = 2 = • 2» > 2~ -4 > 2s . 3t
velja
d (2^ -3] =	- 2 = 9 + 1 >9 = rf(2q"1)
in vidimo, da minimalno število 217-1 ni zelo sestavljeno. Praštevil q i 5 je neskončno; med neskončno mnogo minimalnimi števili '2q 1, q > 5 pa nobeno ni zelo sestavljeno. Na podoben način ugotovi: Če je cj praštevilo, g > II. minimalno št,e\rilo 2q~ 1 ■ 3 ni zelo sestavljeno.
6.	Sestavi preglednico števil d(m) za m od 2 do 200; iz nje vidiš: Vsa zelo sestavljena števila do 200 so 2,4, G, 12, 24, 30, 48, G0.120,180. (Čeprav je 2 praštevilo, je tudi zeio sestavljeno število.)
7.	Ali je minimalno število .4(100) = 24 • 3J ■ 5 ■ 7 zelo sestavljeno (glej npr. število 14 400)7
.Jože Grasselli