カーマイケルのトーシェント関数予想

トーシェント関数 ${\displaystyle \varphi (n)}$ は、n が 3, 4 または 6 の三つのいずれかのとき 2 に等しくなる。よって、これら三つの値のいずれかを n として取れば、他の二つを ${\displaystyle \varphi (m)=\varphi (n)}$ を満たすような m として 用いることができる。

同様に、n が 5, 8, 10 または 12 の四つのいずれかであればトーシェントは 4 に等しく、また、n が 7, 9, 14 または 18 のいずれかであれば 6 に等しくなる。いずれの場合も、${\displaystyle \varphi (n)}$ の値が等しくなる n は複数個存在する。

この予想は、この現象があらゆる n に対して繰り返されると予想している。

k	${\displaystyle \varphi (n)=k}$ となる n (オンライン整数列大辞典の数列 A032447)	そのような値の個数 (オンライン整数列大辞典の数列 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

カーマイケル予想の反例の下限は非常に大きな値であり、これを決定するのは予想の解決に比べれば簡単である。カーマイケル自身は、この予想の反例　(すなわち、${\displaystyle \varphi (n)}$ の値があらゆる他の整数と異なるような n)は少なくとも 10³⁷ より大きいことを示した。ヴィクター・クリー（英語版）はこの結果を 10⁴⁰⁰ まで拡張し、A. シュラフリとスタン・ワゴン（英語版）は${\displaystyle 10^{10^{7}}}$ という値を得、ケヴィン・フォードにより ${\displaystyle 10^{10^{10}}}$ という下限が1998年に決定された^[1]。

これらの下限を求めるのに使われた計算上のテクニックは、クリーによる「最小の反例は、そのトーシェント値の各素因数の2乗で割り切れる」という重要な事実に依存している。クリーの結果は、3以外のフェルマー素数（${\displaystyle 2^{2^{k}}+1}$ の形の素数）と 8 は最小の反例の約数ではないことも含意している。結果として、予想を証明するのは 4 (mod 8) に当てはまる整数のみについて証明するのと同値となる。

フォードはまた、もし反例が存在するならば、（漸近的密度の意味で）正の比率の整数が、同様に反例になることを証明している^[1]。

この予想は真であると広く信じられているが、カール・ポメランスは整数 n が反例となる十分条件を与えている(Pomerance 1974)。この条件によれば、p-1 が ${\displaystyle \varphi (n)}$を割り切るような素数 p の全てが、p^2 が n を割り切るという条件を満たすならば、n は反例となる。しかしながら、ポメランスは、このような整数の存在を証明するのはほぼ不可能であることを示した。かいつまんで言えば、ある素数 ${\displaystyle q}$ に対して p ≡ 1 (mod q) となる最初の k 個の素数 p が全て${\displaystyle q^{k+1}}$よりも小さいならば、そのような整数は全ての整数で割り切れることになり、それゆえ存在しないからである。いずれにしろ、ポメランスの示した反例が存在しないことを証明するのはカーマイケル予想の証明には程遠い。とはいえ、もし反例が存在するなら無限個存在することはフォードが確証したとおりである。

カーマイケルの予想は以下のような別の形で述べることができる: ${\displaystyle A(f)}$ を ${\displaystyle \varphi (n)=f}$ となる正整数の個数とすると、${\displaystyle A(f)=1}$ になることは決してない。これに関連して、ヴァツワフ・シェルピニスキは、1 以外の全ての正整数が ${\displaystyle A(f)}$ の値として現れると予想したが、この予想は1999年にケヴィン・フォードにより証明された^[2]。