Лекция. Евклид алгоритмі жне арифметиканы негізгі теоремасы. Теорема

• Название: Евклид алгоритмі жне арифметиканы негізгі теоремасы. Теорема
• Анкор: Лекция
• Дата: 20.10.2022
• Размер: 225.17 Kb.
• Имя файла: DM_lecture_6 2.docx
• Тип: Документы; #745203

Евклид алгоритмі және арифметиканың негізгі теоремасы.
Теорема (қалдықпен бөлу туралы). Егер болса. Онда



шарты орындалатындай бір ғана сандары табылады.

Дәлелдеуі. сандары үшін төмендегі төрт жағдайдың бірі орын алуы мүмкін. 1) ; 2) ; 3) ;4) ;

Енді (1) және (4) жағдайлардың дәлелдеулерін келтірейік.

1) . Бұл жағдайда берілген сандардың екеуі де оң. Онда қандай да бір саны табылып болады. Егер деп есептесек, онда жоғарыдағы теңсіздіктен , яғни және . Демек (*) шарты орындалады.

4) . Онда . Демек жоғарыдағы жағдайда көрсеткеніміздей қандай да бір саны табылып болады. Егер деп алсақ, немесе . Енді деп есептесек, бұл сандар үшін (*) шарты орындалады.

Бірегейлігі. және болсын. Онда . Яғни саны санына бөлінеді. (*) бойынша, бұл жағдай болғанда ғана орын алады. Яғни . Ендеше . Теорема дәлелденді.

Ескерту. Осы теореманың шартындағы – бөлінгіш, – бөлгіш, – бөлінді, ал – қалдық деп аталады.

Жаттығу. (2) және (3) жағдайлардың дәлелдеулерін келтіріңдер.

Анықтама 1. Егер (*) шартындағы қалдық нөлге тең болса, онда саны санына қалдықсыз бөлінеді деп айтамыз. Белгілеуі: . Оқылуы: « саны санына бөлінеді» немесе « саны санын бөледі». Сонымен _: .

Енді осы қатынастың кейбір қарапайым қасиеттерін келтірейік.

Төменде келтірілген сандарын бүтін сандар деп есептейік.

1. 
   .
   
2. 
   .
   
3. 
   (рефлексивтілік).
   
4. 
   (антисимметриялық).
   
5. 
   (транзитивтілік).
   
6. 
   .
   
7. 
   .
   
8. 
   .
   
9. 
   ,
   
10. 
    (Бұл жерде берілген сандарды оң таңбалы деп есептейміз).
    

Бұл қасиеттердің барлығы да бөлінгіштік қатынасының анықтамасының тікелей салдары болады.

Евклид алгоритмі.

Евклид алгоритмі әдетте екі бүтін санға қолданылады. Мысалы сандары берілсе, алдымен санын санына қалдықпен бөлеміз. Егер қалдық нөлге тең болса, онда алгоритм өз жұмысын тоқтатады. Кері жағдайда бөлгішті қалдыққа тағы да қалдықпен бөлеміз. Қалдықтар біртіндеп кеміп отыратындықтан, бұл процесс ақырлы қадамнан кейін аяқталады. Сондықтан осы әрекет қалдық нөлге тең болғанша жалғасып, өз нәтижесін береді. Евклид алгоритмін жоғарыдағы екі санға қолданғанда пайда болған ең соңғы нөлге тең емес қалдық – осы сандардың ең үлкен ортақ бөлгішін береді. Оны арқылы белгілейміз. және сандарының еселіктерінің ішіндегі ең кішісін – ең кіші ортақ еселік деп айтамыз. және сандарының ең кіші ортақ еселігін арқылы белгілейік.

Анықтама 2. үшін

1. 
   
   
2. 
   егер және онда
   

шарттары орындалса, онда ең үлкен ортақ бөлгіш(ЕҮОБ) деп аталады.

Анықтама 3. а,b бүтін сандары үшін ЕҮОБ(a,b)=1 болса, онда олар өзара жай сандар болады.

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

1. 
   
   
2. 
   егер онда
   

бүтін саны ең кіші ортақ еселік(ЕКОЕ) деп аталады. ЕКОЕ(a,b) жалғыз, себебі және 2 шарттан шығады.

Теорема. Егер а,b нөлдік емес бүтін сандар болса, онда олардың ЕКОЕ табылады және жалғыз, яғни .
Енді Евклид алгоритмінің жалпы жазылуын келтірейік:

