Ең үлкен ортақ көбейткіш, сонымен қатар ең үлкен ортақ бөлгіш және ең үлкен ортақ көбейткіш ретінде белгілі, екі немесе одан да көп бүтін сандар бөлісетін бөлгіштердің ең үлкенін білдіреді..
a, b санының ең үлкен ортақ бөлгіші (a, b) деп белгіленеді. Сол сияқты a, b, c сандарының ең үлкен ортақ бөлгіші (a, b, c) деп белгіленеді. Бірнеше бүтін сандардың ең үлкен ортақ бөлгіштерінің таңбалары бірдей.
Ең үлкен ортақ бөлгішті табудың көптеген жолдары бар. Жалпы факторларға жай көбейткіштерге бөлу, қысқа бөлу, жылжымалы фазалық бөлу және тағы басқа алу жатады.
Ең үлкен ортақ бөлгішке сәйкес ұғым ең кіші ортақ еселік, ал a, b санының ең кіші ортақ еселігі [a, b] түрінде жазылады..
Егер а саны b санына бөлінетін болса, а саны b санының еселігі, ал b саны а санының бөлгіші деп аталады..
Бөлінгіштер де, көбейткіштер де бір бүтін санның екіншісіне қатынасын білдіреді және жалғыз өмір сүре алмайды. Мысалы, 16-ны белгілі бір санның еселігі, ал 2-ді белгілі бір санның бөлгіші деп айта аламыз, бірақ 16-ға еселік және 2-бөлгіш деп бөлек айта алмаймыз..
Екі немесе одан да көп бүтін сандардың Ең үлкен ортақ бөлгіші (GCF) деп те аталатын Ең үлкен ортақ бөлгіш (GCD) олардың барлығын дәл бөлетін ең үлкен оң сан (қалдық қалдырмай).
Мысалы, GCD 18 және 24 6, себебі 6 - екеуін тең бөлетін ең үлкен сан.
GCD келесілер үшін пайдалы:
Бөлшектерді ең кіші мүшелеріне дейін жеңілдету.
Факторингжәне математикалық теңдеулерді шешу.
Қатынастарды ең қарапайым түріне келтіру.
сандар теориясының есептерін шешу.
Бүтін сандардағы жалпы үлгілерді табу немесе қайталанатын құрылымдарға негізделген алгоритмдерді оңтайландыру.
Бұл артықшылықты жоюға және математикалық және нақты әлем қолданбаларында тиімділікті табуға көмектеседі.
Екі санның GCD-ін табудың бірнеше әдісі бар:
Тізім факторлары: Әрбір санның барлық бөлгіштерін тізіп, олардың ортақ ең үлкенін табыңыз.
Жай көбейткіштерге бөлу: Екі санды да жай көбейткіштерге бөліп, ортақ сандарды көбейтіңіз.
Евклид алгоритмі: үлкен саннан кіші санды қайта-қайта алып тастаңыз немесе қалдық нөлге тең болғанша қалдықпен бөлуді қолданыңыз. Соңғы нөлдік емес қалдық - GCD.
GCD(a, b) үшін Евклид алгоритмінің мысалы:
GCD(48, 18):
48 ÷ 18 = 2 қалдық 12
18 ÷ 12 = 1 қалдық 6
12 ÷ 6 = 2 қалдық 0
→ GCD – 6
GCD-ны келесі жағдайларда пайдаланыңыз:
Бөлшектерді немесе қатынасты ең қарапайым түрге келтіру.
Диофантин теңдеулерін шешу (бүтін шешімдері бар теңдеулер).
оңтайландыру алгоритмдері.
Екі санның салыстырмалы жай екенін анықтау (яғни, олардың GCD мәні 1).
Элементтерді ең үлкен тең өлшеммен топтарға бөлу (мысалы, бір нәрсені адамдар немесе контейнерлер арасында біркелкі бөлу).
GCD негізгі арифметикада да, одан да жетілдірілген сандар теориясында немесе алгоритм дизайнында негізгі болып табылады.
