7
$\begingroup$

In this article : https://en.wikipedia.org/wiki/Euler%27s_totient_function

it is stated that for every positive integer $m\ge 2$, there exists a postive integer $k$, such that $\varphi(n)=k$ has exactly $m$ solutions in positive integers $n$.

How can I construct such a number $k$ for a given $m$ ?

I determined such a $k$ for $2\le m\le 100$ , but I did not find a useful pattern to see how to get a number for arbitary $m$

Here the values I found :

m   k

2  10
3  44
4  4
5  8
6  12
7  32
8  36
9  40
10  24
11  48
12  160
13  396
14  2268
15  704
16  312
17  72
18  336
19  216
20  936
21  144
22  624
23  1056
24  1760
25  360
26  2560
27  384
28  288
29  1320
30  3696
31  240
32  768
33  9000
34  432
35  7128
36  4200
37  480
38  576
39  1296
40  1200
41  15936
42  3312
43  3072
44  3240
45  864
46  3120
47  7344
48  3888
49  720
50  1680
51  4992
52  17640
53  2016
54  1152
55  6000
56  12288
57  4752
58  2688
59  3024
60  13680
61  9984
62  1728
63  1920
64  2400
65  7560
66  2304
67  22848
68  8400
69  29160
70  5376
71  3360
72  1440
73  13248
74  11040
75  27720
76  21840
77  9072
78  38640
79  9360
80  81216
81  4032
82  5280
83  4800
84  4608
85  16896
86  3456
87  3840
88  10800
89  9504
90  18000
91  23520
92  39936
93  5040
94  26208
95  27360
96  6480
97  9216
98  2880
99  26496
100  34272
$\endgroup$
  • $\begingroup$ Presumably you could find your answer by looking up Ford's 1999 paper in the Annals of Mathematics... $\endgroup$ – Chris Custer Aug 2 '18 at 22:16
  • $\begingroup$ You could see that the results for successive numbers are quite irregular so it is to be assumed that there is no formula to determine these numbers. If it exists, it would have been established long ago I guess. However........ $\endgroup$ – Piquito Aug 2 '18 at 22:42
4
$\begingroup$

This is a theorem of Kevin Ford in 1999, published in Annals of Mathematics. It is a quite difficult result, and the proof does not go by finding any pattern on the function $A(m)$ that assigns the $k$ to every $m$. It was conjectured long time ago by Sierpiński, and proved using a very strong conjecture (the H-Hypothesis) by Schinzel in 1961. It was a bit of a surprise that it could be proved unconditionality.

Of course, this does not mean that there is no "elementary proof" on this result.

In fact lemma 1.1 in that paper by Kevin Ford shows that, if $A(m)=k$ and $p$ is a prime such that $p>2m+1$, $2p+1$ and $2mp+1$ are prime and $dp+1$ are composite for all $d\mid 2m$ except $d=2$ and $d=2m$, then $A(2mp)=k+2$.

This can be used to find a number $m$ for a given explcit $k$ such that $A(m)=k$, although you will not give the smallest one, and even it can be quite big.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.