카마이클 수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 성질
3. 발견
4. 일반화
참조

1. 개요

카마이클 수는 모든 소인수 p에 대해 p-1이 n-1을 나누어 떨어지게 하는 특징을 갖는 합성수 n을 의미한다. 카마이클 수는 페르마 소수 판정법에서 소수로 오판될 수 있지만, 밀러-라빈 소수 판별법에서는 오판 확률이 낮아진다. 코르셀트의 기준에 따르면, 카마이클 수는 제곱 인수가 없고, 모든 소인수 p에 대해 p-1이 n-1을 나누어야 한다. 카마이클 수는 홀수이며, 최소 3개의 소인수를 갖는다. 카마이클 수는 매우 드물게 분포하며, 1994년에 카마이클 수가 무한히 많다는 것이 증명되었다. 카마이클 수의 개념은 수론적 수체에서 카마이클 아이디얼로 일반화될 수 있으며, 루카스-카마이클 수, 준 카마이클 수, Knödel 수, 고차 카마이클 수 등 다양한 형태로 확장될 수 있다.

2. 성질

페르마의 소정리에 따르면 $p$ 가 소수일 때, 모든 정수 $b$ 에 대해 $b$ ^p - b는 $p$ 의 배수이다. 카마이클 수는 이와 동일한 성질을 가지는 합성수이다. 즉, 합성수 ''n''이 카마이클 수라는 것은 ''n''과 서로소인 모든 밑 ''b''에 대해 다음 합동식이 성립하는 것을 의미한다.

:''b''^''n''-1 ≡ 1 (mod ''n'')

이 때문에 카마이클 수는 페르마 유사소수 또는 절대 페르마 유사소수라고도 불린다. 카마이클 수는 소수가 아님에도 불구하고, 자신과 서로소인 모든 밑 ''b''에 대한 페르마 소수성 검사를 통과한다. 따라서 페르마 검사와 같은 확률적 소수 판별법에서는 카마이클 수를 소수로 잘못 판정할 수 있다. 이러한 이유로 페르마 검사는 강한 유사소수 검사인 베일리-PSW 소수성 검사나 밀러-라빈 소수성 검사보다 덜 효과적이다.

그러나 어떤 카마이클 수도 자신과 서로소인 모든 밑에 대해 오일러-야코비 유사소수나 강한 유사소수는 아니므로^[6], 이론적으로 오일러 검사나 강한 유사소수 검사를 통해 카마이클 수가 실제로는 합성수임을 증명할 수 있다. 예를 들어, 밀러-라빈 소수 판별법에서는 하나의 밑에 대한 오판 확률이 1/4 이하로 줄어든다.

카마이클 수는 무수히 많이 존재한다고 알려져 있지만, 숫자가 커질수록 매우 드물게 나타난다. 가장 작은 카마이클 수는 다음과 같다.

:561, 1105, 1729, 2465, 2821, 6601, 8911, …

카마이클 수는 몇 가지 중요한 특징을 지닌다. 자세한 내용은 하위 섹션에서 다룬다.

2. 1. 코르셀트의 기준

