Các bài toán về hàm số học

Bài toán (VMO 2023-2024)

Với mỗi số nguyên dương \( n \), gọi \( \tau(n) \) là số các ước nguyên dương của \( n \).

a) Giải phương trình nghiệm nguyên dương

\[ \tau(n) + 2023 = n \]

với \( n \) là ẩn số.

b) Chứng minh rằng tồn tại vô số số nguyên dương \( k \) sao cho có đúng hai số nguyên dương \( n \) thỏa mãn phương trình

\[ \tau(kn) + 2023 = n. \]

Bài toán (VMO 2021-2022)

Với mỗi cặp số nguyên dương \( n, m \) thoả mãn \( n < m \), gọi \( s(n, m) \) là số các số nguyên dương thuộc đoạn \([n; m]\) và nguyên tố cùng nhau với \( m \). Tìm tất cả các số nguyên dương \( m \geq 2 \) thoả mãn đồng thời hai điều kiện sau:

i)

\[ \frac{s(n, m)}{m - n} \geq \frac{s(1, m)}{m} \quad \text{với mọi } n = 1, 2, \ldots, m - 1; \]

ii)

\[ 2022^m + 1 \quad \text{chia hết cho } m^2. \]

Bài toán (VMO 2020-2021)

Với số nguyên \( n \geq 2 \), gọi \( s(n) \) là tổng các số nguyên dương không vượt quá \( n \) và không nguyên tố cùng nhau với \( n \).

a) Chứng minh

\[ s(n) = \frac{n}{2} (n + 1 - \varphi(n)), \]

trong đó \( \varphi(n) \) là số các số nguyên dương không vượt quá \( n \) và nguyên tố cùng nhau với \( n \).

b) Chứng minh rằng không tồn tại số nguyên \( n \geq 2 \) thỏa mãn

\[ s(n) = s(n + 2021). \]

Bài toán (VMO 2015-2016)

Số nguyên dương \( n \) được gọi là số hoàn chỉnh nếu \( n \) bằng tổng các ước số dương của nó (không kể chính nó).

a) Chứng minh rằng nếu \( n \) là số hoàn chỉnh lẻ thì \( n \) có dạng

\[ n = p^s m^2 \]

trong đó \( p \) là số nguyên tố có dạng \( 4k + 1 \), \( s \) là số nguyên dương có dạng \( 4h + 1 \) và \( m \) là số nguyên dương không chia hết cho \( p \).

b) Tìm tất cả các số nguyên dương \( n > 1 \) sao cho \( n - 1 \) và

\[ \frac{n(n+1)}{2} \]

đều là các số hoàn chỉnh.

Bài toán (IMO Shortlist 2020)

Cho một số nguyên dương \( n \), gọi \( d(n) \) là số các ước số dương của \( n \), và \( \varphi(n) \) là số các số nguyên dương không vượt quá \( n \) và nguyên tố cùng nhau với \( n \). Liệu có tồn tại một hằng số \( C \) sao cho

\[ \frac{\varphi(d(n))}{d(\varphi(n))} \le C \]

với mọi \( n \ge 1 \)?

Bài toán (IMO Shortlist 2016)

Cho \(\tau(n)\) là số các ước số dương của \(n\). Gọi \(\tau_1(n)\) là số các ước số dương của \(n\) mà khi chia cho 3 có số dư là 1. Tìm tất cả các giá trị nguyên dương của phân số

\[ \frac{\tau(10n)}{\tau_1(10n)}. \]

Bài toán (IMO Shortlist 2004)

Cho \(\tau(n)\) là số các ước số dương của số nguyên dương \(n\). Chứng minh rằng tồn tại vô số số nguyên dương \(a\) sao cho phương trình

\[ \tau(an) = n \]

không có nghiệm nguyên dương \(n\).

Bài toán (IMO Shortlist 2000)

Cho một số nguyên dương \( n \), gọi \( d(n) \) là số tất cả các ước số dương của \( n \). Tìm tất cả các số nguyên dương \( n \) sao cho

\[ d(n)^3 = 4n. \]

Định lý 1

Mọi số hữu tỉ dương đều có thể được viết dưới dạng \(\varphi(m^2)/\varphi(n^2)\), trong đó \(m\) và \(n\) là các số nguyên dương.

Chứng minh

Chúng tôi khẳng định một kết quả mạnh hơn: Nếu \(p_1 < p_2 < \cdots < p_k\) là các số nguyên tố phân biệt và \(a_1, \ldots, a_k\) là các số nguyên, thì tồn tại các số nguyên dương \(m\) và \(n\) với \(mn\) không chia hết cho bất kỳ số nguyên tố nào lớn hơn \(p_k\) sao cho \(p_1^{a_1} \cdots p_k^{a_k} = \varphi(m^2)/\varphi(n^2)\).

Chúng tôi chứng minh khẳng định này bằng quy nạp theo \(p_k\).

Cơ sở của quy nạp là \( p_k = 2 \). Với bất kỳ \( a \in \mathbb{Z} \), rõ ràng \[2^{2a} = \frac{2^{2(a+b)-1}}{2^{2b-1}} = \frac{\varphi(2^{2(a+b)})}{\varphi(2^{2b})}\] cho mỗi số nguyên \( b > |a| \), và \[2^{2a+1} = \begin{cases} \varphi(2^{2(a+1)})/\varphi(1^2) & \text{nếu } a \geq 0, \\ \varphi(1^2)/\varphi(2^{-2a}) & \text{nếu } a < 0. \end{cases}\]

Bây giờ, giả sử \( q \) là một số nguyên tố lẻ và giả định rằng khẳng định đúng khi \( p_k < q \). Gọi \( q_1 < \cdots < q_k = q \) là các số nguyên tố phân biệt và đặt \( r = \prod_{i=1}^k q_i^{a_i} \) với \( a_1, \ldots, a_k \in \mathbb{Z} \). Đặt \( r_0 = r/q_k^{a_k} \) nếu \( 2 \mid a_k \), và \( r_0 = r/((q_k - 1)q_k^{a_k}) \) nếu \( 2 \nmid a_k \). Rõ ràng, tất cả các số nguyên tố trong phân tích của \( r_0 \) đều nhỏ hơn \( q_k = q \). Theo giả thiết quy nạp, tồn tại các số nguyên dương \( m_0 \) và \( n_0 \) với \( m_0n_0 \) không chia hết cho bất kỳ số nguyên tố \( p \geq q_k \) sao cho \[\frac{\varphi(m_0^2)}{\varphi(n_0^2)} = r_0.\]

Rõ ràng, chúng ta có thể lấy \( m_0 = n_0 = 1 \) nếu \( r_0 = 1 \).

Trường hợp 1. \( 2 \mid a_k \)

Trong trường hợp này, chúng ta lấy các số nguyên dương \( b \) và \( c \) với \( b - c = a_k/2 \), và đặt \( m = m_0q^b \) và \( n = n_0q^c \). Khi đó \[\frac{\varphi(m^2)}{\varphi(n^2)} = \frac{\varphi(m_0^2)}{\varphi(n_0^2)} \times \frac{q^{2b-1}(q-1)}{q^{2c-1}(q-1)} = r_0q^{2(b-c)} = \prod_{i=1}^k q_i^{a_i} = r.\]

Trường hợp 2. \( 2 \nmid a_k \)

Khi \( a_k > 0 \), với \( m = m_0q^{(a_k+1)/2} \) và \( n = n_0 \), chúng ta có \[\frac{\varphi(m^2)}{\varphi(n^2)} = \frac{\varphi(m_0^2)}{\varphi(n_0^2)} \times q^{a_k}(q-1) = r_0q^{a_k}(q-1) = \prod_{i=1}^k q_i^{a_i} = r.\]

Nếu \( a_k < 0 \), thì tồn tại các số nguyên dương \( m \) và \( n \) với \( mn \) không chia hết cho bất kỳ số nguyên tố nào lớn hơn \( q_k \) sao cho \( \prod_{i=1}^k q_i^{-a_i} = \varphi(n^2)/\varphi(m^2) \) và do đó \( \prod_{i=1}^k q_i^{a_i} = \varphi(m^2)/\varphi(n^2) \).

Như vậy, khẳng định đúng và do đó định lý cũng đúng.

Link bài báo của định lý này

Bài toán

Cho \( n \in \mathbb{N^*} \). Chứng minh rằng:

\[ \sum_{d \mid n} \sigma(d) \phi \left( \frac{n}{d} \right) = n \tau(n), \]

\[ \sum_{d \mid n} \tau(d) \phi \left( \frac{n}{d} \right) = \sigma(n) \]

Chứng minh

\[ \sum_{d|n} \sigma(d) \phi \left( \frac{n}{d} \right) = \sum_{d|n} \sigma \left( \frac{n}{d} \right) \phi(d) = \sum_{d|n} \left( \sum_{c \mid \frac{n}{d}} c \right) \phi(d) = \sum_{c|n} \sum_{d \mid \frac{n}{c}} \phi(d) c = \sum_{c|n} \left( \frac{n}{c} \right) c = n\sum_{c|n} 1 = n \tau(n) \]

\[ \sum_{d|n} \tau(d) \phi \left( \frac{n}{d} \right) = \sum_{d|n} \tau \left( \frac{n}{d} \right) \phi(d) = \sum_{d|n} \left( \sum_{c \mid \frac{n}{d}} 1 \right) \phi(d) = \sum_{c|n} \sum_{d \mid \frac{n}{c}} \phi(d) = \sum_{c|n} \frac{n}{c} = \sum_{c|n} c \]

\[ = \sigma(n) \]

Ngoài ra còn có thể làm theo cách chứng minh 2 vế đúng với số nguyên tố rồi chứng minh 2 vế là hàm nhân tính.

Bài toán

Cho \( n \) là một số nguyên dương. Chứng minh rằng:

\[ \sum^n_{k=1} \tau(k)=\sum^n_{k=1} \lfloor \frac{n}{k}\rfloor \]

trong đó \( \tau(n) \) là số ước của \( n \).

Chứng minh

Chú ý rằng một số \( 1 \leq d \leq n \) sẽ đóng góp 1 vào \( \tau(m) \) khi và chỉ khi \( d \) chia hết \( m \).

Do đó, trong vế trái, mỗi \( d \) sẽ xuất hiện đúng bằng số lần mà nó là ước của một số \( m \leq n \).

Vì số lần \( d \) là ước của một số nhỏ hơn hoặc bằng \( n \) là \( \lfloor \frac{n}{d} \rfloor \), ta có:

\[ \sum_{m=1}^{n} \tau(m) = \sum_{d=1}^{n} \lfloor \frac{n}{d} \rfloor \]

Vậy ta thu được kết quả mong muốn.

Bài toán

Chứng minh rằng nếu phương trình \( \phi(n) = k \) có một nghiệm duy nhất \( n \), thì \( 36 \) chia hết cho \( n \), trong đó \( \phi(n) \) là hàm số Euler.

Chứng minh

Nếu \( n \) là số lẻ, thì \( \varphi(n) = \varphi(2n) \).

Nếu \( n \equiv 2 \pmod{4} \) thì \( \varphi(n) = \varphi\left(\frac{n}{2}\right) \), suy ra \( 4 \mid n \).

Nếu \( 3 \nmid n \), thì \( \varphi(n) = \varphi\left(\frac{3n}{2}\right) \).

Nếu \( n \equiv 3,6 \pmod{9} \), thì \( \varphi(n) = \varphi\left(\frac{2n}{3}\right) \).

Từ đó suy ra \( 9 \mid n \) và \( 36 \mid n \).

Bài toán

Với mọi số nguyên dương \( n \), ta ký hiệu:

• \( \sigma(n) \) là tổng các ước số của \( n \).
• \( \tau(n) \) là số lượng ước số của \( n \).
• \( \phi(n) \) là hàm số Euler.

Chứng minh rằng nếu \( n \) thỏa mãn điều kiện:

\[ \sigma(n) + \phi(n) = n \tau(n) \]

