تقسیم اقلیدسی
به ازای اعداد صحیح 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