Xét phương trình
$$\phi \left(\phi (n)+k\right)=n-k\text{ với }n,k\text{ nguyeˆn dương.}$$
a) Chứng minh với mỗi số nguyên dương $k$ cố định, chỉ có hữu hạn số $n$ là hợp số thỏa mãn phương trình.
b) Tìm tất cả các số nguyên dương $k$ sao cho phương trình có vô số nghiệm nguyên dương $n$.
(Với $m$ nguyên dương, ký hiệu $\phi (m)$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$)

Trước hết ta có bổ đề quen thuộc sau:

Bổ đề: Với $N$ là hợp số thì $\phi (N)\le N-\sqrt{N}$.

Chứng minh: Thật vậy, gọi $p$ là ước nguyên tố nhỏ nhất của $N$. Khi đó $p\le \sqrt{N}$.

Trong các số $1,2,\dots ,N$ có đúng $N/p$ bội của $p$, và chúng không nguyên tố cùng nhau với $N$. Vì thế
$$N-\phi (N)\ge \frac{N}{p}\ge \sqrt{N}$$

① Giả sử $n$ thỏa mãn $\phi (\phi (n)+k)=n-k$. Ta có $n>k$ và $\phi (n)+k\ge 2$ nên
$$n-k=\phi (\phi (n)+k)\le \phi (n)+k-1.$$
Vì vậy $n-\phi (n)\le 2k-1$. Nếu $n$ là hợp số thì $\sqrt{n}\le n-\phi (n)\le 2k-1$ nên $n\le (2k-1{)}^2$.

Từ đó có hữu hạn hợp số $n$ thoả mãn yêu cầu đề bài.

(2) Giả sử với $k$ nào đó, phương trình có vô số nghiệm nguyên dương $n$. Để ý chỉ có hữu hạn hợp số nên phải có vô số nghiệm $n$ là số nguyên tố, thì $\phi (n)=n-1$ nên
$$\phi (n+k-1)=n-k.$$
Đặt $M=n+k-1$ thì $M-\phi (M)=2k-1$. Nếu $M$ là hợp số thì $\sqrt{M}\le 2k-1$ nên chỉ có hữu hạn giá trị hợp số $M$. Do có vô số giá trị $M$ nên phải có ít nhất 1 giá trị $M$ là số nguyên tố và khi đó
$$M-\phi (M)=1$$
Do đó $2k-1=1$ nên $k=1$. Ngược lại với $k=1$ thì mọi số nguyên tố $n$ thoả mãn yêu cầu nên giá trị duy nhất thoả mãn là $k=1$.