카마이클 수는 '''코르셀트의 기준'''(Korselt's criterion)을 사용하여 대안적으로 정의할 수도 있다. 이 기준은 1899년 알윈 코르셀트가 제시했다.

'''코르셀트의 정리''': 양의 합성수

n

이 카마이클 수가 되기 위한 필요충분조건은 다음 두 가지를 모두 만족하는 것이다.

#

n

은 제곱 인수가 없는 정수이다.

#

n

의 모든 소인수

p

에 대해,

p - 1

은

n - 1

을 나눈다 (즉,

p - 1 \mid n - 1

).

이 기준으로부터 카마이클 수의 몇 가지 중요한 성질을 알 수 있다.

모든 카마이클 수는 홀수이다. 만약 짝수 합성수 $n$ 이 제곱 인수가 없다면 (즉, 소인수 2를 하나만 갖는다면), $n$ 은 적어도 하나의 홀수 소인수 $p$ 를 갖는다. 이때 $p - 1$ 은 짝수이고 $n - 1$ 은 홀수이므로, 짝수인 $p - 1$ 이 홀수인 $n - 1$ 을 나눌 수 없어 코르셀트의 기준을 만족하지 못한다. (카마이클 수가 홀수라는 것은 $-1$ 이 모든 짝수 합성수에 대한 페르마 증인이라는 사실에서도 따른다.)
카마이클 수는 순환군이다.^[9]^[10]
카마이클 수는 정확히 두 개의 소인수를 가질 수 없다. 즉, 최소 3개 이상의 서로 다른 소인수를 가진다.

예를 들어,

n = 2821 = 7 \times 13 \times 31

을 살펴보자.

2821은 소수 7, 13, 31의 곱이므로 제곱 인수가 없다.
$n - 1 = 2821 - 1 = 2820$ 이다.
각 소인수 $p$ 에 대해 $p - 1$ 이 $n - 1$ 을 나누는지 확인한다.
* $7 - 1 = 6$ 이고, $2820 = 6 \times 470$ 이므로 $6 \mid 2820$ 이다.
* $13 - 1 = 12$ 이고, $2820 = 12 \times 235$ 이므로 $12 \mid 2820$ 이다.
* $31 - 1 = 30$ 이고, $2820 = 30 \times 94$ 이므로 $30 \mid 2820$ 이다.

모든 소인수에 대해

p - 1 \mid n - 1

이 성립하므로, 2821은 코르셀트의 기준을 만족하며 카마이클 수이다.

2. 2. 인수분해

카마이클 수는 최소 세 개의 양의 소인수를 갖는다.

k = 3, 4, 5, \ldots

개의 소인수를 갖는 첫 번째 카마이클 수는 다음과 같다.

k	첫 번째 카마이클 수 ( $k$ 개의 소인수)
3	$561 = 3 \cdot 11 \cdot 17\,$
4	$41041 = 7 \cdot 11 \cdot 13 \cdot 41\,$
5	$825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73\,$
6	$321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137\,$
7	$5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73\,$
8	$232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163\,$
9	$9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641\,$

4개의 소인수를 갖는 첫 번째 카마이클 수들은 다음과 같다.

순서	4개의 소인수를 갖는 카마이클 수
1	$41041 = 7 \cdot 11 \cdot 13 \cdot 41\,$
2	$62745 = 3 \cdot 5 \cdot 47 \cdot 89\,$
3	$63973 = 7 \cdot 13 \cdot 19 \cdot 37\,$
4	$75361 = 11 \cdot 13 \cdot 17 \cdot 31\,$
5	$101101 = 7 \cdot 11 \cdot 13 \cdot 101\,$
6	$126217 = 7 \cdot 13 \cdot 19 \cdot 73\,$
7	$172081 = 7 \cdot 13 \cdot 31 \cdot 61\,$
8	$188461 = 7 \cdot 13 \cdot 19 \cdot 109\,$
9	$278545 = 5 \cdot 17 \cdot 29 \cdot 113\,$
10	$340561 = 13 \cdot 17 \cdot 23 \cdot 67\,$

카마이클 수 ''n''은 모든 소인수 ''p''에 대해 ''p'' − 1이 ''n'' − 1을 나누어 떨어지게 하는 특징을 갖는다. 예를 들어 2821의 경우,

: 2821 = 7 × 13 × 31

이고,

: 2821 − 1 = 2820 = (7 − 1) × 470 = (13 − 1) × 235 = (31 − 1) × 94

이다. 반대로, 이 성질을 만족하고 제곱 인수를 갖지 않는 합성수는 카마이클 수이다. 즉, 카마이클 수는 서로 다른 셋 이상의 소수의 곱으로 이루어져 있다.

두 번째 카마이클 수인 1105는 어떤 작은 수보다 더 많은 방식으로 두 제곱수의 합으로 표현될 수 있다. 세 번째 카마이클 수인 1729는 하디-라마누잔 수로 알려져 있는데, 이는 서로 다른 두 가지 방식으로 양수의 두 세제곱수의 합으로 표현될 수 있는 가장 작은 수이기 때문이다.

2. 3. 분포

숫자가 커질수록 카마이클 수는 점점 더 희귀해진다. 예를 들어, 1과 10²¹ 사이에는 20,138,200개의 카마이클 수가 있으며, 이는 약 50조 개 중 하나(5·10¹³분의 1)에 해당한다.^[8]

C(X)

는

X

이하의 카마이클 수의 개수를 나타내는 함수이다. 10의 거듭제곱에 따른 카마이클 수의 분포는 다음과 같다:^[8]

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$C(10^n)$	0	0	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

카마이클 수의 분포, 즉 $C(X)$ 의 증가율에 대한 연구가 진행되어 왔다.

1953년에 쾨델은 $C(X)$ 의 상한에 대해 다음 부등식을 증명했다.

: $C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)$