thì \( n \) là số nguyên tố.

Chứng minh

Bất đẳng thức này thực chất không quá tinh tế như vẻ ngoài của nó, vì ta có thể chứng minh điều sau:

Với \( n > 1 \), \( n \) không phải số nguyên tố, ta có:

\[ \sigma(n) + \varphi(n) < n \tau(n). \] Nhận xét này giúp ta đơn giản hóa vấn đề.

Chứng minh bất đẳng thức

Ta có \( \varphi(n) < n \) cho mọi \( n \) như vậy (đây là một chặn khá thô, nhưng đủ cho mục đích của ta).

Hơn nữa,

\[ \sigma(n) = \sum_{d \mid n} d = \sum_{d \mid n} \frac{d + \frac{n}{d}}{2} \leq \sum_{d \mid n} \frac{n+1}{2} = \frac{n+1}{2} \tau(n) \]

do hàm \( x \mapsto x + \frac{n}{x} \) là hàm lồi trong miền tương ứng.

Giả sử bất đẳng thức không đúng, ta có:

\[ \frac{n+1}{2} \tau(n) + n > n \tau(n). \]

Điều này tương đương với:

\[ \tau(n) < \frac{2n}{n-1}. \] Nhưng ta giả sử \( \tau(n) \geq 3 \), do đó: \[ 2n > 3n - 3 \Rightarrow n < 3, \] mâu thuẫn vì \( n > 1 \) và không phải số nguyên tố.

Do đó, bất đẳng thức đã được chứng minh.

Lưu ý: Ý tưởng chính là cải thiện một chút chặn hiển nhiên \( \sigma(n) \leq n \tau(n) \), vốn đã gần đủ mạnh. Nếu ta không muốn sử dụng lập luận phân tích liên quan đến cặp ước số như trên, ta cũng có thể lập luận rằng ngoài ước số \( n \), tất cả các ước số còn lại đều không vượt quá \( \frac{n}{2} \), từ đó có được chặn dễ dàng:

\[ \sigma(n) \leq \frac{n}{2} (\tau(n) + 1), \]

đủ để giải quyết bài toán ngay lập tức.

Bài toán

Tìm tất cả các hàm số \( f:\mathbb{Z^+} \to \mathbb{Z^+} \) sao cho:

\[ \left(\sum_{d|n} f(d)\right)^2 = \sum_{d|n} f(d)^3 \]

với mọi số nguyên dương \( n \).

Chứng minh

Ký hiệu \( \tau(n) \) là số ước của \( n \) và \( \omega(n) \) là số lượng ước số nguyên tố phân biệt của \( n \).

Dễ dàng kiểm tra rằng \( f(n) = \tau(n) \) với mọi \( n \in \mathbb{Z}^{+} \) thỏa mãn \( \omega(n) \leq 2 \).

Chúng ta sẽ chứng minh rằng \( f(n) = \tau(n) \) với mọi \( n \in \mathbb{Z}^{+} \) bằng phương pháp quy nạp theo \( n \).

Giả sử tồn tại một số nguyên dương \( k \) sao cho \( f(t) = \tau(t) \) đúng với mọi \( t \in \{1,2,\dots,k\} \).

Đặt \( n = k+1 \). Chúng ta cần chứng minh rằng \( f(n) = \tau(n) \).

Không mất tính tổng quát, giả sử \( \omega(n) \geq 3 \).

Ta có:

\[ \sum_{d \mid n} f(n) = f(n) + \sum_{d \mid n, d < n} \tau(d) = -\tau(n) + f(n) + \sum_{d \mid n} \tau(d) \]

và

\[ \sum_{d \mid n} f(n)^3 = f(n)^3 + \sum_{d \mid n, d < n} \tau(d)^3 = -\tau(n)^3 + f(n) + \sum_{d \mid n} \tau(d)^3. \]

Sử dụng đẳng thức:

\[ \left(\sum_{d \mid n} \tau(d)\right)^2 = \sum_{d \mid n} \tau(d)^3, \]

ta suy ra:

\[ (f(n) - \tau(n))^2 + 2(f(n) - \tau(n))\sum_{d \mid n} \tau(d) = (f(n) - \tau(n))\left( f(n)^2 + f(n) \tau(n) + \tau(n)^2 \right). \]

Giả sử rằng \( f(n) \neq \tau(n) \). Khi đó, ta có:

\[ f(n)^2 + (\tau(n) -1) f(n) + \tau(n)^2 + \tau(n) = 2\sum_{d \mid n} \tau(d). \]

Tuy nhiên, ta nhận thấy:

\[ \text{LHS} \geq 1^2 + (\tau(n)-1) \cdot 1 + \tau(n)^2 + \tau(n) > \tau(n)^2. \]

Do đó:

\[ 2 > \frac{\tau(n)^2}{\sum_{d \mid n} \tau(d)} = \prod_{p \mid n} \frac{2(\nu_p(n) + 1)}{\nu_p(n) + 2} \geq \prod_{p \mid n} \frac{4}{3} \geq \left(\frac{4}{3}\right)^3 > 2. \]

Đây là một mâu thuẫn rõ ràng.

Do đó, ta phải có:

\[ f(n) = \tau(n). \]

Bài toán

Hàm \( f(n) \) được định nghĩa như sau:

• \( f(1) = 1 \);
• Với \( n > 1 \), \( f(n) = (-1)^k \), trong đó \( k \) là số lượng ước số nguyên tố của \( n \) (không nhất thiết phải khác nhau).

Ví dụ:

• \( f(12) = (-1)^3 = -1 \).
• \( f(1000) = (-1)^6 = 1 \).

Tính giá trị của tổng

\[ \sum_{d|n} f(d). \]

Chứng minh

Gọi \( f(n) \) là một hàm nhân tính. Nếu \( n = \prod_{i=1}^{k} p_i^{a_i} \), thì tổng các giá trị của \( f \) trên các ước của \( n \) được cho bởi:

\[ \sum_{d|n} f(d) = \prod_{i=1}^{k} \left(1 + f(p_i) + \cdots + f(p_i^{a_i})\right) \]

Áp dụng với \( f(n) = (-1)^{\nu(n)} \), ta có:

\[ \sum_{d|n} f(d) = \prod_{i=1}^{k} \left( (-1)^0 + (-1)^1 + \cdots + (-1)^{a_i} \right) \]

Dãy số hạng trong dấu ngoặc vuông có tổng:

\[ (-1)^0 + (-1)^1 + \cdots + (-1)^{a_i} = \frac{1 + (-1)^{a_i}}{2} \]

Do đó:

\[ \sum_{d|n} f(d) = \prod_{i=1}^{k} \frac{1 + (-1)^{a_i}}{2} \]

Vì có \( k \) thừa số, ta có thể viết gọn lại như sau:

\[ \sum_{d|n} f(d) = \frac{1}{2^k} \prod_{i=1}^{k} (1 + (-1)^{a_i}) \]

Tóm lại nó bằng 1 nếu \(n\) là số chính phương, ngược lại bằng 0.

Bài toán

Gọi \( \tau(n) \) là số ước số dương của \( n \) và \( \varphi(n) \) là hàm số Euler Totient. Tìm tất cả các số nguyên dương \( n \) thỏa mãn:

\[ \varphi(n) + \tau(n^2) = n. \]

Chứng minh

Chúng ta có phương trình Diophantine

\[ (1) \;\ \varphi(n) + \tau(n^2) = n, \]

trong đó \( n \) là một số tự nhiên. Rõ ràng \( n > 2 \) theo phương trình (1). Gọi \( n = \prod_{i=1}^k p_i^{r_i} \) là phân tích nguyên tố của \( n \) với \( p_1 < p_2 < \cdots < p_k \). Áp dụng phân tích này vào phương trình (1), ta thu được

\[ (2) \;\; \prod_{i=1}^k p_i^{r_i-1}(p_i - 1) + \prod_{i=1}^k (2r_i + 1) = \prod_{i=1}^k p_i^{r_i}. \]

Vì \( \varphi(n) \) là số chẵn (do \( n > 2 \)), nên vế trái (LHS) của phương trình (1) là số lẻ, suy ra \( n \) là số lẻ.

Bằng cách chia cả hai vế của phương trình (2) cho \( \prod_{i=1}^k p_i^{r_i} \), ta có

\[ (3) \;\; \prod_{i=1}^k {\textstyle (1 - \frac{1}{p_i})} + \prod_{i=1}^k {\textstyle \frac{2r_i + 1}{p_i^{r_i}} = 1}. \]

Đặt \( {\textstyle F(p,r) = \frac{2r + 1}{p^r}} \), trong đó \( p \) là một số nguyên tố lẻ và \( r \) là một số tự nhiên. Khi đó

\[ {\textstyle F(p,r) - F(p,r+1) = \frac{2r + 1}{p^r} - \frac{2r + 3}{p^{r+1}} = \frac{p(2r + 1) - (2r + 3)}{p^{r + 1}} \geq \frac{3(2r + 1)- (2r + 3)}{p^{r+1}} = \frac{4r}{p^{r+1}} > 0}, \]

suy ra \( {\textstyle F(p,r) \leq F(p,1) = \frac{3}{p}} \). Kết hợp với phương trình (3), ta có

\[ (4) \;\; \prod_{i=1}^k {\textstyle (1 - \frac{1}{p_i})} + \prod_{i=1}^k {\textstyle \frac{3}{p_i} \geq 1}. \]

Nếu \( k \geq 3 \), thì trong phương trình (4)

\[ LHS \leq \prod_{i=1}^3 {\textstyle (1 - \frac{1}{p_i})} + \prod_{i=1}^3 {\textstyle \frac{3}{p_i} \leq \frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} + \frac{3}{3} \cdot \frac{3}{5} \cdot \frac{3}{7} = \frac{16}{35} +\frac{9}{35} = \frac{25}{35} = \frac{5}{7} < 1}, \]

mâu thuẫn này cho thấy \( k < 3 \).

Trường hợp 1: \( k = 1 \)

Khi đó \( n = p^r \), trong đó \( p \) là một số nguyên tố và \( r \) là một số tự nhiên. Phương trình (1) trở thành

\[ p^{r-1}(p - 1) + (2r + 1) = p^r, \]

tức là

\[ (5) \;\; p^{r-1} = 2r + 1. \]

Rõ ràng \( r > 1 \) theo phương trình (5). Hơn nữa, \( p \geq 3 \) cho ta

\[ 3^{r-1} \leq 2r + 1, \]

suy ra \( r < 3 \). Do đó \( r = 2 \) (vì \( r > 1 \)), thay vào phương trình (5) ta được \( p = 5 \). Vậy nghiệm duy nhất của phương trình (1) là \( n = p^r = 5^2 = 25 \).

Trường hợp 2: \( k = 2 \)

Khi đó \( n = p^u \cdot q^v \), trong đó \( p < q \) là hai số nguyên tố và \( u, v \) là hai số tự nhiên. Phương trình (1) trở thành

\[ {\textstyle (6) \;\; (1 - \frac{1}{p})(1 - \frac{1}{q}) + \frac{2u + 1}{p^u} \cdot \frac{2v + 1}{q^v} = 1}. \]

Theo phương trình (6), ta có

\[ {\textstyle (1 - \frac{1}{p})(1 - \frac{1}{q}) + \frac{3}{p} \cdot \frac{3}{q} \geq 1}, \]

tương đương với

\[ (p - 1)(q - 1) + 9 \geq pq, \]

tức là

\[ (7) \;\; p + q \leq 10. \]

Bất đẳng thức này cho ta \( p = 3 \) và \( q \in \{5, 7\} \), và đẳng thức xảy ra khi và chỉ khi \( (p, q, u, v) = (3, 7, 1, 1) \). Nói cách khác, \( n = 3^1 \cdot 7^1 = 21 \) là một nghiệm của phương trình (1).

Cuối cùng, ta xét trường hợp \( (p, q) = (3, 5) \), thay vào phương trình (6) ta được

