برای مشاهده تمام دروس، لطفا در سایت ثبت نام نمایید.

پس از ثبت نام در سایت، تا 24 ساعت بعد می‌توانید به صورت رایگان به تمام محتوای وب سایت دسترسی داشته باشید.

اگر در گذشته ثبت نام کرده‌اید:

ورود به حساب کاربری
لیست

سرفصل‌های این مبحث

نظریه اعداد

  • قضیه تقسیم
  • بخش پذیری در اعداد صحیح
  • ب‌ م‌ م (مقدمه)
  • ب‌ م‌ م (تعریف و قضایا)
  • ب‌ م‌ م (قضیه بزو)
  • ب‌ م‌ م (الگوریتم اقلیدسی)
  • ک‌ م‌ م (مقدمه)‌
  • ک‌ م‌ م (تعریف و قضایا)
  • قضیه اساسی حساب استدلالی
  • اعداد اول (تعریف)
  • اعداد اول (کاربردها)
  • هم‌ نهشتی (تعریف و قضایا)
  • هم‌ نهشتی (آزمون‌ های بخش‌ پذیری)
  • هم‌ نهشتی (تعیین دو رقم سمت راست یک عدد)
  • هم‌ نهشتی (تعیین رقم یکان یک عدد)
  • هم‌ نهشتی (دسته کامل مانده‌ ها)
  • هم‌ نهشتی (قضیه اولر و فرما و ویلسون)
  • هم‌ نهشتی (معادلات)
  • معادلات سیال (حالت اول)
  • معادلات سیال (حالت دوم)
  • معادلات سیال (حالت سوم)
  • معادلات سیال (حالت چهارم)
  • معادلات سیال (حالت پنجم)
  • معادلات سیال (حالت ششم)

قضیه تقسیم

آخرین ویرایش: 16 اسفند 1400
دسته‌بندی: نظریه اعداد
امتیاز:

نظریه اعداد شاخه‌ای از ریاضیات است که به مطالعه اعداد صحیح 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 را بيابيد كه چون بر 11 تقسيم كنيم، باقيمانده تقسيم، نصف خارج قسمت شود.

       a  11q           r=q2¯a=11q+r=11q+q2     ;     0r<11


a=11q+q2       ;     0r<b0r<bq2<11q<22maxq=21a=11×21+212N


maxq=20a=11×20+202=230N

بزرگ‌ترين عدد طبيعی را بيابيد، به‌طوری كه باقيمانده تقسيم آن عدد بر 167، دو برابر مكعب خارج قسمت باشد.

اگر عدد مورد نظر را a بناميم، طبق داده های مساله و قضيه تقسيم داريم:


a=167q+r=167q+2q3    ;    0r<167


0r<167    ;    r=2q302q3<1670q3<83.50q3830q4


r=2q3  :q=0r=0a=0q=1r=2a=167×1+2=169q=2r=16a=167×2+16=350q=3r=54a=167×3+54=555q=4r=128a=167×4+128=796max a=796

دریافت مثال

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

اگر عدد صحیح 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 صحیح است. 

تمرین

عدد a مضرب 5 نيست، صورت های ممكنه آن را بنويسيد.

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


a=5q+r   ;    0r<5r=0a=5qr=1a=5q+1r=2a=5q+2r=3a=5q+3=5q+52=5q+52=5q+12=5q'2r=4a=5q+4=5q+51=5q+51=5q+11=5q'1


از حالات فوق در چهار حالت، عدد a مضرب 5 نيست. 

a=5k±1a=5k±2

نشان دهيد هر عدد صحيح به يكی از دو صورت 2k یا 2k+1 نوشته می‌شود.

فرض كنيد a يک عدد صحيح دل‌خواه باشد.


a را بر 2 تقسیم می‌کنیم، بنابر الگوريتم تقسيم داريم:

a=2k+r    ;   0r<2if   r=0a=2kif   r=1a=2k+1


اعداد به شكل 2k را اعداد زوج و اعداد به شكل 2k+1 را فرد گويند.

دریافت مثال

نکته

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

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

تمرین

اگر x عددی صحيح و فرد باشد، باقيمانده تقسيم x25 بر 8 را بنویسید.

یادآوری)

مربع هر عدد فرد، به‌شكل 8k+1 است که قبلا بررسی شد، این مطلب با مثال های عددی زیر هم مشخص می‌شود:

12=1=80+132=9=81+152=25=83+172=49=86+1             x2=x2=8k+1


پس اگر x عددی صحيح و فرد باشد:

x2=8k+1x25=8k+15x25=8k4x25=8k8+4x25=8k1+4    ;    k1=k'x25=8k'+4r=4

دریافت مثال

نکته

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

تمرین

در يک تقسيم، خارج قسمت 35 و باقيمانده 421 است.

حداكثر چند واحد به مقسوم عليه اضافه كرد تا مقسوم و خارج قسمت تغيير نكنند.

a=bq+ra=b35+421


در حقيقت بايد معلوم كنيم كه در 421 چند بار عدد 35 را می‌توان گنجاند:

42135=12/03=12

دریافت مثال

نکته

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 جمع می‌شود.

تمرین

در يک تقسيم، خارج قسمت برابر 21 و مقسوم عليه 8 است. 

اگر 24 به مقسوم اضافه كنيم، خارج قسمت جديد را به‌دست آورید.

طبق نكته بالا بايد 3 واحد به خارج قسمت قديم اضافه كنيم تا خارج قسمت جديد حاصل شود.


سه برابر مقسوم عليه را به مقسوم اضافه كرده ايم.

a=bq+ra=821+r0r<ba=821+ra+24=821+24+r=821+3+r

دریافت مثال

نکته

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

a=bq+rbq=arq=arb

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

تمرین

در تقسيم عدد صحيح a بر b خارج قسمت 12 و باقيمانده 93 شده است. 

حداكثر چه مقدار می‌توان به مقسوم عليه اضافه نموده تا خارج قسمت تغيير نكند؟

اگر حداكثر مقدار را x در نظر بگیریم:


a=bq+ra=12b+93a=12b+x+r'a=12b+12x+r'12b+93=12b+12x+r'12x=93r'x=93r'12


x باید ماکزیمم باشد.


بايد عددی را از 93 كم كنيم كه در ازای تقسيم آن بر 12 عددی به‌دست آيد كه در Z باشد، بنابراين:

if  r'=9x=93912=7

دریافت مثال

نکته

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

دریافت مثال

خرید پاسخ‌ها

قضیه تقسیم

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

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

برای مشاهده تمام دروس، لطفا در سایت ثبت نام نمایید.

پس از ثبت نام در سایت، تا 24 ساعت بعد می‌توانید به صورت رایگان به تمام محتوای وب سایت دسترسی داشته باشید.

اگر در گذشته ثبت نام کرده‌اید:

ورود به حساب کاربری