여기서 $k_1$ 는 상수이다.

1956년에 에르되시는 이 경계를 다음과 같이 개선했다.

: $C(X) < X \exp\left(\frac{-k_2 \log X \log \log \log X}{\log \log X}\right)$

여기서 $k_2$ 는 상수이다.^[17] 그는 또한 이 상한이 $C(X)$ 의 실제 성장률에 가깝다는 휴리스틱 논증을 제시하기도 했다.

반대로 $C(X)$ 의 하한에 대해서는, 앨퍼드, 그래빌, 그리고 포머란스가 1994년에 충분히 큰 $X$ 에 대해 다음이 성립함을 증명했다.^[3]

: $C(X) > X^\frac{2}{7}.$

2005년에 하먼은 이 하한을 다음과 같이 개선했다^[18]:

: $C(X) > X^{0.332}$

그는 이후 지수를 $0.7039 \times 0.4736 = 0.33336704 > 1/3$ 로 더 개선했다.^[19]

카마이클 수의 점근적 분포에 관해서는 몇 가지 추측이 있다. 1956년에 에르되시는^[17] 충분히 큰 $X$ 에 대해 $X^{1-o(1)}$ 개의 카마이클 수가 있을 것이라고 추측했다. 1981년에 포머란스는^[20] 에르되시의 휴리스틱 논증을 구체화하여 $X$ 까지의 카마이클 수가 적어도 다음과 같을 것이라고 추측했다.

: $X \cdot L(X)^{-1 + o(1)}$

여기서 $L(x) = \exp\left( \frac{\log x \log\log\log x}{\log\log x} \right)$ 이다.

그러나 현재까지의 계산 결과(예: 10²¹까지의 카마이클 수 계산^[8])는 이러한 추측을 뒷받침하지 못하고 있다.

2021년에 다니엘 라르센은 1994년 앨퍼드, 그래빌, 포머란스가 처음 추측했던 카마이클 수에 대한 베르트랑의 공준의 유추를 증명했다.^[4]^[21] 이탕 장과 제임스 메이너드가 쌍둥이 소수 추측 관련 결과를 확립하기 위해 개발한 기술을 사용하여, 라르센은 모든 $\delta>0$ 와 $\delta$ 에 대해 충분히 큰 $x$ 가 주어졌을 때, $x$ 와 $x+\frac{x}{(\log{x})^{\frac{1}{2+\delta}}}$ 사이에 항상 적어도

: $\exp{\left(\frac{\log{x}}{(\log \log{x})^{2+\delta}}\right)}$

개의 카마이클 수가 존재한다는 훨씬 강력한 결과를 얻었다.

3. 발견

페르마의 소정리의 역은 성립하지 않는데, 즉 페르마의 소정리 조건을 만족하는 합성수가 존재하며 이를 카마이클 수라고 부른다.

카마이클 수를 처음으로 발견한 사람은 체코의 수학자 바츨라프 시메르카(Václav Šimerka)였다. 그는 1885년에 이미 처음 7개의 카마이클 수를 찾아냈지만^[11], 그의 연구는 당시 크게 주목받지 못했다.^[12] 이후 1899년 알베르 코르셀트는 카마이클 수의 기본 성질(현재 코르셀트의 기준으로 알려진)을 처음으로 언급했지만, 그러한 수를 실제로 찾아내지는 못했다.

1910년 미국의 수학자 로버트 카마이클^[13]이 가장 작은 카마이클 수인 561을 독자적으로 발견하고 연구 결과를 발표하면서, 이 수들은 그의 이름을 따서 '카마이클 수'로 불리게 되었다. 이후 잭 체르니크, 에르되시 팔, W. R. (레드) 앨포드, 앤드루 그랜빌, 칼 포머런스 등 여러 수학자들의 연구를 통해 카마이클 수가 무한히 많이 존재한다는 사실이 증명되었다.^[3]

