قضیه تقسیم

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

نظریه اعداد شاخه‌ای از ریاضیات است که به مطالعه اعداد صحیح Z و در حالت خاص، اعداد طبیعی N در هم نهشتی ها، کاربردهای بسیاری در دانش کامپیوتر، از جمله حساب با اعداد صحیح بزرگ، رمز نگاری فایل حافظه کامپیوتری و ایجاد اعداد تصادفی دارد.

وقتی با اعداد صحیح سروکار داریم، نمی‌توانیم نسبت به الگوها و خواص بسیاری که این اعداد از خودشان نشان می‌دهند، بی‌تفاوت باشیم.

مجموعه اعداد صحیح Z به‌صورت زیر، معرفی می‌شود:

Z=  ,  3  ,  2  ,  1  ,  0  ,  1  ,  2  ,  

مجموعه اعداد طبیعی N به‌صورت زیر، معرفی می‌شود: 

N=1  ,  2  ,  3  ,  ...

هم‌چنین هر عدد طبیعی و بزرگ‌تر از 1 مانند P که هیچ مقسم علیه مثبتی جز P و 1 نداشته باشد عدد اول نامیده می‌شود و مجموعه اعداد اول را با P نمایش می‌دهیم:

P=2  ,  3  ,  5  ,  7  ,  11  ,  13  ,  ...

یادآوری

اگر SZ ناتهی و از پایین (بالا) کراندار باشد، آن‌گاه S عضو ابتدا (عضو انتها) دارد. اصل استقرای ریاضی معادل خوش ترتیب بودن Z است.

قضیه

الگوریتم تقسیم

فرض کنید a و b دو عدد صحیحی باشند به‌طوری‌که b0 در این‌صورت اعداد صحیح منحصر به‌فردی مانند q و r می‌توان یافت به‌طوری‌که داشته باشیم:

     a     b  q         ¯ra=bq+r    ;    0r<b

a را مقسم می‌نامیم.

b را مقسم علیه می‌نامیم.

q را خارج قسمت می‌نامیم.

r را باقیمانده می‌نامیم.

اثبات

حالت اول- اگر b>0 باشد.

مجموعه زیر را در نظر می‌گیریم:

S=axb  xz  ,  axb0

این مجموعه ناتهی است زیرا کافی است قرار دهیم x=a، بنابراین خواهیم داشت: 

axb=aabaab=a+ab    ;    a+aba+aaab0

بنابراین S زیرمجموعه ناتهی از اعداد طبیعی است و بنابر اصل خوش ترتیبی دارای عضو ابتدایی است که آن را r می‌نامیم.

چون rS می‌باشد، پس عدد صحیحی مانند q وجود دارد به‌طوری‌که: 

r=abq    ;    r0

حال ادعا می‌کنیم که r<b است زیرا در غیر این‌صورت طبق برهان خلف بایستی rb باشد:

rbrb0    ;    r=abqrb=abqb0rb=abq+10rbS

با توجه به‌فرض که rb اما r-b>r یعنی rbS که یک تناقض است، بنابراین:    

0r<b

حال نشان می‌دهیم q و r منحصر به فرد است، برای این کار فرض کنیم a به دو صورت زیر نوشته شود: 

a=bq+ra=bq'+r'

طرفین سمت راست دو تساوی فوق با هم برابر هستند:

bq+r=bq'+r'r'r=bqbq'r'r=bqq'r'r=bqq'

0r'<b0r<br'r<bbqq'<bqq'<1qq'=0


حالت دوم- اگر b<0 باشد.

در این حالت b=b>0 لذا به‌حالت اول بر می‌گردیم.

تمرین

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

25÷7

      25  73    4¯25=73+4    ;    04<7

-25÷7

      25  73    4¯25=73+4  


در تقسیم فوق نمی‌توانیم -4 را به‌عنوان باقیمانده معرفی کنیم زیرا طبق قضیه تقسیم باقیمانده باید نامنفی و کوچک‌تر از مقسوم علیه باشد.


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

25=73425=7347+725=737+325=731+3    ;    q=3125=7q+3


