On Positive Integers n n with ϕ ( n ) = 2 3 ⋅ ( n + 1 ) \phi(n)=\frac{2}{3}\cdot(n+1)
2025
Read On Positive Integers n n with ϕ ( n ) = 2 3 ⋅ ( n + 1 ) \phi(n)=\frac{2}{3}\cdot(n+1) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19915.txt.
Introduction
Christian Hercher settles properties of a curious number puzzle about Euler's totient function, which counts integers sharing no factor with a given number. A question from Erdős and Graham's circle asks which numbers make the totient exactly two thirds of the number plus one. Four chain-like solutions were known.
Hercher proves any solution must be square-free, with no repeated prime factor. Prime factors of a solution also obey a strict divisibility ban among themselves. Any extra solution needs at least seven prime factors and must exceed ten to the fourteenth power. The known four look increasingly lonely. The catalog record lists no author; the byline is the paper's own. Number puzzles yield to such patient fencing-in.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19915
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Positive Integers n n with ϕ ( n ) = 2 3 ⋅ ( n + 1 ) \phi(n)=\frac{2}{3}\cdot(n+1) Abstract While solving a special case of a question of Erdős and Graham Steinerberger asks for all integers n n with ϕ ( n ) = 2 3 ⋅ ( n + 1 ) \phi(n)=\frac{2}{3}\cdot(n+1) . He discovered the solutions n ∈ { 5 , 5 ⋅ 7 , 5 ⋅ 7 ⋅ 37 , 5 ⋅ 7 ⋅ 37 ⋅ 1297 } n\in\{5,5\cdot 7,5\cdot 7\cdot 37,5\cdot 7\cdot 37\cdot 1297\} and found that any additional solution must be greater than 10 10 10^{10} . He conjectured that there are no such additional solutions to this problem. We analyze this problem and prove: • Every solution n n must be square-free. • IF p p and q q are prime factors of a solution n n then p ∤ ( q − 1 ) p\nmid(q-1) . • Any solution additional to the set given by Steinerberger has to have at least 7 prime factors. • For any additional solution it holds n ≥ 10 14 n\geq 10^{14} . Christian Hercher Institut für Mathematik Europa-Universität Flensburg Auf dem Campus 1c 24943 Flensburg Germany [email protected] 1 Introduction In [ 2 ] Erdős and Graham define for positive integers x the functions g_{0}(x):=x+\phi(x) and g_{k+1}(x):=g_{0}(g_{k}(x)) . They ask for solutions of g_{k+r}(x)=2g_{k}(x) . This is listed as Problem #411 in Bloom’s list [ 1 ] . For r=2 Steinerberger [ 4 ] gives six infinite sequences of solutions and postulate that these are all solutions. He proofs that every other solution has to be of the form x=2^{\ell}\cdot p with a prime p>10^{10} fulfilling \phi((3p-1)/4)=(p+1)/2 . This criteria can be reformulated as the search for primes p=8m+7 such that \phi(6m+5)=4m+4 , or—to put it in another way— as the search for positive integers n=6m+5 with \phi(n)=\frac{2}{3}\cdot(n+1) and \frac{1}{3}\cdot(4n+1) being a prime. We drop the primality condition and ask for all positive integers n with \displaystyle\phi(n) \displaystyle=\frac{2}{3}\cdot(n+1). (1) Steinerberger finds four solutions of ( 1 ), namely n\in\{5,35,1195,1679615\} , and conjectures that this list is complete. He checked and found no other solution under 10^{10} . We investigate this question further. 1.1 Outline In Section 2 we prove that every n solving ( 1 ) has to be square-free (Theorem 1 ) and that for every two primes p and r dividing n we have p\nmid(r-1) (Corollary 2 ). Then, in Section 3 we prove directly that Steinerbergers list of known solutions is complete, if one only considers positive integers with at most four prime factors (Theorem 10 ). We also show that for every fixed number of prime factors there are at most finitely many solutions (Corollary 8 ). And in Section 4 we describe how we used the insides gained in the previous sections to write a fast computer program that automates this search for further solutions of ( 1 ). We state the findings that there are no such solutions with n having exactly five or six prime factors (Theorem 10 ) and that for every additional solution n has to be at least 10^{14} (Theorem 13 ). 2 Any solution is square-free Theorem 1 . Let n be a positive integer with \phi(n)=\frac{2}{3}\cdot(n+1) . Then n is square-free. Proof. We want to find all positive integers n which solve equation ( 1 ). Obviously, n=1 is not a solution. Thus, from now on let be n>1 . As \displaystyle\phi(n) \displaystyle=n\cdot\prod_{p\mid n}\frac{p-1}{p} ( 1 ) is equivalent to \displaystyle\prod_{p\mid n}\frac{p-1}{p} \displaystyle=\frac{2}{3}\cdot\left(1+\frac{1}{n}\right) (2) or \displaystyle n \displaystyle=\frac{2\prod_{p\mid n}p}{3\cdot\prod_{p\mid n}(p-1)-2\prod_{p\mid n}p}=:\frac{N}{D}. (3) First observe that for every p\mid n the left hand side of ( 2 ) is \leq 1-\frac{1}{p} . Thus, would n be divisible by 2 or 3, the product on the left side of ( 2 ) would be at most 1-\frac{1}{3}=\frac{2}{3} , hence smaller than the right hand side of ( 2 ). Thus, we know for all primes q\mid n that q\geq 5 . Any such prime divisor q of n clearly divides the left hand side of ( 3 ) and the numerator N of the right hand side of ( 3 ), but N only once. So it does not divide the denominator D . Thus, the only possible non-trivial common divisor of N and D is 2. Since n must be divisible by at least one odd prime D is even, hence \mathop{gcd}(D,N)=2 . Now n is an integer, which means that D\mid N . Hence, D\mid 2 . Since also 2=\mathop{gcd}(D,N)\mid D and D=\frac{n}{N}>0 it follows D=2 . Thus, 3\cdot\prod_{p\mid n}(p-1)-2\prod_{p\mid n}p=2 and n=\prod_{p\mid n}p is square-free. ∎ Now we can reformulate the problem: Find all finite sets \emptyset\neq Q\subset\mathbb{P}\setminus\{2,3\} of primes with \displaystyle 3\cdot\prod_{q\in Q}(q-1)-2\prod_{q\in Q}q \displaystyle=2. (4) In this setting we have \displaystyle\prod_{q\in Q}q \displaystyle=n. (5) Remark that with n=\prod_{q\in Q} it follows from ( 4 ) that 2\equiv 0-2n\equiv n\pmod{3} , hence n\equiv 5\pmod{6} . So the restriction to such n by Steinerberger does not loose any other solutions of ( 1 ). Corollary 2 . Let n be a positive integer with \phi(n)=\frac{2}{3}\cdot(n+1) and let p and r be two primes with pr\mid n . Then p\nmid(r-1) . Proof. From equation ( 4 ) we now that there is a set \{p,r\}\subseteq Q\subset\mathbb{P}\setminus\{2,3\} of primes with n=\prod_{q\in Q}q . Obviously, p divides n and r-1 divides \prod_{q\in Q}(q-1) , but from ( 4 ) we know that both products are relatively prime, because n is odd. Hence, p\nmid(r-1) . ∎ 3 Solutions for small sets with |Q|\leq 4 From now on let \mathbb{P}=\{p_{1},p_{2},\dots\} the set of primes with 2=p_{1}<p_{2}<\dots and \emptyset\neq Q\subset\mathbb{P} a finite subset with Q=\{q_{1},\dots,q_{k}\} and 5\leq q_{1}<\dots<q_{k} . 3.1 The case k=|Q|=1 Lemma 3 . The only solution of equation ( 4 ) with k=1 prime factor is n=5 . Proof. In the case of k=1 equation ( 4 ) reduces to 3(q_{1}-1)-2q_{1}=2 , or q_{1}=5 . Thus, n=q_{1}=5 is the only solution for ( 2 ) with n only having one prime factor. ∎ 3.2 The case k=|Q|=2 Lemma 4 . The only solution of equation ( 4 ) with k=2 prime factor is n=5\cdot 7 . Proof. In the case of k=2 equation ( 4 ) reduces to \displaystyle 3(q_{1}-1)(q_{2}-1)-2q_{1}q_{2} \displaystyle=2. This is equivalent to \displaystyle q_{1}q_{2}-3q_{1}-3q_{2}+1 \displaystyle=0 \displaystyle(q_{1}-3)(q_{2}-3) \displaystyle=8. Since q_{1} and q_{2} are both odd, the only factorization valid is q_{1}-3=2 and q_{2}-3=4 , thus q_{1}=5 , q_{2}=7 , and n=q_{1}q_{2}=35 . This is is the only solution for ( 2 ) with two prime factors. ∎ 3.3 A generalized variant of the case k=2 The method of factoring a certain term to find all solutions of a problem which was used in the previous Section 3.2 can be generalized: Lemma 5 . Let A>B\geq 2 be positive integers and q_{1}<q_{2} be two primes with \displaystyle A\cdot(q_{1}-1)\cdot(q_{2}-1) \displaystyle=B\cdot q_{1}\cdot q_{2}+2. (6) Then \displaystyle((A-B)q_{1}-A)\cdot((A-B)q_{2}-A) \displaystyle=AB+2(A-B). (7) If A=2a and B=2b are both even it follows \displaystyle((a-b)q_{1}-a)((a-b)q_{2}-a) \displaystyle=ab+a-b. (8) Proof. Let A,B,q_{1},q_{2} be as described in the lemma. We are interested in solutions of \displaystyle A\cdot(q_{1}-1)\cdot(q_{2}-1) \displaystyle=B\cdot q_{1}\cdot q_{2}+2. As in the previous section we equivalently restate this equation as \displaystyle(A-B)\cdot q_{1}q_{2}-A\cdot(q_{1}+q_{2})+A-2 \displaystyle=0 \displaystyle(A-B)^{2}q_{1}q_{2}-A\cdot(A-B)(q_{1}+q_{2})+(A-B)(A-2)