D. I. Yunusova qiziqarli matematika


Download 101.83 Kb.
Pdf ko'rish
bet1/19
Sana24.05.2018
Hajmi101.83 Kb.
  1   2   3   4   5   6   7   8   9   ...   19
31617

0 ‘ZBEKIST0N  RESPUBLIKASI  OLIY VA  0 ‘RTA 
MAXSUS  TA’LIM  VAZIRLIGI
0 ‘RTA MAXSUS,  KASB-HUNAR TA’LIMI  MARKAZI
A.  S.  Yunusov,  S. I. Afonina,  M. A. Berdiqulov, 
D.  I.  Yunusova
QIZIQARLI  MATEMATIKA 
VA  OLIMPIADA 
MASALALARI
A kadem ik  litsey,  kasb-hunar kollejlari  uchun
о ‘quv  qo ‘llanma
,,0 ‘Q lT U V C H r   NASHRIYOT-MATBAA  IJODIY UYI 
TOSHKENT -  2007
www.ziyouz.com kutubxonasi

ББК  22.1  z  722
T a q r i z c  h i l a r :
Q.   M.   IBODULLAYEV —  0 ‘z M U  qoshidagi  S.  X.  Sirojiddinov  nom li 
a k a d e m ik   litsey direktori,  fiz ik a -m a tem atik a   fanlari  n o m z o d i;
Y.E.  NIZAMOVA  —  Tqtisodga  ix tiso sla sh g a n   R e s p u b l i k a   litseyi 
direktori,  oliy  toifali  m a te m a tik a   o ‘qit.uvchisi;
D.  DAYLETOV  —  N iz o m iy   no m id ag i  T D P U   „ M a t e m a t i k a   va  uni 
o ‘qitish  m e to d ik a s i“  kafedrasi  o ‘qituvchisi.
Fizika-m atem atika fanlari  nom zodi,  dotsent D.  I. Y U N U S O V A  tahriri 
ostida.
U s h b u   o ‘quv  q o ‘l l a n m a   a k a d e m ik   litsey,  k a s b - h u n a r   kollejlari 
o ‘q u v c h i l a r i   va  o ‘q i t u v c h i l a r i ,   o liy   o ‘q uv  y u r t l a r i n i n g   t a l a b a l a r i ,  
m a te m a tik a  faniga qiziquvchilar u c h u n   yozilgan.
0 ‘quv  q o i l a n m a d a   m a te m a t i k a n i n g   turli  ta d b iq larig a,  qiziqarli 
m a te m a tik a g a  va olim piada  masalalariga  oid  m ateriallar berilgan.
у 4306020500-119  Ont’
iv buwrt  °007
Y  353(04)-2007 
Q3t 1У
 bUyrt'  2007
IS B N   9 7 8 -9 9 4 3 -0 2 -1 0 8 -2  
©  , , 0 ‘qituvchi"  NMI U,   2007
www.ziyouz.com kutubxonasi

