Cho số nguyên dương $k>1$. Với mỗi số nguyên dương $n$, gọi ${\sigma }_k(n)$ là tổng lũy thừa bậc $k$ của các ước nguyên dương của $n$. Gọi $n$ là một số TỐT nếu $n\mid {\sigma }_k(n)$.

a) Chứng minh rằng ${\sigma }_k(n)$ là hàm nhân tính và tồn tại một dãy vô hạn các số TỐT $n_1<n_2<n_3<\cdots$ sao cho $n_i\mid n_{i+1}$ với mọi $i⩾1$.

b) Chứng minh rằng với mọi số nguyên dương $r$, tồn tại một số TỐT có ít nhất $r$ ước nguyên tố phân biệt.

Lời giải (Lim Olympic - Nghệ An TST - P4).

a) Vì $(a,b)=1$ nên mỗi ước dương của $ab$ biểu diễn duy nhất dưới dạng $uv$ với $u\mid a$ và $v\mid b$. Vì thế

$${\sigma }_k(ab)=\sum _{u\mid a}\sum _{v\mid b}(uv{)}^k=\left(\sum _{u\mid a}{u}^k\right)\left(\sum _{v\mid b}{v}^k\right)={\sigma }_k(a){\sigma }_k(b).$$

Ta chứng minh rằng từ mỗi số tốt $m>1$ luôn xây dựng được một số tốt $m^{\prime }>m$ sao cho $m\mid m^{\prime }$. Nếu tồn tại một số nguyên tố $q\mid {\sigma }_k(m)$ nhưng $q\nmid m$, đặt $m^{\prime }=mq$. Do $(m,q)=1$, ta có

$${\sigma }_k(m^{\prime })={\sigma }_k(m)(1+q^k).$$

Mặt khác, $m\mid {\sigma }_k(m)$, $q\mid {\sigma }_k(m)$ và $(m,q)=1$, nên $mq\mid {\sigma }_k(m)$. Bởi vậy $m^{\prime }$ là số tốt.

Xét trường hợp mọi ước nguyên tố của ${\sigma }_k(m)$ đều là ước của $m$. Viết

$$m=\prod _{i=1}^s{p}_i^{a_i},{\sigma }_k(m)=\prod _{i=1}^s{p}_i^{b_i}.$$

Do $m\mid {\sigma }_k(m)$ nên $b_i\ge a_i$ với mọi $i$. Lại có ${\sigma }_k(m)>m^k$, nên tồn tại $j$ sao cho $b_j>k{a}_j$. Đặt

$$m^{\prime }=p_j^{a_j+1}m.$$

Ta có $v_{p_j}(m^{\prime })=2a_j+1$ nên

$${\sigma }_k(m^{\prime })=\left(\sum _{h=0}^{2a_j+1}{p}_j^{hk}\right)\prod _{i\ne j}{\sigma }_k(p_i^{a_i})=\left(1+p_j^{(a_j+1)k}\right)\left(\sum _{h=0}^{a_j}{p}_j^{hk}\right)\prod _{i\ne j}{\sigma }_k(p_i^{a_i})=\left(1+p_j^{(a_j+1)k}\right){\sigma }_k(m).$$

Vì $b_j\ge k{a}_j+1\ge 2a_j+1$ và $b_i\ge a_i$ với $i\ne j$, ta có $m^{\prime }\mid {\sigma }_k(m)$.

Suy ra $m^{\prime }\mid {\sigma }_k(m^{\prime })$, nên $m^{\prime }$ cũng là số tốt.

Bây giờ lấy một ước nguyên tố lẻ $p$ của $2^k+1$. Khi đó

$${\sigma }_k(2p)=(1+2^k)(1+p^k).$$

Ta có $p\mid 1+2^k$ và $2\mid 1+p^k$, nên $2p\mid {\sigma }_k(2p)$. Do đó $n_1=2p$ là số tốt. Áp dụng liên tiếp ta thu được dãy vô hạn các số tốt $n_1<n_2<\cdots$ thỏa mãn $n_i\mid n_{i+1}$.

b) Từ ý trên, ta chỉ cần chứng minh nhận xét sau là bài toán được giải quyết:

Nhận xét. Với tập hữu hạn $\mathcal{P}\subset \mathbb{P}$, chỉ có hữu hạn số tốt mà mọi ước nguyên tố đều thuộc $\mathcal{P}$.

Đầu tiên ta chứng minh bổ đề sau:

Bổ đề 0.2. Với hai số nguyên tố phân biệt $p,q$, tồn tại hằng số $C_{p,q}$ sao cho

$$v_p\left({\sigma }_k(q^a)\right)\le C_{p,q}+{\log }_2(a+1),\forall a\ge 0$$

Chứng minh. Ta có ${\sigma }_k(q^a)=\frac{q^{k(a+1)}-1}{q^k-1}$

Nếu $p$ lẻ, đặt $d={\mathrm{ord}}_p(q^k)$. Khi đó $d\mid p-1$, nên $p\nmid d$.

Nếu $d\nmid a+1$ thì $p\nmid q^{k(a+1)}-1$, do đó $v_p\left({\sigma }_k(q^a)\right)=0$.

Nếu $d\mid a+1$, áp dụng LTE ta có

$$v_p\left(q^{k(a+1)}-1\right)=v_p\left(q^{kd}-1\right)+v_p\left(\frac{a+1}{d}\right).$$

Vì $p\nmid d$ nên $v_p\left(\frac{a+1}{d}\right)=v_p(a+1)\le {\log }_2(a+1)$.

Mặt khác, ${\sigma }_k(q^a)\mid q^{k(a+1)}-1$, nên

$$v_p\left({\sigma }_k(q^a)\right)\le v_p\left(q^{kd}-1\right)+{\log }_2(a+1).$$

trong đó $v_p(q^{kd}-1)$ là một hằng số chỉ phụ thuộc vào $p,q$.

Nếu $p=2$ thì $q$ lẻ. Nếu $a+1$ lẻ, ${\sigma }_k(q^a)$ là tổng của một số lẻ các số lẻ, nên $v_2\left({\sigma }_k(q^a)\right)=0$.

Nếu $a+1$ chẵn, áp dụng LTE ta có

$$v_2\left(q^{k(a+1)}-1\right)=v_2(q^k-1)+v_2(q^k+1)+v_2(a+1)-1.$$

Vì thế

$$v_2\left({\sigma }_k(q^a)\right)=v_2(q^k+1)+v_2(a+1)-1\le v_2(q^k+1)-1+{\log }_2(a+1).$$

trong đó $v_2(q^k+1)-1$ là một hằng số chỉ phụ thuộc vào $q$.

Như vậy, trong mọi trường hợp đều tồn tại hằng số $C_{p,q}$ sao cho

$$v_p\left({\sigma }_k(q^a)\right)\le C_{p,q}+{\log }_2(a+1).$$
$\square$

Để ý ta chỉ cần xét các số tốt có cùng một tập ước nguyên tố là $\{p_1,\dots ,p_s\}\subset \mathcal{P}$ và

$$n=\prod _{i=1}^s{p}_i^{a_i}$$

là một số tốt. Đặt $M=\max \{a_1,\dots ,a_s\}$. Vì ${\sigma }_k(p_i^{a_i})\equiv 1(\mathrm{mod}{p}_i)$ nên $p_i\nmid {\sigma }_k(p_i^{a_i})$ nên

$$a_i=v_{p_i}(n)\le v_{p_i}\left({\sigma }_k(n)\right)=\sum _{j\ne i}{v}_{p_i}\left({\sigma }_k(p_j^{a_j})\right)\le \sum _{j\ne i}{C}_{p_i,p_j}+(s-1){\log }_2(M+1).$$

Đặt $C_i={\sum }_{j\ne i}{C}_{p_i,p_j}$ và $C=\max \{C_1,\dots ,C_s\}$. Chọn $i\in \{1,2,\dots ,s\}$ sao cho $a_i=M$, ta được

$$M\le C+(s-1){\log }_2(M+1).$$

Để ý với $M$ đủ lớn thì $C+(s-1){\log }_2(M+1)<M$, do đó $M$ bị chặn.

Vì thế các số mũ $a_1,\dots ,a_s$ chỉ có hữu hạn giá trị. Suy ra chỉ có hữu hạn số tốt mà mọi ước nguyên tố đều thuộc $\mathcal{P}$, từ đó ta có điều phải chứng minh.