Thuật toán Euclid

Kỳ trước chúng ta đã học về bổ đề Bezout. Hôm nay chúng ta sẽ học về thuật toán Euclid. Thuật toán này dùng để xác định các hệ số trong đẳng thức Bezout.

Trước hết chúng ta phát biểu bổ đề Bezout. 

Bổ đề Bezout. Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a ~x + b ~y.$$

Thuật toán Euclid mục đích đi tìm ước số chung lớn nhất $d$ của hai số $a$ và $b$, và xác định hai giá trị của $x$ và $y$ trong đẳng thức Bezout $$d = a ~x + b ~y.$$

Ý tưởng của thuật toán Euclid rất đơn giản và tự nhiên.

Bổ đề Bezout

Hôm nay chúng ta sẽ học về một kết quả rất hay trong số học, đó là bổ đề Bezout. Bổ đề này phát biểu như sau.

Bổ đề Bezout. Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a x + b y.$$

Muốn xác định giá trị của hai số $x$ và $y$ trong bổ đề Bezout, chúng ta có thể dùng thuật toán Euclid. Chúng ta sẽ học về thuật toán này vào kỳ sau.

Số nguyên tố

Hôm nay chúng ta sẽ tìm hiểu về số nguyên tố - những viên gạch cơ bản của số học.

Số nguyên tố là một số tự nhiên lớn hơn 1 mà không chia hết cho số nào cả, ngoại trừ nó chia hết cho 1 và chia hết cho chính nó. Ví dụ như 2, 3, 5, 7, 11, 13 là số nguyên tố. Số 9 không phải là số nguyên tố vì nó chia hết cho 3. Số 2012 không phải là số nguyên tố vì nó chia hết cho 2.