Бүтін санды жай сандарға жіктеу арқылы ЕҮОБ мен ЕКОЕ табу әдісін тұжырымда

Жай сандар жиынының шексіздігі туралы теореманын дәлелде

1 аныќтама. р натурал санын жай сан дейді, егер ол бірден ‰лкен болса жєне 1 мен р -дан µзгеше бµлгіштері болмаса.

Жай сандардыњ ішінде тек бір ѓана ж±п сан 2 бар

3.Жай сандардыњ шексіздігі

Теорема (Евклидтіњ) . Жай сандар жиыны шексіз.

Дєлелдеу (ќарсы жориыќ). Жай сандар жиыны шекті болсын дейік: Олар р₁=2, р₂, …,р_k сандары болсын, м±ндаѓы р_k ењ ‰лкен жай сан болсын.

Осы берілген жай сандардыњ кµбейтіндісін ќ±райыќ жєне n = р₁ р₂ …р_k +1 т‰ріндегі натурал санды ќарастырайыќ. n > р_k болѓандыќтан n саны ќ±рама сан болады. Олай болса, ол бір жай санѓа бµлінеді. Біраќ жору бойынша барлыќ жай сандар { р₁, р_2, …,р_k } жиынына тиісті. Олай болса n саны р₁, р_2, …,р_k сандарыныњ біреуіне бµлінеді, дєлірек айтсаќ р₁ санына бµлінсін. р₁ р₂ …р_k кµбейтіндісі де р₁ санына бµлінеді жєне n = р₁ р₂ …р_k +1 болѓандыќтан 1 саны да р₁ санына бµлінуі керек. Біраќ б±л м‰мкін емес, µйткені 1< р₁. Осы алынѓан ќайшылыќ теореманы дєлелдейді. #

4.Эратосфен торы. Грек математигі Эратосфен (біздіњ эрамызѓа дейінгі III ѓ.) кезкелген 1,2,3,…, n натурал сандар ќатарынан жай сандарды бµліктеу єдісін ±сынѓан. Б±л єдіс бойынша 1,2,3,…, n сандарыныњ ішінен єуелі 1 саны сызылады, сосын 2-ніњ µзінен басќа 2-ге еселі сандар сызылады, сосын 3-тіњ µзінен басќа 3-ге еселі сандар сызылады жєне т.т.

Сонымен р₁=2, р₂= 3 , р₃= 5, …, р_k £ жай сандарына еселі барлыќ сандарды сызу ќажет.

Бүтін санды жай сандарға жіктеу арқылы ЕҮОБ мен ЕКОЕ табу әдісін тұжырымда

Қандай а санының болса да кем дегенде екі бөлгіші болады — бір саны және сол санның өзі, бұл бөлгіштерді біз а санының меншіксіз бөлгіштері деп атайтын боламыз. а санының меншіксіз бөлгіштерінен өзге бөлгіштерін меншікті бөлгішітері деп атайтын боламыз.

Мысалы, 144 санының меншіксіз белгіштерінен өзге меншікті 13 бөлгіші бар, олар: 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72.

Айталық бутін а мен b екі сан берілсін дейік. а мсн b сандарының әрқайсысын да бөлетін δ санын олардың ортақ бөлгіші деп атайды. а мен b сандарының әркайсысының бөлгіштерінің саны шектеулі, сондықтан а мен b-нін ортақ белгіштерінің саны да шектеулі. Егер δ₁, δ₂,..., δ_m сандары а мен b-нің ортақ бөлгіштері болып табылса, онда олардың ең үлкенін а мен b-нің, ең үлкен ортақ бөлгіші деп атайды да былай белгілейді: (а, Ь)=d. Мысалы, 48 бен 132 сандарының ортақ бөлгіштері 1, 2, 3, 4, 6, 12 болса, онда ең үлкен ортақ бөлгіш

d = (48, 132) = 12

болады. Егер а мен b сандарының ең үлкен ортақ белгіші (а, Ь)=1-ге тең болса, оларды өз ара жай сандар деп атайды.

3-теорема. Бүтін сандар сақинасына қарасты кез келген екі санның осы сақинаға енетін және де жалғыз тәсілмен анықталатын ең үлкен ортақ бөлгіші болады.

Екі санның ең үлкен ортақ бөлгішін табу үшін қазірге дейін Евклид көрсеткен жалғыз ғана әдіс бар. Айталық бүтін а мен b сандарының ең үлкен ортақ бөлгішін табу керек болсын. Анықтық үшін а≥b деп ұйғаралық. Егер а саны b-ге қалдықсыз бөлінсе, онда b саны ізделінді ең үлкен ортақ бөлгіш болып табылады. Ал а саны b-ге бөлінбейді дейік, сонда а-ны b-ге бөлгендегі бөлінді q де, қалдық r болсын және мұнымен бірге

а=bq+r (1)

болады, мұндағы 0≤r<b.

