Сабақтың тақырыбы: Жай және құрама сандар. Эратосфен елегі. Евклид алгоритмі
жүктеу/скачать 47 Kb.
|
- Бұл бет үшін навигация:
- Мысалы
- Теорема-1
- Евклид алгоритмі
| Жалпы жағдайда: , cандары үшін
Анықтама 3: Бір неше сандарға бәріне де бөлінетін ең кіші санды сол сандардың ең кіші ортақ еселігі (ЕКОЕ) дейді. ЕКОЕ ті табу алгоритмі: Берілген сандарды жай көбейткішке жіктейді. Алғашқы санның барлық көбейткіші мен келесі сандардың алғашқы санға кірмеген көбейткіштердің көбейтіндісін аламыз. Мысалы: ЕКОЕ (12;30) – ды табайық, болғандықтан ЕКОЕ (12;30) =2·2·3·5 = 60 болады. Жалпы жағдайда: болса , болады. ЕҮОБ-ті табудың Евклид алгоритмі: Бұл алгоритм төменгі теоремаға негізделеді. Теорема-1: а-және в-сандарының кез келген ортақ бөлгіші а – в санының бөлгіші болады. Дәлелдеме: а; с, в;с болса а=mc , в=nc болады да а-в=mc-nc=(m-n)c Теорема-2: а-санын в-ге бөлгенде бөлінді-q, қалдық r-ға тең немесе , болса ЕҮОБ (а; в)=ЕҮОБ (в; r) (1) болады Дәлелдеме: (а; в)=d, (b;r)=h деп алып d=h дәлелдесек жеткілікті. , немесе болады. Бұдан . Сондай ақ , және r=a-bq болатындықтан . Немесе . Бұдан болатыны дәлелденеді. Теорема-2 ні пайдаланып a, b сандарының ЕҮОБ-ін қалай табуға болатынын қарастырайық. Қалдықпен бөлуді тізбектей орындау арқылы шектеулі қадамнан соң 0 қалдық алатынымыз түсінікті. Себебі әр қалдық өзінің алдындағы қалдықтан кем және ден кем емес болатындықтан шектеусіз жалғасуы мүмкін емес. Немесе қалдық нольге тең болады, жәнеде теорема-2 бойынша ЕҮОБ- табуға арналған бұл тәсілді Евклид алгоритмі деп атайды. Мысалы: 1381955 және 690713 сандарының ЕҮОБ-ін тап. (1381955; 690713) = (690713; 529) = (529; 368) = (368; 161) = (161; 46) = =(46; 23)=23 Біз жоғарыда төменгі теораманы дәлелдедік. Үйге тапсрыма: 255 беттегі жаттығулар. жүктеу/скачать 47 Kb. Достарыңызбен бөлісу:
|