\[ {\textstyle \frac{2}{3} \cdot \frac{4}{5} + \frac{2u + 1}{3^u} \cdot \frac{2v + 1}{5^v} = 1}, \]

tức là

\[ {\textstyle (8) \;\; \frac{2u + 1}{3^u} \cdot \frac{2v + 1}{5^v} = \frac{7}{15}}. \]

Nếu \( \max\{u, v\} > 1 \), thì theo phương trình (8)

\[ {\textstyle \frac{7}{15} = F(3,u) \cdot F(5,v) \leq \max\{F(3,1) \cdot F(5,2), F(3,2) \cdot F(5,1) \} = \max\{\frac{3}{3^1} \cdot \frac{5}{5^2}, \frac{5}{3^2} \cdot \frac{3}{5^1}\} = \max\{\frac{1}{5},\frac{1}{3}\} = \frac{1}{3}}, \]

mâu thuẫn này cho thấy \( u = v = 1 \). Do đó

\[ {\textstyle \frac{2u + 1}{3^u} \cdot \frac{2v + 1}{5^v} = \frac{3}{3} \cdot \frac{3}{5} = \frac{3}{5}}, \]

rõ ràng mâu thuẫn với phương trình (8). Vậy nghiệm duy nhất của phương trình (1) là \( n = 21 \).

Kết luận

Phương trình (1) có đúng hai nghiệm, đó là \( n = 21 \) và \( n = 25 \).

Bài toán

Chứng minh rằng nếu \( n = p_1^{a_1} p_2^{a_2} p_3^{a_3} \dots p_r^{a_r} \), thì

\[ \sum_{d|n} d\phi(d) = \frac{p_1^{2a_1+1} + 1}{p_1 + 1} \dots \frac{p_r^{2a_r+1} + 1}{p_r + 1} \]

Chứng minh

Ta có:

\[ \sum_{d\mid n}d\phi(d) = \sum_{d\mid n}\frac nd\phi\left(\frac nd\right) = n\sum_{d\mid n}\frac 1d\phi\left(\frac nd\right) = n(\text{id}^{-1} * \phi)(n). \]

Do đó, biểu thức trên là một hàm số nhân.

Để thu được kết quả mong muốn, ta chỉ cần đánh giá biểu thức này tại các lũy thừa của số nguyên tố.

Bài toán

Cho \( \xi \) là một số thực dương tùy ý. Chứng minh rằng tồn tại một số nguyên dương \( n \), phụ thuộc vào \( \xi \), sao cho

\[ \frac{\phi(n)}{n} < \xi. \]

Chứng minh

Khẳng định 1.

\(\varphi(n)/n\) có thể tiến tới 1 một cách tùy ý. Cụ thể hơn, tồn tại một dãy tăng \( n_k \) sao cho \( \varphi(n_k)/n_k \to 1 \) khi \( k\to+\infty \).

Chứng minh. Chọn \( n = p \) là một số nguyên tố, khi đó:

\[ \frac{\varphi(n)}{n} = 1 - \frac{1}{p} \]

Rõ ràng, biểu thức này có thể tiến tới 1 một cách tùy ý khi \( p \) tăng vô hạn.

Khẳng định 2.

\(\varphi(n)/n\) có thể tiến tới 0 một cách tùy ý. Cụ thể hơn, tồn tại một dãy tăng \( n_k \) sao cho \( \varphi(n_k)/n_k \to 0 \) khi \( k\to+\infty \).

Chứng minh. Chứng minh này dựa vào thực tế đã biết rằng:

\[ \sum_{p \,{\rm prime}}\frac1p = +\infty. \]

Ta chứng minh rằng:

\[ \prod_{p\, {\rm prime}}\left(1-\frac1p\right) = 0. \]

Giả sử tích trên bằng một hằng số \( c > 0 \). Lấy logarit cả hai vế, ta có:

\[ \ln c = \sum_{p\, {\rm prime}} \ln\left(1-\frac1p\right) \leqslant -\sum_{p\, {\rm prime}}\frac1p = -\infty. \]

Điều này mâu thuẫn, vì \( \ln c \) phải hữu hạn. Ở đây, ta đã sử dụng bất đẳng thức nổi tiếng:

\[ e^{-x} \geqslant 1 - x \quad \Leftrightarrow \quad -x \geqslant \ln(1-x). \]

Bây giờ, đặt \( n_k = \prod_{\ell=1}^k p_k \), trong đó \( p_k \) là số nguyên tố thứ \( k \). Theo điều vừa chứng minh, ta có:

\[ \frac{\varphi(n_k)}{n_k} \to 0 \quad \text{khi } k \to \infty. \]

Do đó, ta suy ra khẳng định cần chứng minh.

Bài toán

(IMO 1998) Với mỗi số nguyên dương \( n \), ký hiệu \( \tau(n) \) là số ước số dương của \( n \) (bao gồm cả 1 và chính nó). Xác định tất cả các số nguyên dương \( m \) sao cho tồn tại số nguyên dương \( n \) thỏa mãn:

\[ \frac{\tau(n^2)}{\tau(n)} = m. \]

Bài toán

(RMM 2011 P4) Cho một số nguyên dương \( n = \prod_{i=1}^s p_i^{\alpha_i} \). Ta ký hiệu \( \Omega(n) \) là tổng số mũ của các thừa số nguyên tố của \( n \), tức là:

\[ \Omega(n) = \sum_{i=1}^{s} \alpha_i. \]

Định nghĩa hàm \( \lambda(n) \) như sau:

\[ \lambda(n) = (-1)^{\Omega(n)} \]

Ví dụ, ta có:

\[ \lambda(12) = \lambda(2^2 \cdot 3^1) = (-1)^{2+1} = -1. \]

Chứng minh hai khẳng định sau:

1. Có vô hạn số nguyên dương \( n \) sao cho \( \lambda(n) = \lambda(n+1) = +1 \).
2. Có vô hạn số nguyên dương \( n \) sao cho \( \lambda(n) = \lambda(n+1) = -1 \).

Link lời giải

Bài toán

(IMO Shortlist 2018 N1) Xác định tất cả các cặp số nguyên dương phân biệt \( (n, k) \) sao cho tồn tại một số nguyên dương \( s \) thỏa mãn số ước của \( sn \) và số ước của \( sk \) bằng nhau.

Chứng minh:

Giả sử \( m \neq n \), nếu không bài toán trở nên hiển nhiên (chọn bất kỳ \( s \)).

Rõ ràng nếu \( m \mid n \) hoặc \( n \mid m \) thì không tồn tại số \( s \) như yêu cầu.

Mệnh đề: Nếu \( \alpha > \beta \geq 0 \) là các số nguyên thì với mọi \( M \geq \beta+1 \), tồn tại \( \gamma \in \mathbb{Z}_{\geq 0} \) sao cho:

\[ \frac{\alpha+\gamma+1}{\beta+\gamma+1} = \frac{M+1}{M}. \]

Có thể kiểm chứng bằng cách đặt:

\[ \gamma = M(\alpha-\beta) - \beta+1. \]

Giả sử:

\[ m = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} q_1^{\alpha'_1} \dots q_\ell^{\alpha'_\ell}, \] \[ n = p_1^{\beta_1} p_2^{\beta_2} \dots p_k^{\beta_k} q_1^{\beta'_1} \dots q_\ell^{\beta'_\ell}. \]

Với điều kiện \( \alpha_i > \beta_i \) và \( \beta_j' > \alpha_j' \).

Chọn \( s \) như sau:

\[ s = \prod_i p_i^{\gamma_i} \prod_j q_j^{\gamma'_j}. \]

Khi đó:

\[ \frac{d(sm)}{d(sn)} = \prod_i \frac{\gamma_i + \alpha_i + 1}{\gamma_i + \beta_i + 1} \prod_j \frac{\gamma'_j + \alpha'_j + 1}{\gamma'_j + \beta'_j + 1} = \frac{T+1}{T} \cdot \frac{T}{T+1} = 1. \]

Vậy ta đã chứng minh được điều cần thiết. \( \square \)

Bài toán

Chứng minh rằng:

1. \(\sigma (n)+\varphi (n)\geq 2n\)
2. \(\sum_{i=1}^{n} \tau (i)=2\sum _{i=1}^{[\sqrt{n}]}[\frac{n}{i}]-[\sqrt{n}]^{2}\)

Chứng minh

1. Ta sử dụng phương pháp quy nạp. Các trường hợp cơ sở là hiển nhiên.

Giả sử ta đã chứng minh điều này cho \( 1,2,\dotsc,n-1 \). Xét \( n \).

Nếu \( n \) là số nguyên tố, ta có:

\[ \sigma(n) = n+1, \quad \varphi(n) = n-1 \]

Suy ra đẳng thức được thỏa mãn.

Nếu \( n \) là hợp số, tức là \( n = pq \) với \( (p,q) = 1 \), ta có:

\[ \sigma(p) > p > \varphi(p) \]

Điều này kéo theo:

\[ (\sigma(p) - \varphi(p))(\sigma(q) - \varphi(q)) > 0 \]

tức là:

\[ \sigma(n) + \varphi(n) > \varphi(p) \sigma(q) + \varphi(q) \sigma(p) \]

Từ đó, ta có:

\[ 2\sigma(n) + 2\varphi(n) > (\sigma(p) + \varphi(p)) (\sigma(q) + \varphi(q)) \geq 2p \cdot 2q = 4n \]

do đó bước quy nạp được thiết lập.

Ta cũng cần chứng minh mệnh đề cho lũy thừa của số nguyên tố (nếu không, ta có thể gặp trường hợp \( \gcd(p, q) \neq 1 \)).

Điều này khá đơn giản:

\[ \sigma(p^k) + \varphi(p^k) = \frac{p^{k+1} - 1}{p - 1} + (p - 1) \cdot p^{k-1} \geq 2p^k \]

Với dấu bằng xảy ra khi và chỉ khi \( k = 1 \).

Chú ý rằng đẳng thức chỉ có thể xảy ra nếu \( n \) là số nguyên tố hoặc \( n = 1 \).

Đối với phần 2), ta biết rằng

\[ \sum_{i=1}^n \tau(i) = \sum_{k=1}^n \left \lfloor \frac{n}{k} \right \rfloor. \]

Do đó, ta chỉ cần chứng minh rằng

\[ \sum_{k=1}^{\left \lfloor \sqrt{n} \right \rfloor} \left \lfloor \frac{n}{k} \right \rfloor - \left \lfloor \sqrt{n} \right \rfloor^2 = \sum_{k=\left \lfloor \sqrt{n} \right \rfloor+1}^{n} \left \lfloor \frac{n}{k} \right \rfloor. \]

Ta sẽ chứng minh điều này bằng quy nạp theo \( n \). Với \( n = 1 \), điều này đúng. Bây giờ ta cần chứng minh cho \( n + 1 \) nếu nó đúng cho \( n \).

\[ \sum_{k=1}^{\left \lfloor \sqrt{n+1} \right \rfloor} \left \lfloor \frac{n+1}{k} \right \rfloor - \left \lfloor \sqrt{n+1} \right \rfloor^2 = \sum_{k=\left \lfloor \sqrt{n+1} \right \rfloor+1}^{n+1} \left \lfloor \frac{n+1}{k} \right \rfloor. \]

Một nhận xét rằng nếu \( i \mid n+1 \) thì \( \left \lfloor \frac{n}{i} \right \rfloor + 1 = \left \lfloor \frac{n+1}{i} \right \rfloor \), ngược lại \( \left \lfloor \frac{n}{i} \right \rfloor = \left \lfloor \frac{n+1}{i} \right \rfloor \). Ta xét hai trường hợp:

Trường hợp 1

Nếu \( a^2 \le n \le (a+1)^2 - 2 \). Điều này có nghĩa là \( \left \lfloor \sqrt{n} \right \rfloor = \left \lfloor \sqrt{n+1} \right \rfloor \). Từ nhận xét trên, ta có

\[ \sum_{k=1}^{\left \lfloor \sqrt{n+1} \right \rfloor} \left \lfloor \frac{n+1}{k} \right \rfloor = \sum_{k=1}^{\left \lfloor \sqrt{n} \right \rfloor} \left \lfloor \frac{n}{k} \right \rfloor + \frac{\tau(n+1)}{2}. \]

Điều này là do \( n+1 \) không phải là số chính phương nên có đúng \( \frac{\tau(n+1)}{2} \) ước số của \( n+1 \) nhỏ hơn hoặc bằng \( \left \lfloor \sqrt{n+1} \right \rfloor \). Tương tự, ta có

\[ \sum_{k=\left \lfloor \sqrt{n+1} \right \rfloor+1}^{n+1} \left \lfloor \frac{n+1}{k} \right \rfloor = \sum_{k=\left \lfloor \sqrt{n} \right \rfloor+1}^{n} \left \lfloor \frac{n}{k} \right \rfloor + \frac{\tau(n+1)}{2}. \]

Từ hai đẳng thức này và \( \left \lfloor \sqrt{n} \right \rfloor = \left \lfloor \sqrt{n+1} \right \rfloor \), ta thu được đẳng thức cần chứng minh.

Trường hợp 2

Nếu \( n = (a+1)^2 - 1 \), thì \( n+1 \) là một số chính phương. Điều này có nghĩa là \( \left \lfloor \sqrt{n+1} \right \rfloor^2 = n+1 = \left( \left \lfloor \sqrt{n} \right \rfloor + 1 \right)^2 \). Vì \( n+1 \) là số chính phương nên có \( \frac{\tau(n+1) - 1}{2} \) ước số nhỏ hơn \( \left \lfloor \sqrt{n+1} \right \rfloor \). Kết hợp với nhận xét, ta có

\[ \sum_{k=1}^{\left \lfloor \sqrt{n+1} \right \rfloor} \left \lfloor \frac{n+1}{k} \right \rfloor = \sqrt{n+1} + \sum_{k=1}^{\left \lfloor \sqrt{n+1} \right \rfloor - 1} \left \lfloor \frac{n}{k} \right \rfloor = \sqrt{n+1} + \sum_{k=1}^{\left \lfloor \sqrt{n} \right \rfloor} \left \lfloor \frac{n}{k} \right \rfloor + \frac{\tau(n+1) - 1}{2}. \]

Và ta cũng có

\[ \sum_{k=\left \lfloor \sqrt{n+1} \right \rfloor+1}^{n+1} \left \lfloor \frac{n+1}{k} \right \rfloor = \sum_{k=\left \lfloor \sqrt{n+1} \right \rfloor}^{n+1} \left \lfloor \frac{n+1}{k} \right \rfloor - \sqrt{n+1} = \sum_{k=\left \lfloor \sqrt{n} \right \rfloor+1}^{n} \left \lfloor \frac{n}{k} \right \rfloor + \frac{\tau(n+1) + 1}{2} - \sqrt{n+1}. \]

Từ hai đẳng thức này và \( \left \lfloor \sqrt{n+1} \right \rfloor^2 = \left( \left \lfloor \sqrt{n} \right \rfloor + 1 \right)^2 \), ta thu được đẳng thức cần chứng minh.

Bài toán

Ký hiệu \(\tau(n)\) là số ước của \(n\). Chứng minh rằng:

\[ \tau(n) \leq 2\sqrt{n} \]

Chứng minh

Đây là một kết quả cổ điển. Chứng minh ngay lập tức từ thực tế rằng với mỗi ước \( d \) của \( n \), ít nhất một trong hai số \( d \) và \( \frac{n}{d} \) (cũng là một ước của \( n \)) thỏa mãn điều kiện:

\[ d \leq \sqrt{n} \quad \text{hoặc} \quad \frac{n}{d} \leq \sqrt{n}. \]

Điều này đảm bảo rằng mọi ước của \( n \) đều có thể được đếm bằng cách chỉ xét các ước \( d \leq \sqrt{n} \), từ đó suy ra mệnh đề cần chứng minh.

Bài toán

Chứng minh rằng nếu \( n \in \mathbb{N} \), \( n > 1 \) và \( r \) là số ước nguyên tố khác nhau của \( n \), thì:

\[ S(n) = \sum_{d \mid n} \left| \mu(d) \right| = 2^r. \]

Ghi chú: \( S \) là một hàm nhân tính.

Chứng minh

Vì hàm Möbius \(\mu\) là hàm nhân tính và giá trị tuyệt đối cũng bảo toàn tính nhân tính, nên \(|\mu(d)|\) cũng là hàm nhân tính. Một kết quả đã biết là nếu \(g\) là hàm nhân tính thì tổng \(\sum_{d|n} g(d)\) cũng là hàm nhân tính. Do đó, \(S(n)\) là hàm nhân tính.

Giờ ta chỉ cần kiểm tra giá trị của \(S(n)\) với lũy thừa của số nguyên tố. Giả sử \(p\) là số nguyên tố và \(a\) là số nguyên dương, khi đó:

\[ S(p^a) = \sum_{k=0}^{a} |\mu(p^k)| = 1 + 1 + 0 + 0 + \ldots + 0 = 2. \]

Do \(S(n)\) là hàm nhân tính, suy ra:

\[ S(n) = 2^r. \]

Vậy ta đã chứng minh được kết quả.

Bài toán

Cho \(\sigma(n)\) là tổng các ước số dương của số tự nhiên \(n\). Chứng minh rằng:

\[ 6 \mid \sigma(6n+5) \quad \forall n \in \mathbb{N} \]

Chứng minh

Bổ đề: Nếu \( ab = 6n + 5 \) thì \( 6 \) chia hết cho \( a + b \).

Chứng minh: Giả sử \( a \equiv 1 \pmod{6} \), khi đó \( ab \equiv 5 \pmod{6} \) suy ra \( b \equiv 5 \pmod{6} \).

Mặt khác, \( a \) không thể đồng dư \( 0,2,3,4 \pmod{6} \). Nếu \( a \equiv 5 \pmod{6} \) thì \( b \equiv 1 \pmod{6} \).

Vậy trong cả hai trường hợp, ta có:

\[ a + b \equiv 0 \pmod{6} \]

tức là \( 6 \) chia hết cho \( a + b \).

Áp dụng bổ đề: Sử dụng bổ đề trên, ta suy ra kết quả bài toán.

Bài toán

Chứng minh rằng với mọi số nguyên dương \( n \), ta có:

\[ 3 \mid \sigma(3n+2) \quad \text{và} \quad 4 \mid \sigma(4n+3). \] Làm hoàn toàn tương tự bài trên.

Bài toán

Cho \( n \ge 2 \) là một số nguyên dương và ký hiệu \( \sigma(n) \) là tổng các ước số dương của \( n \). Chứng minh rằng số nguyên dương nhỏ nhất thứ \( n \) mà nguyên tố cùng nhau với \( n \) có giá trị ít nhất là \( \sigma(n) \), và xác định các giá trị của \( n \) sao cho đẳng thức xảy ra.

Link lời giải

Bài toán

Gọi \(\sigma(\cdot)\) là hàm tổng ước và \(d(\cdot)\) là hàm đếm ước. Tìm tất cả các số nguyên dương \(n\) thỏa mãn:

\[ \sigma(d(n)) = n. \]

Chứng minh

Trước tiên, kiểm tra rằng với \( d(N) \leq 9 \), các nghiệm duy nhất là \( N = 1, 3, 4, 12 \). Các trường hợp \( N \leq 7 \) cũng được xử lý tương tự, do đó giả sử từ đây trở đi rằng \( d(N) \geq 10 \) và \( N \geq 8 \).

Trước hết, ta nhớ lại ước lượng quen thuộc:

\[ d(N) \leq 2\sqrt{N}. \]

Chứng minh

Ta tiếp tục chứng minh rằng với mọi \( N \geq 8 \) và \( d(N) \geq 3 \), ta có:

\[ \sigma(N) \leq \frac{N d(N)}{2}. \]

Kết hợp với bất đẳng thức \( d(N) \leq 2\sqrt{N} \), ta thu được:

\[ N = \sigma(d(N)) \leq \frac{d(N) d(d(N))}{2} \leq \sqrt{N} 2\sqrt{d(N)} \leq 2\sqrt{2} N^{\frac{3}{4}} \Rightarrow N \leq 64. \]

Chứng minh Mệnh đề

Cuối cùng, nếu \( d(N) \geq 16 \) thì từ \( d(N) \leq 2\sqrt{N} \) suy ra \( N \geq 64 \). Do đó, ta chỉ cần xem xét các trường hợp \( d(N) \in \{10, \dots, 15\} \), điều này có thể kiểm tra dễ dàng và bỏ qua ở đây.

Bài toán

Với mỗi số nguyên dương \( k \), ký hiệu \( d(k) \) là số ước số nguyên dương của \( k \) và \( \sigma(k) \) là tổng các ước số nguyên dương của \( k \). Gọi \( \mathbb{N} \) là tập hợp các số nguyên dương. Tìm tất cả các hàm số \( f: \mathbb{N} \to \mathbb{N} \) sao cho:

\[ f(d(n+1)) = d(f(n)+1) \] \[ f(\sigma(n+1)) = \sigma(f(n)+1) \]

đúng với mọi số nguyên dương \( n \).

Chứng minh

Bổ đề 1: \(x = d(x+1) \Leftrightarrow x \in \{2,3\}.\)

Chứng minh:

Giả sử \( x+1 = 2^a \cdot 3^b \cdot p_1^{e_1} \cdots p_k^{e_k} \). Khi đó, ta có:

\[ 2^a \cdot 3^b \cdot p_1^{e_1} \cdots p_k^{e_k} = (a+1)(b+1)(e_1+1) \cdots (e_k+1) + 1. \]

Lưu ý rằng, với mọi \( p \geq 5 \), ta có: \( p^k \geq 4k+1 \); \( 3^a \geq 2a+1 \); và \( 2^a \geq \max \{2a, a+1\} \).

Nếu \( x+1 \) có ước số nguyên tố \( \geq 5 \) hoặc \( e_1 \geq 1 \), thì:

\[ x+1 \geq (a+1)(2b+1)(4e_1+1) \cdots (4e_k+1). \]

Suy ra:

\[ x+1 \geq (a+1)(b+1)(e_1+1) \cdots (e_k+1) + 3e_1 \geq d(x+1) + 1, \]

mâu thuẫn xảy ra.

Do đó, ta có \( x+1 = 2^a \cdot 3^b \), và phương trình trở thành:

\[ (a+1)(b+1) + 1 = 2^a \cdot 3^b. \]

Xét bất đẳng thức:

\[ 2 \geq 3ab + a. \]

Dễ dàng kiểm tra rằng chỉ có hai nghiệm \( (a,b) \) thỏa mãn là \( (2,0) \) và \( (0,1) \), tương ứng với \( x \in \{2,3\} \).

Hệ quả:

\[ \begin{cases} f(d(n+1)) = d(f(n) + 1), & (1) \\ f(\sigma(n+1)) = \sigma(f(n) + 1). & (2) \end{cases} \]

Xét \( n = 3 \) trong phương trình (1), từ Bổ đề 1 ta có: \( f(3) \in \{2,3\} \).

Xét \( n = 1 \) trong phương trình (2), ta có:

\[ \sigma(f(1) + 1) = f(3) \in \{2,3\}. \]

Không có số nguyên dương \( x \) nào thỏa mãn \( \sigma(x) = 2 \), nên suy ra \( f(3) = 3 \), do đó \( f(1) = 1 \).

Mệnh đề 1: \( f(2^k - 1) = 2^k - 1, \forall k \).

Chứng minh:

Ta chứng minh bằng quy nạp. Trường hợp cơ sở \( n = 1,2 \) đã được kiểm tra.

Giả sử \( f(2^k - 1) = 2^k - 1 \), thế \( n = 2^k - 1 \) vào phương trình (2), ta có:

\[ f(\sigma(2^k)) = \sigma(f(2^k - 1) + 1) = \sigma(2^k). \]

Suy ra:

\[ f(2^{k+1} - 1) = 2^{k+1} - 1. \]

Vậy, \( f(2^k - 1) = 2^k - 1 \) đúng với mọi \( k \).

Cuối cùng, thế \( x = 2^k - 1 \) vào phương trình (1), ta có:

\[ f(d(2^k)) = d(f(2^k - 1) + 1) = d(2^k). \]

Suy ra:

\[ f(k+1) = k+1. \]

Do đó, với mọi \( n \), ta có:

\[ f(n) = n. \]

Q.E.D

Bài toán

Xác định tất cả các đa thức \( P(x) \) với hệ số nguyên sao cho \( P(n) \) chia hết cho \( \sigma(n) \) với mọi số nguyên dương \( n \). (Như thường lệ, \( \sigma(n) \) ký hiệu tổng các ước số dương của \( n \).)

Chứng minh

Với \( k \in \mathbb{N} \) cố định, xét \( n = kp \) với \( p \) là một số nguyên tố lớn. Khi đó:

\[ \sigma(n) = \sigma(k)(p+1) \]

suy ra \( p+1 \) chia hết cho \( P(kp) \), do đó \( p+1 \mid P(-k) \).

Vì \( k \) cố định và \( p \) có thể lớn tùy ý, điều này dẫn đến \( P(-k) = 0 \).

Nhưng vì \( k \) là tùy ý, ta suy ra rằng \( P \) có vô số nghiệm, do đó \( P \) phải là đa thức không.

Bài toán

Chứng minh rằng với mọi số tự nhiên \( n \), bất đẳng thức sau luôn đúng:

\[ \sum_{i=1}^{n} \frac{\sigma(i)}{i} \leq 2n, \]

trong đó, \(\sigma(n)\) là hàm tổng ước của \( n \) (tức là \(\sigma_1(n)\)).

Chứng minh

Ta có:

\[ \sum_{k=1}^n \frac{\sigma(k)}{k} = \sum_{k=1}^{n} \sum_{d \mid k} \frac{d}{k}. \]

Đổi thứ tự tổng:

\[ \sum_{d=1}^{n} d \sum_{1 \le k \le n, d \mid k} \frac{1}{k}. \]

Viết lại dưới dạng chỉ số:

\[ \sum_{d=1}^{n} d \sum_{j=1}^{\lfloor n/d \rfloor} \frac{1}{jd} = \sum_{d=1}^n \sum_{j=1}^{\lfloor n/d \rfloor} \frac{1}{j}. \]

Tiếp tục đổi thứ tự tổng:

\[ \sum_{j=1}^n \frac{1}{j} \sum_{d=1}^{\lfloor n/j \rfloor} 1. \]

Từ đây, ta có:

\[ \sum_{j=1}^n \frac{1}{j} \sum_{d=1}^{\lfloor n/j \rfloor} 1 \le \sum_{j=1}^n \frac{n}{j^2} \le n \frac{\pi^2}{6} < 2n. \]

Vậy ta chứng minh được bất đẳng thức cần tìm.

Bài toán

Cho \( n \) là một số nguyên dương thỏa mãn \( 24 \mid n+1 \). Chứng minh rằng tổng các ước dương của \( n \) chia hết cho 24.

Chứng minh

Kiểm tra rằng \( 24 \mid d + (n/d) \) với mọi \( d \) là ước của \( n \), và luôn có \( d \neq n/d \).

Bài toán

Cho \( n \) là một số nguyên dương. Ký hiệu \( \sigma(n) \) là tổng các ước tự nhiên của \( n \) (bao gồm cả \( 1 \) và \( n \)). Một số nguyên \( m \geq 1 \) được gọi là siêu dư (superabundant) (P. Erdős, 1944) nếu với mọi \( k \in \{1, 2, \dots , m - 1 \} \), ta có:

\[ \frac{\sigma(m)}{m} >\frac{\sigma(k)}{k}. \]

Chứng minh rằng tồn tại vô số số siêu dư.

Chứng minh

Gọi \( f(n) = \frac{\sigma(n)}{n} \).

Mệnh đề

Gọi \( p_i \) là số nguyên tố thứ \( i \). Khi đó, tích vô hạn:

\[ \prod_{i=1}^\infty \left(1+\frac{1}{p_i}\right) \]

phân kỳ. Rõ ràng ta có:

\[ \prod_{i=1}^\infty \left(1+\frac{1}{p_i}\right) \geq 1 + \frac{1}{p_1} + \frac{1}{p_2} + \frac{1}{p_3} + \cdots. \]

Ta biết rằng tổng các nghịch đảo của các số nguyên tố phân kỳ, do đó điều này chứng minh mệnh đề.

Vì hàm \(\sigma\) và do đó \(f\) là hàm nhân tính, ta có:

\[ f(p_1) = \left(1+\frac{1}{p_1}\right), \] \[ f(p_1 p_2) = \left(1+\frac{1}{p_1}\right)\left(1+\frac{1}{p_2}\right), \] \[ f(p_1 p_2 p_3) = \left(1+\frac{1}{p_1}\right)\left(1+\frac{1}{p_2}\right)\left(1+\frac{1}{p_3}\right), \]

và cứ thế tiếp tục. Vì tích này phân kỳ, hàm \( f \) có thể đạt giá trị lớn tùy ý. Do đó, nó phải đạt cực đại mới vô số lần. Q.E.D.

Bài toán

(Bulgaria IMO TST 2023 Problem 4) Xác định tất cả các số nguyên dương \( n \) sao cho \( \sigma(n) \nmid n! \) và \( \sigma(n+1) \nmid (n+1)! \). (Như thường lệ, \( \sigma \) ký hiệu tổng các ước số dương.)

Chứng minh

Ta gọi một số nguyên dương \( n \) là thú vị nếu \( \sigma(n) \nmid n! \).

Mệnh đề chính

Mọi số nguyên thú vị \( n > 3 \) đều là lũy thừa chẵn của số nguyên tố.

Chứng minh: Giả sử \( n \) là một số nguyên thú vị nhưng không phải là lũy thừa của một số nguyên tố. Rõ ràng, \( n = 1 \) không thú vị, do đó ta viết:

\[ n = \prod\limits_{i=1}^{k} p_{i}^{\alpha_{i}}, \quad k \geq 2. \]

Với \( \sigma(n) = \prod\limits_{i=1}^{k} \sum\limits_{t=0}^{\alpha_{i}} p_{i}^{t} \), ta đặt:

\[ A_{i} = \sum\limits_{t=0}^{\alpha_{i}} p_{i}^{t}, \quad S(n) = \sum\limits_{i=1}^{k} A_{i}. \]

Nếu giả sử \( S(n) \leq n \), ta có:

\[ n! = A_{1}! \cdot \frac{(A_{1}+A_{2})!}{A_{1}!} \cdot \frac{(A_{1}+A_{2}+A_{3})!}{(A_{1}+A_{2})!} \cdots \frac{S(n)!}{(A_{1}+A_{2}+\dots+A_{k-1})!} \cdot \frac{n!}{S(n)!}. \]

Do đó, \( \sigma(n) = \prod\limits_{i=1}^{k} A_{i} \mid n! \) vì \( A_{i}! \mid \frac{(A_{1}+\dots +A_{i})!}{(A_{1}+\dots +A_{i-1})!} \) và \( S(n)! \mid n! \). Vì \( n \) là thú vị, ta có \( S(n) > n \). Chứng minh rằng bất đẳng thức này không đúng với hầu hết các \( n \):

\[ A_{i} = \frac{p_{i}^{\alpha_{i}+1}-1}{p_{i}-1} < \frac{2p_{i}^{\alpha_{i}+1}-p_{i}^{\alpha_{i}}}{p_{i}-1} = 2p_{i}^{\alpha_{i}}. \]

Suy ra:

\[ n < S(n) = \sum\limits_{i=1}^{k} A_{i} < 2\sum\limits_{i=1}^{k} p_{i}^{\alpha_{i}} \Longrightarrow \frac{1}{2} < \sum\limits_{i=1}^{k} \frac{1}{\prod\limits_{j \neq i} p_{j}^{\alpha_{j}}} \leq \sum\limits_{i=1}^{k} \frac{1}{\prod\limits_{j \neq i} p_{j}}. \] \[ \leq \sum\limits_{i=1}^{k} \frac{1}{2^{k-1}} = \frac{k}{2^{k-1}}. \]

Điều này cho thấy \( 2^{k-2} < k \), tương đương \( k < 4 \). Nếu \( k = 3 \), ta tăng cường bất đẳng thức trên:

\[ \frac{1}{2} < \sum\limits_{i=1}^{k} \frac{1}{\prod\limits_{j \neq i} p_{j}} \leq \frac{1}{6}+\frac{1}{10}+\frac{1}{15} < \frac{1}{2}. \]

Vậy \( k \leq 2 \). Nếu \( n = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \), ta xét từng trường hợp và suy ra \( n = 15 \) hoặc \( n = 12 \) hoặc \( n = 2p_{2}^{\alpha_{2}} \). Tuy nhiên, cả \( 12 \) và \( 15 \) đều không thú vị, và \( n = 2p_{2}^{\alpha_{2}} \) cũng không thú vị vì \( \sigma(n) = 3A_{2} \) và \( 3 + A_{2} \leq n \).

Xét trường hợp \( n = p^{t} \). Nếu \( t \geq 3 \) là số lẻ:

\[ \sigma(n) = \frac{(p^{\frac{t+1}{2}} + 1)(p^{\frac{t+1}{2}}-1)}{p-1}. \]

Vì:

\[ (p^{\frac{t+1}{2}} + 1)+(p^{\frac{t+1}{2}}-1) = 2p^{\frac{t+1}{2}} \leq p^{t}, \]

suy ra \( \sigma(n) \mid n! \). Nếu \( t = 1 \), thì \( n \) thú vị khi và chỉ khi \( p+1 \nmid p! \), nhưng với \( p > 3 \), các số \( 2, \frac{p+1}{2} \) xuất hiện trong tích \( 1\cdot 2\cdot 3 \cdots n \), do đó \( \sigma(n) \mid n! \). Mệnh đề chính được chứng minh.

Kiểm tra \( n = 2 \) và \( n = 3 \), chúng là nghiệm hợp lệ. Theo mệnh đề chính, nếu \( n > 3 \) và \( n+1 \) đều thú vị, thì chúng phải là hai bình phương liên tiếp, điều này là không thể. Vậy bài toán được giải quyết.

Bài toán

Cho \( k \) là một số nguyên dương và \( n = (2^k)! \). Chứng minh rằng \( \sigma(n) \) có ít nhất một ước số nguyên tố lớn hơn \( 2^k \), trong đó \( \sigma(n) \) là tổng tất cả các ước dương của \( n \).

Chứng minh

Tôi sử dụng ba định lý quen thuộc sau:

• Định lý 1: Cho \( n \) là số nguyên dương và \( p \) là số nguyên tố, khi đó: \[ v_p(n!) = \frac{n - s_p(n)}{p-1} \] trong đó \( s_p(n) \) là tổng các chữ số của \( n \) trong hệ cơ số \( p \).
• Định lý 2: Cho \( f_n = 2^{2^n} + 1 \) là số Fermat thứ \( n \), thì tất cả ước số nguyên tố của \( f_n \) đều có dạng \( 1 \mod 2^{n+1} \).
• Định lý 3: Cho \( n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_s^{\alpha_s} \) là phân tích thừa số nguyên tố của \( n \), khi đó: \[ \sigma(n) = \frac{p_1^{\alpha_1+1} - 1}{p_1 - 1} \cdot \frac{p_2^{\alpha_2+1} - 1}{p_2 - 1} \cdots \frac{p_s^{\alpha_s+1} - 1}{p_s - 1}. \]

Quay lại bài toán chính

Từ định lý thứ nhất, ta có:

\[ v_2((2^k)!) = 2^k - 1. \quad (\bigstar) \]

Từ định lý thứ ba và \((\bigstar)\), ta suy ra:

\[ 2^{2^k} - 1 \mid \sigma((2^k)!) \Longrightarrow 2^{2^{k-1}} + 1 \mid \sigma((2^k)!). \]

Gọi \( p \) là một số nguyên tố sao cho \( p \mid 2^{2^{k-1}} + 1 \), khi đó từ định lý thứ hai ta có:

\[ p = 2^k t + 1 \quad \text{với một số nguyên } t. \]

Suy ra \( p > 2^k \), nhưng đồng thời \( p \mid 2^{2^{k-1}} + 1 \mid \sigma((2^k)!) \). Do đó:

\[ p \mid \sigma((2^k)!), \quad p > 2^k. \]

Điều này chứng minh bài toán. \(\square\)

Bài toán

Cho một số nguyên dương \( k \). Chứng minh rằng tồn tại vô hạn số nguyên dương \( n \) thỏa mãn đồng thời các điều kiện sau:

• \( n \) có ít nhất \( k \) ước số nguyên tố khác nhau.
• Tất cả các ước số nguyên tố của \( n \) (ngoại trừ \( 3 \)) đều có dạng \( 4t+1 \), với \( t \) là số nguyên dương.
• \( n \) chia hết cho \( 2^{\sigma(n)} - 1 \), trong đó \( \sigma(n) \) là tổng các ước dương của \( n \).

Chứng minh

Kết quả quen thuộc: Nếu \((a, b) = 1\) thì \(\sigma (ab) = \sigma (a) \cdot \sigma (b)\).

Quay lại bài toán:

Chúng ta chỉ quan tâm đến tính chất \(b)\) và \(c)\). Nếu có thể tạo một dãy \((u_n)\) có tính chất sau: số lượng ước số nguyên tố của \(u_{n+1}\) bằng số lượng ước số nguyên tố của \(u_n\) cộng thêm \(1\), thì bài toán được giải quyết (vì \(u_k, u_{k+1}, ...\) thỏa mãn).