Екі пар а мен b және b мен r сандарын қарастырайық. а мен b сандарын бірінші пар, ал b мен r сандарын екінші пар делік. Бірінші пар а мен b сандарының ортақ бөлгіштерінің қайсысы болса да екінші пар b мен r сандарының да ортак бөлгіштері болатынын және керісінше де солай екендігін байқау оңай.

Мысал. 1419 бен 731 сандарының ен үлкен ортақ белгішін табу керек болсын.

Бұл үшін алдымен былай істейміз:

1419 731

731 1

688 = r

731 688

688 1

43 = r₁

688 43

258 16

258

0= r₂

Мұны мына түрде жазуға болады:

1419 = 731 • 1 + 688,

731 = 688 • 1 + 43,

688 = 43 • 16 + 0.

Бөлгендегі қалдықтар мыналар: 688, 43, 0. Бұлардың нольге тең емес ең соңғысы r₁=43. Демек, ізделінді ең үлкен ортақ бөлгіш

d = (1419. 731) = 43

болады.

6-теорема. а мен b сандарының ең үлкен ортақ d бөлгішін сол а мен b сандары арқылы сызықтық өрнекпен көрсетуге болады, яғни әр уақытта а мен β сандары табылып,

аα+bβ=d

болады.

Салдар. Егер а мен b сандары өз ара жай болса, қашан да бүтін α мен β сандары табылып, бұлар аα + bβ=1 теңдігін қанағаттандырады.

Негізгі теорема. Егер а мен b өз ара жай сандар болып, ал с кез келген бүтін сан болса, онда (ас, b) — (с, b) болады.

Бұл теореманың таза теориялық маңызы болуымен бірге, практикалық маңызы да зор. Атап айтқанда, бұл теореманы пайдалана отырып. ең үлкен ортақ бөлгішті кей жағдайда, бөлу амалын бір рет те орындамай-ақ, оңай табуға болады. Мысалы, 270 пен 189 сандарының ең үлкен ортақ бөлгішін табу керек болсын. 189=7•27 және (7, 270) = 1 болатын себепті,

(270, 189) = (270, 7• 27) = (270, 27)= 27

шьғады. Сонда 27 саны 270 пек 189 сандарының ең үлкен ортақ бөлгіші болады.

Жоғарыда дәлелденген негізгі теоремадан шығатын бір қатар салдарды келтірейік.

7-теорема. Егер (а, b) = 1 және ас саны b-ге бөлінетін болса, онда с саны b-ге бөлінеді.

8-теорема. Егер а мен с сандарының әрқайсысы b мен өз ара жай сан болса, онда олардың ас көбейтіндісі де b-мен өз ара жай сан болады.

І-салдар. Егер де а₁, а₂,..., а_n сандарының әрқайсысы b-мен өз ара жай сан болса, онда олардың а₁, а₂,...а_n көбейтіндісі де b мен өз ара жай сан болады.

2-салдар. Егер де а₁, а₂, а₃,....а_n сандар қатарының әрбір саны басқа бір сандардың b₁,b₂,..,b_m қатарының әрбір санымен жай сан болса, онда а₁, а₂,..а_n көбейтіндісі b₁,b₂,..,b_m көбейтіндісімен жай сан болады.

3-салдар. Егер (а,b)=1 болса, онда кез келген натурал n мен т сандары үшін (аⁿ,b^m)=1 болады.

9-теорема. Егер де с саны өз ара жай а мен b сандарының әрқайсысына бөлінсе, онда ол олардың аb көбейтіндісіне де бөлінеді.

Берілген а мен b сандарының әрқайсысына бірден бөлінетін бүтін сандардың кай қайсысы да сол а және b сандарының ортақ еселігі деп аталады. а мен b сандарына еселік сандардың ішіндегі ең кішісін ең кіші ортақ еселік сан деп атайды да, оны былай белгілейді:

N=[a,b].

10-теорема. а мен b сандарының кез келген ортақ еселік саны олардың ең кіші ортақ еселігіне бөлінеді.

Сонымен, а мен b-нің ең кіші ортақ еселігі мына формула бойынша табылады:

N=ab₁,

немесе

ab

N=——,

(a,b)

яғни а мен b сандарының ең кіші ортақ еселігі сол сандардың көбейтіндісін олардың ен, үлкен ортақ бөлгішіне бөлгендегі бөліндіге тең болады.

Дербес жағдайда, а мен b сандары өз ара жай сандар болғанда, (а,b)=1,

N = аb

болады, яғни өз ара жай сандардың ең кіші ортақ еселігі сол сандардың көбейтіндісіне тен болады.

Мысалдар. 1) 117 мен 99 сандарының ең кіші ортақ еселігін табалық. Бұл сандардың ең үлкек ортақ бөлгіші d=9 болады. Демек,

117•99

N=[117,99]= ——— = 117•11 = 1287.

