solution

Định lý Fermat nhỏ khẳng định nếu $p$ là số nguyên tố thì $a^{p-1} \equiv 1 \pmod p$ với mọi $a$ nguyên tố cùng nhau với $p$. Điều này thường được dùng làm phép thử nhanh (Fermat primality test) để loại bỏ hợp số. Tuy nhiên tồn tại các hợp số $n$ vẫn thỏa mãn $a^{n-1} \equiv 1 \pmod n$ với mọi $a$ nguyên tố cùng nhau với $n$ — gọi là số Carmichael — khiến phép thử Fermat bị đánh lừa.

Theo tiêu chuẩn Korselt, hợp số $n$ là số Carmichael khi và chỉ khi:

1. $n$ không chia hết cho bình phương của bất kỳ số nguyên tố nào (squarefree);
2. với mọi ước nguyên tố $p$ của $n$, ta có $(p - 1) \mid (n - 1)$.

Cho số nguyên $n$, hãy xác định $n$ có phải là số Carmichael hay không.

Ví dụ: $n = 561 = 3 \times 11 \times 17$. Ta có $560$ chia hết cho $2, 10, 16$, nên $561$ là số Carmichael (đây chính là số Carmichael nhỏ nhất).