قضیه بزو

الگو:Pp-vandalism قضیه بزو یا اتحاد بزو الگو:به انگلیسی قضیه‌ای قدرتمند برای حلقه‌های جابجایی مجهز به الگوریتم تقسیم است. دو حالت خاص این قضیه، در مورد اعداد طبیعی و چندجمله‌ای‌ها معروف و پرکاربرد است. این قضیه را نخستین بار ریاضیدان فرانسوی اتین بزو در کتابش «نظریه عمومی معادله های جبری» اثبات کرد.

در مجموعه اعداد طبیعی

فرض کنید $a$ و $b$ دو عدد صحیح باشند که دست کم یکی از آنها مخالف صفر است. در این صورت دو عدد صحیح $r$ و $s$ را می‌توان یافت به طوری که: $d=ra+sb$ که در آن $d$ ب. م. م $a$ و $b$ است. به عبارت دیگر حداقل یک ترکیب خطی از دو عدد صحیح $a$ و $b$ مساوی ب. م. م آن‌ها خواهد بود.

صورت دیگر قضیهٔ بزو

فرض کنید $a$ عددی صحیح و $m$ عددی طبیعی باشد که $(a,m)=1$. در اینصورت عددی طبیعی یکتا مانند $a^{*}$ وجود دارد که $a{a}^{*}\equiv 1(modm)$ باشد و $a^{*}$ را وارون ضربی $a$ به پیمانهٔ $m$ مینامیم.

برای اعدادی که متباین نیستند

اگر $a$ عددی صحیح و $m$ عددی طبیعی باشد $(a,m)$ عدد در دستگاه کامل مانده های $m$ مانند $a^{*}$ وجود دارد که $a{a}^{*}\equiv (a,m)(modm)$

مثال

برای $a=10$ و $b=24$ یک ترکیب خطیشان باید برابر با ب. م. م شان، یعنی $2$ شود. اگر قرار دهیم $r=5,s=-2$ آنگاه $ax+by=10\times 5+24\times (-2)=2$ یا به عبارت دیگر $10\times 5\equiv 2(mod24)$
وارون ضربی 10 به پیمانهٔ 7 برابر 5 است؛ یعنی،$10\times 5=50\equiv 1(mod7)$

اثبات

مجموعه کلیه ترکیب‌های خطی مثبت $a$ و $b$ را $P$ می‌نامیم. یعنی: الگو:چپ‌چین $P=\{ax+by|x,y\in \mathbb{Z},ax+by>0\}$ الگو:پایان چپ‌چین

مجموعه $P$ به وضوح ناتهی است. زیرا مثلاً اگر $y$ ناصفر باشد، با $x=0,y=b$ یک عضو مثبت برای آن به دست می‌آید. چون همه اعضای $P$ مثبت اند، پس $P$ کوچکترین عضو دارد. آن را $d$ می‌نامیم و فرض می‌کنیم $d=a{x}^{\prime }+b{y}^{\prime }>0$. ادعا می‌کنیم $d$ مساوی ب. م. م $a$ و $b$ است. برای این کار، $a$ را بر $d$ تقسیم می‌کنیم. بنابر الگوریتم تقسیم، خارج قسمت $q$ و باقی‌مانده $r$ (که $0\le r\le d$) وجود دارند که: $a=dq+r$. حال باید نشان دهیم $r=0$ اگر $r>0$ آنگاه چون داریم الگو:چپ‌چین $r=a-dq=a-(a{x}^{\prime }+b{y}^{\prime })q=a-a{x}^{\prime }q-b{y}^{\prime }q=a(1-q{x}^{\prime })+b(-y^{\prime }q)$ الگو:پایان چپ‌چین یعنی یک ترکیب خطی از $a$ و $b$ برابر با $r$ مثبت شده‌است که عددی کم تر از $d$ است. این تناقض است. زیرا $d$ کوچکترین ترکیب خطی مثبت $a$ و $b$ بود. پس فرض اولیه درست نبود. یعنی داریم $r=0$. به عبارت دیگر $a$ و مشابها $b$ بر $d$ بخش پذیر اند. ثابت شد $d$ مقسوم علیه مشترک $a$ و $b$ است. اثبات بزرگترین مقسوم علیه مشترک بودن آن مانده‌است. اگر $d^{\prime }$ ب. م. م آن دو باشد، چون $a$ و $b$ هر دو بر $d^{\prime }$ بخش پذیر اند، پس هر ترکیب خطی آن دو نیز بر $d^{\prime }$ بخش پذیر اند. به ویژه $d=a{x}^{\prime }+b{y}^{\prime }$. پس $d$ از $d^{\prime }$ کوچکتر نیست و به عبارت دقیق تر، خود $d^{\prime }$ است.

در مجموعه چندجمله‌ای‌های با ضرایب صحیح

اگر $a(x)$ و $b(x)$ دو چندجمله‌ای با ضرایب صحیح باشند، آنگاه چندجمله‌ای‌های $r(x)$ و $s(x)$ با ضرایب صحیح وجود دارند که $a(x)\times r(x)+b(x)\times s(x)$ برابر با ب. م. م $a(x)$ و $b(x)$ شود.

اثبات

چون در مجموعه چندجمله‌ای‌های با ضرایب صحیح، الگوریتم تقسیم درست است، مشابه اثبات قضیه برای مجموعه اعداد طبیعی، برای این صورت نیز جواب می‌دهد. (البته با تغییر اسامی و متغیرها)

منابع

• بهشتی زواره، رویا، و مریم میرزاخانی. نظریه اعداد. تهران: انتشارات فاطمی.