Кез келген a > b; a, b  сандары үшін қалдық нөлге тең болмаған жағдайда, бөлгішті қалдыққа бұрыштап бөлу арқылы келесі теңдіктер тізбегін аламыз.

,

,

,

,

_{.................................................................. (ЕА)}

,

,

.

Теорема. және сандарының ең үлкен ортақ бөлгіші, оларға Евклид алгоритмін қолданғандағы ең соңғы нөлге тең емес қалдыққа тең болады. Керісінше, жоғарыдағы ең соңғы нөлге тең емес қалдық осы сандардың ең үлкен ортақ бөлгіші болады. Яғни .

Дәлелдеуі. Бізге және теңсіздіктерін дәлелдеу жеткілікті.

( ): – және сандарының кез келген үлкен ортақ бөлгіші болсын. Онда (ЕА) теңдіктер жүйесінің бірінші теңдігінен . Онда екінші теңдіктен . Келесі теңдіктерден импликацияларын аламыз. Демек . Онда .

( ): Енді (ЕА) бойынша кері қарай жүрелік. Соңғы теңдіктен . Оның алдыңғы теңдігінен , онда бөлу қатынасының транзитивтілігінен болады. Ары жалғастыру арқылы ең соңынан және болатынын көреміз. Яғни – және сандарының ортақ бөлгіші болады. Ал ең үлкен ортақ бөлгіштің анықтамасы бойынша . Теорема дәлелденді.

Салдар 1. Екі санның кез келген ортақ бөлгіші олардың ең үлкен ортақ бөлгіштерінің бөлгіші болады.

Дәлелдеуі. Теореманың дәлелдеуінің тура жолынан шығады.

Салдар 2 (Ең үлкен ортақ бөлгіштің сызықты өрнектелуі). Кез келген үшін және саны осы теңдікті қанағаттандыратын ең кіші сан.

Дәлелдеуі. ( ): Теорема бойынша . Онда . Ал теңдіктердің оң жақтарындағы қалдықтарды алдыңғы теңдіктер арқылы басқа қалдықтармен сызықты өрнектей аламыз. Осылай жоғары өрлей отырып ең соңында санын және сандары арқылы сызықты өрнектейміз.

( ): саны және сандары арқылы сызықты өрнектелетін оң сандардың ішіндегі ең кішісі болсын. Яғни . Онда және саны және сандарының кез келген ортақ бөлгішіне бөлінеді. Атап айтқанда, немесе . Демек .

Мысал. а = 525, b = 231 сандары берілсін. Осы сандарға Евклид алгоритмін қолдану үлгісін келтірейік.

_ _42| 42 | 0

_ 63| 42 | 21 2

_ 231| 189 |   42 1

525| 462 |   63 3

231 2

Бұл есептеуді төменгі теңдіктер арқылы жазайық:

525 = 231 2 + 63,

231 = 63 3 + 42,

63 = 42 1 + 21,

42 = 21 2.

Демек, (525, 231) = 21. Енді осы табылған ең үлкен ортақ бөлгіштің сызықты өрнектелуін келтіреміз.

21 = 63 - 42 1 = 63 - (231 - 63 3) 1 = 525 - 231 2 - (231 - (525 - 231 2) 3) = 525 4 - 231 9

Біздің іздеген сызықты коэффициенттер u және v сәйкес 4 және – 9 сандары болады.

Салыстыру теориясы

Анықтама және қарапайым қасиеттері.

Анықтама. а, b Z , N. Егер а және b сандарын m-ге бөлгенде, олардың қалдықтары бірдей болса, онда а және b сандарын модулі бойынша салыстырымды деп айтып, бұл ұғымды арқылы белгілейміз. Басқаша айтқанда, . Бұл бинарлық қатынас рефлексивті, симметриялы және транзитивті, яғни модуль бойынша салыстыру қатынасы эквиваленттік қатынас болады. Бүтін сандар жиынында,бұл қатынас бойынша табиғи жолмен фактор-сақина анықталады. Оны модулі бойынша қалындылар сақинасы деп атап, Z_m арқылы белгілейміз. Мысалы .

Қасиет 1. Берілген модул бойынша салыстыруларды мүшелеп қосуға және алуға болады.

Дәлелдеуі. болсын. Онда .

Қасиет 2. Салыстырудың кез келген жағындағы қосылғышты, оның екінші жағына таңбасын өзгертіп көшіруге болады.

