Евклид алгоритмі арқылы түйіндерді табу және жай көбейткіштерге бөлу. Сандарды жай көбейткіштерге бөлу арқылы nok табу Евклидтің gcd табу алгоритмі
Ең үлкен ортақ бөлгішті табудың екі әдісін қарастырыңыз.
Факторинг арқылы табу
Бірінші әдіс - берілген сандарды бөлшектеу арқылы ең үлкен ортақ бөлгішті табу негізгі факторлар.
Бірнеше санның GCD-ін табу үшін оларды жай көбейткіштерге ыдыратып, олардың барлық берілген сандарға ортақ сандарды бір-біріне көбейту жеткілікті.
1-мысал GCD (84, 90) табайық.
84 және 90 сандарын жай көбейткіштерге бөлеміз:
Сонымен, біз барлық жалпы жай көбейткіштердің астын сыздық, оларды бір-біріне көбейту керек: 1 2 3 = 6.
Сонымен gcd(84, 90) = 6.
2-мысал GCD (15, 28) табайық.
15 және 28 сандарын жай көбейткіштерге бөлеміз:
15 және 28 сандары қос жай, өйткені олардың ең үлкен ортақ бөлгіші біреу.
gcd (15, 28) = 1.
Евклид алгоритмі
Екінші әдіс (басқаша Евклид әдісі деп аталады) кезекті бөлу арқылы GCD табу болып табылады.
Алдымен біз бұл әдісті тек екі берілген санға қолданылатынын қарастырамыз, содан кейін оны үш немесе одан да көп сандарға қалай қолдану керектігін анықтаймыз.
Берілген екі санның үлкені кішіге бөлінетін болса, одан кіші сан олардың ең үлкен ортақ бөлгіші болады.
1-мысалЕкі 27 және 9 санын алайық. 27 саны 9-ға және 9-ға бөлінетіндіктен, 9 саны 27 және 9 сандарының ортақ бөлгіші. Бұл бөлгіш де ең үлкен, өйткені 9 кез келген санға бөлінбейді, 9-дан үлкен. Демек, gcd (27, 9) = 9.
Басқа жағдайларда екі санның ең үлкен ортақ бөлгішін табу үшін қолданылады келесі тапсырысәрекеттер:
- Берілген екі санның ішінен үлкен сан кішіге бөлінеді.
- Содан кейін кішірек сан бөлу нәтижесінде алынған қалдыққа бөлінеді Көбіреказырақ.
- Әрі қарай бірінші қалдық екінші қалдыққа бөлінеді, ол кіші санды бірінші қалдыққа бөлу арқылы алынады.
- Екінші қалдық үшіншіге бөлінеді, ол бірінші қалдықты екіншіге бөлу арқылы алынады және т.б.
- Осылайша, бөлу қалдық нөлге тең болғанша жалғасады. Соңғы бөлгіш ең үлкен ортақ бөлгіш болады.
2-мысал 140 және 96 сандарының ең үлкен ортақ бөлгішін табайық:
1) 140: 96 = 1 (қалған 44)
2) 96: 44 = 2 (қалған 8)
3) 44: 8 = 5 (қалған 4)
Соңғы бөлгіш 4, яғни gcd(140, 96) = 4.
Тізбекті бөлуді бағанға да жазуға болады:
Берілген үш немесе одан да көп сандардың ең үлкен ортақ бөлгішін табу үшін келесі процедураны қолданыңыз:
- Біріншіден, бірнеше деректер жиынынан кез келген екі санның ең үлкен ортақ бөлгішін табыңыз.
- Содан кейін табылған бөлгіштің GCD және кейбір үшінші берілген санды табамыз.
- Содан кейін біз соңғы табылған бөлгіштің және төртінші берілген санның GCD-ін табамыз және т.б.
3-мысал 140, 96 және 48 сандарының ең үлкен ортақ бөлгішін табайық. Біз алдыңғы мысалда 140 және 96 сандарының GCD-ін таптық (бұл 4 саны). 4 саны мен үшінші берілген санның ең үлкен ортақ бөлгішін табу керек - 48:
48 саны 4-ке қалдықсыз бөлінеді. Сонымен gcd(140, 96, 48) = 4.
Санды жай сандардың көбейтіндісі ретінде көрсету деп аталады бұл санды жай көбейткіштерге ыдырату.
Мысалы, 110 = 2 5 11 жазбасы 110 саны 2, 5 және 11 жай көбейткіштерге ыдырайтынын көрсетеді.
Жалпы алғанда, барлығын негізгі факторларға бөлуге болады құрама саноның үстіне кез келген әдіспен факторлардың реті ескерілмесе, бір және бірдей ыдырау алынады. Демек, 110 санының 2 · 5 · 11 көбейтіндісі немесе 5 · 2 · 11 көбейтіндісі ретінде бейнеленуі, мәні бойынша, 110 санының жай көбейткіштерге ыдырауы болып табылады.
Сандарды жай көбейткіштерге жіктегенде, 2, 3, 5 және т.б. бөлу белгілерін қолданып, санның жай көбейткіштерге жіктелуін жазу жолын еске түсірейік. Мысалы, 720 санын жай көбейткіштерге бөлейік.720 саны 2-ге бөлінеді. Демек, 2 саны 720 санының ыдырауындағы жай көбейткіштердің бірі болып табылады. 720-ны 2-ге бөліңіз. 2 саны жазылады. теңдік таңбасының оң жағы, ал 360 бөлімі 720 санының астына жазылады. 360 санын 2-ге бөлсек, 180 аламыз. 180-ді 2-ге бөлсек, 90 аламыз, 90-ды 2-ге бөлеміз, 45-ті аламыз, 45-ті бөлеміз. 3, 15 аламыз, 15-ті 3-ке бөлеміз, 5 аламыз. 5 саны жай, 5-ке бөлгенде 1 шығады. Көбейткіштерге бөлу аяқталды.
720 = 2 2 2 2 3 3 5
Бірдей көбейткіштердің көбейтіндісін қуатпен ауыстыру әдеттегідей: 720 = 5. 720 санының мұндай көрінісі деп аталады. канондық көрінісбұл сан.
Санды жай көбейткіштерге бөлу олардың ең үлкен ортақ бөлгішін және ең кіші ортақ еселігін табу үшін қолданылады.
Мысалы, 3600 және 288 сандарының ең үлкен ортақ бөлгішін және ең кіші ортақ еселігін табыңыз.
Осы сандардың әрқайсысын көрсетейік канондық пішін.
3600 = 2 2 2 2 3 3 5 5 =; 288 = 2 2 2 2 2 3 3 =
3600 және 288 сандарының ең үлкен ортақ бөлгішін жай көбейткіштерге бөлуде барлығы ортақ жай көбейту,берілген сандардың кеңейтімдерінде қамтылған және олардың әрқайсысынан алынуы керек ең төменгі көрсеткішоның көмегімен ол екі кеңейтімге де кіреді. Демек, 3600 және 288 сандарының ең үлкен ортақ бөлгішінің кеңеюіне және көбейткіштері кіреді. Сонымен D (3600? 288) = · = 144.
3600 және 288 сандарының ең кіші ортақ еселігінің жай көбейткіштерге жіктелуі құрамындағы барлық жай көбейткіштерді қамтуы керек. кем дегенде біреуінде 3600 және 288 сандарының кеңейтулерінен және олардың әрқайсысын алу керек ең жоғары ұпаймен,осы сандардың екі кеңеюіне де кіреді. Демек, 3600 және 288 сандарының ең кіші ортақ еселігінің кеңеюіне , , 5 көбейткіштері кіреді. Демек,
К (3600, 288) = 5 = 7200.
Жалпы алғанда, берілген сандардың ең үлкен ортақ бөлгішін табу үшін:
2) Біз барлық берілген сандарға ортақ жай көбейткіштердің көбейтіндісін жасаймыз және олардың әрқайсысы осы сандардың барлық кеңеюіне енетін ең кіші дәреже көрсеткішімен алынады;
3) Осы көбейтіндінің мәнін табамыз – ол осы сандардың ең үлкен ортақ бөлгіші болады.
Берілген сандардың ең кіші ортақ еселігін табу үшін:
1) Әрбір берілген санды канондық түрде көрсетеміз;
2) Осы сандардың кеңейтулерінде болатын барлық жай көбейткіштерден көбейтінді құраймыз және әрқайсысы осы сандардың барлық кеңейтімдеріне енетін ең үлкен көрсеткішпен алынады;
3) Осы көбейтіндінің мәнін табамыз – ол осы сандардың ең кіші ортақ еселігі болады.
Билет нөмірі 45. Сандардың ең кіші ортақ еселігі. Оның қасиеттері мен табу әдістері. Мысалдар.
gcd (ең кіші ортақ бөлгіш) арқылы ең кіші ортақ еселікті (LCM) есептеу
Ең кіші ортақ еселікті табудың бір жолы LCM мен GCD арасындағы қатынасқа негізделген. LCM және GCD арасындағы бар қатынас белгілі ең үлкен ортақ бөлгіш арқылы екі оң бүтін санның ең кіші ортақ еселігін есептеуге мүмкіндік береді. Сәйкес формуланың пішіні бар LCM(a, b)=a b: GCD(a, b) . Жоғарыда келтірілген формула бойынша LCM табу мысалдарын қарастырыңыз.
Мысал.
Екі санның ең кіші ортақ еселігін табыңыз 126 және 70 .
Шешім.
Бұл мысалда a=126, b=70. Формула арқылы өрнектелген LCM және GCD арасындағы байланысты қолданайық LCM(a, b)=a b: GCD(a, b). Яғни, алдымен сандардың ең үлкен ортақ бөлгішін табуымыз керек 70 және 126 , содан кейін біз жазылған формула бойынша осы сандардың LCM есептей аламыз.
Табайық GCD(126, 70), Евклид алгоритмін қолдана отырып: 126=70 1+56, 70=56 1+14, 56=14 4, Демек, gcd(126, 70)=14.
Енді біз қажетті ең кіші ортақ еселікті табамыз: LCM(126, 70)=126 70: GCM(126, 70)=126 70:14=630.
Жауап:
LCM(126, 70)=630.
Мысал.
Немен тең ҰОК(68, 34)?
Шешім.
Өйткені 68 толығымен бөлінеді 34 , содан кейін GCD(68, 34)=34. Енді ең кіші ортақ еселікті есептейміз: LCM(68, 34)=68 34:GCM(68, 34)=68 34:34=68.
Жауап:
LCM(68, 34)=68.
Алдыңғы мысал оң бүтін сандар үшін LCM табу үшін келесі ережеге сәйкес келетінін ескеріңіз ажәне б: егер сан абөлінген б, онда осы сандардың ең кіші ортақ еселігі а.
Сандарды жай факторларға бөлу арқылы LCM табу
Ең кіші ортақ еселікті табудың тағы бір жолы сандарды жай көбейткіштерге бөлуге негізделген. Егер біз осы сандардың барлық жай көбейткіштерінің көбейтіндісін жасасақ, содан кейін осы көбейтіндіден осы сандардың кеңейтулерінде болатын барлық жалпы жай көбейткіштерді алып тастасақ, онда алынған туынды осы сандардың ең кіші ортақ еселігіне тең болады.
LCM табудың жарияланған ережесі теңдіктен шығады LCM(a, b)=a b: GCD(a, b). Шынында да, сандардың туындысы ажәне бсандардың кеңеюіне қатысатын барлық факторлардың көбейтіндісіне тең ажәне б. Өз кезегінде gcd(a, b)сандардың кеңеюінде бір мезгілде болатын барлық жай көбейткіштердің көбейтіндісіне тең ажәне б(бұл сандарды жай көбейткіштерге бөлу арқылы GCD табу бөлімінде сипатталған).
Мысал келтірейік. Мұны бізге хабарлаңыз 75=3 5 5және 210=2 3 5 7. Осы кеңейтулердің барлық факторларының көбейтіндісін жасаңыз: 2 3 3 5 5 5 7. Енді біз бұл өнімнен санның кеңеюінде болатын барлық факторларды алып тастаймыз 75 және санның кеңеюінде 210 (мұндай факторлар 3 және 5 ), содан кейін өнім пішінді алады 2 3 5 5 7. Бұл көбейтіндінің мәні сандардың ең кіші ортақ еселігіне тең 75 және 210 , яғни, LCM(75, 210)= 2 3 5 5 7=1 050.
Мысал.
Сандарды кеңейту 441 және 700 жай көбейткіштерге айналдырып, осы сандардың ең кіші ортақ еселігін табыңыз.
Шешім.
Сандарды жіктеп көрейік 441 және 700 негізгі факторлар үшін:
Біз алып жатырмыз 441=3 3 7 7және 700=2 2 5 5 7.
Енді осы сандардың кеңеюіне қатысатын барлық факторлардың көбейтіндісін жасайық: 2 2 3 3 5 5 7 7 7. Осы өнімнен екі кеңейтімде бір уақытта болатын барлық факторларды алып тастап көрейік (мұндай бір ғана фактор бар - бұл сан 7 ): 2 2 3 3 5 5 7 7. Осылайша, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.
Жауап:
LCM(441, 700)= 44 100.
Сандарды жай көбейткіштерге ыдырату арқылы LCM табу ережесін сәл басқаша тұжырымдауға болады. Санның кеңеюінен факторларға болса асанның кеңеюінен жетіспейтін көбейткіштерді қосыңыз б, онда алынған туындының мәні сандардың ең кіші ортақ еселігіне тең болады ажәне б .
Мысалы, барлық бірдей сандарды алайық 75 және 210 , олардың факторизациясы келесідей: 75=3 5 5және 210=2 3 5 7. Көбейткіштерге 3 , 5 және 5 санның ыдырауынан 75 2 және 7 санның ыдырауынан 210 , біз өнімді аламыз 2 3 5 5 7, кімнің мәні ҰОҚ(75, 210).
Мысал.
Сандардың ең кіші ортақ еселігін табыңыз 84 және 648 .
Шешім.
Алдымен сандардың ыдырауын аламыз 84 және 648 негізгі факторларға. Олар ұқсайды 84=2 2 3 7және 648=2 2 2 3 3 3 3. Көбейткіштерге 2 , 2 , 3 және 7 санның ыдырауынан 84 жетіспейтін факторларды қосу 2 , 3 , 3 және 3 санның ыдырауынан 648 , біз өнімді аламыз 2 2 2 3 3 3 3 7, ол тең 4 536 . Осылайша, сандардың қажетті ең кіші ортақ еселігі 84 және 648 тең 4 536 .
Жауап:
LCM(84, 648)=4536.
GCD табудың екі негізгі әдісін екі негізгі әдіспен қарастырайық: Евклид алгоритмін қолдану және факторинг арқылы. Екі, үш және одан да көп сандар үшін екі әдісті де қолданайық.
Yandex.RTB R-A-339285-1
GCD табудың Евклид алгоритмі
Евклид алгоритмі екі оң санның ең үлкен ортақ бөлгішін есептеуді жеңілдетеді. Евклид алгоритмінің тұжырымдары мен дәлелдемелерін Ең үлкен ортақ бөлгіш: анықтауыш, мысалдар бөлімінде бердік.
Алгоритмнің мәні қалдықпен бөлуді дәйекті түрде жүргізу болып табылады, оның барысында форманың теңдік қатары алынады:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
Біз бөлімді қашан аяқтай аламыз rk + 1 = 0, бола тұра r k = gcd (a , b).
1-мысал
64 және 48 .
Шешім
Белгілеуді енгізейік: a = 64 , b = 48 .
Евклид алгоритміне сүйене отырып, бөлуді жүзеге асырамыз 64 үстінде 48 .
Біз 1-ді, ал қалған 16-ны аламыз. q 1 = 1, r 1 = 16 болып шығады.
Екінші қадам - бөлу 48 16-ға қарай біз 3 аламыз. Яғни q2 = 3, а r 2 = 0.Осылайша, 16 саны шарттағы сандар үшін ең үлкен ортақ бөлгіш болып табылады.
Жауап: gcd(64, 48) = 16.
2-мысал
Сандардың GCD дегеніміз не 111 және 432 ?
Шешім
Бөлу 432 үстінде 111 . Евклид алгоритмі бойынша 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 теңдік тізбегін аламыз.
Осылайша, сандардың ең үлкен ортақ бөлгіші 111 және 432 3 болып табылады.
Жауап: gcd(111, 432) = 3.
3-мысал
661 және 113 сандарының ең үлкен ортақ бөлгішін табыңыз.
Шешім
Біз сандарды ретімен бөліп, GCD аламыз (661 , 113) = 1 . Бұл 661 және 113 салыстырмалы жай сандар екенін білдіреді. Егер біз жай сандар кестесіне қарасақ, біз оны есептеулерді бастамас бұрын анықтай аламыз.
Жауап: gcd(661, 113) = 1.
Сандарды жай факторларға бөлу арқылы GCD табу
Екі санның ең үлкен ортақ бөлгішін көбейткіштер әдісімен табу үшін осы екі санды ыдырату арқылы алынған және оларға ортақ барлық жай көбейткіштерді көбейту керек.
4-мысал
220 және 600 сандарын жай көбейткіштерге бөлсек, екі көбейтіндіні аламыз: 220 = 2 2 5 11және 600 = 2 2 2 3 5 5. Бұл екі өнімдегі ортақ факторлар 2, 2 және 5 болады. Бұл NOD дегенді білдіреді (220, 600) = 2 2 5 = 20.
5-мысал
Сандардың ең үлкен ортақ бөлгішін табыңыз 72 және 96 .
Шешім
Сандардың барлық жай көбейткіштерін табыңыз 72 және 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Екі санның жалпы жай көбейткіштері: 2 , 2 , 2 және 3 . Бұл NOD дегенді білдіреді (72, 96) = 2 2 2 3 = 24.
Жауап: gcd(72, 96) = 24.
Екі санның ең үлкен ортақ бөлгішін табу ережесі ең үлкен ортақ бөлгіштің қасиеттеріне негізделген, оған сәйкес gcd (m a 1 , m b 1) = m gcd (a 1 , b 1) , мұндағы m - кез келген натурал сан. .
Үш немесе одан да көп сандардың GCD табу
Біз GCD табуымыз керек сандар санына қарамастан, біз екі санның қатарынан GCD табудан тұратын бірдей алгоритмді ұстанамыз. Бұл алгоритм келесі теореманы қолдануға негізделген: бірнеше сандардың GCD a 1 , a 2 , … , a kсанына тең d k, ол gcd дәйекті есептеуінде кездеседі (a 1 , a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .
6-мысал
78 , 294 , 570 және төрт санының ең үлкен ортақ бөлгішін табыңыз. 36 .
Шешім
Белгілеуді енгізейік: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.
78 және 294 сандарының GCD табудан бастайық: d2= GCD (78 , 294) = 6 .
Енді табуды бастайық d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Евклид алгоритмі бойынша 570 = 6 95 .Соны білдіреді d 3 = GCD (6 , 570) = 6 .
d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) табыңыз. 36 6-ға қалдықсыз бөлінеді. Бұл бізге алуға мүмкіндік береді d4= GCD (6 , 36) = 6 .
d4 = 6, яғни GCD (78 , 294 , 570 , 36) = 6 .
Жауап:
Енді сол және басқа сандар үшін GCD есептеудің басқа әдісін қарастырайық. Сандардың барлық жалпы жай көбейткіштерін көбейту арқылы gcd таба аламыз.
7-мысал
78 , 294 , 570 және сандарының gcd мәнін есептеңдер 36 .
Шешім
Мына сандарды жай көбейткіштерге бөлейік: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .
Барлық төрт сан үшін ортақ жай көбейткіштер 2 және 3 сандары болады.
НОД екен (78, 294, 570, 36) = 2 3 = 6.
Жауап: gcd(78 , 294 , 570 , 36) = 6 .
Теріс сандардың gcd мәнін табу
Егер теріс сандармен жұмыс істеу керек болса, онда біз ең үлкен ортақ бөлгішті табу үшін осы сандардың модульдерін пайдалана аламыз. Таңбалары қарама-қарсы сандар: сандар қасиетін біле отырып, біз мұны істей аламыз nжәне -nбөлгіштері бірдей.
8-мысал
Теріс бүтін сандардың gcd мәнін табыңыз − 231 және − 140 .
Шешім
Есептеулерді орындау үшін шартта берілген сандардың модульдерін алайық. Бұл 231 және 140 сандары болады. Оны қысқаша айтып көрейік: GCD (− 231 , − 140) = GCD (231, 140) . Енді екі санның жай көбейткіштерін табу үшін Евклид алгоритмін қолданайық: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 және 42 = 7 6. Біз gcd (231, 140) = 7 аламыз .
Ал NOD бері (− 231 , − 140) = GCD (231 , 140) , содан кейін сандардың gcd − 231 және − 140 тең 7 .
Жауап: gcd (− 231 , − 140) = 7 .
9-мысал
585, 81 және үш санның gcd мәнін анықтаңыз − 189 .
Шешім
Жоғарыдағы тізімдегі теріс сандарды олардың сандарымен ауыстырайық абсолютті мәндер, біз GCD аламыз (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Содан кейін біз барлық берілген сандарды жай көбейткіштерге бөлеміз: 585 = 3 3 5 13, 81 = 3 3 3 3 және 189 = 3 3 3 7. 3 және 3 жай көбейткіштері үш санға ортақ. gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 болады.
Жауап: GCD (− 585 , 81 , − 189) = 9 .
Мәтінде қатені байқасаңыз, оны бөлектеп, Ctrl+Enter пернелерін басыңыз
