카마이클의 총체적인 함수 추측
Carmichael's totient function conjecture수학에서 카마이클의 총함수 추측은 정수 수를 n보다 적게, 합쳐서 n으로 계산하는 오일러의 총함수 φ(n)의 값의 다양성에 관한 것이다.그것은 모든 n에 대해 φ(m) = φ(n)과 같은 다른 정수 m ≠ n이 적어도 하나 있다고 명시한다.로버트 카마이클은 1907년에 처음으로 이 추측을 말했으나, 추측이라기보다는 정리로서 말했다.그러나 그의 증거는 잘못된 것이었고, 1922년 그는 자신의 주장을 철회하고 그 추측을 공공연한 문제라고 말했다.
예
totient 함수 φ(n)은 n이 세 값 3, 4, 6 중 하나일 때 2와 같다.따라서 이 세 가지 값 중 하나를 n으로 본다면 나머지 두 값 중 하나를 of(m) = φ(n)의 m으로 사용할 수 있다.
마찬가지로, totent는 n이 4개의 값 5, 8, 10, 12 중 하나일 때 4와 같고, n이 4개의 값 7, 9, 14, 18 중 하나일 때 6과 같다.각각의 경우에, n의 값이 φ(n)과 같은 값을 갖는 n의 값이 두 개 이상 있다.
추측에 의하면 이러한 반복적인 값의 현상은 모든 n을 지탱하고 있다고 한다.
| k | n φ(n) = k(OEIS의 시퀀스 A03247)와 같은 숫자 n | 그러한 ns의 수(OEIS의 순서 A014197) |
| 1 | 1, 2 | 2 |
| 2 | 3, 4, 6 | 3 |
| 4 | 5, 8, 10, 12 | 4 |
| 6 | 7, 9, 14, 18 | 4 |
| 8 | 15, 16, 20, 24, 30 | 5 |
| 10 | 11, 22 | 2 |
| 12 | 13, 21, 26, 28, 36, 42 | 6 |
| 16 | 17, 32, 34, 40, 48, 60 | 6 |
| 18 | 19, 27, 38, 54 | 4 |
| 20 | 25, 33, 44, 50, 66 | 5 |
| 22 | 23, 46 | 2 |
| 24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 10 |
| 28 | 29, 58 | 2 |
| 30 | 31, 62 | 2 |
| 32 | 51, 64, 68, 80, 96, 102, 120 | 7 |
| 36 | 37, 57, 63, 74, 76, 108, 114, 126 | 8 |
| 40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 9 |
| 42 | 43, 49, 86, 98 | 4 |
| 44 | 69, 92, 138 | 3 |
| 46 | 47, 94 | 2 |
| 48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 11 |
| 52 | 53, 106 | 2 |
| 54 | 81, 162 | 2 |
| 56 | 87, 116, 174 | 3 |
| 58 | 59, 118 | 2 |
| 60 | 61, 77, 93, 99, 122, 124, 154, 186, 198 | 9 |
| 64 | 85, 128, 136, 160, 170, 192, 204, 240 | 8 |
| 66 | 67, 134 | 2 |
| 70 | 71, 142 | 2 |
| 72 | 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 | 17 |
하한
카마이클의 추측에는 비교적 쉽게 판단할 수 있는 하한선이 매우 높다.카르마이클 자신은 자신의 추측에 대한 어떤 백례(즉, φ(n)가 모든 다른 숫자의 합계와 다른 값 n)가 적어도 10이어야37 한다는 것을 증명했고, 빅터 클리는 이 결과를 10으로400 연장했다.Schlafly와 Wagan이 10 7의 하한을, 10 10 의 하한을 1998년에 Kevin Ford가 결정했다.[1]
이 하한들의 기초가 되는 계산 기법은 가장 작은 counterrexample이 그것의 토털 값을 나눈 소수 정사각형으로 분리되어야 한다는 것을 보여줄 수 있게 하는 Klee의 몇 가지 주요 결과에 의존한다.Klee의 결과는 3을 제외한 8과 페르마 프리타임(형식 2k + 1)이 가장 작은 카운트렉샘플을 나누지 않는다는 것을 암시한다.결과적으로, 추측을 입증하는 것은 모든 정수에 대한 추측이 4 (mod 8)로 일치한다는 것을 증명하는 것과 같다.
기타 결과
포드는 또한 만약 추측에 대한 백작샘플이 존재한다면, 정수의 양의 비율(무증상 밀도)도 백작샘플이라는 것을 증명했다.[1]
비록 그 추측이 널리 믿어지고 있지만, 칼 포머런스는 정수 n이 그 추측에 대한 백례(Pomerance 1974년)가 될 수 있는 충분한 조건을 주었다.이 조건에 따르면 p - 1이 φ(n), p가2 n을 나누는 등 prime p마다 n은 counterexample이다.그러나 포머런스는 그러한 정수의 존재는 매우 가능성이 낮다는 것을 보여주었다.본질적으로 1(mod q) (여기서 q가 prime인 경우)에 대한 첫 번째 k primes p concuous가 모두 q보다k+1 작을 경우, 그러한 정수는 모든 prime에 의해 분할될 것이므로 존재할 수 없다는 것을 보여줄 수 있다.어쨌든 포머런스의 백범례가 존재하지 않는다는 것을 증명하는 것은 카마이클의 추측을 증명하는 것과는 거리가 멀다.그러나 만약 그것이 존재한다면 포드가 주장한 것처럼 무한히 많은 백배아들이 존재한다.
Carmichael의 추측을 진술하는 또 다른 방법은, A(f)가 )(n) = f에 대한 양의 정수 n의 수를 나타낸다면, A(f)는 결코 1과 같을 수 없다는 것이다.이와 관련, 와카와프 시에르피에스키 교수는 1을 제외한 모든 양의 정수는 케빈 포드에 의해 1999년에 증명된 추정치인 A(f)의 값으로 발생한다고 추측했다.[2]
메모들
참조
- Carmichael, R. D. (1907), "On Euler's φ-function", Bulletin of the American Mathematical Society, 13 (5): 241–243, doi:10.1090/S0002-9904-1907-01453-2, MR 1558451.
- Carmichael, R. D. (1922), "Note on Euler's φ-function", Bulletin of the American Mathematical Society, 28 (3): 109–110, doi:10.1090/S0002-9904-1922-03504-5, MR 1560520.
- Ford, K. (1999), "The number of solutions of φ(x) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, JSTOR 121103, MR 1715326, Zbl 0978.11053.
- Guy, Richard K. (2004), Unsolved problems in number theory (3rd ed.), Springer-Verlag, B39, ISBN 978-0-387-20860-2, Zbl 1058.11001.
- Klee, V. L., Jr. (1947), "On a conjecture of Carmichael", Bulletin of the American Mathematical Society, 53 (12): 1183–1186, doi:10.1090/S0002-9904-1947-08940-0, MR 0022855, Zbl 0035.02601.
- Pomerance, Carl (1974), "On Carmichael's conjecture" (PDF), Proceedings of the American Mathematical Society, 43 (2): 297–298, doi:10.2307/2038881, JSTOR 2038881, Zbl 0254.10009.
- Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 228–229, ISBN 978-1-4020-2546-4, Zbl 1079.11001.
- Schlafly, A.; Wagon, S. (1994), "Carmichael's conjecture on the Euler function is valid below 1010,000,000", Mathematics of Computation, 63 (207): 415–419, doi:10.2307/2153585, JSTOR 2153585, MR 1226815, Zbl 0801.11001.