3. 1. 바츨라프 시메르카의 발견 (1885)

카마이클 수를 처음으로 발견한 사람은 로버트 대니얼 카마이클이나 알베르 코르셀트가 아닌, 체코의 수학자 바츨라프 시메르카(Václav Šimerka)였다.^[11] 그는 1885년에 이미 처음 7개의 카마이클 수를 발견하여 발표했다. 이는 카마이클의 발표(1910년)보다 25년, 코르셀트의 기준 발표(1899년)보다 14년 앞선 것이었다. 그러나 시메르카는 코르셀트의 기준과 같은 카마이클 수의 일반적인 성질이나 판별법까지 발견하지는 못했다.^[12]

시메르카가 발견한 처음 7개의 카마이클 수는 다음과 같다.

시메르카가 발견한 처음 7개의 카마이클 수
수	소인수분해
561	$3 \cdot 11 \cdot 17$
1105	$5 \cdot 13 \cdot 17$
1729	$7 \cdot 13 \cdot 19$
2465	$5 \cdot 17 \cdot 29$
2821	$7 \cdot 13 \cdot 31$
6601	$7 \cdot 23 \cdot 41$
8911	$7 \cdot 19 \cdot 67$

그의 연구는 당시 체코 과학 저널인 ''Časopis pro pěstování matematiky a fysiky''에 게재되었으나, 국제적으로 널리 알려지지 않아 오랫동안 주목받지 못했다.

3. 2. 카마이클의 발견과 연구 (1910~)

알프레드 코르셀트는 카마이클 수의 기본 성질을 처음으로 관찰했지만, 어떤 예도 제시하지는 않았다.

1910년, 카마이클^[13]은 가장 작은 카마이클 수인 561을 발표했고, 이후 이 수들은 그의 이름을 따서 명명되었다. 561이 카마이클 수라는 것은 코르셀트의 기준으로 설명될 수 있다. 실제로

561 = 3 \cdot 11 \cdot 17

은 제곱 인수가 없고, 각 소인수 p에 대해 p-1은 n-1 (즉, 560)을 나눈다. 구체적으로

3-1=2

,

11-1=10

,

17-1=16

은 모두 560의 약수이다. (

2 \mid 560

,

10 \mid 560

,

16 \mid 560

)

다음 여섯 개의 카마이클 수는 온라인 정수열 사전(OEIS)의 수열 A002997에 나열된 순서대로 다음과 같다.

:

1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104;\quad 12 \mid 1104;\quad 16 \mid 1104)

:

1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728;\quad 12 \mid 1728;\quad 18 \mid 1728)

:

2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464;\quad 16 \mid 2464;\quad 28 \mid 2464)

:

2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820;\quad 12 \mid 2820;\quad 30 \mid 2820)

:

6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600;\quad 22 \mid 6600;\quad 40 \mid 6600)

:

8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910;\quad 18 \mid 8910;\quad 66 \mid 8910).

1939년 잭 체르니크(Jack Chernick)^[14]는 카마이클 수의 부분 집합을 생성하는 방법을 제시하는 정리를 증명했다. 이 정리에 따르면, 만약 세 인수

(6k + 1)

,

(12k + 1)

,

(18k + 1)

가 모두 소수이면, 그 곱

(6k + 1)(12k + 1)(18k + 1)

은 카마이클 수가 된다. 이 공식이 무한히 많은 카마이클 수를 생성하는지는 아직 해결되지 않은 문제이지만, 딕슨의 추측이 참이라면 그럴 것으로 예상된다.

에르되시 팔(Paul Erdős)은 직관적으로 무한히 많은 카마이클 수가 존재할 것이라고 추측했다. 1994년 W. R. (레드) 앨포드(W. R. (Red) Alford), 앤드루 그랜빌(Andrew Granville), 칼 포머런스(Carl Pomerance)는 올슨의 상수에 대한 경계를 이용하여 실제로 카마이클 수가 무한히 많이 존재함을 증명했다. 구체적으로 그들은 충분히 큰

