Phép chia với số dư

Cơ sở lý thuyết của phép chia với dư là một định lý trong lý thuyết số. Phép chia này được áp dụng trong thuật toán Euclid để tìm ước số chung lớn nhất của hai số nguyên khác không.

Định lý về phép chia với số dư

Giả sử cho hai số nguyên a và d, với d ≠ 0

Khi đó tồn tại duy nhất các số nguyên q và r sao cho a = qd + r và 0 ≤ r < | d |, trong đó | d | là giá trị tuyệt đối của d.

Các số nguyên trong định lý được gọi như sau

• q được gọi là thương khi chia a cho d. Đôi khi nó còn được gọi là thương hụt.
• r được gọi là dư khi chia a cho d
• d được gọi là số chia
• a được gọi là số bị chia

Phép toán tìm q và r được gọi là phép chia với dư.

Ví dụ

• Nếu a = 7 và d = 3, khi đó q = 2 và r = 1, vì 7 = (2)(3) + 1.
• Nếu a = 7 và d = −3, khi đó q = −2 và r = 1, vì 7 = (−2)(−3) + 1.
• Nếu a = −7 và d = 3, khi đó q = −2 và r = -1, vì −7 = (−2)(3) - 1
• Nếu a = −7 và d = −3, khi đó q = 2 và r = -1, vì −7 = (2)(−3) - 1.

Chứng minh

Chứng minh định lý bao gồm hai phần: đầu tiên là chứng minh sự tồn tại của q và r, thứ hai là chứng minh tính duy nhất của q và r.

Sự tồn tại

Xét tập hợp

$S=\left\{a-<!--\; -\; -->n\mathrm{d\; <div\; class="min-w-[250px]\; max-w-[94vw]\; md:max-w-[770px]">\; <ins\; class="adsbygoogle"\; style="display:block;\; text-align:center;"\; data-ad-layout="in-article"\; data-ad-format="fluid"\; data-ad-client="ca-pub-9247024304160346"\; data-ad-slot="4115752014"></ins>\; </div>}:n\in <!--\; \in \; -->Z\right\}$

Ta khẳng định rằng S chứa ít nhất một số nguyên không âm. Có hai trường hợp như sau.

• Nếu d < 0, thì −d > 0, và theo tính chất Archimede, có một số nguyên n sao cho (−d)n ≥ −a, nghĩa là a − dn ≥ 0.
• Nếu d > 0, thì cũng theo tính chất Archimede, có một số nguyên n sao cho dn ≥ −a, nghĩa là a − d(−n) = a + dn ≥ 0.

Như vậy S chứa ít nhất một số nguyên không âm. Theo nguyên lý sắp thứ tự tốt, trong S có một số nguyên không âm nhỏ nhất, ta gọi số đó là r. Đặt q = (a − r)/d, thì q và r là các số nguyên và a = qd + r.

Ta còn phải chỉ ra rằng 0 ≤ r < |d|. Tính không âm của r là rõ ràng theo cách chọn r. Ta sẽ chứng tỏ dấu bất đẳng thức thứ hai.

Giả sử ngược lại r ≥ |d|. Vì d ≠ 0, r > 0, nên d > 0 hoặc d < 0.

• Nếu d > 0, thì r ≥ d suy ra a-qd ≥ d. Từ đó a-qd-d ≥0, lại dẫn tới a-(q+1)d ≥ 0. Do đó, nếu đặt r’='a-(q+1)d thì r’ thuộc S và r’=a-(q+1)d=r-d <r, điều này mâu thuẫn với tính chất r là phần tử không âm nhỏ nhất của S.
• Nếu d<0 thì r ≥ -d do đó a-qd ≥ -d. Từ đó suy ra rằng a-qd+d ≥0, tiếp tục suy ra r’= a-(q-1)d ≥ 0. Do đó, r’ thuộc S và, vì r’=r+d với d < 0 ta cór’= a-(q-1)d<r, mâu thuẫn với giả thiết r là số nguyên không âm nhỏ nhất trong S.

Như vậy ta đã chứng minh sự tồn tại của q và r.

Tính duy nhất

Giả sử rằng tồn tại q, q' , r, r' với 0 ≤ r, r' < |d| sao cho a = dq + r và a = dq' + r' . Không mất tính tổng quát giả sử q ≤ q' .

Từ hai đẳng thức trên ta có: d(q' - q) = (r - r' ).

Nếu d > 0, thì r' ≤ r và r < d ≤ d+r' , và vì thế (r-r' ) < d. Nếu d < 0, thì r ≤ r' và r' < -d ≤ -d+r, và do đó -(r- r' ) < -d. Trong cả hai trường hợp, ta có |r- r' | < |d|.

Mặt khác, đẳng thức d(q' - q) = (r - r' ) chứng tỏ rằng |d| chia hết cho |r- r' |; vì vậy |d| ≤ |r- 'r' | hoặc |r- r' |=0. Nhưng vì |r-r' | < |d|, nên chỉ có thể r=r' . Thay vào đẳng thức d(q' - q) = (r - r' ), ta có dq = dq' và vì d khác 0, nên q = q' . Tính duy nhất đã được chứng minh.

Liên kết

• Bàn luận phi chính thức về thuật toán chia và nguyên tắc sắp xếp tốt