Số Carmichael

Số Carmichael là hợp số n thỏa a^(n-1) ≡ 1 (mod n) với mọi a nguyên tố cùng nhau với n. Chúng đánh lừa kiểm tra Fermat nên rất quan trọng trong an toàn thông tin.

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

• n là hợp số, không chia hết cho bình phương số nguyên tố nào (square-free), và
• với mọi ước nguyên tố p của n, ta có (p - 1) | (n - 1).

Ví dụ

Input:
561
Output:
YES

561 = 3 x 11 x 17, square-free, và 2|560, 10|560, 16|560 nên 561 là số Carmichael.