قضیه بزو

از ویکی‌پدیا، دانشنامهٔ آزاد.

قضیه ی بزو:فرض کنید a و b دو عدد صحیح ای باشند که دست کم یکی از آنها مخالف صفر است. در این صورت دو عدد صحیح r و s می توان یافت به طوری که: d=xa+yb که در آن d ب.م.م a و b است. یعنی حداقل یک ترکیب خطی از دو عدد صحیح a و b مساوی ب.م.م a و b است. اثبات: مجموعه کلیه ترکیبات خطی مثبت a و b را u می نامیم. مجموعه ی u ناتهی است. ادعا می کنیم d مساوی ب.م.م a و b است. برای این کار، a را بر d تقسیم می کنیم. بنابر الگوریتم تقسیم داریم:

                                           a=dq+r 
                              0 کوچکتر مساوی r و r کوچکتر از d

اگر r بزرگتر از 0 باشد خواهیم داشت:

                                     r=a-dq=a-axq-byq 
                                          r=a-aqx-bqy 

چون r بزرگتر از صفر باشد و r یک ترکیب خطی a و b است پس r عضو مجموعه ی u است. اما r کوچکتر از d است و این خلاف آن است که d عضو ابتدای u است بنابراین r=0 و لذا a بر d بخشپذیر است. به همین ترتیب b بر d بخشپذیر است. حال فرض کنید c یک شمارنده ی مشترک a و b باشد، از آنجا ax+by بر c بخشپذیر است یعنی d بر c بخشپذیر است و لذا c کوچکتر مساوی d است.