Қасиет 3. Салыстырудың кез келген жағына модулге еселі санды қосуға болады.

Қасиет 4. Берілген модул бойынша екі салыстыруды мүшелеп көбейтуге болады, яғни .

Қасиет 5. Салыстырудың екі жағын да бірдей дәрежеге шығаруға болады, яғни

Қасиет 6. Егер a₀ b₀ (modm), a₁ b₁ (modm),..., a_n b_n (modm), x y(modm), онда a₀xⁿ +a₁x^n-1+...+a_n b₀ yⁿ +b₁y^n-1+...+b_n (modm).

Қасиет 7. Салыстырудың екі жағын да модулмен өзара жай болатын олардың ортақ бөлгішіне қысқартуға болады.

Қасиет 8. Салыстырудың екі жағы мен модулді бірдей санға көбейтуге және олардың ортақ бөлгішіне бөлуге болады.

Қасиет 9. Егер a b салыстыруы бірнеше әртүрлі модул бойынша орындалса, онда бұл салыстыру аталған модулдердің ең кіші ортақ еселігі үшін де орындалады.

Қасиет 10. Егер салыстыру m модулі бойынша орындалса, онда ол осы m саныны кез келген бөлгіші d модулі үшін де орындалады.

Қасиет 11. Егер салыстырудың бір жағы мен модулі қандай да бір санға бөлінсе, онда салыстырудың екінші жағы да сол санға бөлінеді.

Мысал. Кез келген n натурал саны үшін 37ⁿ⁺² +16ⁿ⁺¹+23ⁿ саны 7-ге бөлінетінін дәлелде.

Шешуі. 37 2(mod7), 16 2(mod7), 23 2(mod7). Енді бірінші салыстыруды n+2, екіншіні n+1, ал үшіншіні n дәрежеге шығарып, мүшелеп қосамыз. Онда . Демек берілген сан 7-ге бөлінеді.

Қалындылардың толық және келтірілген жүйесі.

Осының алдында _m қатынасы бүтін сандар жиынын өзара қиылыспайтын кластарға бөледі. Барлық кластар саны m -ге тең. Әрбір класта m –ге бөлгенде қалдықтары бірдей болатын бүтін сандар жатады.

Анықтама. _m арқылы анықталған эквиваленттік кластың кез келген элементін m модулі бойынша қалынды деп атаймыз. Әрбір кластан бір-бір элементтен алынып құрылған қалындылар жүйесін m модулі бойынша қалындылардың толық жүйесі (толық жүйеде дәл m бүтін сан болады) деп атайды. Ал тек m –ге бөлгенде пайда болған қалдықтардан құрылған жүйе – ең кіші теріс емес қалындылар деп аталады. Егер модулдері бойынша ең кіші болса, онда  қалындысы абсолютті кіші қалынды делінеді.

Мысал :m = 5.

Онда:0, 1, 2, 3, 4 - ең кіші теріс емес қалындылар;-2, -1, 0, 1, 2 - абсолютті кіші қалындылар. Келтірілген екі қалындылар жүйесі де толық жүйе болады.

Лемма 1. 1) m модулі бойынша өзара салыстырымды болмайтын m сан m модулі бойынша қалындылардың толық жүйесі болады.

2) Егер а және m сандары өзара жай, ал x санының мәндері m модулі бойынша толық жүйеден таңдалса, онда кез келген b саны үшін аx+b түріндегі сандар да m модулі бойынша толық жүйе құрады.

Дәлелдеуі. 1) тұжырым айқын.2) тұжырымды дәлелдейік. аx+b түріндегі сандардың саны дәл m-ге тең. Енді осы алынғани сандар жүйесіндегі кез келген екі санның m модулі бойынша салыстырымды емес екенін көрсетейік. Шынынд x₁ және x₂толық жүйеден алынған қандай да бір сандар үшін a x₁+b a x₂+b(mod m) болсын дейік. Онда:a x₁+b a x₂+b(mod m) немесе a x₁a x₂(mod m). Яғни x₁ x₂(mod m). Бұл x₁ және x₂толық жүйеден алынғанына қайшы. Берілген  эквиваленттік кластың барлық сандары осы эквиваленттік кластың бір элементіне m –ге еселі санды қосу арқылы алнатындықтан, осы кластың барлықт сандарының m молдулімен ең үлкен ортақ бөлгіші бірдей болады. Біз олардың ішінде m модулімен ең үлкен ортақ бөлгіші 1-ге тең қалындыларды бөліп қарастырамыз.

