i
i
“1127-Zalar-uporaba” — 2010/7/14 — 14:21 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 20 (1992/1993)
Številka 2
Strani 120–123
Borut Zalar:
UPORABA OSTANKOV PRI PROBLEMIH IZ TEO-
RIJE ŠTEVIL
Ključne besede: matematika, teorija števil, praštevila, ostanek, delji-
vost.
Elektronska verzija: http://www.presek.si/20/1127-Zalar.pdf
c© 1992 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.
120
UPORABA OSTANKOV PRI PROBLEMIH IZ TEORIJE
ŠTEVIL
Ogledali si bomo uporabo ostankov pri nekaterih problemih iz teorije naravnih
števil, ki navidez nimajo z ostanki nobene direktne zveze. Včasih se namreč
izkaže, da različn i algebraični izrazi ne morejo biti povsem poljubni, ampak
imajo pri deljenju z nekaterimi števili povsem določene ostanke . Oglejmo si
najprej preprost zgled.
Zgled 1. Dokaži, da enačba x 2 - 3y
številih .
14 rume rešitve v naravnih
Pri deljenju s 3 ima število x lahko tri različne ostanke:
1. možnost . 5tevi lo x je oblike 3k .
Tedaj je število x 2 - 3y deljivo s 3 (z drugimi besedami x 2 - 3y ima pri
deljenju s 3 ostanek O) in zato ne more biti enako 14, ki ima pri deljenju s 3
ostanek 2.
2. možnost. 5tevilo x je oblike 3k + 1.
Tedaj je
x 2 - 3y = 9k 2 + 6k + 1 - 3y = 3(3k2 + 2k - y) + 1,
to rej ima število x 2 - 3y pri deljenju s 3 ostanek 1 in zato ne more biti enako
14.
3. možnost. 5tevilo x je oblike 3k + 2.
Tedaj je
x 2 - 3y = 9k2 + 12k + 4 - 3y = 3(3k2 + 4k + 1 - y) + 1,
torej število x 2 - 3y ne more biti enako 14.
Ker smo upoštevali vse možnosti in rešitve nismo dobili, enačba pač ni
rešljiva v naravnih številih.
S podobnim prijemom bomo ugnali malce drugačen problem.
Zgled 2. Poišči vsa tista naravna števila n , za katera je število 2n - 1
popolni kvadrat.
I 121
Napišimo nekaj prvih členov zaporedja :
21 - 1 = 1
22 - 1 = 3
23 - 1 = 7
24 - 1 = 15
25 - 1 = 31.
Vidimo, da dajo vsi členi, razen prvega, pri deljenju s 4 ostanek 3. Tudi v
splošnem to z lahkoto dokažemo, saj je za vsak n ~ 2 število 2n deljivo s 4 .
Od tod sledi :
Le bi veljalo 2n - 1 = m 2 , potem bi moralo biti število mliho.
1. možnost. Število m je oblike 4k + 1.
Tedaj je
m2 = 16k2 + 8k + 1 = 4(4k2 + 2k) + 1
in da pri deljenju s 4 ostanek 1, zato ne more biti enako številu 2n - 1 za
n > 2.
2 . možnost. Stevilo m je oblike 4k + 3 .
Tedaj je
m2 = 16k2 + 24k + 9 = 4(4k 2 + 6k + 2) + 1
in podobno kot prej ne more biti enako številu 2n - 1 za n ~ 2. Ostane nam
še možnost n = 1, ki nam da edino rešitev 21 - 1 = 12 .
Zgled 3. Dokaži, da obstaja neskončno mnogo naravnih šte vil, ki j ih ni
mogoče zapisati kot vsoto treh kubov naravnih števil.
Le vzamemo naravno število n , moramo rešiti enačbo n = x 3 + y3 + z3
v naravnih številih ali pa pokazati , da rešitev te enačbe ne obstaja . Takoj se
vidi , da za števila 2 , 4 , 5 , 6 , 7 , 9 , 11 enačba ni rešljiva . Na prvi pogled pa
ni jasno , kaj je z rešljivostjo te enačbe za velike n. Na pomoč bomo tokrat
poklicali ostanke pri deljenju z 9 . Vzemimo poljubno naravno število x .
1. možnost . Stevilo x je oblike 3k.
Tedaj je x 3 očitno deljiv z 9 .
2 . možnost. Št evilo x je oblike 3k + 1.
122
Tedaj
da pri deljenju z 9 ostanek 1.
3. možnost . Stevilo x je oblike 3k +2.
Tedaj
x 3 = 27 k3 + 54k 2 + 36k + 8 = 9(3k3 + 6k 2 + 4k) + 8
da pri deljenju z 9 ostanek 8.
To pomeni, da lahko dajo števila x 3 , y3 in z3 pri deljenju z 9 ostanke
0, 1 ali 8. Zdaj imamo 27 možnih kombinacij glede na ostanke posameznih
števil x3 , y 3 in z3. Le preverimo vse, dobimo , da ima število x3 + y3 + z3
lahko pri deljenju z 9 ostanek 0, 1, 2, 3, 6, 7 ali 8. To pomen i, da tistih
števil, ki dajo pri deljenju z 9 ostanek 4 ali 5, ni mogoče izraziti kot vsoto
treh kubov. Seveda je takih števil neskončno.
Se več informacij o ostankih dobimo takrat, ko imamo opravka s prašte-
viii. Pri deljenju s 6 lahko liho število daje ostanek 1, 3 ali 5. Le pa imamo
praštevilo različno od 3, potem pri deljenju s 6 tudi ostanek 3 ni možen. Le
bi namreč imeli p = 6k + 3 = 3(2k + 1) , bi število p ne bilo praštevilo . Ta
razmislek nam bo prišel prav v naslednjem zgledu.
Zgled 4. Dokaži, da je število p2 - 1 deljivo s 24 za vsako praštevilo p,
ki je večje od 4:
1. možnost Stevilo p je oblike 6k + 1. Tedaj je
p2 _ 1 = 36k2 + 12k = 12k(3k + 1).
Torej je število p2 - 1 deljivo z 12. Hitro se lahko prepričate , da je eno od
števil k in 3k + 1 sodo , drugo pa liho, kar pomeni, da je število k(3k + 1)
deljivo z 2, število p2 - 1 pa s 24.
2. možnost . 5tevilo p je oblike 6k + 5.
Tedaj je
p2 _ 1 = 36k2 + 60k + 24 = 12(3k2 + 5k + 2) .
Hitro se lahko prepričate , da je število 3k 2 + 5k + 2 vedno sodo, zato je
število p2 - 1 deljivo s 24.
Za konec pa še en zgled s praštevili .
Zgled 5. P a  vsa taka praJteviila p, da je 1 4 ~ ~  + 1 pra~tcvilo. 
Naj bo p # 3. K u  je p praztevilo, ni deljivo s 3, zato daje pri deljenju s 
3 ostantk bodisi 1 bodisi 2. 
1. mdnost. Stevilo p je oblikt 3k + 1. 
Tedaj jt 3ttviio 
in zato ni pra3ttvilo. 
2. mdnost. Stmilo p je oblike 3k + 2. 
T d a j  ja 3fttvib 
in zato ni pr&tevilo. ct je p = 3, je  + 1 = 127. Z malee vztrajnoati re 
lahko sami prepribte, da je 127 praawila. 
Borut zalar