Xét \(15\), ta có:

\[ \sigma (15) = 24 \Rightarrow 2^{\sigma (15)} - 1 \vdots 15. \]

Theo định lý Zsigmondy, tồn tại một số nguyên tố \(q\) sao cho \(\text{ord}_q(2) = 24\). Ở đây, \(q = 241\).

Ta có:

\[ q \equiv 1 \pmod{4} \]

(vì \(\text{ord}_q(2) = 24 \Rightarrow q - 1 \vdots 24\)) và do \((q, 15) = 1\), nên:

\[ \sigma (15q) = \sigma (15) \cdot \sigma (q). \]

Do đó:

\[ 2^{\sigma (15q)} - 1 = 2^{\sigma (15) \cdot \sigma (q)} - 1 \vdots 2^{\sigma (15)} - 1 \vdots 15q. \]

Suy ra \(15q\) thỏa mãn điều kiện bài toán.

Lặp lại quy trình trên \(k, k+1, ...\) lần, ta nhận được một dãy số dạng \(15 \cdot q \cdot p_1 \cdot p_2 \cdots\) có nhiều hơn \(k\) ước số nguyên tố và tất cả các ước số nguyên tố lớn hơn \(3\) của nó đều có dạng \(4t+1\).

Điều phải chứng minh.