SO‘ZBOSHI
Agar  o'quvchi,  hech  b o 'lm ag an d a  bir  marta  o 'zi  mustaqil 
ravishda birorta  matematik masalani hal qilsa,  u albatta,  unutilmas 
hayajonli damlarni boshidan kechiradi vag'alaba  nashidasini suradi.
Bunday „kichik" g'alabalar,  ayniqsa bolalik chog'ida yuz bersa, 
inson bu  onlarni  hayotining oxirigacha xotirasida saqlab  qoladi.
0
‘quvchilar ustozlari  bilan birgalikda birorta qiziqarli masalani 
hal etib, uni to ‘liq o'zlashtirib olganlaridan so‘ng,  mustaqil  ravishda 
masala  yechish,  m a tem a tik a  bilan  shug'ullanish  xuddi  tennis 
o ‘ynash  yoki  futbol  o £ynash  kabi  maroqli  b o iis h i  mumkinligini 
anglashlari  m um kin.  Natijada,  ajab  emas,  ular  m atem atika  bilan 
butun  u m r  do'stlashib  qolishsa,  yoki  hayotlarida  matematikani 
o'zlariga  kasb  qilib  olishsa,  yoki  m atem atika  ko‘p  islilatiladigan 
kasb  egasi  bo'lishsa!
Ushbu o'quv q o iian m an in g  qiziqarli  matematika va olimpiada 
masalalari  deb  atalishi  bejiz  emas.  M atem atika  fani,  B.  Paskal 
aytganidek,  o 'ta  jiddiy fan b o ‘lib,  uni  ozgina  bo'lsa  h am  qiziqarli 
qilish  imkoniyatlarini  q o 'ld an   boy bermaslik zarur.  H ozirda  aka- 
dem ik  litsey  o 'q u v   rejasiga  shu  n o m   bilan  ataluvchi  predm et 
kiritilganligi bunday o ‘quv qo'llanm ani yozish zaruriyatini  keltirib 
chiqardi.
Albatta,  qiziqarli  m a tem a tik a d an   b un d an   oldin  ham   ju d a 
ko'plab  kitoblar  yozilgan.  Ayniqsa  yosh  m atematiklarni  tarbiya- 
lashda A. A ’zamov va  B.  Haydarovlarning „Matematika sayyorasi“ , 
Y.  Perelm anning  „Qiziqarli  m atem atika",  M.  G ardnerning  „ М а ­
т ем атически е  чудеса  и  т а й н ы "   va  h.k.  kitoblarning  ahamiyati 
katta.
U shbu  o ‘quv  q o 'll a n m a   h a m   yoshlarning  m a te m a tik a g a  
qiziqishlarini uyg'otishga ozgina bo'lsa ham  xizmat qilsa,  mualliflar 
o 'z   maqsadlariga  erishgan  b o i a r   edilar.
Mualliflar ushbu  q o 'llan m an i  nashrga tayyorlashda  qimmatli 
m a slah atlarin i  ay a m a g a n   O 'z M U   d o tsen ti  N.  A bdullayevga, 
T D P U   dotsenti  A.  Qulmatovga  va  professor  N.  Sherboyevga  o 'z  
minnatdorchiliklarini  bildiradilar.
3
www.ziyouz.com kutubxonasi

I  BOB.  SONLAR  NAZARIYASI DAN  QISQACHA 
M A’LUM OT
l-§ .  NATURAL  SONLAR
M a ’lumki.  sanash  uchun  1,  2,  ...  natural  sonlar  ishlatiladi. 
/V={1,  2 ,...}  to 'p lam   esa  natural sonlar to'plami deyiladi.
Agar a va b natural  sonlar uchun  shunday q natural son topilib, 
a  =  b ■
  q  shart  bajarilsa,  u  holda  a  natural  son  b  natural  songa 
b o ‘lin a d ideymiz va  a lb   ko'rinishda  bclgilaymiz.  Faqat  ikkita  har 
xil  natural bo'luvchiga ega bo'lgan  natural  son  tub son deyiladi.  Bu 
t a ’rifdan  ko'rinadiki,  masalan,  2,  3 , 5   sonlari  tub  sonlar  bo'lib,
1,  4,  6  sonlari  tub  sonlar  emas.  H aqiqatan  ham ,  2,  3,  5  sonlari 
faqat  1  ga  va  o'ziga  bo'linadi;  1  esa  faqat  o'ziga  bo'linadi;  4  ning 
b a rc h a   n atu ra l  b o 'iu v ch ilari  1 , 2 , 4 ;   6  ning  b a rc h a   n atural 
bo'iuvchilari  1,  2,  3,  6  lardan  iborat.  Agar  natural  sonning  turli 
natural  bo'luvchilarining  soni  3  va  undan  ortiq  bo'lsa,  bunday 
natural  son  m urakkab  natural  son  deyiladi.  Demak,  4,  6  sonlari 
murakkab natural sonlar,  1  esa  na  tub,  na  murakkab son  ekan.  1  ni 
ko'paytirish  amaliga  nisbatan  neytral element deymiz.
S h u n d a y   qilib,  h ar  bir  n atu ra l  son  yoki  tu b   son,  yoki 
murakkab  son,  yoki  1  ga  teng  bo'Iar  ekan.
T e o r e m a .   Deylik,  a  —  birdan fa rqli  natural son  bo ‘Isin.  U 
holda  uning  birdan  katta  eng kichik  natural  bo ‘luvehisi  tub  sondir.
I s b o t .   H aqiqatan  ham ,  agar  a im   bo'lib,  m  —  murakkab 
son  bo'lsa,  m  ning p bo'luvchisi  bo'lib,  p <   m  va  
ф
  1 .  U  holda 
