Phép chia có 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 ứng dụng trong giải thuật Euclid tìm ước chung lớn nhất của hai số nguyên khác không.

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ư.

• 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 định lý gồm hai phần: đầu tiên chứng minh sự tồn tại của q và r, thứ hai, chứng minh tính duy nhất của q và r.

Xét tập hợp

S = { a − n d : n ∈ Z } {displaystyle S=left{a-nd:nin mathbb {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ố ấy 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ử nguợ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.

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à như vậy (r-r' ) < d. còn 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 |r- r' |; do đó |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.

• Informal discussion of the division algorithm and well-ordering principle