Bài toán

Xác định tất cả các số nguyên \( n > 1 \) sao cho tổng các ước dương của \( n \) là một lũy thừa của \( 3 \).

Chứng minh

Gọi \( n = \prod p_i^{k_i} \), khi đó ta có:

\[ 3^t = \sigma(n) = \prod \sigma(p_i^{k_i}) = \prod 3^{t_i}. \]

Do đó, ta cần giải phương trình:

\[ \frac{p^{k+1} - 1}{p - 1} = 3^t \]

với \( p \) là số nguyên tố.

• Nếu \( p = 2 \), ta có:
\[ 2^{k+1} - 1 = 3^t. \]

Theo định lý Mihailescu, điều này chỉ xảy ra khi \( k = 1 \).

• Nếu \( p > 2 \), theo định lý Zsigmondy, vế trái có ít nhất \( \tau(k+1) - 1 \) ước số nguyên tố phân biệt. Điều này chỉ có thể xảy ra khi:
\[ \tau(k+1) - 1 = 1 \implies k+1 \text{ là số nguyên tố } q \text{ sao cho } \frac{p^q - 1}{p - 1} = 3^t. \]
• Nếu \( 3 \mid (p - 1) \), theo LTE, ta có:
\[ v_3(\text{LHS}) = v_3(q) \leq 1. \]

Điều này buộc phải có \( q = 3 \) và \( t = 1 \), dẫn đến:

\[ p^2 + p + 1 = 3. \]

Nhưng điều này chỉ xảy ra khi \( p = 1 \), mâu thuẫn.

• Nếu \( 3 \nmid (p - 1) \), thì bậc của \( p \) theo modulo 3 là:
\[ q = \operatorname{ord}_3(p) \mid 3 - 1 = 2 \Rightarrow q = 2. \]

Trong trường hợp này, ta cần:

\[ p + 1 = 3^t. \]

Điều này chỉ xảy ra khi \( p = 2 \) và \( t = 1 \).

Vậy nghiệm duy nhất là \( n = 2 \).

Bài toán

Tìm tất cả các số nguyên dương \( n \) sao cho cả \( n \) và \( \sigma(\sigma(n)) \) đều là số hoàn hảo.

Ghi chú: Một số hoàn hảo là số thỏa mãn \(\sigma(n) = 2n\), trong đó \(\sigma(n)\) là tổng các ước của \( n \):

\[ \sigma(n) = \sum_{d | n} d. \]

Chứng minh

Bổ đề 1. Cho một số nguyên dương \( n \). Khi đó \( n \) là số hoàn hảo chẵn khi và chỉ khi \( n = 2^{m-1}(2^m-1) \) với \( m \in \mathbb{N}^*, m > 1 \) và \( 2^m - 1 \) là số nguyên tố.

Bổ đề 2. Hàm ước số tổng quát \( \sigma(n) \) có tính chất nhân tính và thỏa mãn:

\[ \sigma(p^\alpha) = \frac{p^{\alpha+1}-1}{p-1}. \]

Giải quyết bài toán

Giả sử \( n \) là số lẻ, tức là \( (2, n) = 1 \). Vì \( \sigma(n) \) có tính nhân tính, ta có:

\[ \sigma(\sigma(n)) = \sigma(2n) = \sigma(2) \cdot \sigma(n) = 3 \cdot 2n = 6n. \]

Suy ra:

\[ \sigma(\sigma(n)) = \sigma(6n) = \sigma(2) \cdot \sigma(3n) = 3 \sigma(3n). \]

Nhưng \( \sigma(\sigma(n)) \) là số hoàn hảo, do đó:

\[ \sigma(6n) = 12n = 3\sigma(3n) \Rightarrow \sigma(3n) = 4n. \]

Điều này dẫn đến:

\[ \sigma(3n) = 4n < 6n = \sigma(2n). \]

Đặt \( n = 3^\alpha M \) với \( (3, M) = 1 \), ta có:

\[ \sigma(3n) = \sigma(3^{\alpha+1} M) = \sigma(3^{\alpha+1}) \sigma(M) = \frac{3^{\alpha+2}-1}{2} \sigma(M). \]

Và:

\[ \sigma(2n) = \frac{3^{\alpha+2}-3}{2} \sigma(M). \]

Từ bất đẳng thức \( \sigma(3n) < \sigma(2n) \), ta có:

\[ 1 > 3, \]

đây là một mâu thuẫn. Do đó, \( n \) phải là số hoàn hảo chẵn. Áp dụng Bổ đề 1, ta có:

\[ n = 2^{m-1}(2^m-1), \]

với \( 2^m-1 \) là số nguyên tố. Khi đó:

\[ \sigma(\sigma(n)) = \sigma(2^m(2^m-1)) = (2^{m+1}-1) \cdot 2^m. \]

Theo Bổ đề 1, \( 2^{m+1}-1 \) phải là số nguyên tố. Đặt \( p = 2^{m+1}-1 \) và \( q = 2^m-1 \), ta có:

\[ h = \operatorname{ord}_p(2) \Rightarrow 2^h \equiv 1 \pmod{p}. \]

Vì vậy:

\[ p-1 = 2q. \]

Áp dụng định lý Fermat nhỏ, ta có:

\[ 2^{p-1} = 2^{2q} \equiv 1 \pmod{p} \text{ và } 2^{m+1} \equiv 1 \pmod{p}. \]

Suy ra \( h \mid 2q \) và \( h \mid m+1 \). Xét các trường hợp của \( h \):

• Nếu \( h = 2 \), thì \( p = 3 \Rightarrow m = 1 \Rightarrow n = 1 \), mâu thuẫn.
• Nếu \( h = q \), thì \( 2^m - 1 \mid m+1 \Rightarrow m = 1 \) hoặc \( m = 2 \). Với \( m = 2 \), ta có \( n = 6 \), thỏa mãn bài toán.
• Nếu \( h = 2q \), thì \( 2^{m+1}-2 \mid m+1 \Rightarrow m = 1 \).

Vậy nghiệm duy nhất của bài toán là \( n = 6 \).

Bài toán

Cho \( n \) là một số nguyên dương sao cho tổng các ước số nguyên dương của nó, ký hiệu là \( \sigma(n) \), là một lũy thừa của 2.

Chứng minh rằng \( n \) là số không chứa bình phương (square-free).

Chứng minh

Nếu \(2 \mid n\), thì ta có:

\[ 1 + 2 + \cdots + 2^{\nu_2(n)} = 2^{\nu_2(n) + 1} - 1 \mid \sigma(n), \]

mà \(\sigma(n)\) là lũy thừa của 2, nên ta phải có:

\[ 2^{\nu_2(n) + 1} - 1 = 1. \]

Tuy nhiên, điều này dẫn đến:

\[ 2^{\nu_2(n) + 1} - 1 \geq 2^{1 + 1} - 1 = 3, \]

mâu thuẫn. Vậy \(2 \nmid n\).

Bây giờ, giả sử ngược lại rằng tồn tại số nguyên tố \(p\) chia \(n\) sao cho \(\nu_p(n) > 1\). Theo lập luận trên, \(p\) phải là số lẻ. Khi đó:

\[ 1 + p + p^2 + \cdots + p^{\nu_p(n)} = \frac{p^{\nu_p(n) + 1} - 1}{p-1} \]

là một ước của \(\sigma(n)\), mà \(\sigma(n)\) là lũy thừa của 2, nên:

\[ \frac{p^{\nu_p(n) + 1} - 1}{p-1} \]

cũng là lũy thừa của 2. Tuy nhiên, do \(\nu_p(n) + 1 > 2\) và \(p > 2\), theo định lý Zsigmondy, tồn tại một ước nguyên tố của \(p^{\nu_p(n) + 1} - 1\) không chia hết cho \(p-1\). Vì \(2 \mid p-1\), nên ước nguyên tố này không phải là 2, mâu thuẫn với việc \(\frac{p^{\nu_p(n) + 1} - 1}{p-1}\) là lũy thừa của 2.

Do đó, giả thiết ban đầu sai và ta hoàn tất chứng minh.

Bài toán

Chứng minh rằng tồn tại ít nhất 100.000 số nguyên dương \( n \) sao cho tổng các ước số dương của \( n \), ký hiệu là \( \sigma(n) \), là một lũy thừa của 2.

Chứng minh

Theo bài viết tham chiếu, \(n\) phải là số không chứa bình phương (squarefree). Vì \(\sigma(p) = p + 1 = 2^k\) với mọi số nguyên tố \(p\) chia \(n\), suy ra \(p\) phải là một số nguyên tố Mersenne.

Do đó, số lượng các số \(n\) thỏa mãn bài toán chính là \(2^N\), trong đó \(N\) là số lượng các số nguyên tố Mersenne.