a \m   va  a l p   shartlardan  a lp   munosabat  kelib  chiqadi.  Bu  esa 
m  —  birdan  katta  eng  kichik  natural  bo'luvchi  degan  shartga zid, 
dem ak,  m  —  tub  son.
Xulosa.  Bu  teorem adan  agar  a  murakkab  son  bo'lsa,  a  ning 
albatta  bitta  4 a   dan  katta b o 'lm ag an  tub  bo'luvchisi  bor bo'lishi 
kelib  chiqadi.
H aqiqatan  ham,  a  -   murakkab  son,  p esa  uning birdan  katta 
eng  kichik tub bo'luvchisi  bo'lsin.  U  holda  shunday q son  topilib,
a  =  pq  >  p 2  yoki  p  <  4 a   kelib  chiqadi.
4
www.ziyouz.com kutubxonasi

Demak,  birdan  katta  a  natural  son  tub  son  bo'lishi  uchun 
p  < 4 a   tub  sonlarning  birortasiga  ham   bo'linmasligi  yetarli.
Masalan,  101  tub  son  bo'lishi  yoki  b o lm aslig in i  aniqlash 
uchun  uni  VlOl  dan   kichik  bo'lgan  2,  3,  5,  7  tub  sonlarga bo'lib 
ko'ramiz.  101  bu  sonlarning birortasiga  ham bo'linmaydi,  demak, 
101
  tub  son  ekan.
E v k l i d   t e o r e m a s i .   Tub  sonlar  to ‘plam i  cheksiz  to ‘p - 
lamdir.

s b  о t .  H a q i q a t a n   h a m ,   b a r c h a   tu b   s o n l a r   t o ' p l a m i  
P  -   {p^ p 2,..., p k }  chekli  to 'p la m d a n   iborat  bo'lsin.  U  holda 
Pi  • Pi  • ••• ■
  Pk  4  *  natural  son  P to 'p la m g a   tegishli  bo'lm agan  tub 
son  bo'lishi  ko'rinib  turibdi.  Chunki  bu  son  p \ ,p 2,...,p k  tub 
sonlarning birortasiga  ham   bo'linmaydi.
M isol.  397,  401,  403,  409,  677,  697,  701  sonlaridan  biri 
murakkab  son  bo'lishini  ko'rsating.
Matematik induksiya nietodi. Agar bizga n natural songa bog'liq 
biror bir  F(n)  tasdiq  berilgan  bo'lsa,  ko'p  hollarda  bu  tasdiqning 
isboti  m atem atik  induksiya  metodi  deb  yuritiladigan  usulda  isbot 
qilinadi.  Shu  usulga qisqacha to'xtalib o'tamiz.
Faraz  qilaylik,  n  ( n >   p ,  p  —  tayinlangan)  natural  son  va 
F(n)  tasdiq  berilgan  bo'lsin.
M atem atik  induksiya  metodi  bilan  isbot  qilish  quyidagi  uch 
bosqichdan  iborat.
Induksiya  bazisi. 
F(n)  tasdiq  n  =  p  u ch u n  to 'g 'ri  bo'lishi 
isbot  qilingan  bo'lsin.
Induksiya farazi.  F{k)  tasdiq  barch a  h  >  к  >  p  natural  sonlar 
uch u n   to 'g 'ri  deb  faraz  qilinadi.
Yakuniy  bosqich.  F(k)  tasdiqning  n  dan  kichik  barcha  к  lar 
uchun  to'g'riiigidan  n  uchun  ham   to 'g 'ri  bo'lishi  keltirib  chiqari- 
ladi.
M isol.  H ar  qanday  n  natural  son  uch u n
I 2  +  22  +  32  +  . . .   +  n2  =  я^ г+1| -2—-1--  tenglik o'rinli  ekanligini 
isbotlang.
Yechish.  1. n -   1  bo'lganda,  I2 =  -^i+n(2+-1),  1  =  1  .  Ya’ni tenglik
О
o'rinli.
5
www.ziyouz.com kutubxonasi

