به نام خدا
قضیۀ بزو: فرض کنید $a$ و $b$ دو عدد صحیح باشند که دست کم یکی از آنها مخالف صفر است. در این صورت دو عدد صحیح $r$ و $s$ را میتوان یافت بهطوری که: $d=ra+sb$ ($d$ ب. م. م $a$ و $b$ است). بهعبارت دیگر حداقل یک ترکیب خطی از دو عدد صحیح $a$ و $b$ مساوی ب. م. م آنها خواهد بود.
این قضیه را نخستین بار ریاضیدان فرانسوی اتین بزو در کتابش «نظریۀ عمومی معادلههای جبری» اثبات کرد.
اثبات:
مجموعه کلیه ترکیبهای خطی مثبت $a$ و $b$ را $P$ مینامیم. یعنی:
$$P=\{ax+by|x,y \in \mathbb{Z},ax+by>0\}$$
مجموعۀ $P$ بهوضوح ناتهی است. زیرا مثلاً اگر $y$ ناصفر باشد، با $x=0,y=b$ یک عضو مثبت برای آن بهدست میآید. چون همۀ اعضای $P$ مثبتاند، پس $P$ کوچکترین عضو دارد. آن را $d$ مینامیم و فرض میکنیم $d=ax'+by' >0$. ادعا میکنیم $d$ مساوی ب. م. م $a$ و $b$ است. برای اینکار، $a$ را بر $d$ تقسیم میکنیم. بنابر الگوریتم تقسیم، خارج قسمت $q$ و باقیمانده $r$ (که $ 0\leq r\leq d$) وجود دارند که: $a=dq+r$. حال باید نشان دهیم $r=0$. اگر $r>0$ آنگاه چون داریم:
$$r=a-dq=a-(ax'+by')q=a-ax'q-by'q=a(1-ax')+b(-y'q)$$
یعنی یک ترکیب خطی از $a$ و $b$ برابر با $r$ مثبت شدهاست که عددی کمتر از $d$ است. این تناقض است. زیرا $d$ کوچکترین ترکیب خطی مثبت $a$ و $b$ بود. پس فرض اولیه درست نبود. یعنی داریم $r=0$. بهعبارت دیگر $a$ و مشابهاً $b$ بر $d$ بخشپذیراند. ثابت شد $d$ مقسومعلیه مشترک $a$ و $b$ است. اثبات بزرگترین مقسومعلیه مشترک بودن آن ماندهاست. اگر $d'$ ب. م. م آن دو باشد، چون $a$ و $b$ هر دو بر $d'$ بخشپذیراند، پس هر ترکیب خطی آن دو نیز بر $d'$ بخشپذیر است. بهویژه $d=ax'+by'$. پس $d$ از $d'$ کوچکتر نیست و بهعبارت دقیقتر، $d$ برابر با خود $d'$ است.
منبع: Wikipedia - قضیۀ بزو
