4-маoруза. Бутун сонларга ъалыасида бщлиш ва унинг асосий ъоссалари р е ж а

3-ТЕОРЕМА. Агар " a,b Î Z учун a=bq+r тенглик щринга эга бщлса, (a,b)=(b,r) бунда a,b,r лар 0 дан фарыли бутун сонлар.
ИСБОТ. S сони a ва b ларнинг ихтиурий умумий бщлувчиси бщлсин, у ъолда a=bq+r, r=a-bq тенгликдан муносабат келиб чиыади. Бундан S сони b ва r ларнинг умумий бщлувчиси эканлиги келиб чиыади, аксинча, айтайлик, d , b ва r ларнинг ихтиёрий умумий бщлувчиси бщлсин, бунда a=bq+r тенгликдан Þ яoни d a ва b ларнинг умумий бщлувчиси эканлиги келиб чиыади. Булардан теоремани тщьри эканлиги келиб чиыади.


4-ТЕОРЕМА. (Евклид алгоритми). Агар " a,b Î Z лар учун
(1)
тенгликлар щринга эга бщлса (a,b)=r_n -0 дан фарыли охирги ыолдиыыа экуб бщлади.
ИСБОТ. (1) нинг 1-тенглигида 3-теоремани эoтиборга олсак, (a,b)=(b,r) 2-тенгликдан эса (b₁r₁)=(r₁r₂) ... (r_n-2, r_n-1)=(r_n-1, r_n)
(r_n-1, r_n) =r_n .
Булардан ( a,b)=(b₁r₁)=(r₁,r₂)=...=(r_n-1, r_n)=r_n га эга бщламиз.
Мисол. a =7975 ва 2585 сонларини ЭКУБини топинг
7975=3 × 2585+220
2585=11 × 220+165
220 = 1 × 165 + 55
165 = 3 × 55
бундан (7975,2585)=55 .
5-ТЕОРЕМА. Агар (a,a₂,...,a_n)=d, (d,a_n)=d Þ (a,a₂,...,a_n)=d бщлади.
ИСБОТ. Теорема шартига асосан
бу эса ЭКУБни 1) шарти. Айтайлик d a,a₂,...,a_n ларнинг ихтиёрий умумий бщлувчиси бщлсин.
Хусусан. d₁ d ,a_n ларни хам умумий булувчиси бщлади.
(d ,a_n )=d дан келиб чиыади. Бу эса ЭКУБ нинг 2-шарти. Демак, (a,a₂,...,a_n)= d тенглик щринга эга.
НАТИЖА. Агар (a,a₂)=d₁ (d₁,d₃)=d₂ ... (d_n-2,a_n)=d_n-1 бщлса, (a,a₂,...,a_n)=d_n-1 бщлади.
МИСОЛ. (988,2014, 42598, 6729) ни топинг.
(988, 2014)=38 (38, 42 598)=38
(38, 6729)=1 Демак, (98, 2014, 42598, 6729)=1
Бир неча сонларнинг ЭКУБи ыуйидаги асосий хоссаларга эга.
5-ТЕОРЕМА Бир неча сонларнинг ЭКУБи уларнинг мусбат умумий булувчиларининг энг каттасига тенг.
Айтайлик, (a,a₂,...,a_n)= d ва d >0 a,a₂,...,a_n cонларнинг мусбат умумий бщлувчиларининг энг каттаси бщлсин, бу ъолда
2-томондан d умумий бщлувчиларнинг каттаси бщлгани сабабли
d £ d , Булардан d=d
6-ТЕОРЕМА. Агар (a,b) =d бщлса, k¹0 (ak,bk)=kd бщлади.
ИСБОТ. (1) нинг ъар бир тенглигини, хар икки томонини k га кщпайтирсак.
(2)
Бундан (ak,bk)=r_nkÞ (ak,bk)=k(a,b) .