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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

به ازای اعداد صحیح a و b که b مخالف صفر باشد، اعداد صحیح یکتایی مانند q و r وجود دارند به طوریکه:

(در این تعریف، q را خارج قسمت، r را باقی‌مانده، a را مقسوم و b را مقسوم‌علیه می‌نامند)

اثبات[ویرایش]

در واقع در اثبات قضیه، مجموعه {a−|b|q>0:q∈Z}{a−|b|q>0:q∈Z} را در نظر میگیریم و نشان می دهیم که غیر تهی است و دارای کوچکترین عضو است و کوچکترین عضو آن را با rr نمایش می دهیم. یعنی به ازای عددی صحیح qq داریم r=a−b|q|r=a−b|q| . اگر r>|b|r>|b| در اینصورت r−b=a−b(q+1)r−b=a−b(q+1) که بنابر تعریف عضوی از مجموعه ی بالا است. اما r−|b|<rr−|b|<r که این با کوچکترین عضو بودن rr در تناقض است. پس باید r≤|b|r≤|b| .

برای دومی هم فرض کنیم که یکتا نباشند یعنی a=bq+r0≤r<|b| a=bq+r0≤r<|b| a=bq′+r′0≤r′<|b′| a=bq′+r′0≤r′<|b′| اگر r≠r′r≠r′ پس می توانیم فرض کنیم r′>rr′>r در اینصورت r′−r=|b|(q−q′)r′−r=|b|(q−q′) یعنی |b||r′−r|b||r′−r و لذا b≤r′−rb≤r′−r . در حالیکه از 0≤r<|b|,0≤r′<|b′|0≤r<|b|,0≤r′<|b′| نتیجه می شود r′−r<|b|r′−r<|b| که تناقض است. پس r′=rr′=r و لذا |b|(q−q′)=0|b|(q−q′)=0 و چون b≠0b≠0 پس q−q′=0q−q′=0 لذا q=

منابع[ویرایش]

  • ریاضیات گسسته دوره پیش‌دانشگاهی. چاپ ۱۳۸۱. شرکت چاپ و نشر کتاب‌های درسی ایران. ۳۱. 

این قضیه بیانگر همان رابطه تقسیمی است که در دوران ابتدائی به صورت بسیار ساده آموزش داده شده است. قضیه الگوریتم تقسیم برای حالتی که مقسوم یا مقسوم علیه یا هر دو منفی باشند نیز معتبر است. http://math.irancircle.com/4230/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%D9%8A%D8%AA%D9%85-%D8%AA%D9%82%D8%B3%D9%8A%D9%85?show=4233#a4233