高欧拉商数

高欧拉商数（highly totient number）k是有以下性质，大于1的正整数：使以下方程式有多个解

φ(x) = k

其中φ是欧拉函数，而且若k用其他较小的整数代入时，解的个数都会比刚刚的个数要少。

例如方程式φ(x) = k，在k=1,2,3,4,5,6,7,8时，分别有2,3,0,4,0,4,0,5个解，φ(x) = 8有5个解，若代入小于8的数值，解都少于5个，因此8是高欧拉商数。

头几个高欧拉商数是：

1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440 （OEIS数列A097942）.

分别使上述方程有1, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54及72个解。若将使φ(x) = k分别恰有0个解、1个解、2个解……的最小k值组成一个数列，则高欧拉商数会是此数列的一个子集。例如8为高欧拉商数，φ(x) = 8有5个解，表示任何小于8的整数都无法使φ(x) = k有5个解，因此8是使φ(x) = k有5个解的最小k值。

若x的质因数分解为$x=\prod _{i}p_{i}^{e_{i}}$，其欧拉商数为以下的乘积：

$\phi (x)=\prod _{i}(p_{i}-1)p_{i}^{e_{i}-1}.$

因此，高欧拉商数和较小的整数相比，高欧拉商数可以表示为更多种以上式表示的乘积。

高欧拉商数的概念有点类似高合成数；1既是高合成数中唯一的奇数，也是高欧拉商数中唯一的奇数（其实1是欧拉函数值域中唯一的奇数）。而且高欧拉商数和高合成数都有无限多个，不过随着数字的增加，要找到高欧拉商数也就越来困难，因为欧拉商数和质因数分解有关，数字越大，就越难进行质因数分解。

举例

有五个整数（15, 16, 20, 24和30）的欧拉商数是8。比8小的整数中，没有哪一个是五个整数的欧拉商数。因此8是高欧拉商数。

表

n	使$\phi (k)=n$的k值（OEIS数列A032447）	使$\phi (k)=n$的k的个数（OEIS数列A014197）
0		0
1	1, 2	2
2	3, 4, 6	3
3		0
4	5, 8, 10, 12	4
5		0
6	7, 9, 14, 18	4
7		0
8	15, 16, 20, 24, 30	5
9		0
10	11, 22	2
11		0
12	13, 21, 26, 28, 36, 42	6
13		0
14		0
15		0
16	17, 32, 34, 40, 48, 60	6
17		0
18	19, 27, 38, 54	4
19		0
20	25, 33, 44, 50, 66	5
21		0
22	23, 46	2
23		0
24	35, 39, 45, 52, 56, 70, 72, 78, 84, 90	10
25		0
26		0
27		0
28	29, 58	2
29		0
30	31, 62	2
31		0
32	51, 64, 68, 80, 96, 102, 120	7
33		0
34		0
35		0
36	37, 57, 63, 74, 76, 108, 114, 126	8
37		0
38		0
39		0
40	41, 55, 75, 82, 88, 100, 110, 132, 150	9
41		0
42	43, 49, 86, 98	4
43		0
44	69, 92, 138	3
45		0
46	47, 94	2
47		0
48	65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210	11
49		0
50		0

相关条目

• L. Havelock, A Few Observations on Totient and Cototient Valence from PlanetMath

相关条目

• 高合成数
• 非欧拉商数
• 高互补欧拉商数

参考资料

• L. Havelock, A Few Observations on Totient and Cototient Valence from PlanetMath