| 3 Comments | Nguyễn Kim Sở
Trong các phép tính trên số nguyên thì phép chia là đặc biệt nhất. Phép chia có một số tính chất mà các phép toán khác không có. Ví dụ chúng ta có thể tiến hành cộng, trừ, nhân với số 0 nhưng phép chia thì không được. Phép cộng, trừ, nhân trên tập số nguyên cho ta số nguyên nhưng phép chia thì không hẳn vậy. Chính vì tính dị biệt đó mà trong lý thuyết số người ta đã xây dựng hẳn một lý thuyết về phép chia các số nguyên. Trong đó có sự góp mặt với rất nhiều công trình của các nhà toán học nồi tiếng như Pierre de Fermat, Leonhard Euler, Johann Carl Friedrich Gauss, ... và cho tới tận bây giờ vẫn còn nguyên giá trị.
Khi làm việc với các bài toán liên quan đến phép chia hết, phép chia có dư thì khó khăn nhất đối với học sinh là những bài toán có chứa lũy thừa bởi việc phân tích, đánh giá rất phức tạp. Nhiều bài toán vượt ra ngoài khả năng tính toán của con người (hiện tại) bởi số liệu lớn. Khi đó chỉ còn cách vận dụng thông minh, khéo léo các tính chất, các định lý số học, ... để chỉ ra tính đúng đắn của bài toán đã cho. Bài viết này sẽ tìm hiểu và khai thác một số bài toán như vậy. Trước tiên chúng ta nhắc lại một số kiến thức cần thiết.
1. Khái niệm đồng dư thức
Cho số nguyên dương \(m\) và các số nguyên \(a, b\). Nếu khi chia \(a\) và \(b\) cho \(m\) ta được cùng một số dư thì ta nói \(a\) đồng dư với \(b\) theo modulo \(m\). Ki hiệu \(a \equiv b(\bmod m)\).
2. Định lý Fermat nhỏ
Cho \(p\) là số nguyên tố, khi đó với mọi số nguyên \(a\) thì \(a^p \equiv a(\bmod p)\). Đặc biệt, nếu \(a\) không chia hết cho \(p\) thì:
\(a^{p-1} \equiv 1(\bmod p) \)
3. Định lý Euler
Cho \(n\) là số nguyên dương bất kỳ và \(a\) là số nguyên tố cùng nhau với \(n\). Khi đó:
\(a^{\varphi(n)} \equiv 1(\bmod n)\)
trong đó \(\varphi(n)\) là phi hàm Euler (được xác định là số các số nguyên dương nhỏ hơn \(n\) và nguyên tố cùng nhau với \(n\) ). Chú \(y^{\prime}\) Nếu \(n\) có dạng phân tích chính tắc:
\[n=p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k}\]
thì \(\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \ldots\left(1-\frac{1}{p_k}\right)\).
4. Bổ đề LTE (Lifting The Exponent Lemma)
- Cho \(p\) là số nguyên tố, \(a\) là số nguyên và \(\alpha\) là số tự nhiên. Ta gọi \(p^\alpha\) là lũy thừa đúng của \(a\) và \(\alpha\) là số mũ đúng của \(p\) trong khai triển của \(a\) nếu \(p^\alpha \mid a\) nhưng \(p^{\alpha+1} \mid a\). Khi đó ta ký hiệu:
\[p^\alpha \| a \text { hoặc } v_p(a)=\alpha .\]
- Bổ đề LTE
+ Bổ đề cho số nguyên tố \(p\) lẻ
Cho \(a, b \in \mathbb{Z}, n \in \mathbb{N}^*\) và \(p\) là số nguyên tố lè thỏa mãn: \(p \mid(a-b)\) và \(p|a, p| b\). Khi đó:
\[v_p\left(a^n-b^n\right)=v_p(a-b)+v_p(n)\]
Đặc biệt khi \(2 \nmid n\) và \(p\) là số nguyên tố lè sao cho \(p \mid(a+b)\) và \(p \nmid a, p \nmid b\). Khi đó:
\[v_p\left(a^n+b^n\right)=v_p(a+b)+v_p(n) .\]
+ Bổ đề cho số nguyên tố chẵn \(\boldsymbol{p}=2\)
Cho \(a, b \in \mathbb{Z}, n \in \mathbb{N}^*\) và thỏa mãn: \(2 \mid n\) và \(2 \nmid a, 2 \nmid b\). Khi đó:
\[v_2\left(a^n-b^n\right)=v_2(a+b)+v_2(a-b)+v_2(n)-1\]
Bây giờ chúng ta cùng xem xét dấu hiệu đặc trưng cũng như kết hợp sử dụng các kiến thức nêu trên để giải quyết một số bài toán dưới đây.
Bài toán 1. Chứng minh rằng tồn tại vô số số nguyên dương \(n\) để \(2024^n-1\) chia hết cho \(n\).
Lời giải. Ta sẽ chứng minh bằng quy nạp rằng dãy \(\left\{u_n\right\}\) xác định bời:
\[\left\{\begin{array}{l}u_1=1 \\u_{n+1}=2024^{u_n}-1\end{array}\right.\]
sẽ thỏa mãn điều kiện \(2024^{u_n}-1\) chia kết \(u_n\).Thật vậy:
Với \(n=1\), khi đó \(u_1=1\) và hiển nhiên
\[2024^{u_1}-1=2023 \vdots 1 .\]
Giả sử bài toán đúng tới \(n=k\), nghĩa là:
\[\left(2024^{u_k}-1\right) \text { chia kết } u_k \]
Khi đó ta có:
\[\begin{aligned}& u_{k+1}=2024^{u_k}-1=v . u_k\left(v \in \mathbb{N}^*\right) \\& \Rightarrow 2024^{u_{k+1}}-1=2024^{v \cdot u_k}-1 \\&=\left(2024^{u_k}\right)^v-1 \vdots\left(2024^{u_k}-1\right)\end{aligned}\]
hay \(\left(2024^{u_{k+1}}-1\right) \vdots u_{k+1}\). Nghĩa là khẳng định cũng đúng với \(n=k+1\). Theo nguyên lý quy nạp khẳng định đúng với mọi \(n \in \mathbb{N}^*\).
Để ý rằng \(\left\{u_n\right\}\) là dãy tăng vô hạn nên bài toán được chứng minh.
Với số tự nhiên \(a>2\), bằng cách quy nạp tương tự như trên chúng ta cũng xây dựng được một dãy
tăng \(\left\{u_n\right\}\) xác định bởi: \(\left\{\begin{array}{l}u_1=1 \\ u_{n+1}=a^{u_n}-1\end{array}\right.\) sẽ thỏa mãn điều kiện \(a^{u_n}-1\) chia kết \(u_n\). Ta có kết quả tồng quát hơn.
Bài toán 2. Cho a là một số tụ nhiên lớn hơn 2. Khi đó luôn tồn tại vô số số nguyên duơng \(n\) để \(a^n-1\) chia hết cho \(n\).
Vấn đề đặt ra ở đây là tại sao a phải lớn hon 2? Câu trả lời không khó bởi lẽ với \(a=2\) thì dãy \(\left\{u_n\right\}\) xác định như trên không phải là dãy tăng, cụ thể là \(u_n=1, \forall n \in \mathbb{N}^*\), và khi đó bài toán không còn đúng nữa.
Bài toán 3. Chứng minh rằng không tồn tại số nguyên duơng \(n\) nào để \(\left(2^n-1\right)\) chia hết cho \(n\).
Lời giải.
Trước hết ta chứng minh bổ đề sau:
Bổ đề. Cho \(p\) là một số nguyên tố lè, \(d\) là số nguyên dương nhỏ nhất đề \(\left(2^{\mathrm{d}}-1\right)\) : \(p\) và \(m\) là số nguyên dương thỏa mãn \(\left(2^m-1\right) \vdots p\). Khi đó \(m\) :d. Chứng minh. Thật vậy, vì \(m \geq d\) nên ta có biểu diễn: \(m=k \cdot d+r(0 \leq r
Khi đó: \(\left(2^m-1\right)-\left(2^r-1\right)=2^m-2^r\)
\[\begin{aligned}&=2^{k . d+r}-2^r=2^r\left(2^{k . d}-1\right) \\&\left.=2^r\left[\left(2^d\right)^k-1\right)\right] \vdots\left(2^{\mathrm{d}}-1\right) \\& \Rightarrow\left(2^{\mathrm{m}}-1\right)-\left(2^r-1\right) \vdots p \Rightarrow\left(2^r-1\right) \vdots p\end{aligned}\]
Do \(d\) là số nhỏ nhất và \(0 \leq r
Trở lai bài toán:
Già sử phản chứng: \(n\) là số nguyên, \(n \geq 2\) mà \(\left(2^n-1\right) \vdots n \Rightarrow n\) lè. Gọi \(p\) là ước số nguyên tố bé nhất của \(n\), khi đó: \(\left(2^n-1\right) \vdots p\).
Theo định lý Fermat bé thì \(\left(2^{p-1}-1\right) \vdots p\). Gọi \(d\) là số nguyên dương nhỏ nhất mà \(\left(2^d-1\right) \vdots p\) thì theo bổ đề trên suy ra:
\[\left\{\begin{array}{l}n \vdots d \\p-1 \vdots d\end{array}\right. \]
Nhưng \((n ; p-1)=1\) vì \(n\) không có ước số nào bé hơn \(p \Rightarrow d=1\). Khi đó \(\left(2^1-1\right) \vdots p \Rightarrow p=1\). Mâu thuẫn! Vậy điều giả sử phản chứng là sai. Bài toán được chứng minh.
Đến đây có thể thấy chìa khóa để giải các bài toán trên dựa vào kết quả rất đơn giản: Với mọ \(a, b\) nguyên, \(n\) nguyên duơng và \(a \neq b\) thì \(\left(a^n-b^n\right) \vdots(a-b)\). Điều đó gợi thêm cho chúng ta một ý tưởng về cách sử dụng bổ đề LTE để giải quyết một số bài toán liên quan đến tính chia hết của \(\left(a^n-b^n\right)\) hoặc \(\left(a^n+b^n\right)\).
Bài toán dưới đây là một ví dụ điển hình của ứng dụng bổ đề LTE trong giải toán mà việc sử dụng các phương pháp khác có thể không dễ chút nào.
Bài toán 4. Chứng minh rằng tồn tại vô số số nguyên duơng \(n\) để \(2024^n+1\) chia hết cho \(n\).
Lời giải. Đế ý rằng \(2024+1=2025=3^4 \cdot 5^2\). Ta sẽ chứng minh tất cả các số \(n\) có dạng \(n=3^k\) đều thỏa mãn \(\left(2024^n+1\right)\) € \(n\).
Thật vậy, vì \(n=3^k\) là một số lẻ nên sử dụng bổ đề LTE ta có:
\[\begin{aligned}v_3\left(2024^n+1\right) & =v_3(2024+1)+v_3(n) \\& =v_3(2025)+v_3(n)=4+v_3(n) \\& =4+k .\end{aligned}\]
Rõ ràng: \(4+k>k \Rightarrow n=3^k \mid\left(2024^n+1\right)\). Bài toán được chứng minh.
Ngoài ra chúng ta có thể xét các số n có dạng \(n=5^k\) cũng thu được kết quả tương tư.
Để kết lại cho bài viết này chúng tôi đưa ra một số bài tập tự luyện. Hi vọng rằng những nội dung ở trên sẽ giúp ích được các bạn, nhất là các em học sinh, sinh viên trong quá trình học tập cũng như nghiên cứu sau này.
BÀI TẬP TỰ LUYỆN
Bài tập 1. (Tổng quát hóa của Bài toán 1 \& Bài toán 2)
Cho \(a, b\) là các số nguyên dương thỏa mãn \(a \geq 2+b\). Chứng minh rằng tồn tại vô số số nguyên dương \(n\) để \(a^n-b^n\) chia hết cho \(n\).
Bài tập 2. (Tổng quát hóa của Bài toán 4)
Cho \(a\) là số nguyên dương lớn hơn 1 và không có dạng \(2^m-1(m \in \mathbb{N}, m \geq 2)\). Chứng minh rằng tồn tại vô số số nguyên dương \(n\) để \(\left(a^n+1\right)\) chia hết cho \(n\).
Bài tập 3. (Trích câu 3.b, đề thi chọn HSG lớp 12, tỉnh Vĩnh Long - năm học 2019-2020)
Chứng minh rằng tồn tại vô số số nguyên dương \(n\) đề \(\left(2^n+1\right)\) chia hết cho \(n\).
Bài tập 4. (Trích đề thi vô địch toàn Liên Xô lớp 8 , năm 1978)
Chứng minh rằng với bất kỳ số tự nhiên n nào thì \(\left(1978^n-1\right)\) không thể chia hết cho \(\left(1000^n-1\right)\).
Bài tập 5. (Trích câu 4, đề thi IMO 1999 tại Bucharest - Romania)
Tìm tất cả các cặp \((n, p)\) nguyên dương và \(p\) là số nguyên tố sao cho:
\[n^{p-1} \mid(p-1)^n+1\]
