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

گەورەترین بەشدراوی ھاوبەش (بە ئینگلیزی: 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);
}