n

에 대해, 1과

n

사이에 적어도

n^{2/7}

개의 카마이클 수가 존재함을 보였다.^[3]

이후 토마스 라이트 (수학자)(Thomas Wright)는 임의의 서로소인 정수

a

와

m

에 대해, 등차수열

a + k \cdot m

(단,

k = 1, 2, \ldots

) 안에 무한히 많은 카마이클 수가 존재함을 증명했다.^[15]

카마이클 수 연구는 더 큰 수를 찾는 방향으로도 진행되었다. Löh와 Niebuhr는 1992년에 1,101,518개의 소인수를 가지며 1600만 자릿수가 넘는 매우 큰 카마이클 수를 발견했다. 이후 기록은 10,333,229,505개의 소인수와 295,486,761,787 자릿수를 가진 수로 갱신되었으며, 이는 현재까지 알려진 가장 큰 알려진 소수보다 훨씬 큰 규모이다.^[16]

3. 3. 잭 체르니크의 정리 (1939)

잭 체르니크(Jack Chernick)^[14]는 1939년에 카마이클 수의 부분 집합을 구성하는 데 사용할 수 있는 정리를 증명했다. 이 정리에 따르면, 어떤 자연수 ''k''에 대해 세 수

6k + 1

,

12k + 1

,

18k + 1

가 모두 소수이면, 이 세 수의 곱인

(6k + 1)(12k + 1)(18k + 1)

은 카마이클 수가 된다.

하지만 이 공식을 사용해서 무한히 많은 카마이클 수를 생성하는지는 아직 해결되지 않은 문제이다. 이는 딕슨의 추측과 관련이 있는 것으로 알려져 있다.

3. 4. 무한성 증명 (1994)

에르되시 팔(Paul Erdős)은 직관적으로 무한히 많은 카마이클 수가 존재해야 한다고 주장했다. 1994년에 W. R. (레드) 앨포드(W. R. (Red) Alford), 앤드루 그랜빌(Andrew Granville) 및 칼 포머런스(Carl Pomerance)는 올슨의 상수에 대한 경계를 사용하여 실제로 무한히 많은 카마이클 수가 존재한다는 것을 보여주었다. 구체적으로, 그들은 충분히 큰

n

에 대해 1과

n

사이에 적어도

n^{2/7}

개의 카마이클 수가 있음을 증명했다.^[3]

이후 토마스 라이트 (수학자)(Thomas Wright)는

a

와

m

이 서로소일 때, 등차수열

a + k \cdot m

(

k = 1, 2, \ldots

)에 무한히 많은 카마이클 수가 존재한다는 것을 증명했다.^[15]

4. 일반화

카마이클 수의 개념은 여러 방식으로 일반화될 수 있다.

수론적 수체 $K$ 의 정수환 ${\mathcal O}_K$ 에서는 페르마의 소정리와 유사하게, 소 아이디얼 $\mathfrak p$ 에 대해 $\alpha^{{\rm N}(\mathfrak p)} \equiv \alpha \pmod{\mathfrak p}$ 가 성립한다. 이를 일반화하여, 소 아이디얼이 아닌 아이디얼 $\mathfrak a$ 가 모든 $\alpha \in {\mathcal O}_K$ 에 대해 $\alpha^{{\rm N}(\mathfrak a)} \equiv \alpha \pmod{\mathfrak a}$ 를 만족할 때, $\mathfrak a$ 를 카마이클 아이디얼이라고 부른다. 이는 카마이클 수의 개념을 수체의 아이디얼로 확장한 것이다.

또한 추상대수학의 관점에서, 합성수 $n$ 이 카마이클 수라는 것은 정수 모듈로 $n$ 의 환 $\mathbf{Z}_n$ 에서 $n$ 제곱 함수 $x \mapsto x^n$ 가 자기 준동형 사상이 되는 것과 같다. 이 조건을 특정 조건을 만족하는 모든 $\mathbf{Z}_n$ -대수로 확장하여 ''' $m$ 차 카마이클 수'''라는 더 일반적인 개념을 정의할 수 있다. 일반적인 카마이클 수는 이 정의에서 1차 카마이클 수에 해당한다.

4. 1. 수체의 카마이클 아이디얼

