INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A06

ON THE EQUATION m − 1 = aφ(m)

Marian Deaconescu Kuwait University, Kuwait

                          deacon@mcs.sci.kuniv.edu.kw

Dedicated to Haidar Khajah

Received: 12/5/04, Revised: 9/19/05, Accepted: 2/12/06, Published: 2/22/06

Abstract

Let φ denote Euler’s totient function. It is shown that if r ≥ 2 there exist only finitely many positive integers n such that φ(n) divides n − 1 and φ(n)^{2} ≡ r (mod n). It is also shown that if k ≥ 2 there exist only finitely many positive integers n such that φ(n) divides n − 1 and φ(n)^{k} ≡ 1 (mod n).

1. Introduction

Let φ denote Euler’s totient function. D.H. Lehmer [5] proposed the following:

Conjecture. If a ≥ 2 is an integer, then there is no positive integer m such that

aφ(m) = m − 1.

In other words, if m ≥ 2, then φ(m) divides m − 1 if and only if m is a prime. I will refer in the sequel to Lehmer’s conjecture as to (L). The interested reader may consult R.K. Guy’s book [3] for a list of references.

The aim of this note is to derive more information on (hypothetical) counterexamples to Lehmer’s conjecture. Two finiteness results are proved by elementary methods, information that can be viewed as an argument for the veracity of (L).

From now on n will denote a counterexample to (L) and ϕ = φ(n) for the sake of simpler

Typeset by AMS-TEX

notation. Since n is a counterexample to (L), we can find an integer a ≥ 2 such that

(1)  n − 1 = aϕ.

Since (n, ϕ) = 1, we see that n must be composite, square-free and odd, thus n = ∏_{i=1}^{s} p_{i} for some s ≥ 2 and for some distinct odd primes p_{i}, 1 ≤ i ≤ s. We have ϕ = φ(n) = ∏_{i=1}^{s}(p_{i} − 1) and for simplicity we will use also the notation ψ = ψ(n) = ∏_{i=1}^{s}(p_{i} − 2). D.H. Lehmer proved in [5] that s ≥ 7 and subsequently it was shown by Cohen and Hagis [1] that s ≥ 14.

The starting point of this note was the following simple observation:

ϕ^{2} ≢ 1 (mod n).

To prove this, note first that since n is composite and odd we have ϕ > \sqrt{n} and thus, by (1), a < \sqrt{n}. If n|ϕ^{2} − 1, then, by (1), n|(\frac{n−1}{a})^{2} − 1, implying n|a^{2} − 1 < n and forcing a = 1, a contradiction since a ≥ 2.

Since ϕ^{2} > n, division of ϕ^{2} by n gives a positive quotient q and a remainder r such that

(2)  ϕ^{2} = qn + r, 2 ≤ r ≤ n − 1.

This raises the following question: if r ≥ 2 , what can be said of the counterexamples n to (L) that satisfy the condition ϕ^{2} ≡ r (mod n)? Though we don’t even know whether or not such counterexamples do exist at all, something sensible can be said, namely:

Theorem 1.1. If r ≥ 2 is fixed, there exist only finitely many counterexamples n to (L) such that ϕ^{2} ≡ r (mod n).

Another question suggested by the remark that ϕ^{2} ≢ 1 (mod n) is related to the order of ϕ modulo n. This is the smallest positive integer k = |ϕ| satisfying ϕ^{k} ≡ 1 (mod n). By Lagrange’s theorem, k divides ϕ since ϕ is the order of the group of units of the ring Z_{n} of residue classes modulo n. Since n is composite, the group of units is not cyclic, so 3 ≤ k ≤ \frac{ϕ}{2}. If k ≥ 3 is fixed, it is natural to ask about the number of counterexamples n to (L) that satisfy ϕ^{k} ≡ 1 (mod n):

Theorem 1.2. If k ≥ 3 is fixed, there exist only finitely many counterexamples n to (L) such that ϕ^{k} ≡ 1 (mod n).

Finally, information on the counterexamples to (L) leads to characterizations of primes as follows:

Theorem 1.3. Let m ≥ 2 be an integer and assume that m ≡ 1 (mod φ(m)). Then the following are equivalent: a) m is a prime.

b) φ(m)^{2} ≡ 1 (mod m).

c) φ(m)^{3} ≡ −1 (mod m).

d) φ(m)^{4} ≡ 1 (mod m).

2. Preliminaries

This section contains several remarks on a counterexample n to Lehmer’s conjecture (L). Since n is composite, the following result from [2] is useful: ϕ(ϕ − 1) > (n − 1)ψ. By (1), n − 1 = aϕ and we obtain ϕ − 1 > aψ, hence

(3)  ϕ ≥ aψ + 2.

