高互補歐拉商數

高互補歐拉商數（highly cototient number）k是有以下性質，大於1的正整數：使以下方程式有多個解

x - φ(x) = k

其中φ是歐拉函數，而且若k用其他較小的整數代入時，解的個數都會比剛剛的個數要少。若k=1時，上式會有無窮多組解，因此在定義上，k需是大於1的正整數。前幾個高互補歐拉商數為：

2, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 119, 167, 209, 269, 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889, ... （OEIS數列A100827）

許多高互補歐拉商數是奇數，大於8的高互補歐拉商數都是奇數，大於167的高互補歐拉商數都是29 mod 30的數。

高互補歐拉商數的概念類似高合成數。高合成數有無限多個，而高互補歐拉商數也有無限多個。但數字越大，要進行整數分解也就越難，因此判斷高互補歐拉商數也越難。

例子

$x$的互補歐拉商數（cototient）定義為$x-\phi (x)$，也就是小於等於此數的正整數中，和此數至少有一個共同質因數（即不互質）的正整數。例如6的互補歐拉商數是4，因為有4個小於等於6的正整數和6有共同的質因數：2, 3, 4, 6，因此6的互補歐拉商數是4。只有二個整數（6和8）的互補歐拉商數是4。而互補歐拉商數是2和3的整數都不到2個，因此4是高互補歐拉商數。

（OEIS數列A063740）

k（高互補歐拉商數會用粗體表示）	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
x – φ(x) = k解的個數	1	∞	1	1	2	1	1	2	3	2	0	2	3	2	1	2	3	3	1	3	1	3	1	4	4	3	0	4	1	4	3

n	使得$k-\phi (k)=n$的k	使得$k-\phi (k)=n$的k的個數 （OEIS數列A063740）
0	1	1
1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ... （所有的質數）	∞
2	4	1
3	9	1
4	6, 8	2
5	25	1
6	10	1
7	15, 49	2
8	12, 14, 16	3
9	21, 27	2
10		0
11	35, 121	2
12	18, 20, 22	3
13	33, 169	2
14	26	1
15	39, 55	2
16	24, 28, 32	3
17	65, 77, 289	3
18	34	1
19	51, 91, 361	3
20	38	1
21	45, 57, 85	3
22	30	1
23	95, 119, 143, 529	4
24	36, 40, 44, 46	4
25	69, 125, 133	3
26		0
27	63, 81, 115, 187	4
28	52	1
29	161, 209, 221, 841	4
30	42, 50, 58	3
31	87, 247, 961	3
32	48, 56, 62, 64	4
33	93, 145, 253	3
34		0
35	75, 155, 203, 299, 323	5
36	54, 68	2
37	217, 1369	2
38	74	1
39	99, 111, 319, 391	4
40	76	1
41	185, 341, 377, 437, 1681	5
42	82	1
43	123, 259, 403, 1849	4
44	60, 86	2
45	117, 129, 205, 493	4
46	66, 70	2
47	215, 287, 407, 527, 551, 2209	6
48	72, 80, 88, 92, 94	5
49	141, 301, 343, 481, 589	5
50		0

質數

高互補歐拉商數中，頭幾個是質數的是

2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839, 1049, 1259, 1889, 2099, 2309, 2729, 3359, 3989, 4289, 4409, 5879, 6089, 6719, 9029, 9239, ... （OEIS數列A105440）

相關條目

• 高歐拉商數