گەورەترین بەشدراوی ھاوبەش

گەورەترین بەشدراوی ھاوبەش (داڕێژە:بە ئینگلیزی)، بریتییە لە گەورەترین ژمارە لە نێوان بەشدراوە ھاوبەشەکانی دوو ژمارە، گەورەترین بەشدراوی ھاوبەشی دوو ژمارەی $a$ و $b$ ھێما دەکرێ بە $(a, b)$ .

ڕێگاکانی ھەژمارکردنی گەورەترین بەشدراوی ھاوبەش

بە بەکارھێنانی کۆمەڵە بەشدراوەکان

لەم ڕێگەیەدا کۆمەڵەی بەشدراوەکانی ھەر دوو ژمارەکە دەنووسرێت، و پاشان بە بەراوردکردنی کۆمەڵەکان و بەشدراوە ھاوبەشەکان گەورەترین بەشدراوی ھاوبەش دەدۆزرێتەوە.

شیتەڵکردن

سەرەتا دوو ژمارەکە شیتەڵ دەکرێت بە کۆلکە سەرەتایییەکان، پاشان کۆلکە ھاوبەشەکان بە کەمترین توان لێک دەدرێن.

بۆ نموونە گەورەترین بەشدراوی ھاوبەش بۆ دوو ژمارەی $60$ و $48$ بریتییە لە $12$

\begin{matrix} 48 & 2 \\ 24 & 2 \\ 12 & 2 \\ 6 & 2 \\ 3 & 3 \\ 1 \end{matrix}

48 = 2^{4} \cdot 3

\begin{matrix} 60 & 2 \\ 30 & 2 \\ 15 & 3 \\ 5 & 5 \\ 1 \end{matrix}

60 = 2^{2} \cdot 3 \cdot 5

داڕێژە:Ltr

(48, 60) = 2^{2} \cdot 3 = 12

داڕێژە:Ltr/end

ئەلگۆریتمی ئیقلیدس

بە بەکارھێنانی ئەلگۆریتمی ئیقلیدس (ڕێگەی نێردیوانیشی پێ دەورترێت) دەتوانرێت گەورەترین بەشدراوی ھاوبەشی دوو ژمارە بدۆزرێتەوە.

نموونە

گەورەترین بەشدراوی ھاوبەش بۆ دوو ژمارەی $8$ و $12$ بریتییە لە $4$

واتە داڕێژە:Ltr

4

=

(12, 8)

.

داڕێژە:Ltr/end ڕێگایەکی دۆزینەوەی گەورەترین بەشدراوی ھاوبەشی دوو ژمارە، بە بەکارھێنانی دیاگرامی ڤەن: داڕێژە:Ltr

٤٨ = ٢ × ٢ × ٢ × ٢ × ٣،

١٨٠ = ٢ × ٢ × ٣ × ٣ × ٥.

داڕێژە:Ltr/end ^[١]

بچووکترین چەندجارەی ھاوبەش= ٢ × ٢ × ( ٢ × ٢ × ٣ ) × ٣ × ٥ = ٧٢٠

گەورەترین بەشدراوی ھاوبەش = ٢ × ٢ × ٣ = ١٢.

سەلمێنراوی بێزۆ (Bezout)

وا دابنێ $a$ و $b$ دوو ژمارەی تەواو بن کە لانیکەم یەکێکیان سیفر نییە. ئەگەر $(a, b) = d$ ئەوا، دوو ژمارەی تەواو وەکوو $r$ و $s$ بوونیان ھەیە و پاسادانی ئەم ھاوکێشە دەکەن: داڕێژە:Ltr

d = r a + s b

داڕێژە:Ltr/end

بە زمانی پرۆگرامکردنی C لە ڕێگەی خوارەوە گەورەترین بەشدراوی ھاوبەشی دوو ژمارە دەدۆزرێتەوە:

int GreatestCommonDivisor(int a, int b)
{
    int h;
    if (a == 0) return abs(b);
    if (b == 0) return abs(a);

    do {
        h = a % b;
        a = b;
        b = h;
    } while (b != 0);

    return abs(a);
}