From (1) and (2) one obtains that

(4)  n(ϕ − aq) = ϕ + ar, ϕ(ϕ − aq) = q + r.

Clearly, ϕ−aq ≥ 1, whence q ≤ \frac{ϕ−1}{a}. By (1) and (2), q +r ≤ \frac{ϕ−1}{a} +n−1 = \frac{ϕ−1}{a} +aϕ < (a+1)ϕ. Since by (4) ϕ|q+r, we see that q+r ≤ aϕ = n−1 and thus by (4) again ϕ(ϕ−aq) = q+r ≤ aϕ, giving q ≥ \frac{ϕ−a}{a}. And since r = ϕ^{2} − qn we obtain

(5)  \frac{ϕ − a}{a} ≤ q ≤ \frac{ϕ − 1}{a}, 1 ≤ ϕ − aq ≤ a, \frac{n − ϕ}{a} ≤ r ≤ n − \frac{ϕ}{a}.

By (5), r − q ≥ \frac{n−ϕ−ϕ+1}{a} > \frac{1}{a}, so

(6)  r ≥ q + 1.

By (3) and (5), q ≥ \frac{ϕ−a}{a} ≥ \frac{aψ+2−a}{a} > ψ − 1, whence

(7)  q ≥ ψ.

By (5) and (3) again, r ≤ n − \frac{ϕ}{a} ≤ n − \frac{aψ+2}{a} = n − ψ − \frac{2}{a} < n − ψ, hence

(8)  r ≤ n − (ψ + 1).

We also need a lower bound for ϕ in terms of a. Observe first that ψ ≥ a + 1, for if not, then n = aϕ + 1 ≥ ψϕ + 1, a contradiction for s ≥ 2. Now use (3) to get ϕ ≥ aψ + 2 ≥ a(a + 1) + 2 = a^{2} + a + 2 and record this last inequality as

(9)  ϕ ≥ a^{2} + a + 2.

3. Proofs

Proof of Theorem 1.1. To prove the Theorem, note that (6) and (7) imply r ≥ ψ + 1 and note that only finitely many n’s may satisfy this inequality for a fixed r.

But this line of proof ultimately depends on an elementary result from [2] and it is worth including here a short and elegant proof, due to one of the editors, a proof that rests on Th. 328 of Hardy and Wright’s book [4].

The proof goes as follows. Since n − 1 = aϕ , then by Th. 328 of [4] we have that a = O(log log n). If ϕ^{2} ≡ r (mod n), then a^{2}r ≡ 1 (mod n). Now, if |r| < \frac{n}{(log log n)^{2}} , then a^{2}r = o(n) and for sufficiently large n we cannot have a^{2}r ≡ 1 (mod n) unless a^{2}r = 1. Thus, for a fixed r such that |r| < \frac{n}{(log log n)^{2}} , there exist only finitely many counterexamples n satisfying ϕ^{2} ≡ r (mod n). And it is clear that, for r fixed, there are only finitely many positive integers n such that |r| ≥ \frac{n}{(log log n)^{2}} , which completes the proof.

Proof of Theorem 1.2. It is easy to show that the number of counterexamples to (L) having a fixed number s of prime divisors is finite. Indeed, let s ≥ 2 be fixed and let n = aϕ + 1 be a counterexample to (L) having s prime factors. Since a = ∑\begin{matrix}d|n \\ d<n \end{matrix} \frac{1}{φ(d)} < (\frac{3}{2})^{s}, we see that there are only finitely many such a’s possible. Fix now such an a. Since there are exactly 2^{s} − 1 divisors d of n with d < n and since 1 = ∑\begin{matrix}d|n \\ d<n \end{matrix} \frac{1}{aφ(d)}, it is clear that n cannot be arbitrarily large.

Suppose now that ϕ^{k} ≡ 1 (mod n). Since n − 1 = aϕ, it follows that n|a^{k} − 1 if k is even and n|a^{k} + 1 if k is odd. In any case, n ≤ a^{k} + 1, giving aϕ ≤ a^{k}. Thus ϕ ≤ a^{k−1} < (\frac{3}{2})^{s(k−1)}.

So k − 1 > \frac{1}{s}log_{\frac{3}{2}} (ϕ) > \frac{1}{s}log_{\frac{3}{2}} (2^{s}s!). This implies in turn that k − 1 − log_{\frac{3}{2}} 2 > \frac{1}{s}log_{\frac{3}{2}} (s!) and it is now clear that there exist only finitely many values of s satisfying the last inequality. The result now follows from the first paragraph.

Proof of Theorem 1.3. The implications a) ⇒ b), c), d) are clear and the implication b) ⇒ a) was proved in the Introduction. Note that if n is a counterexample to c) ⇒ a), or to d) ⇒ a), then n is a counterexample to (L) and we can use the notation and the partial results in the Preliminaries.