Анықтама. Қалындылардың толық жүйесінен алынған, m модулімен ең үлкен ортақ бөлгіші 1-ге тең қалындылар жүйесін m модулі бойынша келтірілген қалындылар жүйесі деп атайды.

Келтірілген қалындылар жүйесін әдетте ең кіші оң қалындылар ішінен таңдайды. Олардың санын ( m ) – Эйлер функциясының мәніне тең деп есептейді. Яғни ( m ) – m модулі бойынша келтірілген қалындылар жүйесіндегі сандардың санын білдіреді.

Мысал. m = 42 болсын. Онда осы модул бойынша келтірілген қалындылар жүйесі төмендегідей: 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 1) m модулі бойынша екеуара салыстырымды болмайтын (m) сан m модулі бойынша келтірілген қалындылар жүйесін құрады.

2) Егер (a,m) = 1және x саны қандай да m модулі бойынша келтірілген қалындылар жүйесінен мәндер таңдаса, онда аx сандар да m модулі бойынша келтірілген қалындылар жүйесінен мәндер таңдайды.

Дәлелдеуі. 1) тұжырым – анықтамадан. 2) тұжырымды көрсетейік. аx сандары екеуара салыстырымсыз және олардың саны дәл (m)-ге тең. (a,m)=1, (x,m)=1 (ax.m)=1 болғандықтан, олардың әрқайсысы модулмен өзара жай. Демек, аx сандары да m модулі бойынша келтірілген қалындылар жүйесін құрады.

Лемма 3. m₁, m₂, ..., m_k – екеуара жай сандар тізімі және m₁ m₂ ...m_k =M₁ m₁ =M₂ m₂ =...=M_k m_k болсын. Мұндағы M_j =m₁ ...m_j-1 m_j+1 ...m_k

1) Егер x₁, x₂ , ..., x_k сандары сәйкес m₁, m₂, ..., m_k модулдері бойынша қалындылардың толық жүйесін қабылдаса, онда M₁ x₁ +M₂ x₂ + ...+M_k x_k сызықты өрнегінің мәндері де m=m₁ m₂ ...m_k модулі бойынша қалындылардың толық жүйесінің мәндерін қабылдайды.

2) ) Егер x₁ , x₂ , ..., x_k сандары сәйкес m₁, m₂, ..., m_k модулдері бойынша қалындылардың келтірілген жүйесін қабылдаса, онда M₁ x₁ +M₂ x₂ + ...+M_k x_k сызықты өрнегінің мәндері де m = m₁ m₂ ...m_k модулі бойынша қалындылардың келтірілген жүйесін құрады.

Дәлелдеуі.

1) M ₁ x ₁ +M ₂ x ₂ + ...+M _k x _k өрнегі x ₁ , x ₂ , ..., x _k сандарының аталған мәндері ұшін m₁ m₂ ...m_k =m мән қабылдайтыны түсінікті. Осы мәндердің m модулі бойынша екеуара салыстырмды болмайтынын көрсетсек болады. Егер



M_s –тен бөлек кез келген M_j көбейтіндісі m_s санына еселі болады, Сондықтан, соңғы салыстырудың екі жағындағы m_s санына еселі қосылғыштарды алып тастасақ,  болатынын көреміз. Бұл x _s сандарының m _s модулі бойынша қалындылардың толық жүйесінің мәндерін түгел қабылдап өтетініне қайшы болады.

2). M₁ ₁ + M₂ ₂ + ...+ M_k _k өрнегі (m₁ ) (m₂ ) ... (m_k ) = (m₁ m₂ ... m_k ) = (m) (Эйлер функциясы мультипликативті!) әртүрлі мән қабылдайды және олар m = m₁ m₂ ...m_k модулі бойынша өзара жай сандар болады. Оны жоғарыдағы әдіспен көрсете аламыз. Ал кез келген 1 s k үшін (M₁ ₁ + M₂ ₂ + ...+ M_k _k ,m_s ) = (M_s _s , m_s ) = 1болғандықтан, (M₁ ₁ + M₂ ₂ + ...+ M_k _k ,m_s ) =1, демек M ₁ ₁ +M ₂ ₂ + ...+M _k _k өренегініңғ мәндері m модулі бойынша келтірілген қалындылар жүйесін құрады.