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

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

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

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

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

شیتەڵکردن دەستکاری

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

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

{\begin{array}{r|l}48&2\\24&2\\12&2\\6&2\\3&3\\1&\end{array}}

48=2^{4}\cdot 3\,

{\begin{array}{r|l}60&2\\30&2\\15&3\\5&5\\1&\end{array}}

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

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

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

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

نموونە دەستکاری

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

واتە

4

=

(12,8)

.

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

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

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

^[١]

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

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

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

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

d=ra+sb

بە زمانی پرۆگرامکردنی 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);
}