Let n be a counterexample to c) ⇒ a), so ϕ^{3} ≡ rϕ ≡ aϕ ≡ −1 (mod n). Then n|ϕ(r − a), giving n|r−a and forcing r = a. But, by (6), (7), and the fact that ψ ≥ a+1 we get r ≥ ψ+1 > a, a contradiction. Finally, let n be a counterexample to d) ⇒ a), that is ϕ^{4} ≡ r^{2} ≡ a^{2}r ≡ 1 (mod n). Then n|r^{2} − a^{2}r = r(r − a^{2}), forcing, as above, r = a^{2}. Then, by (5), we have a^{2} = r ≥ \frac{n−ϕ}{a} = \frac{(a−1)ϕ+1}{a}, which gives a^{3} − 1 ≥ (a − 1)ϕ. Thus ϕ ≤ a^{2} + a + 1, contradicting (9) and completing the proof.

4. Remarks

The lower bound ψ + 1 given for r in the proof of Theorem 1.1 is not the best possible. The fact that r ∈ [ψ + 1, n − (ψ + 1)] serves only the purpose of providing a ”symmetric” interval for r. A better lower bound is \frac{ϕ+2}{2} and this is obtained by combining (5), (3) and the fact that a ≥ 2.

By Cohen and Hagis’ result, if N denotes the smallest odd square-free integer with 14 prime factors satisfying (N, φ(N)) = 1 and if r ≤ \frac{φ(N)}{2}, then there is no counterexample n to (L) satisfying ϕ^{2} ≡ r (mod n). In particular, if r ≤ 10^{23}, there is no counterexample n to (L) such that φ(n)^{2} ≡ r (mod n).

Suppose that a = 2, so n = 2ϕ + 1. Then, by (5), we derive at once that q = \frac{ϕ−2}{2} and r = \frac{3ϕ+2}{2}. Unfortunately, these equalities don’t seem to provide an apparent contradiction able to show that such an n doesn’t exist.

Based on the information at hand it is not difficult to show that if ϕ^{k} ≡ 1 (mod n), then k ≥ 5. Indeed, suppose first that k = 3, that is ϕ^{3} ≡ rϕ ≡ a^{2}r ≡ 1 (mod n). Then n|rϕ−ra^{2} = r(ϕ − a^{2}). But from (2) it is clear that (n, r) = 1, thus n|ϕ − a^{2}. Since ϕ, a^{2} < n, this gives ϕ − a^{2} = 0, contradicting (9). As a direct consequence of Theorem 1.3, k ≠ 4.

Lehmer’s conjecture can be rephrased in group theoretical terms. Those familiar with group theory will quickly realize that (L) is equivalent to the following group-theoretical statement: if G is a finite group and if |Aut(G)| divides |G| − 1, then the holomorph of G is a Frobenius group. Unfortunately, this change of language doesn’t seem to provide any clue for a general method of attack of (L).

Theorem 1.3 suggests an interesting question: are there positive composite integers m such that m|φ(m)^{3} + 1? Or, more generally, is it possible , for such a composite integer m, to find a positive integer k such that m|φ(m)^{2k+1} + 1? If m is a prime, then m|φ(m) + 1 (in this case k = 0).

The smallest possible example one can think of is k = 1 and m = pq, where p, q are odd primes. It is a simple exercise to check that pq|(φ(pq))^{3} + 1 is equivalent to p|q^{2} − q + 1 and q|p^{2} −p+1. That these two divisibilities cannot hold in the same time was established by Geoff Bailey (a.k.a. Fred the Wonder Worm ) on December 9th 2004 in The Math Forum@Drexel (http://mathforum.org/sci.math.research).

Bailey’s observation raises suggests another interesting open problem. Let n ≥ 3, let p_{i}, 1 ≤ i ≤ n be distinct primes and let f(p_{i}) = p_{i}^{2} − p_{i} + 1. Is it possible that the product of all p_{i}’s divides the product of all f(p_{i})’s?

6 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A06

References

1. G.L. Cohen and P. Hagis, On the number of prime factors of n if ϕ(n)|n − 1, Niew Arch. Wisk. (3) 28 (1980), 177–185.

2. M. Deaconescu, Adding units mod n, El. Math. 55 (2000), 123–127.

3. R.K. Guy, Unsolved Problems in Number Theory, third edition, Springer Verlag , New York, 2004.

4. G. Hardy and E. Wright, An Introduction to the Theory of Numbers, 5th edition, Clarendon Press, Oxford, 1979.

5. D.H. Lehmer, On Euler’s totient function, Bull. Amer. Math. Soc. 38 (1932), 745-751.