Theo giả thuyết, số nguyên tố Mersenne là vô hạn. Theo trang https://www.mersenne.org/primes/, hiện có ít nhất 51 số nguyên tố Mersenne đã biết. Như vậy, số lượng các số \(n\) thỏa mãn ít nhất là:

\[ 2^{51} \approx 2.2 \cdot 10^{15} \gg 10^5. \]

Do đó, có ít nhất \(2^{51}\) số \(n\) thỏa mãn yêu cầu bài toán.

Bài toán

Với mỗi số nguyên dương \( n \), ta kí hiệu \( d(n) \) là số ước dương của \( n \) và \( s(n) \) là tổng các ước dương của \( n \). Ví dụ:

• \( d(2018) = 4 \) vì \( 2018 \) có bốn ước dương: \( (1, 2, 1009, 2018) \).
• \( s(2018) = 1 + 2 + 1009 + 2018 = 3030 \).

Hãy tìm tất cả các số nguyên dương \( x \) sao cho:

\[ s(x) \cdot d(x) = 96. \]

Chứng minh

Đáp án là \(14, 15, 47\).

Rõ ràng \(d(x)\) phải là một ước của \(96\). Nếu \(d(x) \geq 6\), thì \(s(x) \leq 16\), dẫn đến \(x < 16\). Trong các số nguyên dương nhỏ hơn \(16\), chỉ có \(12\) có ít nhất \(6\) ước. Nhưng \(s(12) \neq 16\), nên \(d(x) < 6\).

Vậy ta chỉ cần xét các trường hợp \(d(x) = 2, 3, 4\).

Trường hợp 1: \(d(x) = 2\)

Khi đó \(x\) là số nguyên tố, nên \(s(x) = x + 1\). Giải phương trình:

\[ (x+1) \cdot 2 = 96 \Rightarrow x+1 = 48 \Rightarrow x = 47. \]

Trường hợp 2: \(d(x) = 3\)

Khi đó \(x\) là bình phương của một số nguyên tố và \(s(x) = 32\). Kiểm tra \(x = 4, 9, 25\) không thỏa mãn, nên không có nghiệm trong trường hợp này.

Trường hợp 3: \(d(x) = 4\)

Ta có \(s(x) = 24\). Kiểm tra các số \(x\) nhỏ hơn \(24\) có đúng 4 ước, ta thấy chỉ có \(14\) và \(15\) là nghiệm.

Kết luận: Nghiệm của bài toán là \( \boxed{14, 15, 47} \).

Bài toán

Bài toán

Cho số nguyên \( N = 2^a p_1 p_2 ... p_m \) với \( m \geq 1 \), \( a \in \mathbb{N} \), và \( p_1, p_2, ..., p_m \) là các số nguyên tố phân biệt. Biết rằng:

\[ \sigma(N) = 3N \]

trong đó \( \sigma(N) \) là tổng tất cả các ước số dương của \( N \). Chứng minh rằng tồn tại một số nguyên tố \( p \) sao cho \( 2^p - 1 \) cũng là một số nguyên tố, và \( 2^p - 1 \) chia hết cho \( N \).

Chứng minh

Giả sử không mất tính tổng quát rằng \(2 < p_1 < p_2 < \ldots < p_m\) (nếu \(p_1 = 2\), ta có thể xử lý tương tự bằng cách viết \(N = 2^{a+1} p_2 \cdots p_m\)).

Ta biết rằng:

\[ \sigma(N) = (2^{a+1} - 1)(p_1+1) \cdots (p_m+1) \]

suy ra:

\[ (2^{a+1}-1)(p_1+1) \cdots (p_m+1) = 3 \cdot 2^a p_1 \cdots p_m \quad (*) \]

Định lý 1: \((p_1+1) \nmid p_t\) với mọi \(t \leq m\).

Chứng minh: Giả sử tồn tại một số \(t\) sao cho \((p_1+1) \mid p_t\). Vì \(p_1+1 > 1\), ta có \(p_1+1 = p_t\), tức là \(p_1 = 2\) và \(p_t = 3\), mâu thuẫn. \(\blacksquare\)

Định lý 2: Nếu \(p_i+1\) là lũy thừa của 2 với một số \(i\), thì bài toán được chứng minh.

Chứng minh: Giả sử \(p_i+1 = 2^k\) với một số nguyên dương \(k\), suy ra \(p_i = 2^k - 1\). Nếu \(k\) là hợp số, đặt \(k = ab\) với \(a, b \geq 2\), khi đó:

\[ (2^a-1) \mid (2^{ab}-1) = (2^k-1) = p_1 \Rightarrow 2^a-1 \in \{1, p_1\} \]

suy ra \(a = 1\) hoặc \(b = 1\), điều này vô lý.

Do đó, \(p_1 = 2^k - 1\) với \(k\) là số nguyên tố. Nếu \(k=1\), thì \(p_1=1\), một mâu thuẫn. Vì vậy, ta có \(p_1=2^k-1\) là số nguyên tố chia hết \(N\) và \(k\) là số nguyên tố, như mong muốn. \(\blacksquare\)

---

Giờ giả sử rằng \(p_i+1\) không phải là lũy thừa của 2 với mọi \(i\). Từ \((*)\), ta có:

\[ (p_1+1) \mid 3 \cdot 2^a p_1 \cdots p_m \]

Sử dụng kết quả từ Định lý 1, ta suy ra:

\[ (p_1+1) \mid 3 \cdot 2^a \]

Do đó, ta có thể viết:

\[ p_1+1 = 3 \cdot 2^{x_1}, \quad x_1 \in \mathbb{N} \]

khi đó:

\[ (2^{a+1}-1)(p_2+1) \cdots (p_m+1) = 2^{a-x_1} p_1 p_2 \cdots p_m \]

Tương tự, ta có thể viết:

\[ p_2+1 = p_2 \cdot 2^{x_2} \]

Tiếp tục lập luận như vậy, ta suy ra:

\[ p_i+1 = p_{i-1} \cdot 2^{x_i}, \quad \forall i \geq 2 \]

So sánh số mũ của 2, ta được:

\[ x_1 + x_2 + \cdots + x_m = a \]

Thay vào \((*)\), ta có:

\[ 2^{a+1} - 1 = p_m \]

mâu thuẫn với giả thiết ban đầu.

Vậy bài toán đã được chứng minh. \(\blacksquare\)

Nguồn

Bài toán

Cho \( n \geq 2 \) là một số nguyên dương cố định và \( d_1, d_2, ..., d_m \) là tất cả các ước số dương của \( n \). Chứng minh rằng:

\[ \frac{d_1 + d_2 + \dots + d_m}{m} \geq \sqrt{n + \frac{1}{4}} \]

Đồng thời, tìm giá trị của \( n \) sao cho đẳng thức xảy ra.

Chứng minh

Chúng ta cần chứng minh bất đẳng thức:

\[ \frac{\sigma (n)}{\tau (n)}\ge \sqrt{n + \frac{1}{4}}. \]

Chú ý rằng \(\frac{\sigma (n)}{\tau (n)}\) là một hàm số nhân.

Hơn nữa, bất đẳng thức sau đúng với mọi \(m, n \in \mathbb{N} \setminus \{1\}\):

\[ \sqrt{n + \frac{1}{4}} \times \sqrt{m + \frac{1}{4}} > \sqrt{mn+\frac{1}{4}}. \]

Do đó, ta chỉ cần chứng minh:

\[ \frac{\sigma (p^{\alpha})}{\tau (p^{\alpha})} \ge \sqrt{p^{\alpha} + \frac{1}{4}}, \]

với \(p\) là một số nguyên tố bất kỳ và \(\alpha \in \mathbb{N}\).

Bất đẳng thức trên có thể được chứng minh dễ dàng, với dấu bằng chỉ xảy ra khi \(p=2\) và \(\alpha =1\).

Hơn nữa, bất đẳng thức đã chứng minh trước đó đảm bảo rằng dấu bằng chỉ xảy ra khi \(n=2\).

Nguồn

Bài toán

Cho hai số nguyên dương \( m \) và \( n \), chứng minh rằng tồn tại một số nguyên dương \( k \) và một tập hợp \( S \) chứa ít nhất \( m \) bội số của \( n \) sao cho các số

\[ \frac{2^k \sigma(s)}{s} \]

là số lẻ với mọi \( s \in S \), trong đó \( \sigma(s) \) là tổng của tất cả các ước dương của \( s \) (bao gồm cả \( 1 \) và \( s \)).

Chứng minh

Trước tiên, chúng ta xây dựng số \( n^{*} \) như sau:

\[ n^{*} = \prod p_i^{\alpha_i} \]

trong đó \( p_i \) là tất cả các ước số nguyên tố lẻ của \( n \) và \( \alpha_i = 1 \) nếu \( \nu_{p_i}(n) \) là số lẻ, ngược lại \( \alpha_i = 0 \).

Tiếp theo, chúng ta xây dựng tập hợp \( S \) với các phần tử có dạng:

\[ s = n \cdot n^{*} \cdot 2^t \cdot q \]

trong đó \( t \) và \( q \) là các ẩn số thỏa mãn \( (q, n) = 1 \).

Gọi \( a = \nu_2(n) \). Lưu ý rằng \( \nu_{p_i}(nn^{*}) \) là số chẵn, do đó tổng:

\[ 1 + p_i + \dots + p_i^{\alpha_i} \]

là số lẻ. Khi đó, ta có:

\[ \frac{\sigma(s)}{s} = \frac{P \cdot \sigma(q) \cdot (2^{a+t+1}-1)}{n \cdot n^{*} \cdot 2^t \cdot q} \]

trong đó \( P \) là tích của các biểu thức \( 1 + p_i + \dots + p_i^{\alpha_i^{\prime}} \), là các ước của \( n \cdot n^{*} \). Từ nhận xét trước đó, ta có \( P \) là số lẻ.

Chúng ta chọn \( m \) số chính phương lẻ \( q_i \) sao cho \( (q_i, n) = 1 \). Khi đó, \( \sigma(q_i) \) cũng là số lẻ với lý do tương tự như trên.

Ta chứng minh rằng:

\[ t = \prod \phi\left(\frac{n \cdot n^{*} \cdot q_i}{2^a}\right) - a - 1 \]

và \( k = t + a \) phù hợp (lưu ý rằng ta có thể chọn \( q_i \) đủ lớn để đảm bảo \( t \) là số dương).

Dễ thấy rằng:

\[ \frac{2^k \cdot \sigma(s)}{s} = \frac{2^k \cdot P \cdot \sigma(q_i) \cdot (2^{a+t+1}-1)}{n \cdot n^{*} \cdot 2^t \cdot q_i} = \frac{2^{a+t+1}-1}{\frac{n}{2^a} \cdot n^{*} \cdot q_i} \cdot {P \cdot \sigma(q_i)} \]

là một số nguyên dương từ Định lý Euler, đồng thời cũng là số lẻ vì tất cả các thành phần trong đó đều là số lẻ.

Nguồn

Bài toán

Một số nguyên \( n \geq 2 \) được gọi là kháng nếu nó nguyên tố cùng nhau với tổng tất cả các ước của nó (bao gồm cả \( 1 \) và \( n \)).

Xác định số lượng tối đa các số kháng liên tiếp.

Ví dụ:

• \( n = 5 \) có tổng các ước \( S = 6 \), do đó là số kháng.
• \( n = 6 \) có tổng các ước \( S = 12 \), do đó không phải số kháng.
• \( n = 8 \) có tổng các ước \( S = 15 \), do đó là số kháng.
• \( n = 18 \) có tổng các ước \( S = 39 \), do đó không phải số kháng.

Chứng minh

Đáp án là \(5\), đạt được ví dụ với các số nguyên từ \(575\) đến \(579\).

Giải thích

Ký hiệu \(d(n)\) là tổng các ước của \(n\).

