CHƯƠNG 1. KIẾN THỨC CHUẨN BỊ 20 (mod m) được gọi là cấp của a modulo m. Ta kí hiệu cấp của a modulo m bởi ordm a. Ta tìm cấp của 2 modulo 5.
Vậy cấp của 2 modulo 5 là 4 : ord5 2 = 4. Tìm cấp của 4 modulo 5. Vậy cấp của 4 modulo 5 là 2 : ord5 4 = 2. Để có thể tìm tất cả các nghiệm của đồng dư thức ax ≡ 1 (mod m), ta cần đến định lí sau Định lý 1.
Nếu a và m là các số nguyên nguyên tố cùng nhau, m > 0,. thì số nguyên x0 là nghiệm của ax ≡ 1 (mod m) khi và chỉ khi x0. ordm a Chứng minh. Nếu ordm a | x0 thì x0 = k · ordm a, với k là số nguyên dương.
Do đó ax0 = ak·ordm a = (aordm a )k ≡ 1 (mod m). Như vậy x0 là nghiệm của ax ≡ 1 (mod m). Ngược lại, giả sử ax0 ≡ 1 (mod m). Dùng thuật toán chia Euclid ta được x0 = q · ordm a + r, (0 ≤ r < ordm a).
Từ trên, ta thấy rằng ax0 = aq·ordm a+r = aq·ordm a · ar = (aordm a )q · ar ≡ ar (mod m) ≡ 1 (mod m). Do 0 ≤ r < ordm a và ordm a là số nguyên dương bé nhất thỏa mãn phương trình đồng dư thức ax ≡ 1 (mod m). Vậy x0 = q · ordm a, tức là x0. CHƯƠNG 2 KHAI TRIỂN b-PHÂN: PHẦN NGUYÊN VÀ PHẦN LẺ 2.
Phần nguyên Ta thường quen biểu diễn số nguyên qua tổng các lũy thừa của 10 (biểu diễn thập phân). Thực ra không có lí do gì đặc biệt quyết định việc đó (ngoài việc chúng ta có mười ngón tay?!). Có nhiều dân tộc dùng những hệ đếm khác: người Babylonia dùng cơ số 60. Các bộ tộc thời cổ đại thường dùng cơ số 5, tương ứng với việc đếm trên 5 ngón tay.
Hiện nay, người Trung Hoa và người Nhật Bản vẫn còn dùng các bàn tính gẩy dựa trên hệ đếm cơ số 5. Người Maya cổ đại sử dụng cơ số 20, và cho đến ngày nay, ở Đan Mạch và Pháp người ta vẫn sử dụng cơ số 20. Cơ số 12 được sử dụng nhiều ở Anh. Máy tính điện tử thì dùng cơ số 2, 8, 16,.
Trong phần này, ta sẽ chứng tỏ rằng mọi số nguyên lớn hơn 1 đều có thể dùng làm cơ số. Giả sử b là số nguyên, b > 1. Khi đó, mọi số nguyên dương n đều có thể viết được một cách duy nhất dưới dạng n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 Trong đó aj là những số nguyên, 0 ≤ aj ≤ b − 1 với j = 0, 1,. , k ; đồng thời ak 6= 0 Chứng minh.
• Sự tồn tại biểu diễn: Thực hiện liên tiếp thuật toán chia. Trước tiên, chia n cho b, ta được n = bq0 + a0 , 0 ≤ a0 ≤ b − 1 Lại chia q0 cho b, ta có q0 = bq1 + a1 , 0 ≤ a1 ≤ b − 1 CHƯƠNG 2. KHAI TRIỂN B-PHÂN: PHẦN NGUYÊN VÀ PHẦN LẺ 22 Tiếp tục quá trình trên, ta nhận được q1 = bq2 + a2 , 0 ≤ a2 ≤ b − 1 q2 = bq3 + a3 , 0 ≤ a3 ≤ b − 1. qk−2 = bqk−1 + ak−1 , 0 ≤ ak−1 ≤ b − 1 qk−1 = b · 0 + ak , 0 ≤ ak ≤ b − 1 Quá trình này kết thúc khi ta nhận được thương bằng 0.
Điều này đạt được sau hữu hạn bước, bởi vì n > q0 > q1 >. ≥ 0, mà mọi dãy giảm những số nguyên không âm sẽ dừng sau hữu hạn bước. Như vậy ta có n = bq0 + a0 = b(bq1 + a1 ) + a0 = b2 q1 + a1 b + a0 = b3 q2 + a2 b2 + a1 b + a0 = ··· = ak bk + ak−1 bk−1 + · · · + a1 b1 + a0 trong đó aj là những số nguyên, 0 ≤ aj ≤ b − 1 với j = 0, · · · , k ; đồng thời ak 6= 0 vì ak = qk−1 là thương khác 0 cuối cùng. • Tính duy nhất của biểu diễn: Giả sử phản chứng, còn có một cách biểu diễn khác, n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 = ck bk + ck−1 bk−1 + · · · + c1 b + c0 trong đó 0 ≤ ak ≤ b − 1, 0 ≤ ck ≤ b − 1 (nếu cần, ta có thể thêm vào phía trước một trong hai biểu diễn những hệ số bằng 0 để số số hạng trong hai biểu diễn là như nhau; tất nhiên lúc này điều kiện ak , ck 6= 0 có thể bị vi phạm).
Khi đó ta có (ak − ck )bk + (ak−1 − ck−1 )bk−1 +. + (a1 − c1 )b + (a0 − c0 ) = 0 Nếu hai biểu diễn là khác nhau, thì tồn tại số nguyên j nhỏ nhất sao cho aj 6= cj. Khi đó bj [(ak − ck )bk−j +. KHAI TRIỂN B-PHÂN: PHẦN NGUYÊN VÀ PHẦN LẺ 23 suy ra (ak − ck )bk−j +.
Nhưng do 0 ≤ aj ≤ b − 1, 0 ≤ cj ≤ b − 1 nên −b < aj − cj < b. Do đó, b|(aj − cj ) khi và chỉ khi aj = cj , mâu thuẫn. Từ đó định lí được chứng minh. Với b = 2, ta có hệ quả sau: Hệ quả 2.
Bất kì số nguyên dương nào cũng đều có thể biểu diễn được dưới dạng tổng các lũy thừa của 2 Chứng minh. Cho n là một số nguyên dương.1) với b = 2, ta có n = ak 2k + ak−1 2k−1 +. + a1 2 + a0 trong đó aj là một trong hai số 0 hoặc 1. Từ đó, ta có điều phải chứng minh.
Trong khai triển được mô tả trong định lí (2.1), b được gọi là cơ số của khai triển. Ta gọi cách viết số thông thường mà ta sử dụng là biểu diễn 10 phân, hay còn gọi là biểu diễn thập phân. Biểu diễn theo cơ số 2 còn được gọi là biểu diễn nhị phân, biểu diễn theo cơ số 8 gọi là biểu diễn bát phân, và biểu diễn theo cơ số 16 gọi là biểu diễn thập lục phân. Các hệ số aj được gọi là các chữ số của sự khai triển.
Các chữ số nhị phân (0 hoặc 1) được gọi là bits (binary digits) trong ngôn ngữ tin học. Ta thường viết (ak ak−1 · · · a1 a0 )b thay cho ak bk + ak−1 bk−1 + · · · + a1 b + a0 Ví dụ 2. Số 236 trong hệ cơ số 7 được biểu diễn như sau: (236)7 = 2 · 72 +3·7+6 và nó có giá trị bằng 135 trong hệ thập phân. Số 10010011 trong hệ nhị phân được biểu diễn như sau: (10010011)2 = 1 · 27 + 1 · 24 + 1 · 21 + 1 và có giá trị bằng 147 trong hệ thập phân CHƯƠNG 2.
KHAI TRIỂN B-PHÂN: PHẦN NGUYÊN VÀ PHẦN LẺ 24 Quá trình chứng minh định lí (2.1) cho ta phương pháp để tìm khai triển theo cơ số b của một số nguyên dương n cho trước. Ta thực hiện thuật toán chia số n cho số b, rồi chia thương tìm được cho b,. , cho đến khi ta nhận được thương bằng 0. Các số dư có được, kể từ số dư cuối cùng trở lên số dư đầu tiên, là các chữ số từ trái sang phải trong khai triển b phân của số nguyên đó.
Để tìm khai triển nhị phân của số 1864, ta thực hiện thuật toán chia lần lượt như sau: 1864 = 2 · 932 + 0, 932 = 2 · 466 + 0, 466 = 2 · 233 + 0, 233 = 2 · 116 + 1, 116 = 2 · 58 + 0, 58 = 2 · 29 + 0, 29 = 2 · 14 + 1, 14 = 2 · 7 + 0, 7 = 2 · 3 + 1, 3 = 2 · 1 + 1, 1 = 2 · 0 + 1, Vậy (1864)10 = (11101001000)2 Trong khi làm việc, máy tính thường ghi các chữ số bởi bóng đèn “sáng, tắt”. Bóng đèn sáng chỉ số 1, bóng đèn tắt chỉ số 0. Vì thế, để thuận tiện nhất, ta dùng hệ đếm cơ số 2, trong đó, để biểu diễn một số nào đó, ta sử dụng hai chữ số 0 và 1. Một số nguyên n biểu diễn bởi k chữ số 1 và 0 được gọi là một số k − bit.
Máy tính sử dụng cơ số 8 hoặc cơ số 16 cho mục đích hiển thị thông tin trên màn hình. Với cơ số 16, hay còn gọi là thập lục phân, có 16 chữ số được kí hiệu bởi 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Các kí tự A, B, C, D, E và F được sử dụng để biểu diễn các con số 10, 11, 12, 13, 14, CHƯƠNG 2. KHAI TRIỂN B-PHÂN: PHẦN NGUYÊN VÀ PHẦN LẺ 25 15 trong hệ thập phân.
Chúng ta xem ví dụ dưới đây để thấy được cách chuyển đổi từ hệ thập lục phân sang hệ thập phân. Để chuyển đổi (A35B0F)16 từ hệ thập lục phân sang hệ thập phân, ta viết (A35B0F)16 = 10 · 165 + 3 · 164 + 5 · 163 + 11 · 162 + 0 · 16 + 15 = (10705679)10 Việc chuyển đổi giữa hệ nhị phân và hệ thập lục phân có thể thực hiện được một cách đơn giản. Ta có thể viết mỗi chữ số trong hệ thập lục phân tương ứng với một cụm gồm bốn chữ số trong hệ nhị phân dựa vào bảng dưới đây Hệ thập lục phân Hệ nhị phân Hệ thập lục phân Hệ nhị phân 0 0000 8 1000 1 0001 9 1001 2 0010 A 1010 3 0011 B 1011 4 0100 C 1100 5 0101 D 1101 6 0110 E 1110 7 0111 F 1111 Ví dụ 2. Ví dụ đơn giản cho việc chuyển đổi từ hệ thập lục phân sang hệ nhị phân là (2FB3)16 = (10111110110011)2.
Mỗi chữ số trong hệ thập lục phân tương ứng với một cụm gồm bốn chữ số trong hệ nhị phân (hai chữ số 0 đầu tiên trong cụm (0010)2 tương ứng với (2)16 đã được lược bỏ) Để chuyển đổi từ hệ nhị phân sang hệ thập lục phân, ví dụ (11110111101001)2 , ta làm như sau: Chia các chữ số ra thành cách nhóm gồm bốn chữ số, bắt đầu từ phải sang. Khi đó, từ phải sang trái, ta được các nhóm như sau: 1001, 1110, 1101 và 0011 (ta thêm hai chữ số 0 vào hai vị trí đầu tiên).