Inverse function of EulerPhi

hbghlyj

1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8
oeis.org/A000010
是否存在正整数k，使得关于n的方程φ(n)=k有唯一正整数解
n为奇数时，φ(n)=φ(2n).所以n是偶数.

hbghlyj

ListPlot[Array[EulerPhi, 10000]]

它的上边界是y=x-1，它们是素数
集中的几条直线是谁？

设p为素数，那么$\phi(p^n)=(p-1)p^{n-1}$对应直线$y=\frac{p-1}px$，$\phi(p^n)=(p-1)p^{n-1}$
这个猜测好像不太对，偏离了一点？
ListPlot[Array[EulerPhi[EulerPhi[#]] &, 10000]]

hbghlyj

chaoli.club/index.php/7230
Carmichael's totient function conjecture
Carmichael, R. D. (1922), "Note on Euler's φ-function"

hbghlyj

k	numbers n such that φ(n) = k (sequence A032447)	number of such ns (sequence 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

hbghlyj

A007366 Numbers $k$ such that $\varphi(x) = k$ has exactly 2 solutions.
Contains $\Set{2\cdot3^{6k+1}| k \ge 1}$ as a subsequence. This is the simplest proof for the infinity of these numbers (see Sierpiński, Exercise 12, p. 237)

hbghlyj

若$\varphi(n)=2\cdot3^{6k+1}$，求证$n=3^{6k+2}$ or $2\cdot3^{6k+2}$


相关：若$\varphi(n)=2$，求证$n \le 6$

睡神

这个好像不难

显然，$3\mid n $

1、当$n=3^{\alpha_1}$时，$\varphi(n)=2\cdot 3^{\alpha_1-1}$，此时$\alpha_1=6k+2$，即$n=3^{6k+2}$

2、当$n=3^{\alpha_1}\cdot p^{\alpha_2}$时，$\varphi(n)=2\cdot(p-1)\cdot 3^{\alpha_1-1}\cdot p^{\alpha_2-1}$

假设$p\ge 5$，则$2\mid (p-1)$

此时  $\varphi(n)=2^t\cdot x\cdot 3^{\alpha_1-1},t\ge 2$矛盾

所以  $p=2$

所以  $\alpha_1=6k+2,\alpha_2=1$，即$n=2\cdot 3^{6k+2}$

3、假设$n$至少存在3个素因数

设$n=3^{\alpha_1}\cdot p^{\alpha_2}_2\cdot \cdots \cdot p^{\alpha_m}_m,m\ge 2$

$\varphi(n)=2\cdot (p_2-1)\cdot \cdots \cdot (p_m-1)\cdot 3^{\alpha_1-1}\cdot p^{\alpha_2-1}_2\cdot \cdots \cdot p^{\alpha_m-1}_m=2^t\cdot x\cdot 3^{\alpha_1-1},t\ge m\ge 2$矛盾

hbghlyj

睡神 发表于 2024-4-29 04:48
此时  $\varphi(n)=2^t\cdot x\cdot 3^{\alpha_1-1},t\ge 2$矛盾

谢谢！还有一个类似的：

A085713 Numbers $k$ such that $\varphi(x) = k$ has exactly 3 solutions.

如果 $\varphi(x) = k$ 正好有 3 个解，则这 3 个解为$(3p, 4p, 6p)$, 其中 $p$ 是 1 或素数。