i
i
“1169-Kejzar-0” — 2010/7/19 — 11:28 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 21 (1993/1994)
Številka 2
Strani 82–85
Bogdan Kejžar:
EULERJEVA FUNKCIJAϕ
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/21/1169-Kejzar.pdf
c© 1993 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
li)"-'-/i)eme",,-, It: ,,-, 1,,-,,-,
EULERJEVA FUNKCIJA ep
Govorili bomo o funkciji iz teorije števil, ki nosi Ime velikega matematika
Eulerja. Leonhard Euler je živel v 18 . stoletju in je delal ter ustvarjal na
vseh področjih uporabne in teorijske matematike . Sodi med najplodnejše
matematike vseh časov .
Eulerjeva funkcija !p preslikuje naravna števila v naravna števila. Vred-
nost funkcije pri danem naravnem številu n je definirana takole : Med števili
1, 2, 3, . .. n poiščemo vsa z n tuja števila , jih preštejemo in rezultat je !pen).
Torej , vrednost !p( n) nam pove, koliko je pod n števil , ki so tuja z n.
Navedimo nekaj primerov: !p(l) = 1, !p(2) = 1, !p(4) = 2, !p(7) =6 in
!p(10) =4, saj so števila 1, 3 , 7 in 9 tuja zlO.
Naloga 1. Izračunaj !p(5), !p(8), !p(17) in !p(18).
Sedaj pa izračunajmo še !p(40) . 5tevilo 40 razstavimo na praštevila:
40 = 23 ·5. To nam pove, da je neko število tuje s 40 , če ni deljivo niti z 2
niti s 5. Med števili 1, 2, 3, ... 40 jih je polovica (vsako drugo število), to je
20, deljivih z 2. Vsako peto število po vrsti je deljivo s 5, zato jih je petina
(torej 8) deljivih s 5. 5tiri števila pa so deljiva z 2 in s 5 hkrati, saj je vsako
deseto število po vrsti deljivo z 2 in s 5. Zato je 20 - 4 = 16 števil deljivih
samo z 2 in ne s 5, 8 - 4 = 4 pa je deljivih s 5 in ne z 2. Torej je s 5 ali z 2
(vsaj z enim od teh dveh števil) deljivih natanko 16 + 4 + 4 =24 števil. Zato
je !p(40) = 40 - 24 = 16 .
Naloga 2. Izračunaj !p(55) in !p(63).
Vrednost !p(315) pa izračunajmo skupaj . Najprej število 315 razstavimo
na produkt samih praštevil : 315 = 32 .5 .7. Razcep nam pove da je neko
število tuje s 315 natanko tedaj, ko ni deljivo z nobenim od števil 3, 5 in
7. Vrednost !p(3l5) bomo poiskali tako, da bomo med števili 1, 2, 3, ...
315 "prečrtali" najprej vsa števila, ki so deljiva s 3, nato med preostalimi še
neprečrtanimi vsa tista , ki so deljiva s 5, in končno še vsa, ki so deljiva s 7.
Ostala bodo samo še števila tuja s 315 .
83
Ko med števili 1, 2, 3, .. . 315 prečrtarno števila , ki so deljiva s 3, to so
števila 1 · 3, 2·3 , 3 · 3, ... 315 · 3, ostane še
. 315 1
315 - - = 315 · (1 - -)
3 3
števil.
Sklep 1. Ce med prvimi 315 števili prečrtamo vsa s 3 deljiva števila ,
potem ostane še 315 · (1 - ~ ) neprečrtanih števil.
Preštejmo, koliko je v tem ostanku števil , ki so deljiva s 5. Vsa števila
(med prvimi tristo petnajstimi) deljiva s 5 so 1· 5,2 ·5,3 ·5, ... ~ . 5. Med
temi števili so bila v prvem koraku prečrtana vsa s 3 deljiva števila . To je
natanko toliko števil, kolikor je med števili 1, 2, 3, oo ' 3k5 takih, ki jih 3 deli.
Ostalo je torej še (glej Sklep 1. - namesto 315 vzameš 3~5) ~ . (1 - ~)
števil deljivih s 5. Prečrtarno še ta in ostane
1 315 1 1 1
315 · (1 - -) - - . (1 - -) = 315 · (1 - -) . (1 - -)
3 5 3 3 5
števil.
Sklep 2. Ko med prvimi 315 števili prečrtamo vsa števila, ki so deljiva
s 3 ali s 5, ostane še 315· (1 - ~) . (1- %) števil.
Sedaj pa poglejmo, koliko večkratnikov števila 7 moramo še prečrtati .
Med prvimi tr istopetnajstimi štev ili so deljiva s 7 naslednja : 1 ·7 , 2·7, 3 ·7, oo '
~ · 7. V prvih dveh korakih smo med temi števili pre črtali vsa števila deljiva
s 3 in s 5. Med njimi je ostalo še (Sklep 2.) natanko 3~5 . (1 - ~) . (1 - %)
neprečrtanih števil. Ko prečr tarno še ta, nam ostane
1 1 315 1 1 1 1 1
315·(1--) .(1--)-- ·(1--) ·(1--) =315·(1--).(1--) .(1--)
3 57 3 5 3 5 7
števil.Ta števila so tuja s 315 in zato je
1 1 1 2 246lp(315) =315 · (1 - -) . (1 - -) . (1 - -) =3 ·5·7· - . - . - = 144.
3 5 7 3 5 7
84
Naloga 3. Podobno kot zgoraj izračunaj !p(1000) . !p(1001) in !p(770) .
Razstavimo število n na produkt različnih praštevilskih potenc:
S pomočjo tega razcepa izračunajrno !pen). Najprej med števil i 1,2 ,3 , oo. n
odvržemo vsa , ki so deljiva s PI. Ostane še
n 1
n - - = n(l--)
PI PI
števil. Sedaj med preostalimi odvržemo tista , ki so deljiva s P2 in niso hkrati
deljiva s PI. Št evila, ki so deljiva hkrati s PI in s P2, smo odvrgli že na
prejšnem koraku . Tako nam po drugem koraku ostane še
1 nIl 1
n(l - -) - -(1- -) = n(l - - )(1- -)
PI P2 PI PI P2
števil.
Med preostalimi števili nato odvržemo tista števila, ki so deljiva s P3.
To so natanko tista števila med števili 1, 2, 3, oo , n, ki so deljiva s P3 in niso
deljiva niti s PI niti s P2. Ostane še
lIn 1 1 1 1 1
n(l - - )(1 - -) - -(1 - -)(1 - ---'-) = n(l - -)(1 - -)(1 - -)
PI P2 P3 PI P2 PI P2 P3
števil. Ta postopek nas po k korakih , ko nam ostanejo samo še z n tuja
števila, pripelje do formule :
1 1 1 1
!pen) = n(l - -)(1- -)(1 - -) oo . (1 - -).
PI P2 P3 Pk
Ob upoštevanju razcepa števila n na prafaktorje lahko to formulo zapišemo
tudi nekoliko drugače :
Naloga 4. 5 pomočjo pravkar izpeljane formule preveri rezultate , ki si
jih dobil pri prejšnih nalogah.
I 
1 ?a brdce, ki pomajg OQM)VC verjstnoQtnega Muna, dodajmo Pc nalogo, 
I ki jim bo razkrila k ma razlago formula za ~ ( n ) .  
I 
I