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.

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

sửa

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

Khi đó tồn tại duy nhất các số nguyên qr 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à 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 qr được gọi là phép chia với dư.

Ví dụ

sửa
  • 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

sửa

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

Sự tồn tại

sửa

Xét tập hợp

 

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à adn ≥ 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à ad(−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 = (ar)/d, thì qr 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ì rd suy ra a-qdd. 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 Sr’=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 qr.

Tính duy nhất

sửa

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

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

Nếu d > 0 thì r' rr < dd+r' , và như vậy (r-r' ) < d. còn nếu d < 0 thì rr' 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.

Liên kết

sửa

Tham khảo

sửa