카마이클 수의 개념은 모든 수론적 수체

K

에서 카마이클 아이디얼로 일반화될 수 있다. 0이 아닌 모든 소 아이디얼

\mathfrak p

in

{\mathcal O}_K

에 대해,

{\mathcal O}_K

의 모든

\alpha

에 대해

\alpha^{{\rm N}(\mathfrak p)} \equiv \alpha \bmod {\mathfrak p}

가 성립한다. 여기서

{\rm N}(\mathfrak p)

는 아이디얼

\mathfrak p

의 노름이다. (이는 소수

p

가 주어질 때, 모든 정수

m

에 대해

m^p \equiv m \bmod p

가 성립한다는 페르마의 소정리를 일반화한 것이다.)

{\mathcal O}_K

에서 0이 아닌 아이디얼

\mathfrak a

가 소 아이디얼이 아니면서,

{\mathcal O}_K

의 모든

\alpha

에 대해

\alpha^{{\rm N}(\mathfrak a)} \equiv \alpha \bmod {\mathfrak a}

가 성립할 때, 즉

{\rm N}(\mathfrak a)

가 아이디얼

\mathfrak a

의 노름일 때, 이 아이디얼

\mathfrak a

를 카마이클 아이디얼이라고 부른다.

K

가 유리수체

\mathbf Q

일 때, 아이디얼

\mathfrak a

는 주 아이디얼이며, 만약

a

를 양의 생성자로 둔다면, 아이디얼

\mathfrak a = (a)

는

a

가 일반적인 의미의 카마이클 수일 때 정확히 카마이클 아이디얼이다.

K

가 유리수보다 큰 수체일 때

{\mathcal O}_K

에서 카마이클 아이디얼을 만드는 것은 쉽다.

K

에서 완전히 분해되는 모든 소수

p

에 대해, 주 아이디얼

p{\mathcal O}_K

는 카마이클 아이디얼이다. 무한히 많은 소수가 모든 수론적 수체에서 완전히 분해되므로,

{\mathcal O}_K

에는 무한히 많은 카마이클 아이디얼이 있다. 예를 들어,

p

가 4를 법으로 1과 합동인 모든 소수일 때, 가우스 정수

\mathbb Z[i]

에서 아이디얼

(p)

는 카마이클 아이디얼이다.

소수와 카마이클 수는 다음 등식을 만족한다.

:

\gcd \left(\sum_{x=1}^{n-1} x^{n-1}, n\right) = 1.

4. 2. 루카스-카마이클 수

양의 합성 정수 n은 n이 제곱 인수가 없는 수이고, n의 모든 소인수 p에 대해 p + 1이 n + 1을 나누는 조건을 만족할 때 루카스-카마이클 수라고 한다. 처음 몇 개의 루카스-카마이클 수는 다음과 같다.

: 399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287 등이 있다.

4. 3. 준 카마이클 수

준 카마이클 수는 제곱 인수가 없는 합성수 ''n''으로, 0이 아닌 모든 정수 ''b''와 ''n''의 모든 소수 인자 ''p''에 대해 ''p'' + ''b''가 ''n'' + ''b''를 나누는 수이다. 만약 ''b'' = -1 이면 카마이클 수이고, ''b'' = 1 이면 루카스-카마이클 수이다. 첫 번째 준 카마이클 수는 다음과 같다.

: 35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ...

4. 4. Knödel 수

주어진 양의 정수 ''n''에 대한 ''n''-'''Knödel 수'''는 모든 i < m 가 ''m''과 서로소인 합성수 ''m''이며, i^{m - n} ≡ 1 (mod m)을 만족하는 수이다. n = 1인 경우는 카마이클 수이다.

4. 5. 고차 카마이클 수

추상대수학의 개념을 사용하여 카마이클 수를 일반화할 수 있다.

기존 카마이클 수의 정의는 합성 정수 ''n''이 정수 계수 환 '''Z'''_''n''에서 자신으로의 ''n''제곱 함수 ''p''_''n''이 항등 함수일 때를 의미한다. 항등 함수는 '''Z'''_''n''에 대한 유일한 '''Z'''_''n''-대수 자기 준동형 사상이므로, 이 정의는 ''p''_''n''이 '''Z'''_''n''의 대수 자기 준동형 사상인지를 묻는 것과 같다. ''n''이 소수일 때도 ''p''_''n''은 동일한 속성을 만족한다.

