카마이클 수

정의

합성수 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ \gcd(b,m)=1 }[/math]인 임의의 양의 정수 [math]\displaystyle{ b }[/math]에 대해

[math]\displaystyle{ b^{m-1}\equiv 1\pmod m }[/math]

일 때, [math]\displaystyle{ m }[/math]을 카마이클 수(Carmichael number)라고 한다.

페르마의 소정리에 의해서 모든 소수는 위의 조건을 만족한다. 그런데, 소수가 아닌 합성수인 경우에도 이를 만족하는 수가 존재하며, 이것을 카마이클 수라고 부른다.

목록

• 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, ... (oeis:A002997)

성질

• 합성수 [math]\displaystyle{ m=p_1 p_2 \cdots p_n }[/math]에 대해 [math]\displaystyle{ p_1,p_2,\dots, p_n }[/math]이 서로 다른 소수일 때, 임의의 [math]\displaystyle{ 1\le i \le n }[/math]에 대해 [math]\displaystyle{ (p_i -1)\mid (m-1) }[/math]이면 [math]\displaystyle{ m }[/math]은 카마이클 수이다. 그 역도 성립한다. 즉, m이 카마이클 수 일때, square-free이고, 위의 성질을 만족해야 한다.

따라서, m이 카마이클 수인 것과 square-free와 위의 성질을 만족하는 합성수라는 것은 동치조건이다.