1. Introduction

Euler Totient Function, \( φ(n) \) , is a number theory function defined on positive integers. For a positive integer \( n \) , the number of positive integers (including 1) that are less than or equal to \( n \) and are coprime with \( n \) is written as \( φ(n) \) . About the Euler Totient Function (Unless otherwise specified below, \( φ(n) \) only refers to Euler Totient Function), some related equations have been proposed and discussed the solutions of these equations which is a significant topic in elementary number theory. Besides, around \( φ(n) \) , there have been rich conclusions and put forward many conjectures with contributions.

In 1932, Derrick Henry Lehmer proposed a conjecture that no composite number satisfies \( φ(n)∣n-1 \) . In other words, for each positive integer \( k,kφ(n)=n-1 \) has no solutions. In Lehmer’s thesis [1], if \( n \) is a solution of (1), then \( n \) is a prime or the product of seven or more distinct primes. In 1963, K. Zhao and S. Qi proved that such a composite number \( n \) is at least the product of 12 different odd prime numbers [2]. Moreover, in 1980, Cohen and Haggis further proved that it is a product of at least 14 different odd prime numbers. In 2009, William D Banks and Florian Luca proved that such an \( n \) is at most \( {x^{1/2}}/{(logx)^{1/2+o(1)}} \) as \( x→+∞ \) . Unfortunately, there is still no definitive answer to this question, but the academic community has come up with many reasonable conclusions. This article will discuss some n properties that can be derived from this equation and briefly discuss the case where \( k=2 \) .

This article will summarise some previous methods and use elementary methods to draw some conclusions for the case of \( k=2 \) .

2. Properties of \( n \) which satisfies the Equation

2.1. Readiness Knowledge

There are some basic theorems about Euler functions. [2] The Euler function is denoted by \( φ(n) \) .

Theorem 1. Let the standard decomposition formula of \( n \) be: \( n=p_{1}^{{r_{1}}}p_{2}^{{r_{2}}}⋯p^{{ar_{k}}} \) , then,

\( φ(n)=n(1-\frac{1}{{p_{1}}})(1-\frac{1}{{p_{2}}})⋯(1-\frac{1}{{p_{k}}})\ \ \ (1) \)

To prove Theorem 1, it is needed to prove some inferences and theorems. Intuitively, the correctness of this theorem is obvious. For example, let \( n \) be \( 24=3*{2^{3}} \) , the reduced residue system \( (1≤r≤n) \) is \( \lbrace 1,5,7,11,13,17,19,23\rbrace \) , hence \( φ(24)=8 \) , and using the formula above, \( φ(24)=24(1-\frac{1}{2})(1-\frac{1}{3})=8 \) . However, to prove this theorem, some pre-conclusions are needed. Here are two lemmas given without proof.

Lemma 1. Let \( n≥1 \) , then:

\( \sum _{(d∣n)}^{​}φ(d)=n\ \ \ (2) \)

Lemma 2. \( Let(m,n)=1,{ T_{1}}:=\lbrace {t_{1}}:{t_{1}}∣m\rbrace ,{ T_{2}}:=\lbrace {t_{2}}:{t_{2}}∣n\rbrace \) , then \( T=\lbrace {t_{1}}{t_{2}}:{t_{1}}∈{T_{1}},{t_{2}}∈{T_{2}}\rbrace \) includes all the factors of \( mn \) . In other words, \( T=\lbrace t:t∣mn\rbrace \) .

Then there is the theorem:

Theorem 2. \( Let(m,n)=1 \) , then \( φ(mn)=φ(m)φ(n) \) .

Proof. Let \( h=mn \) , using induction method: if \( h=1 \) , it is obvious; suppose that if \( h=1,2,⋯,nm-1 \) , the conclusion is valid, let \( t|nm,t={t_{1}}{t_{2}},{t_{1}}|m,{t_{2}}∣n \) , by the assumption above, except for \( {t_{1}}=m,{t_{2}}=n \) , the equation \( φ({t_{1}}{t_{2}})=φ({t_{1}})φ({t_{1}}) \) holds.

Hence, by Lemma 2,