در تساوی جدید باقیمانده را به‌صورت r=3 معرفی می‌کنیم.

تمرین

اگر باقیمانده تقسیم اعداد m و n بر 17 به‌ترتیب 5 و 3 باشد، باقیمانده تقسیم عدد زیر را بر 17 را به‌دست آورید. 

(2m-5n)

m=17q1+52m=217q1+52m=2×17q1+10n=17q2+35n=517q2+35n=5×17q2+15


2m5n=2×17q1+105×17q2+152m5n=172q15q252m5n=172q15q2517+172m5n=172q15q21+122m5n=17q+12r=12

دریافت مثال

افراز مجموعهبه‌کمک قضیه الگوریتم تقسیم 

اگر عدد صحیح a را بخواهیم بر 5 تقسیم کنیم، این عدد صحیح یا بر 5 تقسیم پذیر است یعنی r=0 یا باقیمانده تقسیم آن بر 5 عدد 1 یا 2 یا 3 یا 4 است، به‌عبارت دیگر:

a=5q+0a=5q+1a=5q+2a=5q+3a=5q+4

و چون aZ یک عدد دل‌خواه در نظرگرفته شده بود، می‌توان گفت که هر عدد صحیح را می‌توان به یکی از 5 صورت فوق نوشت.

تعریف- فرض کنید a و k دو عدد صحیحی باشند به‌طوری‌که k0 در این‌صورت اعداد صحیح منحصر به‌فردی مانند q و r می‌توان یافت به‌طوری‌که داشته باشیم:

      a  kq    r¯a=kq+r    ;    0r<k

با توجه به این‌که 0r<k یعنی مقادیری که r می‌پذیرد، به‌صورت زیر است:

r=0  ,  1  ,  2  ,  .....  ,  k1

هر عدد صحیح مانند a را می‌توان به یکی از k صورت زیر نوشت:

a=kq+0a=kq+1a=kq+2   a=kq+k1

با این کار توانسته‌ایم مجموعه Z را دقیقا به k زیر مجموعه خودش افراز کنیم.

تمرین

عدد صحیح و فرد a را در نظر بگیرید:

این عدد را به یکی از دو صورت 4k+1 یا 4k+3 بنویسید. 

فرض کنیم aZ و عددی فرد باشد. اگر a  را بر 4 تقسیم کنیم، خواهیم داشت:

      a  4q    r¯a=4q+r    ;    0r<4


با توجه به این‌که 0r<4 یعنی داریم:

r=0  ,  1  ,  2  ,  3


 عدد a را می‌توان به یکی از 4 صورت زیر نوشت:

1   :   p=4k+0    ;    A1=aa=4k2   :   p=4k+1    ;    2=aa=4k+13   :   p=4k+2    ;    A3=aa=4k+24   :   p=4k+3    ;    A4=aa=4k+3


چهار مجموعه A4  ,  A3  ,  A2  ,  A1 مجموعه Z را افراز می‌کند.


حالات a=4ka=4k+2 زوج هستند و حالات a=4k+1a=4k+3 فرد هستند.  

نشان دهید که مربع هر عدد فرد به شکل 8t+1 نوشته می‌شود. (باقیمانده تقسیم مربع هر عدد فرد بر 8 مساوی با 1 است.)

a=4k+1a2=4k+12a2=16k2+8k+1a2=82k2+k+1a2=8t'+1a=4k+3a2=4k+32a2=16k2+24k+9a2=82k2+3k+1+1a2=8t''+1

تمرین

ثابت کنید اگر p>3 عددی اول باشد، آن‌گاه به یکی از دو صورت p=6k+1p=6k+5 نوشته می‌شود.  

کافی است p را بر 6 تقسیم کنیم، طبق قضیه الگوریتم تقسیم خواهیم داشت:

      p  6q    r¯p=6q+r    ;    0r<6


با توجه به این‌که 0r<6 یعنی داریم:

r=0  ,  1  ,  2  ,  3 , 4 , 5


