ب‌ م‌ م (قضیه بزو)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 03 شهریور 1400
دسته‌بندی: نظریه اعداد
امتیاز:
بازدید: 30 مرتبه

مقدمه‌ای بر قضیه بزو

قبل از بیان قضیه بزو، لازم است مقدمات زیر را بیان کنیم:

تمرین

دو عدد 12 و 18 را در نظر می‌گیریم. هر ترکیب خطی از این دو عدد به‌صورت 12x+18y است.  

چند ترکیب خطی از این دو عدد می‌نویسیم:

x=1y=1121+181=30x=3y=2123+182=0x=2y=1122+181=6x=3y=2123+182=72

آیا تمام ترکیبات خطی فوق بر 6 بخش پذیرند؟

12x+18y=62x+3y=6k


همان‌طور که ملاحظه می‌کنید، تمام ترکیبات خطی فوق بر 6 بخش پذیرند، که در آن 6 بزرگ‌ترین مقسوم علیه مشترک دو عدد 12 و 18 می‌باشد.

کدام‌یک از ترکیبات خطی دو عدد 12 و 18 مساوی ب.م.م این دو عدد است؟

اما آن‌چه مورد توجه ماست آن است که یکی از ترکیبات خطی دو عدد 12 و 18 مساوی ب.م.م این دو عدد یعنی 6 است که در این‌جا به ازای x=2y=1 اتفاق افتاده است. 


این مطلب به‌طور کلی برای هر دو عدد صحیح a و b برقرار است که در قضیه بزو آمده است.

قضیه بزو

قضیه

فرض کنید a و b دو عدد صحیحی باشند که دست‌کم یکی از آنها مخالف صفر است:  

در این‌صورت دو عدد صحیح r و s می‌توان یافت به‌طوری‌که:

ar+bs=a,b=d

یعنی حداقل یک ترکیب خطی از دو عدد صحیح a و b مساوی ب‌‌‌م‌م آن دو عدد است:

if  a,b=d      r  ,  sZ    ;    ra+sb=d

اثبات

مجموعه کلیه ترکیبات خطی مثبت a و b را در زیر مشاهده می‌کنید: 

A=ma+nb  m  ,  nZ    ;    ma+nb>0

این مجموعه، غیر تهی است زیرا:

a=±1×a+0×b>0  aAAb=0×a+±1×b>0  bA   A

A زیر مجموعه N یعنی AN می‌باشد و N خوش ترتیب است، زیرا مجموعه N تهی نیست و دارای عضو ابتدا است در نتیجه مجموعه A دارای عضو ابتدایی مانند d بوده و داریم:

  dAr,sZ   ;    d=ra+sb>0

باید ثابت کنیم که d همان ب‌م‌م دو عدد a و b هست، یعنی در دو شرط تعریف زیر صادق است:  

1   da  ,db2   c>0    ;    cacbcd

برای اثبات 1 داریم:

ابتدا a را بر d تقسیم می‌کنیم:

بنا بر قضیه تقسیم، اعداد صحیح منحصر به‌فرد q و t یافت می‌شود به‌قسمی‌که:

a=dq+t    ;     0td

ثابت می‌کنیم t=0 است.

بر اساس برهان خلف اگر t0 باشد، فرض می‌کنیم t>0 باشد: 

a=dq+tt=adq       ;    d=ra+sbt=ara+sbqt=a1rq+bsq    ;     1rq=m'Zsq=n'Zt=m'a+n'b>0t>0

t>0 است و این مطلب خلاف عضو ابتدا بودن d است در نتیجه t=0a=dq و به‌همین ترتیب ثابت می‌شود که ab.


برای اثبات 2 داریم:

c>0  ,  ca  ,  cb   c?dcacracbcsbcra+sbcdcd

نکته

1- عکس قضیه بزو در حالت کلی برقرار نمی‌باشد.

اگر عددی مانند d برابر با ترکیب خطی دو عدد صحیح مانند a و b باشد، نمی‌توان نتیجه گرفت که d ب‌م‌م دو عدد a و b است. 

به‌عنوان نمونه:

35+43=275,3=27


2- صورت و فرم دیگری از قضیه بزو به‌شکل زیر مطرح می‌شود:

اگر a و b دو عدد صحیح و حداقل یکی از آنها مخالف صفر باشد، در مجموعه زیر:  

A=ra+sb>0r  ,  sZ

عضو ابتدای مجموعه فوق بزرگ‌ترین مقسوم علیه مشترک a و b است، یعنی: 

d=minA=a,b


3- آن‌چه لازم است بدانیم این است که قضیه بزو فقط وجود r و s را بیان می‌کند، اما راه حل عملی برای پیدا کردن آنها ارائه نمی‌دهد، البته بعدا روش‌هایی برای یافتن آنها ارائه خواهیم داد.  

نتایج حاصل از قضیه بزو

if   ra+sb=1a,b=1

اثبات

هرگاه ترکیب خطی دو عدد صحیح a و b عدد 1 باشد، آن دو عدد نسبت به هم اولند و برعکس.

ثابت می‌کنیم:

if    ra+sb=1a,b=1

بنابر برهان خلف، فرض می‌کنیم a,b1:

a,b1c>1   ;   a,b=ccacracbcsbcra+sbc1c1