''n''제곱 함수 ''p''_''n''은 임의의 '''Z'''_''n''-대수 '''A'''에서도 정의될 수 있다. 한 정리에 따르면, ''n''이 소수일 필요충분조건은 모든 이러한 함수 ''p''_''n''이 대수 자기 준동형 사상이라는 것이다.

이 두 조건을 바탕으로, 임의의 양의 정수 ''m''에 대해 '''m차 카마이클 수'''를 정의할 수 있다. ''m''차 카마이클 수는 '''Z'''_''n''-가군으로서 ''m''개의 원소로 생성될 수 있는 모든 '''Z'''_''n''-대수에 대해 ''p''_''n''이 자기 준동형 사상인 모든 합성수 ''n''이다. 정의에 따라, 1차 카마이클 수는 일반적인 카마이클 수와 같다.

하우(Howe)는 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 = 443,372,888,629,441 이 2차 카마이클 수임을 보였다.^[22] 코르셀트의 판정법은 하우에 의해 고차 카마이클 수로 일반화될 수 있다.

같은 논문에서 제시된 휴리스틱 논증은 임의의 ''m''에 대해 ''m''차 카마이클 수가 무한히 많을 것이라고 시사하지만, 현재까지 3차 이상의 카마이클 수는 발견되지 않았다.

참조

_[1] 서적 Prime Numbers and Computer Methods for Factorization Birkhäuser
_[2] 서적 Prime Numbers: A Computational Perspective Springer 2005
_[3] 논문 There are Infinitely Many Carmichael Numbers http://www.math.dart[...]
_[4] 웹사이트 Teenager Solves Stubborn Riddle About Prime Number Look-Alikes https://www.quantama[...] 2022-10-13
_[5] 서적 Number Theory and Its History https://archive.org/[...] McGraw-Hill 1948
_[6] 논문 Strong Carmichael numbers 1976
_[7] 논문 Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases 1995-08
_[8] 간행물 The Carmichael numbers up to 10²¹ http://tucs.fi/publi[...] Turku Centre for Computer Science 2017-06-26
_[9] 웹사이트 Carmichael Multiples of Odd Cyclic Numbers http://www.numerican[...]
_[10] 문서 Proof sketch: If $n$ is square-free but not cyclic, $p_i \mid p_j - 1$ for two prime factors $p_i$ and $p_j$ of $n$ . But if $n$ satisfies Korselt then {{tmath|1= p_j - 1 \mid n - 1 }}, so by transitivity of the "divides" relation {{tmath|1= p_i \mid n - 1 }}. But $p_i$ is also a factor of {{tmath|1= n }}, a contradiction.
_[11] 논문 Zbytky z arithmetické posloupnosti http://dml.cz/handle[...]
_[12] 논문 Václav Šimerka: quadratic forms and factorization 2013
_[13] 논문 Note on a new number theory function https://www.ams.org/[...]
_[14] 논문 On Fermat's simple theorem https://www.ams.org/[...]
_[15] 논문 Infinitely many Carmichael Numbers in Arithmetic Progressions
_[16] 논문 Constructing Carmichael numbers through improved subset-product algorithms
_[17] 논문 On pseudoprimes and Carmichael numbers http://www.renyi.hu/[...]
_[18] 논문 On the number of Carmichael numbers up to ''x''
_[19] 논문 Watt's mean value theorem and Carmichael numbers 2008
_[20] 논문 On the distribution of pseudoprimes
_[21] 논문 Bertrand's Postulate for Carmichael Numbers https://academic.oup[...] 2022-07-20
_[22] 논문 Higher-order Carmichael numbers 2000-10
_[23] 문서 The Carmichael numbers up to 10²¹ http://s369624816.we[...] 2007-05
_[24] 서적 Prime Numbers and Computer Methods for Factorization Birkhäuser
_[25] 서적 Prime Numbers: A Computational Perspective https://archive.org/[...] Springer 2005
_[26] 논문 There are Infinitely Many Carmichael Numbers http://www.math.dart[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com