Ta khẳng định rằng nếu \(n\) là số chẵn, thì \(n\) chỉ có thể là số chính phương hoặc gấp đôi một số chính phương. Điều này đúng vì nếu tồn tại số nguyên tố \(p > 2\) sao cho \(v_p(n) = k\) với \(k\) là số lẻ, thì tổng các ước của \(p^k\) là:

\[ d(p^k) = p^k + p^{k-1} + \dots + 1 \]

là một số chẵn. Vì \(d(n)\) là hàm nhân tính, ta có:

\[ d(n) = d(p^k) \cdot d\left(\frac{n}{p^k}\right). \]

Vậy \(d(n)\) chia hết cho \(2\), nhưng \(n\) cũng chia hết cho \(2\), nên \(\gcd(n, d(n)) \geq 2\), do đó \(n\) không phải là số resistant.

Bây giờ, giả sử tồn tại 6 số resistant liên tiếp. Khi đó, có 3 số chẵn và chúng phải có dạng \(x^2\) hoặc \(2y^2\). Tuy nhiên, ta có:

• Khoảng cách giữa hai số chính phương chẵn liên tiếp ít nhất là 12.
• Khoảng cách giữa hai số có dạng \(2y^2\) ít nhất là 6.

Do đó, nếu ba số chẵn liên tiếp có dạng \(2k\), \(2k+2\) và \(2k+4\), thì hoặc:

• \(2k = x^2\), \(2k+2 = 2y^2\), \(2k+4 = z^2\) với một số \(x, y, z\), hoặc
• \(2k = 2x^2\), \(2k+2 = y^2\), \(2k+4 = 2z^2\) với một số \(x, y, z\).

Trong cả hai trường hợp, \(2k\) và \(2k+4\) có cùng dạng, nhưng khác nhau ít hơn 6, dẫn đến mâu thuẫn. Vậy số lượng tối đa các số resistant liên tiếp là \(\leq 5\).

Nguồn

Bài toán

Ký hiệu \(\sigma(n)\) là tổng các ước của \(n\). Chứng minh rằng tồn tại vô hạn số nguyên \(n\) sao cho \(\sigma(n)\) là một số chính phương.

Chứng minh

Dưới đây là một chứng minh sơ cấp lấy từ bài báo của Beukers, Luca, Oort trên AMM 5, 2012.

Chứng minh

Gọi \( p_1, p_2, p_3, \dotsc \) là dãy số nguyên tố và \( N > 2 \) là một số tự nhiên.

Với mỗi \( i \), đặt \( r_i \) là số nguyên nhỏ nhất sao cho \( p_i^{r_i} > N \). Rõ ràng, \( r_i = 1 \) nếu \( p_i > N \).

Chọn \( t \) sao cho \( p_t \) lớn hơn mọi thừa số nguyên tố trong \( \prod_{p_i \leq N} \sigma(p_i^{r_i}) \).

Với mọi \( p_i > N \), ta có:

\[ \sigma(p_i) = 2 \cdot \frac{p_i + 1}{2}. \]

Do đó, các thừa số nguyên tố của \( \sigma(p_i) \) đều nhỏ hơn \( p_i \).

Vậy mỗi phân tích thừa số của \( \sigma(p_i^{r_i}) \) với \( i \leq t \) chỉ bao gồm các số nguyên tố nhỏ hơn \( p_t \).

Ta viết các phân tích thừa số như sau:

\[ \sigma(p_i^{r_i}) = p_1^{a_{i1}} \cdot p_2^{a_{i2}} \cdots p_{t-1}^{a_{i,t-1}}, \quad i = 1,2,\dotsc,t. \]

Số lượng phân tích thừa số nguyên tố là \( t \), trong khi tổng số thừa số nguyên tố trong các phân tích này nhỏ hơn hoặc bằng \( t-1 \).

Do đó, trong ma trận \( t \times (t-1) \) gồm các hệ số \( (a_{ij}) \), số hàng lớn hơn số cột.

Từ đại số tuyến tính trên trường hai phần tử \( \mathbb{F}_2 \), có thể tìm được các \( \epsilon_i \in \{0,1\} \) với \( 1 \leq i \leq t \), không phải tất cả đều bằng 0, sao cho:

\[ \epsilon_1(a_{11},\dotsc,a_{1,t-1})+\epsilon_2(a_{21},\dotsc,a_{2,t-1})+\dotsc+\varepsilon_t(a_{t1},\dotsc,a_{t,t-1}) \]

có tất cả các phần tử chẵn.

Do đó, \( \sigma(p_1^{\epsilon_1r_1} \cdots p_t^{\epsilon_tr_t}) \) là một số chính phương.

Như vậy, ta đã xây dựng được một ví dụ về \( \sigma(n) = m^2 \) mà trong đó các thừa số nguyên tố của \( n \) đều lớn hơn \( N \).

Bằng cách chọn \( N \) lớn tùy ý, ta có thể xây dựng vô hạn ví dụ như vậy.

Lưu ý rằng cùng bài báo trên cũng chứng minh rằng \( \sigma(n) \) vô hạn lần là một lũy thừa bậc \( k \) với mọi số nguyên dương \( k \).

Nguồn

Bài toán

Ký hiệu \( s(k) \) là tổng tất cả các ước tự nhiên của số \( k \), bao gồm cả chính nó. Biết rằng:

\[ s(N) + s(3N) = s(4N). \]

Chứng minh rằng số \( N \) là số chẵn.

Chứng minh

Giả sử ngược lại rằng \(N\) là số lẻ. Khi đó, với mỗi ước \(d\) của \(N\), số \(4N\) có các ước \(d, 2d, 4d\), do đó:

\[ S(4N) = 7S(N). \]

Vấn đề trở thành kiểm tra liệu \(S(3N) = 6S(N)\) có thể xảy ra hay không. Tuy nhiên, điều này rõ ràng không thể xảy ra, bởi vì tập hợp các ước của \(3N\) nằm trong hợp của hai tập: tập thứ nhất chứa các ước của \(N\), và tập thứ hai chứa các bội ba của các ước đó.

Do đó, ta có:

\[ S(3N) \leq 4S(N). \]

Mâu thuẫn xảy ra, do đó giả thiết ban đầu sai. Vậy \(N\) không thể là số lẻ.

Nguồn

Bài toán

Cho \( n \in \mathbb{N} \) và hàm tổng các ước số được xác định bởi:

\[ s(n) = 2n + 1. \]

Chứng minh rằng \( n \) là bình phương chính xác của một số lẻ.

Chứng minh

Gọi \( n = \prod p_i^{e_i} \) là phân tích thừa số nguyên tố của \( n \). Ta biết rằng:

\[ s(n) = (1 + p_1 + p_1^2 + \dots + p_1^{e_1}) \dots (1 + p_m + p_m^2 + \dots + p_m^{e_m}) = 2n + 1. \]

Rõ ràng, tổng này là số lẻ. Do đó, mỗi thừa số ở vế trái đều là số lẻ, suy ra mỗi \( e_i \) đều là số chẵn, ngoại trừ có thể là số mũ của thừa số nguyên tố 2. Như vậy, ta có thể viết:

\[ n = 2^t K^2 \]

với \( K \) là số lẻ.

Bây giờ, ta cần chứng minh rằng \( t = 0 \).

Ta biết rằng:

\[ 1 + 2 + \dots + 2^t = 2^{t+1} - 1 \]

là một ước của \( s(n) = 2^{t+1}K^2 + 1 \), tức là:

\[ 2^{t+1}K^2 + 1 \equiv 0 \pmod{2^{t+1} - 1} \] \[ \Rightarrow K^2 + 1 \equiv 0 \pmod{2^{t+1} - 1}. \]

Rõ ràng, nếu \( t \geq 1 \), thì \( 2^{t+1} - 1 \equiv -1 \pmod{4} \). Như vậy, \( 2^{t+1} - 1 \) có một ước nguyên tố \( p \equiv 3 \pmod{4} \). Điều này dẫn đến:

\[ K^2 \equiv -1 \pmod{p}. \]

Nhưng theo định lý nhỏ Fermat và tính chất của bậc đồng dư, điều này chỉ xảy ra khi \( 4 \mid p - 1 \), mâu thuẫn với \( p \equiv 3 \pmod{4} \). Do đó, \( t = 0 \), kết thúc chứng minh.

Nguồn

Bài toán

Gọi \(\sigma(n)\) là tổng các ước dương của số \(n\). Cho một số nguyên dương \(N = 2^r b\), trong đó \(r\) và \(b\) là các số nguyên dương và \(b\) là số lẻ. Biết rằng:

\[ \sigma(N) = 2N - 1. \]

Chứng minh rằng \(b\) và \(\sigma(b)\) là nguyên tố cùng nhau.

Chứng minh

Với mỗi ước số \(a\) của \(b\), ta có:

\[ 2^i a | N \quad \forall r \geq i \geq 0. \]

Do đó:

\[ 2^{r+1}b - 1 = \sigma(N) = (1 + 2 + 2^2 + \dots + 2^r) \sigma(b) = (2^{r+1} - 1) \sigma(b). \]

Gọi \(m = \gcd(b, \sigma(b))\), khi đó ta có:

\[ m | 1 \implies m = 1. \]

Vậy ta chứng minh được điều cần thiết.

Nguồn

Bài toán

Bài toán

Gọi một số \( n \) là tốt nếu thỏa mãn hai điều kiện:

1. \( n \) nhỏ hơn tổng các ước của nó (trừ \( 1 \) và \( n \)).
2. \( n \) không thể được biểu diễn dưới dạng tổng của một số tập con các ước khác của nó (trừ \( 1 \) và \( n \)).

Chứng minh rằng có vô hạn số tốt.

Chứng minh

Chọn \( n = 70p \), trong đó \( p > 143 \) là số nguyên tố.

Các ước số thực sự của \( n \) là:

\[ 2,5,7,10,14, 35, 70, p, 2p, 5p, 7p,10p,14p, 35p. \]

Xét tổng các ước số chứa \( p \):

\[ p + 2p + 5p + 7p + 10p + 14p + 35p = 74p > n. \]

Do đó, tổng các ước số này đã vượt quá \( n \).

Mặt khác, xét tổng các ước số không chứa \( p \):

\[ 2 + 5 + 7 + 10 + 14 + 35 + 70 = 143 < p. \]

Do \( p > 143 \) và không có tập con nào của \( \{p, 2p, 5p, 7p, 10p, 14p, 35p\} \) có tổng bằng \( 70p \), suy ra \( n \) là số tốt.

Nguồn

Bài toán

Với một số nguyên dương \( n \), ta định nghĩa \( S(n) \) là tổng tất cả các ước của \( n \). Hỏi có bao nhiêu số nguyên dương có ba chữ số \( n \) thỏa mãn:

\[ S(6n) \geq 12S(n)? \]

Chứng minh

Ta đặt \(n = 2^a3^bk\) với \(\gcd(k,6) = 1\).

Ta có công thức tổng các ước:

\[ S(n) = (2^{a+1} - 1)(3^{b+1} - 1) \frac{S(k)}{2}. \]

Tương tự:

\[ S(6n) = (2^{a+2} - 1)(3^{b+2} - 1) \frac{S(k)}{2} = \frac{(2^{a+2} - 1)(3^{b+2} - 1)}{(2^{a+1} - 1)(3^{b+1} - 1)} S(n). \]

Xét giá trị lớn nhất của \(\frac{(2^{a+2} - 1)}{(2^{a+1} - 1)}\) và \(\frac{(3^{b+2} - 1)}{(3^{b+1} - 1)}\), điều này xảy ra khi \(a = b = 0\).

Thật vậy:

\[ \frac{(2^{0+2} - 1)(3^{0+2} - 1)}{(2^{0+1} - 1)(3^{0+1} - 1)} = 12. \]

Do đó, ta tìm tất cả các số có ba chữ số thỏa mãn \(a = b = 0\), tức là các số \(n\) sao cho \(100 \leq n \leq 999\) và \(\gcd(n,6) = 1\).

Nếu không có sai sót, kết quả là:

\[ \boxed{300}. \] Nguồn

Bài toán