modulo - Phần 2


Trong bài trước chúng ta đã học về khái niệm modulo. Hai số $a$ và $b$ được gọi là bằng nhau modulo $n$, ký hiệu $a = b \pmod{n}$, khi mà $a-b$ chia hết cho $n$.

Ví dụ $15 = 3 \pmod{4}$ và $99 = -1 \pmod{10}$.




Chúng ta cũng đã học về các tính chất của modulo.

Công thức cộng:
Nếu $a = b \pmod{n}$ và $x = y \pmod{n}$ thì $a +x = b + y \pmod{n}$.

Công thức cộng (trường hợp đặc biệt):
Nếu $a = b \pmod{n}$ thì $a + z = b + z \pmod{n}$.

Công thức trừ:
Nếu $a = b \pmod{n}$ và $x = y \pmod{n}$ thì $a - x = b - y \pmod{n}$.

Công thức trừ (trường hợp đặc biệt):
Nếu $a = b \pmod{n}$ thì $a - z = b - z \pmod{n}$.

Công thức nhân:
Nếu $a = b \pmod{n}$ và $x = y \pmod{n}$ thì $a x = b y \pmod{n}$.

Công thức nhân (trường hợp đặc biệt):
Nếu $a = b \pmod{n}$ thì $a z = b z \pmod{n}$.

Công thức luỹ thừa:
Nếu $a = b \pmod{n}$  thì $a^k = b^k \pmod{n}$.

Trong các công thức trên thì công thức lũy thừa là đặc biệt tiện dụng.

Bây giờ chúng ta sẽ xem một vài ví dụ. Ở ví dụ đầu tiên chúng ta sẽ làm từng bước từ từ để làm quen cách sử dụng các công thức.

Ví dụ: Chứng minh rằng $2012^{2013} + 1$ chia hết cho 7.

Phân tích: Rõ ràng nhìn đề bài thì chúng ta thấy ngay đây thực ra là bài toán
$$
2012^{2013} = ~~? ~\pmod{7}
$$

Trước tiên, chúng ta lấy 2012 chia cho 7, chúng ta sẽ được 287 và số dư sẽ là 3. Có nghĩa là
$$
2012 = 3 \pmod{7}.
$$

Đến đây, chúng ta áp dụng Công thức Luỹ thừa, và chúng ta sẽ có
$$
2012^{2013} = 3^{2013} \pmod{7}.
$$

Các bạn thấy không, từ một con số khổng lồ $2012^{2013}$, chỉ bằng Công thức Luỹ thừa, chúng ta đã giản ước nó xuống thành con số nhỏ hơn $3^{2013}$. Tuy nhiên, con số $3^{2013}$ này vẫn còn khổng lồ lắm.

Bây giờ, chúng ta sẽ xem xét các luỹ thừa $3^{k}$ một cách từ từ để phát hiện ra quy luật của nó. Chúng ta có
$$3^0 = 1 \pmod{7},$$ $$3^1 = 3 \pmod{7},$$ $$3^2 = 9 = 2 \pmod{7},$$ dùng Công thức nhân, chúng ta sẽ có
$$3^3 = 3 \times 2 = 6 \pmod{7},$$
tiếp tục dùng công thức nhân, chúng ta có
$$3^4 = 3 \times 6 = 18 = 4 \pmod{7},$$ $$3^5 = 3 \times 4 = 12 = 5 \pmod{7},$$ $$3^6 = 3 \times 5 = 15 = 1 \pmod{7},$$ $$3^7 = 3 \times 1 = 3 \pmod{7},$$ $$3^8 = 3 \times 3 = 9 = 2 \pmod{7},$$ $$3^9 = 3 \times 2 = 6 \pmod{7},$$ $$3^{10} = 3 \times 6 = 18 = 4 \pmod{7},$$ $$3^{11} = 3 \times 4 = 12 = 5 \pmod{7},$$ $$3^{12} = 3 \times 5 = 15 = 1 \pmod{7},$$ $$3^{13} = 3 \times 1 = 3 \pmod{7},$$ $$3^{14} = 3 \times 3 = 9 = 2 \pmod{7},$$ $$3^{15} = 3 \times 2 = 6 \pmod{7},$$
A!, chúng ta phát hiện ra rồi, đó là theo modulo 7, thì số $3^k$ lần lượt sẽ bằng 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6,..., đây là quy luật tuần hoàn. Như vậy thì tuỳ theo số mũ $k$ mà $3^k$ sẽ bằng một trong các giá trị sau: 1, 3, 2, 6, 4, 5. Chu kỳ tuần hoàn là 6. Như vậy thì

  • nếu số mũ $k = 6n$ thì $3^k = 1 \pmod{7}$
  • nếu số mũ $k = 6n + 1$ thì $3^k = 3 \pmod{7}$
  • nếu số mũ $k = 6n + 2$ thì $3^k = 2 \pmod{7}$
  • nếu số mũ $k = 6n + 3$ thì $3^k = 6 \pmod{7}$
  • nếu số mũ $k = 6n + 4$ thì $3^k = 4 \pmod{7}$
  • nếu số mũ $k = 6n + 5$ thì $3^k = 5 \pmod{7}$


Ở bài toán mà chúng ta đang giải, số mũ $k$ bằng $2013 = 3 \pmod{6}$, tức là có dạng $6n + 3$, và vì vậy $3^{2013} = 6 \pmod{7}$. Phân tích xong rồi, bây giờ chúng ta sẽ ghi xuống lời giải.

Lời giải: Chúng ta có $2012 = 3 \pmod{7}$, do đó $2012^{2013} = 3^{2013} \pmod{7}$.

Chúng ta có
$$3^2 = 9 = 2 \pmod{7},$$ $$3^3 = 6 \pmod{7},$$ $$3^4 = 18 = 4 \pmod{7},$$ $$3^5 = 12 = 5 \pmod{7},$$ $$3^6 = 15 = 1 \pmod{7}.$$ Do đó với mọi $n$, chúng ta có $3^{6n} = (3^6)^n = 1^n = 1 \pmod{7}$.

Chúng ta có $2013 = 2010 + 3 = 6n + 3$, vì vậy
$$3^{2013} = 3^{6n+3} = 3^{6n} \times 3^3 = 1 \times 6 = 6 \pmod{7}.$$

Tóm lại, chúng ta có $2012^{2013} = 3^{2013} = 6 \pmod{7}$. Vì vậy $2012^{2013} + 1$ chia hết cho 7. $\blacksquare$


Đọc lại lời giải một lần nữa, chúng ta phát hiện ra điểm mấu chốt. Đó là tại thời điểm chúng ta phát hiện ra $3^6 = 1 \pmod{7}$. Điểm này chính là điểm mấu chốt bởi vì dùng Công thức Luỹ thừa thì chúng ta sẽ được một phương trình rất quan trọng là
$$
3^{6n} = 1 \pmod{7}.
$$
Đây là điểm đặc biệt của con số 1. Đến đây chúng ta bỗng phát hiện ra, con số $-1$ cũng rất đặc biệt, tại sao chúng ta không dùng nó. Trong modulo 7, con số $-1$ chính là con số 6. Bây giờ ta quay trở lại bài toán. Chúng ta có
$$
3^3 = 6 = -1 \pmod{7},
$$
và vì vậy
$$
3^{3n} = (3^3)^n = (-1)^n \pmod{7}.
$$


Do đó với một con số $k$ bất kỳ, để tìm $3^k = ~?~ \pmod{7}$ chúng ta chỉ việc lấy $k$ chia cho 3 để lấy kết quả $k = 3n + r$ trong đó $r = 0, 1, 2$, sau đó áp dụng công thức

$$
3^k = 3^{3n+r} = 3^{3n} \times 3^r = (-1)^n \times 3^r \pmod{7}.
$$

Trong bài toán chúng ta, $2013 = 3 \times 671$, và vì vậy chúng ta có
$$
3^{2013} = (-1)^{671} = -1 \pmod{7}.
$$
Tóm lại, chúng ta đã tìm ra cách giải thứ hai.

Lời giải thứ hai: Chúng ta có $2012 = 3 \pmod{7}$, do đó $2012^{2013} = 3^{2013} \pmod{7}$.

Chúng ta có
$$3^3 = 6 = -1 \pmod{7}.$$

Do đó
$$
3^{2013} = 3^{3 \times 671} = (3^3)^{671} = (-1)^{671} = -1 \pmod{7}.
$$

Vì vậy $2012^{2013} + 1$ chia hết cho 7. $\blacksquare$




Bài tập về nhà: Chứng minh rằng $11 + 2011^{2012} + 2012^{2013}$ chia hết cho 13.

Hẹn gặp lại các bạn tại "modulo - Phần 3"