1    :     p=6k+0=23k2    :     p=6k+13    :     p=6k+2=23k+14    :     p=6k+3=32k+1     ;    3p5    :     p=6k+4=23k+26    :     p=6k+5


p در حالات 5,3,1 زوج است و با اول بودنِ آن در تناقض است.


 p در حالت 4 مضربی از عدد 3 است و با اول بودنِ آن در تناقض است.


 p در حالات 6,2 صحیح است. 

دریافت مثال

نکته

1- اگر a عدد فردی باشد که نتوان آن را به‌صورت 8k+1 نوشت، در این‌صورت a مربع کامل نیست.

به‌عنوان نمونه عدد 25 را می‌توان به‌صورت 52=25=83+1 نوشت پس مربع کامل است. 

دریافت مثال

نکته

2- اگر a و b دو عدد طبیعی باشند به‌طوری‌که a<b باشد، در این‌صورت باقیمانده تقسیم a بر b خود عدد a است.  

        a   b       0¯     0         a                                  a=b0+a

بنابراین باقیمانده هر یک از اعداد n1  ,  ...  ,  4  ,  3  ,  2  ,  1 بر n به‌ترتیب برابر است با:

n1  ,  ...  ,  4  ,  3  ,  2  ,  1

نکته

3- اگر a و b دو عدد طبیعی باشند به‌طوری‌که a=bq+r0r<b در این‌صورت q=ab است.  

منظور از ab جزءصحیح کسر ab است. 

اثبات

a=bq+rab=bbq+rbab=q+rb0r<b0rb<10+qrb+q<q+1qab<q+1ab=q

تعداد مضارب صحیح مثبتی از b که کوچک‌تر یا مساوی a هستند، برابر است با ab 

تمرین

تعداد مضارب مثبت 5 که کوچک‌تر یا مساوی 138 است را بیابید. 

138=527+3


تعداد مضارب مثبت 5 که کوچک‌تر یا مساوی 138 برابر است با:

1385=27

دریافت مثال

نکته

4- در هر تقسیم a=bq+r حداکثر به اندازه x=rq واحد می‌توان به مقسوم علیه اضافه کرد تا مقسوم و خارج قسمت تغییر نکنند.

اثبات

a=bq+ra=b+xq+r'a=bq+xq+r'    ;    a=bq+rbq+r=bq+xq+r'r'=rxq    ;    rxq0rxq0  xrqx=rq

دریافت مثال

نکته

5- اگر a و b دو عدد طبیعی باشند به‌طوری‌که a=bq+r0r<b با شرط a>b مقسوم از دو برابر باقیمانده بزرگ‌تر است:

a>2r

اثبات

روش اول-

a=bq+r0r<ba=bq+r>b+r>r+r=2ra>2r


روش دوم- واضح است که چون a و b دو عدد طبیعی هستند و a>b باشد، بنابراین q1:      

q1bqb    ;    b>rbq>rbq+r>r+ra>2r

نکته

6- در هر تقسیم، هرگاه هر مضرب صحیح و مثبتی از مقسوم علیه را به مقسوم بیفزاییم، باقیمانده تغییر نمی‌کند.

اثبات

a=bq+r0r<ba=bq+ra+nb=bq+nb+r=bq+n+r

واضح است که رابطه اخیر یک تقسیم را معرفی می‌کند که باقیمانده آن همان باقیمانده تقسیم عدد a بر عدد b یعنی r است.

در حالت کلی، اگر n برابر مقسوم علیه را به مقسوم اضافه کنیم، خارج قسمت جدید با عدد n جمع می‌شود.

دریافت مثال

نکته

7- به کسر زیر توجه کنید:

a=bq+rbq=arq=arb

می‌توانیم مقادیری مختلف را به a و r و b اضافه کنیم، به‌طوری که q یعنی خارج قسمت، تغییری نکند. 

دریافت مثال

نکته

8- همواره در تقسیم a بر b به‌طوری‌که a=bq+r باشد، حداکثر n=br1 واحد می‌توان به مقسوم اضافه کرد تا خارج قسمت تغییر نکند.

دریافت مثال

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

قضیه تقسیم

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

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