به یک تناقض رسیدیم پس فرض باطل است و a,b=1 است. 


ثابت می‌کنیم:

if   a,b=1ra+sb=1

بنابر قضیه بزو داریم:

if   a,b=1r  ,  sZ    ;    ra+sb=1

a,b=1abcac

نتیجه فوق به لم اقلیدس معروف است.

اثبات

abcbc=aqa,b=1r,sZ  ;  ra+sb=1


ra+sb=1c×ra+sb=c×1rac+sbc=c    ;    bc=aqrac+saq=carc+sq=c    ;    rc+sq=q'aq'=cac

a,b=dad,bd=1

اثبات

a,b=dr  ,  sZ    ;    ra+sb=d1dra+sb=1ddrad+sbd=1ad,bd=1

تساوی rad+sbd=1 ترکیب خطی از r و s هست و ثابت می‌شود که r,s=1 یعنی در قضیه بزو، ضرایب ترکیب خطی که d را می‌سازد، همواره نسبت به‌هم اول هستند.  

if    a,b=1  ,  a,c=1a,bc=1

اثبات

ثابت می‌کنیم:

if  a,b=1  ,  a,c=1a,bc=1

a,b=1  r1,s1Z   ;   r1a+s1b=1a,c=1  r2,s2Z   ;   r2a+s2c=1

r1a+s1b×r2a+s2c=1r1r2a2+r1s2ac+s1r2ab+s1s2bc=1ar1r2a+r1s2c+s1r2b+s1s2bc=1    ;    r1r2a+r1s2c+s1r2b=rs1s2=sra+sbc=1a,bc=1


ثابت می‌کنیم:

if   a,bc=1a,b=1  ,  a,c=1

a,bc=1ra+sbc=1ra+sbc    =1a,c=1ra+scb   =1a,b=1

فرمول فوق را به‌صورت زیر می‌توان بسط داد.

a,b1=1  ,  a,b2=1  ,  ...  ,  a,bn=1a,b1b2...bn=1

ab  ,  acab,c

اثبات

هرگاه عددی دو عدد را بشمارد، آن‌گاه همواره ب‌م‌م آن دو عدد را می‌شمارد.

فرض می‌کنیم b,c=d آن‌گاه ثابت می‌کنیم ad.

b,c=d   r  ,  sZ    ;    rb+sc=dabarbacascarb+sc=dad    

ak  ,  bk  ,  a,b=1abk

اثبات

akk=aq'bkk=bq''

a,b=1r,sZ  ;  ra+sb=1kra+sb=k1rak+sbk=k    ;    k=aq'k=bq''rabq''+sbaq'=kabrq''+sq'=k    ;    rq''+sq'=q     abq=kabk

if  pabpa       pb

p عددی اول است و یکی از دو عدد a و b را عاد می‌کند. 

اثبات

اگر pa حکم  ثابت است، اگر p|a باید p,a=1 آن‌گاه: 

if    p|ap,a=1

بر طبق لم اقلیدس داریم:

pabpb

a,b=d  ,  kNka,kb=kd

اثبات

هرگاه دو عدد صحیح a و b را در عدد طبیعی k ضرب کنیم، بزرگ‌ترین شمارنده مشترک آن دو عدد در k ضرب می‌شود.

ثابت می‌کنیم:

a,b=dka,kb=kd

a,b=d1       da  dbkdkb  2        x>0    ;      xka  ,  xkbx?kd


a,b=dr,sZ    ;    ra+sb=dkra+sb=kdrak+sbk=dk

xkaxrakxkbxsbkxrak+sbkxkdxkd


ثابت می‌کنیم:

ka,kb=kda,b=d

ka,kb=kd1       kdkadakdkbdb  2    c>0  ,  ca  ,  cbc?d

ka,kb=kdrka+skb=kdra+sb=dcacracbcsbcra+sb=dcdcd

if   an,bm=1a,b=1    ;    m  ,  nN

اثبات

if   an,bm=1ran+sbm=1ran1a+sbm1b=1    ;    r1=ran1s1=sbm1r1a+s1b=1a,b=1

if   a,b,cZ  ;    a,b=1  ,  ca  ,  dbc,d=1 

اثبات

a,b=1r,sZ  ;   ra+sb=1caa=ck1dbb=dk2

ra+sb=1rck1+sdk2=1rk1c+sk2d=1      ;   r1=rk1s1=sk2r1c+s1d=1c,d=1

if  a,b,cZ    ;    a,b=1  ,  ca+b  a,c=b,c=1

اثبات

a,b=1r  ,  sZ   ;   ra+sb=1

ثابت می‌کنیم b,c=1:

ca+ba+b=cka=ckbra+sb=1rckb+sb=1rkc+srb=1       ;     r1=rks1=srr1c+s1b=1c,b=1


ثابت می‌کنیم a,c=1:

ca+ba+b=ckb=ckara+sb=1ra+scka=1rsa+skc=1    ;    r1=rss1=skr1a+s1c=1a,c=1

قضیه

هر ترکیب خطی a و b مانند ax+by=t بر ب‌م‌م دو عدد a و b یعنی a,b=d بخش پذیر است:      

  ax+by=td=a,bdadaxdbdbydax+bydt

دریافت مثال

مثال‌ها و جواب‌ها

ب‌م‌م (قضیه بزو)

1,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید