Giới thiệu

Các kiến thức liên quan tới số học luôn đóng vai trò quan trọng trong lập trình thi đấu. Chúng có ứng dụng thực tiễn liên quan đến đời sống, đồng thời cũng đưa cho ta những quan sát, nhận xét quan trọng khi tiếp cận một vấn đề trong lập trình. Đôi khi, những quan sát này chính là "key" để giải một bài toán hóc búa, hay đơn giản giúp bạn có thêm ý tưởng để cải thiện độ phức tạp của chương trình. Nếu không nắm vững các lý thuyết liên quan đến số học, bạn dễ bị mắc phải những sai sót liên quan đến tính chất trong các phép toán. Trong series về lý thuyết số học, Viblo sẽ trình bày các chuyên đề quan trọng giúp bạn tự tin hiểu và xử lý các bài lập trình thi đấu nặng về tính toán học. Ở bài viết đầu tiên, Viblo sẽ giới thiệu tới các bạn về đồng dư, một khái niệm thường xuyên gặp phải trong lập trình thi đấu. Bài viết được tham khảo từ sách Lý thuyết sơ cấp của các số - W. SIERPINSKI

Đồng dư và các tính chất

Giả sử $a$ và $b$ là các số nguyên. Ta nói rằng $a$ đồng dư với $b$ theo modulo $m$ nếu hiệu của $a$ và $b$ chia hết cho $m$. Sử dụng ký hiệu được đề xuất bởi Gauss ta viết:

$a \equiv b ( \bmod m )$ (1)

Công thức (1) tương đương với $m | a - b$

Rõ ràng nếu hai số nguyên là đồng dư modulo $m$ thì chúng có cùng số dư khi chia cho $m$. Ký hiệu đồng dư $\equiv$ được sử dụng khá giống ký hiệu $=$. Ta liệt kê dưới đây một số mối liên hệ giữa các đồng dư thức và các đẳng thức.

Tính phản xạ: Mọi số nguyên là đồng dư với chính nó theo mọi modulo, nghĩa là $a \equiv a (\bmod m)$ với mọi số nguyên a và mọi số tự nhiên $m$ vì rõ ràng $a-a = 0$ chia hết cho mọi số tự nhiên $m$.

Tính đối xứng: Đồng dư thức (1) tương đương với đồng dư thức $b \equiv a (\bmod m )$ vì rõ ràng các số $a – b$ và $b – a$ cùng chia hết hoặc cùng không chia hết cho $m$.

Tính kết hợp: nếu $a \equiv b (\bmod m)$ và $b \equiv c (\bmod m )$ thì $a \equiv c (\bmod m )$ vì ta có đẳng thức $a-c = (a-b) + (b-c)$ và lưu ý tổng của hai số chia hết cho $m$ là một số chia hết cho $m$.

Ta có một số tính chất khác của đồng dư sau đây. Ta chứng minh hai đồng dư thức với cùng modulo có thể cộng hoặc trừ tương ứng các vế. Thật vậy giả sử

$a \equiv b ( \bmod m ) \text { và } c \equiv d ( \bmod m )$ (2)

Để chứng minh $a+c \equiv b+d(\bmod m)$ và $a-c \equiv b-d(\bmod m)$ ta lưu ý các đẳng thức $(a+c)-(b+d)=(a-b)+(c-d)$ và $(a-c)-(b-d)=(a-b)-(c-d)$. Tương tự sử dụng đẳng thức $a c-b d=(a-b) c+(c-d) b$, ta chứng minh được từ (2) suy ra đồng dư thức $a c \equiv b d(\bmod m)$. Hệ quả là ta có thể nhân theo vế hai đồng dư thức với cùng modulo.

Các định lý về các tính chất cộng, trừ, nhân các đồng dư thức ở trên có thể mở rộng cho hữu hạn các đồng dư thức.

Định lý về phép cộng các đồng dư thức chứng tỏ ta có thể chuyển vế đối dấu mọi hạng tử trong một đồng dư thức bởi vì phép toán này tương đương với việc trừ các hạng tử trong cả hai vế.

Từ tính chất phép nhân các đồng dư thức chứng tỏ có thể nhân một đồng dư thức với mọi só nguyên tùy ý và do đó ta có thể lũy thừa cả hai vế của đồng dư thức với số mũ bất kỳ.

Tuy nhiên ta không thể chia một đồng dư thức cho một đồng dư thức khác (ngay cả khi thương số là các số nguyên). Chẳng hạn $48 \equiv 18(\bmod 10)$ và $12 \equiv 2(\bmod 10)$ nhưng không có $4 \equiv 9(\bmod 10)$.

Do một ước số của ước số của một số nguyên cũng là ước số của số nguyên đó nên nếu $d \mid m$ thì đồng dư thức $a \equiv b(\bmod m)$ chứng tỏ $a \equiv b(\bmod d)$.

Tính kết hợp của các đồng dư thức cùng với tính chất cộng và nhân các đồng dư thức chứng tỏ trong đồng dư thức cho trước ta có thể thay mọi hạng tử hoặc nhân tử bởi các số đồng dư với nó.

Quy tắc này không đúng với các lũy thừa. Chẳng hạn đồng thức thức $2^{6} \equiv 4(\bmod 5)$ không thể thay thế bởi đồng dư thức $2^{1} \equiv 4(\bmod 5)$ mặc dù $6 \equiv 1(\bmod 5)$.

Giả sử $f(x)=A_{0} x^{n}+A_{1} x^{n-1}+\ldots+A_{n-1}+A_{n}$ là đa thức bậc $n$ với hệ số nguyên. Ký hiệu $m$ là số tự nhiên và $a, b$ là các số nguyên thỏa mãn $a \equiv b(\bmod \mathrm{m})$. Từ định lý về các lũy thừa tự nhiên và tính chất nhân các đồng dư thức suy ra

$$\begin{aligned} &A_{0} a^{n} \equiv A_{0} b^{n}(\bmod m), \\ &A_{1} a^{n-1} \equiv A_{1} b^{n-1}(\bmod m), \\ &\cdots \\ &A_{n-1} a \equiv A_{n-1} b(\bmod m), \\ &A_{n} \equiv A_{n}(\bmod m) . \end{aligned}$$

Cộng lại ta có $A_{0} a^{n}+A_{1} a^{n-1}+\ldots+A_{n-1} a+A_{n} \equiv A_{0} b^{n}+A_{1} b^{n-1}+\ldots+A_{n-1} b+A_{n}(\bmod m)$. Nghĩa là $f(a) \equiv f(b)(\bmod m)$. Ta đã chứng minh được

Định lý 1. Nếu $f(x)$ là đa thức một biến $x$ với hệ số nguyên thì đồng dư thức $a \equiv b(\bmod \mathrm{m})$ suy ra đồng dư thức $f(a) \equiv f(b)(\bmod m)$.

Định lý 1 cho ta quy tắc cho biết một số có chia hết cho 9,7,11,13,27,37 hay không.

Ký hiệu $N$ là số tự nhiên. Biểu diễn của $N$ trong hệ thập phân được cho bởi biểu diễn có dạng $N=c_{1} 10^{n-1}+c_{2} 10^{n-2}+\ldots+c_{n-1} 10+c_{n}$. Đặt (3)

$$f(x)=c_{1} x^{n-1}+c_{2} x^{n-2}+\ldots+c_{n-1} x+c_{n}$$

Khi đó $f(x)$ là đa thức hệ số nguyên và (4)

$$f(10)=N$$

Theo Định lý 1 thì vì $10 \equiv 1(\bmod 9)$ ta có (5)

$$f(10) \equiv f(1)(\bmod 9)$$

Nhưng $f(1)=c_{1}+c_{2}+\ldots+c_{n}$ và hệ quả là theo $(4)$ và $(5)$ thì $N \equiv c_{1}+c_{2}+\ldots+c_{n}(\bmod 9)$ chứng tỏ mọi số tự nhiên $N$ sai khác tổng các chữ số của nó trong hệ cơ số 10 một bội số của 9. Do đó $N$ chia hết cho 9 khi và chỉ khi tổng các chữ số của nó chia hết cho 9. Tổng quát hơn nếu ký hiệu $S_{N}$ là tổng các chữ số của $N$ (trong hệ thập phân) thì với các số tự nhiên $N$ và $N^{\prime}$ ta có $N \equiv s_{N}(\bmod 9)$, $N^{\prime} \equiv s_{N^{\prime}}(\bmod 9)$ suy ra $N N^{\prime} \equiv s_{N} s_{N^{\prime}}(\bmod 9)$. Vì $N N^{\prime} \equiv s_{N^{\prime}}(\bmod 9)$ nên $s_{N N^{\prime}} \equiv s_{N^{\prime}} s_{N^{\prime}}(\bmod 9)$.

Từ (3) và đồng dư thức $10 \equiv-1(\bmod 11)$, Định lý 1 suy ra $f(10) \equiv f(-1)(\bmod 11)$, do đó theo (4) và (3) ta có $(-1)^{n-1} N \equiv c_{1}-c_{2}+c_{3}-c_{4}+\ldots(\operatorname{mod11})$. Từ đây ta nhận được quy tắc về tính chia hết cho 11. Bây giờ ta tìm các quy tắc về tính chia hết cho 7 hoặc $13 .$

Ký hiệu $\left(c_{1}, c_{2}, \ldots, c_{n}\right)_{10}$ là số trong hệ thập phân có các chữ số là $c_{1}, c_{2}, \ldots, c_{n}$ (ký hiệu này là cần thiết để phân biệt với tích các chữ số $c_{1}, c_{2}, \ldots, c_{n}$ ). Mọi số tự nhiên đều có dạng $N=\left(c_{n-2} c_{n-1} c_{n}\right)_{10}+\left(c_{n-5} c_{n-4} c_{n-3}\right)_{10} \cdot 1000+\left(c_{n-8} c_{n-7} c_{n-6}\right)_{10} \cdot 1000^{2}+\ldots$ Vì $1000 \equiv-1(\bmod 7)$ và $1000 \equiv-1(\bmod 13)$ nên ta có $N \equiv\left(c_{n-2} c_{n-1} c_{n}\right)_{10}-\left(c_{n-5} c_{n-6} c_{n-7}\right)_{10}+\left(c_{n-8} c_{n-7} c_{n-6}\right)_{10}-\ldots(\bmod 7)$ và đồng dư thức tương tự cũng nhận được khi thay modulo 7 bởi modulo $13 .$

Các đồng dư thức này cũng cho ta biết quy tắc về tính chia hết cho 7 hoặc 13. Chẳng hạn ta có $N=8589879056 \equiv 56-879+589-8$ theo cả modulo 7 và modulo 13 . Vì số trong vế phải các đồng dư thức này (bằng -242) là không chia hết cho cả 7 lẫn 13 nên $N$ không chia hết cho cả 7 lẫn $13 .$

Các quy tắc với 27 và 37 được dựa trên tính chất $100 \equiv 1$ theo $\bmod 27$ và $\bmod 37$. Từ đây ta nhận được các quy tắc tương tự với các trường hợp ở trên. Chẳng hạn ta có $N=24540509 \equiv 509+540+24$ theo $\bmod 27$ và $\bmod 37$. Số trong vế phải là $1073$ có thể viết thành $1073 \equiv 73+1$ theo $\bmod 27$ và $\bmod 37$. Số $74$ chia hết cho $37$ nhưng không chia hết cho $27$ và do đó số $N$ cũng chia hết cho $37$ nhưng không chia hết cho $27$.

Một số bài tập

1. Tìm hai chữ số tận cùng của số $2^{1000}$.

Lời giải. Ta có $2^{10}=1024 \equiv 24(\bmod 100)$ vì vậy $2^{20} \equiv 24^{2} \equiv 76(\bmod 100)$. Nhưng $76^{2} \equiv 76(\bmod 100)$ suy ra theo quy nạp $76^{k} \equiv 76(\bmod 100), k=1,2, \ldots .$ Do đó $2^{1000}=2^{20.50} \equiv 76^{50} \equiv 76(\bmod 100)$. Vậy hai chữ số tận cùng của $2^{1000}$ là 7 và 6.

2. Chứng minh rằng ít nhất một trong sáu đồng dư thức sau là đúng (Erdos):

1. $x \equiv 0(\bmod 2)$,
2. $x \equiv 0(\bmod 3)$,
3. $x \equiv 1(\bmod 4)$,
4. $x \equiv 3(\bmod 8)$,
5. $x \equiv 7(\bmod 12)$,
6. $x \equiv 23(\bmod 24)$ với số nguyên $x$ bất kỳ.

Chứng minh. Nếu số nguyên $x$ không thỏa mãn cả 1) và 2) thì nó không chia hết cho 2 và 3 do đó có dạng $24 t+\mathrm{r}$ với $t$ là số nguyên và $r$ là một trong các số $1,5,7,11,13,17,19,23$. Khi đó dễ dàng kiểm tra số $x=24 t+r$ thỏa mãn các đồng dư thức 3),3),5),4),3),3),4),6) tương ứng.

Ghi chú. P.Erdos đã đặt ra bài toán sau đây: cho trước số tự nhiên $n$, có tồn tại hay không tập hợp hữu hạn các đồng dư thức với modulo phân biệt lớn hơn $n$ mà mọi số nguyên thỏa mãn ít nhất một trong số chúng? H.Davenport đặt ra giả thuyết rằng câu trả lời là khẳng định nhưng sẽ không có một lời giải đơn giản. P.Erdos đã tự chứng minh giả thuyết này trong trường hợp $n=2$ bằng cách sử dụng một số đồng dư thức với modulo là ước số của 120 . D.Swift đã cho lời giải với $n=3$ bằng cách sử dụng các đồng dư thức với modulo là ước số của 2880. Giả thuyết đã được chứng minh với mọi $n<20$ (Choi).

3. Tìm hai chữ số tận cùng của số $9^{9^{9}}$.

Lời giải. Theo modulo 100 thì $9^{2} \equiv 81,9^{4} \equiv 81^{2} \equiv 61,9^{8} \equiv 61^{2} \equiv 21,9^{9} \equiv 21.9 \equiv 89,9^{10} \equiv 89.9 \equiv 1$. Ta có $9^{9} \equiv 9(\bmod 10)$ suy ra $9^{9}=10 k+9$ với $k$ là số tự nhiên. Vì vậy từ $9^{10} \equiv 1(\bmod 100)$ suy ra $9^{9^{9}}=9^{10 k+9} \equiv 9^{9} \equiv 89(\bmod 100)$ chứng tỏ chữ số tận cùng của $9^{9^{9}}$ là 9 và chữ số liền trước đó là $8 .$

4. Tìm hai chữ số tận cùng của số $9^{9^{9}}$.

Lời giải. Từ bài tập 3 suy ra $9^{9^{9}} \equiv 9(\bmod 10)$ do đó $9^{9^{9}}=10 t+9$ với $t$ là số tự nhiên. Suy ra $9^{9^{9}}=9^{10 t+9} \equiv 9^{9} \equiv 89(\bmod 100)$. Vì vậy hai chữ số tận cùng của $9^{9^{9}}$ là hai chữ số tận cùng của $9^{9^{9}}$.

Tài liệu tham khảo

1. Lý thuyết sơ cấp của các số - W. SIERPINSKI
2. cp-algorithms.com
3. Handbook Competitive Programming - Antti Laaksonen
4. Competitve programming 3 - Steven Halim, Felix Halim
5. Giải thuật và lập trình - Thầy Lê Minh Hoàng