\( \sum _{({t_{1}}∣m)}^{​}φ({t_{1}})\sum _{({t_{2}}∣n)}^{​}φ({t_{2}})=(\sum _{(t∣mn)}^{​}φ(t)-φ(mn))+φ(m)φ(n)\ \ \ (3) \)

From Lemma \( 1,mn=(mn-φ(mn))+φ(m)φ(n) \) , which is equivalent to \( φ(mn)=φ(m)φ(n) \) .

So, Theorem 1 can be proved.

The proof of Theorem 1. From Theorem 2,

\( φ(n)=φ(p_{1}^{{α_{1}}})⋯φ(p_{k}^{{α_{k}}}). \ \ \ (4) \)

Then, it is just needed to prove \( φ({p^{α}})={p^{α}}-{p^{α-1}} \) . From the definition of \( φ(n),φ({p^{α}})={p^{α}}-\sum _{i∈I}^{​}i, I=\lbrace i∣i \) and \( p \) are mutually prime \( \rbrace =\lbrace i∣i \) is a multiple of \( p\rbrace \) . At the same time, the number of multiples of \( p \) from 1 to \( {p^{α}} \) is \( {p^{α-1}} \) , hence \( φ({p^{α}})={p^{α}}-{p^{α-1}} \) .

Meanwhile, here is another theorem.

Theorem 3.

1.Let \( (m,n)=d \) , then \( φ(mn)=φ(m)φ(n)\cdot \frac{d}{φ(d)} \) .

2. If \( a∣b \) , then \( φ(a)∣φ(b) \) .

Proof. (1)

\( \begin{matrix} & \\ \frac{φ(mn)}{mn} & =\prod _{(p∣mn)}^{​}(1-\frac{1}{p})=\frac{\prod _{(p∣m)}^{​}(1-\frac{1}{p})\prod _{(p∣n)}^{​}(1-\frac{1}{p})}{\prod _{(p∣(m,n))}^{​}(1-\frac{1}{p})}=\frac{\frac{φ(m)}{m}\frac{φ(n)}{n}}{\frac{φ(d)}{d}} \\ & \\ & \\ \end{matrix}\ \ \ (5) \)

Thus \( φ(mn)=φ(m)φ(n)\frac{d}{φ(d)} \) .

(2) Let \( b=ac \) , from (1), \( φ(b)=φ(ac)=φ(a)φ(c)\frac{d}{φ(d)}=dφ(a)\frac{φ(c)}{φ(d)} \) , where \( (a,c)=d \) .

Since \( d∣c,\frac{dφ(c)}{φ(d)}=\frac{c\prod _{p∣c}^{​}(1-\frac{1}{p})}{\prod _{p∣d}^{​}(1-\frac{1}{p})} \) is an integer(because the factors of c include the factors of d). Hence \( φ(a)∣φ(b) \) .3

2.2. Lehmer’s Conjecture

There has been systematic research in the academic community on the properties of Euler Totient Functions and their divisibility with some other functions. In 1932, an American mathematician, Derrick Henry Lehmer, supposed a conjecture:

Proposition 1. There is no composite number \( n \) such that:

\( φ(n)∣n-1. \)

As mentioned earlier, it is tough to solve this problem completely, but some n properties can be obtained. Firstly, in case \( k=1 \) , it is evident that \( n \) satisfies (1) is equivalent to \( n \) is a prime. Thus, consider \( k \) as an integer greater than 1 in the following discussion.

Theorem 4. Let \( k≥2,kφ(n)=n-1 \) , then:

1. \( n \) is the product of different odd prime numbers.

2. If odd prime \( p \) satisfies \( p∣n \) , then \( n \) does not contain prime factors in the form of \( pt+1 \) .

3. If \( k≢1( mod 3) \) , then \( n≢0( mod 3) \) .

Proof. Since \( k≥2 \) , then \( n \gt 2 \) , and since \( 2∣φ(n) \) , so \( 2∤n \) ; if prime \( p∣n,n \) has prime factors with the form \( pt+1 \) or \( {p^{2}}∣n \) , \( p∣φ(n) \) , thus \( p∣n-1 \) (because \( kφ(n)=n-1) \) , and it is impossible. So, the first and the second conclusion can be proved.