2
.  n - k   uchun  I 2  +  22+  ...  +  к2  =  к{к+]^ 2к+)2  tenglik  o'rinli
deb  faraz  qilamiz.
3.  n --k + 1  u ch u n  tenglik o'rinli  ekanligini  isbotlaymiz:
i 2+22+ ...+  ^2+(jt+i) 2  =
Farazga ko'ra,
J2  +  22+  ...  + k 2  +  (k +   l ) 2  = M ^ l I i p A l l ) + (/t+ 1)2_
U
 
h o l d a  
k(k+\)  (2k+\)
  + ( A .+  1  ) 2   =  
( k
  +   l ) f * l i | ± l >   +  
k
  +   i j   =
_  
n
 
n  
2k2 +k+bk+6  _   (k+\)(2k2 + 7k+6)
-
( K   +   [ > 
6
 
6
2k 2 +  7k + 6  kvadrat  uchhadni  ko'paytuvchilarga  ajratamiz: 
2 k 2 +  7 k  + 6 =  (k +  2)  (2  к +  3).
Bundan
12
+ 2з + . . . + а 2+ ( л + i )3  =  .tffia t i a a g g i a   y0ki
kelib  chiqadi.  Demak,  berilgan  tenglik  har  qanday  natural  son 
uchun  o'rinli  ekan.
2-  §.  ARIFM ETI KAN IN G  ASOSIY  TEOREMASI
T e o r e m a .   Har qanday natural son yoki birga  teng, yo ki tub 
son, yo ki ко ‘paytuvchilari tartibigacha aniq/ikda yagona usulda  tub 
sonlar ко ‘paytmasiga yoyiladi.
I s b o t .   M atem atik induksiya  metodi  bilan  isbot  qilamiz.
1  -  b о s q i с h  .  Induksiya bazisi  n  -   1  bo'lsin.  U  holda  teore­
m a isbot b o ‘ldi.
2 -  b o s q i c h .   Har qanday  1  <  к  <  n  uchun  teorem a  to'g'ri 
bo'lsin.  Y a’ni  /:yoki  1  ga teng,  yoki  tub  son,  yoki  ko'paytuvchilari 
tartibigacha yagona usulda tub sonlar ko'pavtmasiga  yoyiladi.
3 -  b o s q i c h .   Agar  n  tub  son  bo'lsa,  isbot  tam om .  Agar 
n  murakkab  son  bo'lsa,  u  holda  1  <  a  <  n  va  1  <  b  <  n  shartlarni 
q a n o a t la n t ir a d ig a n   s h u n d a y   n a tu ra l  so n la r  m avjud  b o 'lib , 
n  =  a  ■
  b  induksiya  faraziga  ko'ra  a,  b  lar tub sonlar yoki  k o 'p ay ­
tu v c h ilari  ta rtib ig ach a  a n iq lik d a   y agona  usulda  tub  s o n lar
6
www.ziyouz.com kutubxonasi

ko'paytm asiga  yoyiladi.  Agar  a,  b  lar  tub  sonlar  bo'lsa,  isbot 
tu g a y d i.  Aks  h o ld a  
a  =  p l  -...  p k ,  b  =  p k+x  ■
 

 p m  b o 'l i b ,  
n  =  p x  ■... ■
  p k  ■
  p k+1  •... • p m  .  Endi  bu  yoyilma  yagona  ekanligini 
isbot  qilamiz.  Faraz  qilaylik,  n  =  q {  ■... • qs  tenglik  n  ning  boshqa 
yoyilmasi  bo'lsin.  Bundan  n - p x - ... ■
  p m  =  qt  • •  qs  kelib  ch iqa­
di.  Bu  tenglikning  ikkala tom onini  p x  ga bo'laylik.  U  holda  p x  va 
qx,...,q s  lar tub sonlar bo'lganligi  uchun  qx,...,q s  lardan biri  p x  ga 
teng. Aniqlik uchun  p x  =  q x  bo'lsin.  U holda  p 2  ■... •  p m  =  q2  ■
 ■■■ ■
 Qs ■
 
Bu  yoyilmalar  n  dan  kichik  sonlarning  yoyilmalari  bo'lganligi 
uch u n ,  induksiya  faraziga  ko'ra,  ko'paytuvchilari  tartibigacha 
yagona.
n  natural  sonni  tub  ko'paytuvchilarga  yoyganimizda, p x  tub 
son  yoyilmada  a ,  m arta,  p 2  tub  son  a 2  m arta  va  hokazo,  p m
tub  son  a m  m arta  uchrasin.  U  holda 
n  = 
■... •  p “ 'n  ifoda  n 
natural sonning kanonik yoyilmasi deyiladi.  Kanonik yoyilmada tub 
ko'paytuvchilarni o'sish tartibidajoylashtirsak, yoyilma yagona bo'li­
shi  ravshan.
3- §.  SONLI  FUNKSIYALAR
t(w)  va  a ( « )   funksiyalar.  х(л)  orqali  n  natural  sonning b a r­
cha  natural  bo'iuvchilari  sonini,  a(n )  orqali  n  natural  sonning 
barcha  natural  bo'iuvchilari  yig'indisini  belgilaymiz.
Masalan,  6  ning  natural  bo'iuvchilari  1 ,2 ,  3 , 6   sonlardan 
iborat.  D em ak,  x(6 )  =  4  va  0 (6 )  =  1  +  2  +  3  +  6  =  12.
Agar  n  =  p * 1  ■... • 
tenglik  n  natural  sonning  tub  bo'luv- 
chilarga  kanonik yoyilmasi bo'lsa,  u  holda
x{n)  =  (a,  +  1)  -...-(a,,,  +  1).
Haqiqatan  h am ,  n  ning  har  qanday  q  bo'luvchisi 
d  =  p f 1  ■■■■■pll k , 
1
  <  P[  <  a , , 
l < p 2 < a 2 ,..., 
1
  <  p^  <  a k
ko'rinishda 
bo'lishi 
ravshan. 
p, 
ni 
(a,  + 1)  usulda,  p 2  ni 
( a ,   + 1)  usulda  va  h.k.,  p*  ni  ( a k  + 1)  usulda  tanlab  olishimiz 
m um kin  bo'lgani  uchun  р ,,...,р А  larni  (a,  +  1) ■... • (a*  +  1)  ta 
usulda tanlash  imkoniyati  bor.  Natural  son barcha  natural bo'luv- 
chilarining  yig'indisi
7
www.ziyouz.com kutubxonasi

2 > Р '  
-  P i 2 
p [ k
  =  (1  + 
P\
  + 
+  p k
  +  ...+  
p a
k k )
1 —
 P A: —cx A-
ga tengligini  ko'rish  qiyin  emas.  U  holda
1
 
ot(- + l

CX; 
1 “ 
Pj 
1
  +  Pi  + ... +  />,-'=  ——!-----
1  -  
Pi
formulaga asosan

ai-fl 

a^-rl 

cu+1
1 - 
1 - p2 
I - pk
formula  hosil qilinadi.
Agar  a(n)  =  2n  tenglik  bajarilsa,  u  holda  n  soni  m ukam m al 
son  deyiladi.
Masalan,  6 va 28 sonlari  mukammal sonlardir.  Haqiqatan  ham,
!-22  1 - 32
a ^  = jd ' T
r   =  3 ' 4  =  12  =  2 ' 6 ’
1 - 23  1 - I 2 
a(28)  =  - L - i -  • у - i -   =  7  • 8  =  56  =  2 • 28.
Misol.  6 ,  28,  496,  8128,  33550336,  8589869056,  137438691328 
sonlari  birinchi  uchraydigan  yettita  m ukam m al  sondir.
M isol.  496  mukam m al  bo'lishini  tekshirib  ko‘ring.
Agar  o(a)  =  b,  a(b)  -   a  o'rinli  bo'lsa,  a  va  b  sonlari  do'si 
sonlar  deyiladi.
Masalan,  220  va  284;  18416  va  17246  sonlari  do'st  sonlardir. 
Quyida  100 000 gacha bo'lgan do'st sonlar jadvalini  keltiramiz:
220 =  22 -  5 -11 
284 =  22 •71
1 184 = 25 •37 
1210 =  2 - 5 - l l 2
2620 = 22 -  5 -  131 
2924 =  22 -  17-43
5020 = 23 -  5  -  251 
5564 =  22 •  13  ■
  107
6232 =  23 ■
  19 -41 
6368  =  25 -  199
10744 -   23 -  17 -79 
10856  =  23 -  23 -  59
8
www.ziyouz.com kutubxonasi

12285  =  З3 •  5 •  7•  13 
17296 =  24 - 2 3 - 4 7
14595--=  3 - 5 - 7  -  139 
184 1 6 = 24 •  1151
63020 =  22 •  5  •  23 •  137
76084 =  22 •  23■827 
66992 = 24 •53 •  79 
71145 = 39 -  5-  17-31 
87633  =  З2 •  7 -  13-  107 
88730 = 2 - 5 -   19-467
66928  =  24 - 4 7 - 8 9  
67095  =  33 -  5-  7 -  71 
69615  = 32-5-7-13-17 
79750 = 2 - 5 4 1 - 2 9
Sonning butun  qismi.  Sonning o ‘zidan  oshmaydigan eng katta 
butun son,  sonning butun qismi deyiladi va x haqiqiy sonning butun 
qismi  [xj  orqali  belgilanadi.
Masalan,  5,2  sonning  butun  qismi  5  ga;  -   5,2  ning  butun 
qismi esa -  6 ga  teng.  Berilgan  sondan  shu  sonning butun  qismini 
ayirsak,  hosil  b o i g a n   son  berilgan  sonning  kasr  qismi  deyiladi.
Masalan,  5,2 -   5  = 0,2; 
-   5,2 -   ( -  6 )  = 0,8.
у   =  \x)  funksiya  ixtiyoriy  haqiqiy  son  u ch u n   aniqlangan.
M asalan ,  [n]  =  3 , 
[e]  =  2  , 
[4 l}  =  2 ,  
[V6 ]  =  2  ,
Bu  funksiya    ning  b u tu n   qiymatlarida  uzilishlarga  ega  (1.1- 
chizma).
f--~r]  =  - 4   va  h.  k.
э

*■
О
1 .1 -  chizm a.
я!  ning  kanonik yoyilmasi.  n \ -   2tt|  • 3“ 2  •... • 
.  p m—  n  dan 
kichik  b o ig a n   birinchi  tub  son.
www.ziyouz.com kutubxonasi

M isol.  50!  nechta  nol  bilan  tugashini  toping. 
5 0 ! _ 2 ai  .  3a*  . 

4 7
am  bo'lib,
Demak,  50!  12  ta  nol  bilan  tugar  ekan,  chunki  u  (5 -2)i2  ga
b o iin a d i,  lekin  (5 -2)13ga  bo'linmaydi.  100!,  2 00!  lar  nechta  nol 
bilan  tugashini  hisoblab  k o ‘ring.
4-§.  QOLDIQLI  BO‘LISlI  HAQIDAGI  TEOREMA
T e o r e m a .   Agar a butun son  va m natural son berilgan bo 'Isa, 
shunday  q,  r  butun  sonlar  m avjud  bo ‘lib,  a  =  mq + r,  0  <  r  <  m 
munosabatlar о ‘rinli  bo 'ladi.
H aqiqatan  ham ,  agar  a  -   0  bo'lsa,  0  =  m ■
 0 + 0  ■
Agar,  a  =  1  bo'lsa,  m  =  1  b o 'lg a n d a   1  =  1 1 + 0 ;   m  >  1
b o ‘lganda  1  =  m  ■
 0 +  1  bo'lib,  teorema  o'rinli.
Endi  ixtiyoriy a  natural  son  uchun  teorema o'rinli  bo'lsin  deb 
faraz  qilamiz.  U  holda 
shunday  q,  r  butun  sonlar  mavjudki, 
a  =  mq  +  r . Q < r < m   m u n o s a b a t   o ' r i n l i   b o ' l s i n .   B u n d a n  
a +  \  =  mq  + r + \  tenglikni  hosil  qilamiz  va  r +  \ < m   bo'lsa, 
q,  r +  1  s o n la r   t e o r e m a   s h a r tl a r in i  q a n o a t l a n t i r a d i .   A g ar
r  +  1  >  m 
b o ' l s a ,  
a  +  1  =  mq  +  r +  1  =  mq  + m  + (r +  j  -  m)  =
-   m(q  +  1)  + (r +  1  -  /и);  q  +  1  =  q 1,  r +  1  =  r  belgi lash lar  kirit-
sak,  a +  1  =  mq ’ +  r \   0  <  /•'  <  m  m u n o sab atlar  o'rinli  bo'ladi. 
Shunday  qilib.  har  qanday  a  uchun  teorem a  to'g'riligidan  a +  1 
uchun  ham   teorema to'g'ri  bo'lishini  isbot  qildik.  Demak, barcha 
natural  sonlar  va  0  butun  son  uchun  teorema  to'g'ri  ekan.
www.ziyouz.com kutubxonasi

Endi  a  <  0 bo'lsin.  U  holda -  a  >  0  bo'lib,  shunday q,  /-butun 
so n la r  m avjud  b o ‘lib, -  a  =  mq  +  ,  0  <  r  <  m  s h a rtla r  o 'rin li 
bo'ladi.  U  holda  a  =  m( - q)   -   r  ifodani  hosil  qilamiz,  bundan 
a  =  m (-q   +  1)  +  ( / / / -   r)  b o ' l i b ,   0  <  r  <  m  b o ' l g a n i   u c h u n
0  <  m  -  r  <  m  bo'ladi.  D em ak,  a  <  0  b u tu n   son  u ch u n   ham  
teorema to'g'ri  ekan.
5- §.  EVKLID  ALGORITMI
Agar  a  butun  son  va  b  natural  son  berilgan  bo'lsa,  u  holda 
qoldiqli  bo'lish  haqidagi  teoremaga  ko 'ra  shunday  q0,  /-,  butun
sonlar  mavjudki,  a  =  bq0  +  /,  va  0  < 
<  b  munosabatlar  o'rinli 
bo'ladi.  Ifodadagi  bo'luvchi  va  qoldiq  q0,  rl  u ch u n   teoremani 
y a n a  
q o ' l l a s a k ,  
s h u n d a y  
q x,  r2 
s o n l a r  
t o p i l i b ,  
b  =  r^q{  + ry,  0  <  r2  < 
1
1
  munosabatlar o'rinli bo'ladi.  Bujarayonni 
qoldiq  nolga  teng bo'lgunga  qadar davom  ettiramiz:
a  -   bq0  +  t], 
0
  <  r(  <  b ;
b  =  r,<7,  + r2, 
0
  <  r2  <  >\;
t ] = r 2q2 +r3, 
0
  <  i\  <  r2 ;
r„-2  =  ';,-!r,i,  0  ^  n,  <  V i ;
Гц- 1  —
  hiЯп 
hir\ >  1 n+\  ~  ® •
Bunday ketma-ket  bo'lish jarayoni  Evklid algoritmi deb ataladi.
M isol.  67  va  23  conlari  uchun  Evklid  algoritmini  tuzamiz:
67  =  2 3 - 2   +  21;
23  =  21-1  +  2;
21 
= 2 - 1 0 + 1;

=  1  •  2  +  0 .
Bu  jarayonda  qoldiqlarning  m o n o ton   kamayishidan  ko'ri- 
nadiki,  a  butun  son  va  b  natural  sonlar  uchun  Evklid  algoritmi 
chekli  qadam dan  so'ng  to'xtaydi.
Endi  Evklid  algoritmining  b a ’zi  bir  tadbiqlari  bilan  tanishib 
chiqamiz.
Agar  a  butun  son  va  b  natural  son  berilgan  bo'lsa,  qoldiqli 
bo'lish  haqidagi  teoremaga  asosan  a  =  bq +  r,  0  <  r  <  b .  U  holda 
(a, b)  =  (b, r ) .  Y a’ni,  a va  b laming eng  katta  um um iy boiuvchisi
www.ziyouz.com kutubxonasi

b  va  r  larning  eng  katta  um um iy  boMuvchisiga  teng  (isbot  qilib 
k o ‘ring).  Bu  tasdiqni  Evklid  algoritmiga  qo'llasak,  (a,b)  =  rtJ 
ekanligi  kelib  chiqadi.
M isol.  1643  va  3763  sonlarining  eng  katta  umum iy  bo'luv- 
chisini  va  eng  kichik  um um iy  karralisini  Evklid  algoritmidan 
foydalanib  topaylik:
Bu  s o n l a r n i n g   u m u m i y   k a r r a lis in i  t o p i s h   u c h u n   esa 
\a,b\  ■
  (a,b)  =  a  ■
  b  formuladan  foydalanamiz:


Download 101.83 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9   ...   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling