Лекция 1 Матрицалар және анықтауыштар
ЕКОЕ, ЕҮОБ, Евклид алгоритмі
жүктеу/скачать 1,93 Mb.
|
- Бұл бет үшін навигация:
- 3-анықтама
- ЕҮОБ-ті табудың Евклид алгоритмі
- Дәлелдеме
- Евклид алгоритмі
| 5.1.2 ЕКОЕ, ЕҮОБ, Евклид алгоритмі
2-анықтама: Бірнеше сандардың бәрін бөлетін санды осы сандардың ортақ бөлгіші, ортақ бөлгіштердің ең үлкенін ең үлкен ортақ бөлгіш (ЕҮОБ) деп атайды, m және n сандарының ең үлкен ортақ бөлгішін ЕҮОБ(m,n) не (m,n) деп белгілейді. ЕҮОБ-ті табу алгоритмі: Берілген сандарды жай көбейткіштерге жіктейміз. Барлық сандарға ортақ көбейткіштерді тауып көбейтіндісін аламыз. 3-анықтама: Өзара жай сандар деп ЕҮОБ-і 1-ге тең сандарды айтамыз. 4-анықтама: Бірнеше сандардың бәріне де бөлінетін ең кіші санды сол сандардың ең кіші ортақ еселігі (ЕКОЕ) дейді, m және n сандарының ең кіші ортақ еселігін ЕКОЕ(m,n) не [m,n] деп белгілейді. ЕКОЕ-ті табу алгоритмі: Берілген сандарды жай көбейткіштерге жіктейміз. Алғашқы санның барлық көбейткіші мен келесі сандардың алғашқы санға кірмеген көбейткіштерінің көбейтіндісін аламыз. ЕҮОБ-ті табудың Евклид алгоритмі төмендегі теоремаға негізделеді. 2-теорема: а және в сандарының кез келген ортақ бөлгіші a – b санының бөлгіші болады. Дәлелдеме: a ⁞ с, b⁞с болса a =mc , b =nc болады да a - b =mc-nc=(m-n)c. 3-теорема: a санын в санына бөлгенде бөлінді - q, қалдық -r болса, онда ЕҮОБ (a, b)=ЕҮОБ (b, r) . (1) 3-теореманы пайдаланып a, b сандарының ЕҮОБ-ін қалай табуға болатынын қарастырайық. Қалдықпен бөлуді тізбектей орындау арқылы шектеулі қадамнан соң 0 қалдық алатынымыз түсінікті. Себебі әр қалдық өзінің алдындағы қалдықтан кем және одан кем емес болатындықтан шектеусіз жалғасуы мүмкін емес. Демек, қалдық нольге тең болғанда 3-теорема бойынша ЕҮОБ соңғы 0-ге тең емес қалдыққа тең болады. Бұл тәсілді Евклид алгоритмі деп атайды. 4-теорема: Екі оң бүтін санға Евклид алгоритмін қолданғанда алғашқы нөлге тең қалдықтың алдындағы қалдық бұл сандардың ЕҮОБ-і болады. жүктеу/скачать 1,93 Mb. Достарыңызбен бөлісу:
|