When \( k≡0( mod 3) \) , the conclusion is right. When \( k≡2( mod 3) \) , if \( n≡0( mod 3) \) , assume \( n= \) \( {p_{1}}⋯{p_{s}},{p_{1}}=3,{p_{2}},⋯,{ p_{s}} \) are different odd prime numbers. Thus,

\( 2k\prod _{j=2}^{s}({p_{j}}-1)=3\prod _{j=2}^{s}{p_{j}}-1, \)

And from conclusion 2, \( {p_{j}}≡-1( mod 3) \) , and module 3, then:

\( 1≡2( mod 3), \)

And it is impossible.

Thus:

Inference 1. If \( n \) satisfies \( (I) \) and \( n={p_{1}}⋯{p_{s}} \) , then:

\( φ(n)=\prod _{i=1}^{s}({p_{i}}-1) (6) \)

Proof. Obviously.

First, discuss a simple case where \( k=2 \) and \( n \) is the product of two prime numbers:

\( 2φ(n)=n-1. \)

It is equivalent to:

\( \begin{matrix} & \\ 2({p_{1}}-1)({p_{2}}-1) & ={p_{1}}{p_{2}}-1, \\ & \\ {p_{1}}{p_{2}}-2({p_{1}}+{p_{2}})+3 & =0 \\ & \\ ({p_{1}}-2)({p_{2}}-2) & =1. \\ \end{matrix} \)

Thus, \( {p_{1}}={p_{2}}=3 \) is impossible because \( {p_{i}} \) are different prime numbers. Similarly, it can be proved that when \( n={p_{1}}{p_{2}}{p_{3}} \) , no \( n \) satisfies \( 2φ(n)=n-1 \) .

Moreover, here is another theorem proved by K. Zhao [3].

Theorem 5. Let \( n \) satisfy \( (1) \) and \( n={p_{1}}⋯{p_{s}} \) , then:

\( k \lt \prod _{i=1}^{s}\frac{{p_{i}}}{{p_{i}}-1}\ \ \ (7) \)

Proof. From (1) and Inference 1:

\( k\prod _{i=1}^{s}{p_{i}}-1=\prod _{i=1}^{s}{p_{i}}-1 \)

Thus,

\( k=\prod _{i=1}^{s}\frac{{p_{i}}}{{p_{i}}-1}-\prod _{i=1}^{s}\frac{1}{{p_{i}}-1} \lt \prod _{i=1}^{s}\frac{{p_{i}}}{{p_{i}}-1}. \)

By theorem 5, it can be directly obtained:

Inference 2. If \( n={p_{1}}⋯{p_{s}},s≤11 \) is a solution of (1), then \( k=2 \) or \( k=3 \) .

Proof. From (2),

\( \begin{matrix} & \\ k & \lt \prod _{i=1}^{s}\frac{{p_{i}}}{{p_{i}}-1} \\ & \\ & ≤\frac{3}{2}\cdot \frac{5}{4}\cdot \frac{7}{6}\cdot \frac{11}{10}\cdot \frac{13}{12}\cdot \frac{17}{16}\cdot \frac{19}{18}\cdot \frac{23}{22}\cdot \frac{29}{28}\cdot \frac{31}{30}\cdot \frac{37}{36} \lt 4 \\ \end{matrix} \)

Thus, \( k=2 \) or \( k=3 \) .

Through a proof process and calculation process similar to the above proof, the following theorem can be proved:

Theorem 6. If \( k=2 \) , the solution \( (1) \) is at least the product of 12 odd prime numbers.

3. Conclusion

When \( k=2 \) , the solution of (1) is at least the product of 12 odd prime numbers. Using computers, it can be reached that when \( k=2 \) , the solution is at least the product of 14 or more prime numbers. Unfortunately, it is not easy to push the conclusion to positive infinity, to completely solve the conjecture, in addition to the methods of elementary number theory, some analytical methods of number theory are necessary. William D Banks and Florian Luca’s thesis [4] proved that \( \ \ \ L(x) \lt \lt {x^{1/2}}log{x^{3}}/4 \) ., where \( L(x) \) is the solution set of \( (1) \) , which provides a significant method of researching this problem. Meanwhile, G Tenenbaum provided some relevant research on analytical number theory [5].