Tutorial — Residue Sequence Selection

Xét các phần tử $x \in [1, n - 1]$ có $\gcd(x, n) > 1$. Nếu chọn $x$ vào dãy con, tích các phần tử sẽ chia hết cho $\gcd(x, n)$ nên không thể chia $n$ dư $1$.

Do đó, dãy con hợp lệ chỉ có thể gồm các phần tử nguyên tố cùng nhau với $n$. Tích $P$ của tất cả các phần tử này chia cho $n$ có số dư cũng nguyên tố cùng nhau với $n$.

Nếu $P \equiv 1 \pmod n$, ta chọn toàn bộ các phần tử nguyên tố cùng nhau với $n$. Nếu $P \ne 1 \pmod n$, ta loại bỏ duy nhất phần tử $P$ khỏi tập hợp để thu được tích bằng $1 \pmod n$.