solution

Một số $g$ gọi là căn nguyên thuỷ modulo $p$ (với $p$ nguyên tố) nếu các luỹ thừa $g^1, g^2, \dots, g^{p-1}$ tạo thành đủ tất cả các số dư khác $0$ modulo $p$; tương đương: cấp của $g$ đúng bằng $p-1$.

Cho $q$ số nguyên tố, với mỗi số hãy tìm căn nguyên thuỷ nhỏ nhất ($g \ge 1$).

Gợi ý: $g$ là căn nguyên thuỷ khi và chỉ khi với mọi ước nguyên tố $f$ của $p-1$ ta có $g^{(p-1)/f} \not\equiv 1 \pmod p$.

Ví dụ: Với $p=7$, căn nguyên thuỷ nhỏ nhất là $3$.