2) Өз ара жай (16, 9) =1 екі 16 омен 9 сандарының ең кіші ортақ еселігі

N=[16, 9]=16•9=144

болады.

Мысал. 18, 4, 27, 75 сандарының ең кіші ортак еселігі

N=[18, 4, 27, 75]=[[18, 4], 27, 75]=[36, 27, 75] =

108•75

=[[36, 27], 75] = [108, 75] = ——— =108•25=2700, N=2700.

3. Евклид алгоритмі.Ерте д‰ниедегі грек математигі ±сынѓан сандардыњ ењ ‰лкен ортаќ бµлгішін табу єдісін берейік. Б±л єдісті Евклид алгоритмі дейді, ол тµмендегі леммаларѓа с‰йенеді.

1 лемма.Егер а M b болса, онда (а , b) = b.

Дєлелдеу. а M b жєне b M b болѓандыќтан , онда b саны а жєне b сандарыныњ ортаќ бµлгіші болады. Екінші жаѓынан , егер с саны а жєне b сандарыныњ кезкелген ортаќ бµлгіші болса, онда ол b саныныњ да бµлгіші болады. 2 аныќтаманыњ барлыќ шарттары орындалѓандыќтан (а , b) = b болады. #

2 лемма.Егер а = b q + r болса, онда (а , b) = (b , r) , м±ндаѓы а , b жєне r нµлден µзгеше.

Евклид алгоритмі.Екі санныњ ењ ‰лкен ортаќ бµлгішін тµмендегі теорема арќылы береміз.

Теорема.Егер а = b q₀ + r₁ ; 0£ r₁ < b,

b = r₁ q₁ + r₂ ; 0£ r₂ < r₁,

. . . . . . . . . . . . . . . . . . . . .( 1 )

r_n-2 = r_n-1 q_n-1 + r_n ; 0£ r_n < r_n-1,

r_n-1 = r_n q_n,

онда (а , b) = r_n.

Дєлелдеу. 2-ші лемма бойынша ( 1 ) -ніњ 1-ші тењдігінен (а , b) = (b , r₁), 2-ші тењдіктен (b , r₁) = (r₁, r₂) , осылайша жалѓастыра отырып соњѓы тењдіктен (r_n-2, r_n-1) = (r_n-1, r_n). Олай болса, (а , b) = (r_n-1, r_n). Біраќ r_n-1 M r_n жєне 1-ші лемма бойынша (r_n-1, r_n) = r_n. Сондыќтан (а , b) = r_n . #

2º ќасиет.Егер (а₁, а₂ , . . . , а_n-1) = d₁ жєне d = (d₁, а_n) болса, онда d = (а₁,. . . , а_n).

Салдар.Егер (а₁, а₂) = d₁, (d₁, а₃) = d₂, . . . , (d_n-2, а_n) = d_n-1 болса, онда (а₁,. . . , а_n) = d_n-1.

3º ќасиет.а₁,. . . , а_n б‰тін сандарыныњ оњ ортаќ d бµлгіштерініњ шамасы бойынша ењ ‰лкені осы сандардыњ ењ ‰лкен ортаќ бµлгіші болады.

Дєлелдеу. d >0 саны а₁,. . . , а_n б‰тін сандарыныњ ортаќ бµлгіші . Сондыќтан

d = (а₁,. . . , а_n) саны d санына бµлінеді, онда d ³d. Сонымен бірге d >0 саны а₁,. . . , а_n б‰тін сандарыныњ оњ ортаќ бµлгіштерініњ шамасы бойынша ењ ‰лкені, ал d осындай бµлгіштердіњ біреуі, онда d³ d. Осы d ³d жєне d³ d тењсіздіктерінен d =d шыѓады. #

4º ќасиет.Егер а жєне b сандарыныњ єрбірін бір t ¹0 санына кµбейтсек, онда олардыњ ењ ‰лкен ортаќ бµлгіші де осы t санына кµбейтіледі.

Дєлелдеу. Жоѓарыда Евклид алгоритмінде берілген тµмендегі тењдіктердіњ єрбірін

t ¹0 санына кµбейтейік

а = b q₀ + r₁ ;

b = r₁ q₁ + r₂ ;

. . . . . . . . . . . . . . . .

r_n-2 = r_n-1 q_n-1 + r_n ;,

r_n-1 = r_n q_n,

онда

а t = b t q₀ + r₁ t ;

b t = r₁ t q₁ + r₂ t ;

. . . . . . . . . . . . . . . .

r_n-2 t = r_n-1 t q_n-1 + r_n t ;,

r_n-1 t = r_n t q_n.

Олай болса (а t , b t) = r_n t = (а , b) t . #

5º ќасиет.Егер d саны а жєне b сандарыныњ ењ ‰лкен ортаќ бµлгіші болса, онда х жєне y б‰тін сандары табылып, а х + bу = d тењдігі орындалады.

4.