Journal de Théorie des Nombres de Bordeaux

Jason P. Bell

Logarithmic frequency in morphic sequences

Jean-François Jaulent

Plongements ${\ell }$-adiques et ${\ell }$-nombres de Weil

Reynald Lercier

Thomas Sirvent

On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field

Amanda Folsom

Class invariants and cyclotomic unit groups from special values of modular units

Bill Allombert

Karim Belabas

Practical Aurifeuillian factorization

Omar Kihel

Florian Luca

Omar KIHEL et Florian LUCA
Variants of the Brocard-Ramanujan equation
Tome 20, no 2 (2008), p. 353-363.
<http://jtnb.cedram.org/item?id=JTNB_2008__20_2_353_0>
© Université Bordeaux 1, 2008, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir la
présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 20 (2008), 353-363
Variants of the Brocard-Ramanujan equation
par Omar KIHEL et Florian LUCA
Résumé. Dans cet article, nous étudions quelques variations sur
l’équation diophantienne de Brocard-Ramanujan.
Abstract. In this paper, we discuss variations on the Brocard-
Ramanujan Diophantine equation.
1. Introduction
Brocard (see [4, 5]), and independently Ramanujan (see [15, 16]), posed
the problem of finding all integral solutions to the diophantine equation
(1) n! + 1 = x2.
Although it is unlikely that equation (1) has any solution with n > 7, the
fact that it has only finitely many solutions has only been conditionally
proved by Overholt (see [13]). He showed that the weak form of Szpiro’s
conjecture implies that equation (1) has only finitely many solutions. The
weak form of Szpiro’s conjecture is a special case of the ABC conjecture
and asserts that there exists a constant s such that if A, B, and C are
positive integers satisfying A + B = C with gcd(A,B) = 1, then
C ≤ N(ABC)s,
where N(k) is the product of all primes dividing k taken without repetition.
Berend and Osgood [1] showed that if P ∈ ZZ[X] is a polynomial of degree
≥ 2, then the density of the set of positive integers n for which there exists
an integer x satisfying the more general diophantine equation
(2) n! = P (x)
is zero. Erdős and Obláth [7] and Pollack and Shapiro [14] showed that if
P (x) = xd ± 1 and d ≥ 3, then equation (2) has no solution with n > 1.
Generalizing Overholt’s result, the second author [11] showed that the full
ABC conjecture implies that equation (2) has only finitely many solutions.
A wealth of information about this equation can be found in the recent
paper [2].
Manuscrit reçu le 13 février 2007.
354 Omar Kihel, Florian Luca
In this paper, we discuss some variations on the above diophantine equa-
tions. We look at the following diophantine equations:
(3) xp ± yp =
n∏
k×n
k=1
k,
and
(4) P (x) =
n∏
k×n
k=1
k,
where P ∈ Q[x] is a polynomial of degree ≥ 2. Here and in what follows,
we write k × n to mean that k does not divide n.
2. New results
In what follows, we use the Vinogradov symbols ,  and  as well
as the Landau symbols O and o with their regular meanings. Recall that
A  B, B  A and A = O(B) are all equivalent and mean that |A| ≤ c|B|
holds with some positive constant c.
Theorem 1. The Diophantine equation
xp ± yp =
n∏
k×n
k=1
k
admits only finitely many integer solutions (x, y, p, n) with p ≥ 3 a prime
number and gcd(x, y) = 1.
Proof. There is no loss of generality to consider only the ’+’ sign and to
assume that |x| > |y|. Since the right hand side is positive, we get that x
is positive. Note that gcd(x, y) = 1 implies that no prime q ≤ n coprime to
n divides either x or y. Now either x ≤ n, or x ≥ n + 1. In the first case,
(n− 1)!1/2 ≤ xp + |y|p ≤ 2np,
therefore by Stirling’s formula
(n− 1)
2
(1 + o(1)) log n ≤ p log n + log 2.
For large n, the above inequality implies that p ≥ n/3. Note however that
xp + yp = (x + y)(xp + yp)/(x + y), and, by Fermat’s Little Theorem, it
follows easily that (xp + yp)/(x + y) = δm, where δ ∈ {1, p}, and every
prime factor of m is 1 (mod p). Since every prime factor of m is ≤ n ≤ 3p,
it follows that
xp + yp
x + y
≤ p(p + 1)(2p + 1).
Brocard-Ramanujan 355
However,
xp + yp
x + y
≥ xp−2 ≥ 2p−2.
Indeed, the above inequality holds for positive y because
xp + yp > xp ≥ 2xp−1 = (2x)xp−2 ≥ (x + y)xp−2,
and for negative y because
xp + yp
x + y
= xp−1 + xp−2(−y) + · · ·+ (−y)p−1 > xp−1 > xp−2.
We thus get the inequality
2p−2 ≤ p(p + 1)(2p + 1),
which shows that p is bounded, and since p ≥ n/3, we get that n is bounded
as well in this case.
We now assume that x ≥ n + 1. If y > 0, then nn > n! > xp ≥ (n + 1)p,
and if y < 0, then
nn > (x + y)
(
xp−1 + xp−2(−y) + · · ·+ (−y)p−1
)
> xp−1 ≥ (n + 1)p−1.
In both cases, we get p ≤ n. We write again
xp + yp = (x + y)
(
xp + yp
x + y
)
,
and we use the fact that (xp + yp)/(x + y) = δm, where δ ∈ {1, p}, and
every prime factor of m is 1 (mod p). If y > 0, we get
m =
xp + yp
δ(x + y)
>
xp
2xp
=
xp−1
2p
,
while if y < 0, then
m =
1
δ
(
xp + yp
x + y
)
=
1
δ
(
xp−1 + xp−2(−y) + · · ·+ (−y)p−1
)
>
xp−1
2p
.
Thus, we always have
m ≥ x
p−1
2p
>
(2xp)(p−1)/p
4p
>
(∏n
k×n
k=1
k
)(p−1)/p
4p
,
where we used the fact that
∏n
k×n
k=1
k = xp + yp < 2xp. Let M be the largest
divisor of
∏n
k×n
k=1
k build up only from primes of the form q ≡ 1 (mod p).
Then m | M , and so
log M >
p− 1
p
log
 n∏
k×n
k=1
k
− log(4p) > p− 12p (n−1) log
(
n− 1
e
)
− log(4p).
356 Omar Kihel, Florian Luca
In the above inequality, we used Stirling’s formula as well as the fact that∏n
k×n
k=1
k > (n− 1)!1/2. It is clear that for all q ≤ n, the order of q in n! is⌊
n
q
⌋
+
⌊
n
q2
⌋
+ · · · < n
∑
i≥1
1
qi
=
n
q − 1
.
Thus,
log M < n
∑
q≤n
q≡1 (mod p)
log q
q − 1
.
Comparing the above inequalities, we get
p− 1
2p
log(n− 1)− p− 1
p
− log 4p
n− 1
<
n
n− 1
∑
q≤n
q≡1 (mod p)
log q
q − 1
,
which together with the fact that p ≤ n leads to
p− 1
2p
log(n− 1) ≤ n
n− 1
∑
q≤n
q≡1 (mod p)
log q
q − 1
+ O(1).
Writing q = 1 + pt for some t ≤ n/p and using the trivial inequality∑
q≤n
q≡1 (mod p)
log q
q − 1
≤ log n
p
∑
t≤n/p
1
t
 log
2 n
p
,
we get
1
3
log(n− 1) ≤ p− 1
2p
log(n− 1)  log
2 n
p
+ O(1),
therefore p  log n. Using the Montgomery-Vaughan Theorem concerning
primes in arithmetic progressions (see [12]) as well as partial summation,
we deduce that ∑
q≤n
q≡1 (mod p)
log q
q − 1
 log n
p
,
and therefore get
1
3
log(n− 1) ≤ p− 1
2p
log(n− 1)  log n
p
+ O(1),
which leads to p  1. Since now p may be assumed fixed, we may apply
Dirichlet’s theorem on primes in arithmetical progressions, to get that∑
q≤n
q≡1 (mod p)
log q
q − 1
=
log(n− 1)
p− 1
+ O(1),
Brocard-Ramanujan 357
and now we are led to
p− 1
2p
log(n− 1) ≤ log(n− 1)
p− 1
+ O(1),
which tells us that(
p− 1
2p
− 1
p− 1
)
= O
(
1
log(n− 1)
)
,
which admits only finitely many solutions (p, n) with p ≥ 5 because
p− 1
2p
− 1
p− 1
=
p2 − 4p + 1
2p(p− 1)
≥ 6
40
for p ≥ 5. Finally, since nn > xp−1 and n and p are bounded, we get that x
is also bounded. The statement with p = 3 follows from the same arguments
by strengthening the inequality
n∏
k×n
k=1
k > (n− 1)!1/2,
to say
n∏
k×n
k=1
k > n!2/3
for n sufficiently large. To see that this last inequality holds, note that
n∏
k×n
k=1
k ≥ n!
nτ(n)
,
where τ(n) is the number of divisors of n. Thus, it suffices to show that the
inequality
nτ(n) < n!1/3
holds for large n, and this inequality is implied by
τ(n) log n <
n
3
log(n/e).
Since log(n/e) > (log n)/2 if n is large, it follows that it is enough that the
inequality
τ(n) <
n
6
holds for large n, and this last inequality is obvious. ut
Before stating and proving Theorem 2, we restate the ABC conjecture
mentioned already in the introduction. The ABC conjecture asserts that
for any ε > 0 there exists a constant C(ε) depending only on ε, such that
358 Omar Kihel, Florian Luca
if A, B and C are three nonzero coprime integers satisfying A + B = C,
then
max(|A|, |B|, |C|) < C(ε)N(ABC)1+ε.
Theorem 2. Let P ∈ Q[x] be a polynomial of degree ≥ 2. Then the ABC
conjecture implies that the equation
P (x) =
n∏
k×n
k=1
k
has only finitely many solutions (x, n), where x is a rational number and n
is a positive integer.
Proof. We write the equation as
a0x
d + a1xd−1 + · · ·+ ad = ad+1
n∏
k×n
k=1
k,
where a0, . . . , ad+1 are integers with a0ad+1 6= 0. Here, one may choose
ad+1 to be the least common denominator of all the coefficients of P (x).
Multiplying both sides of the above equation by ad−10 and letting y = a0x,
it follows that we arrive at the equation
yd + b1yd−1 + · · ·+ bd = bd+1
n∏
k×n
k=1
k,
where bi = aiai−10 for i = 1, . . . , d, and bd+1 = ad+1a
d−1
0 . Note now that y
is an integer because for every fixed positive integer n the above equation
shows that the rational number y is a root of a monic polynomial with
integer coefficients; hence, an algebraic integer, and therefore a rational
integer. With the substitution z = y + b1/d, we may rewrite the above
equation as
zd + c2zd−2 + · · ·+ cd = cd+1
n∏
k×n
k=1
k,
where ci are rational numbers whose denominator divides dd. Finally, we
multiply the above equation by dd and use the substitution t = dz to arrive
at
td + e2td−2 + · · ·+ ed = ed+1
n∏
k×n
k=1
k,
where t and ei are integers for i = 2, . . . , d + 1. Let j ≤ d be the largest
index in {2, . . . , d} such that ej 6= 0. If this index does not exist, then the
Brocard-Ramanujan 359
above equation is
td = ed+1
n∏
k×n
k=1
k.
By the Prime Number Theorem, for large n, the interval (n/2, n) contains
≈ n/(2 log n) prime numbers p and none of those divides n. Since d > 1
and t is an integer, it follows that every such prime number divides ed+1.
In particular, n/2 < ed+1, which shows that n is bounded.
Assume now that j exists and rewrite the equation as
(5) tj + (e2tj−2 + · · ·+ ej) =
ed+1
td−j
n∏
k×n
k=1
k.
Since for large t we have that |td + e2td−2 + · · ·+ ej |  |t|d, it follows that
|t|d  |td + e2td−2 + · · ·+ ed| 
n∏
k×n
k=1
k  (n− 1)!1/2,
therefore, by taking logarithms and invoking Stirling’s formula, we get
(6) |t| ≥ exp
(
1
2d
(1 + o(1))n log n + O(1)
)
.
We now set A = tj , B = (e2tj−2 + · · · + ej), C = ed+1td−j
∏n
k×n
k=1
k, and we
apply the ABC conjecture to equation (5). We note that our A, B, C are
not necessarily coprime, but their greatest common divisor is O(1). Indeed,
let D1 = gcd(t, ej). Clearly, D1 ≤ |ej |, and
gcd(A,B) = gcd(tj , e2tj−2 + · · ·+ ej) |
(
gcd(t, e2tj−2 + · · ·+ ej)
)j
| Dd1 .
Thus, we may apply the ABC-conjecture and get that
|t|j 
|t||B| ∏
p≤n
p
1+ε  |t|(j−1)(1+ε) · 4(1+ε)n.
Choosing ε = 1/j, we get that (j − 1)(1 + ε) = j − 1/j, and that the
inequality
|t|1/j  4(1+ε)n < 42n
holds. This last inequality leads to
(7) |t| ≤ exp (2jn log 4 + O(1)) ≤ exp(2dn log 4 + O(1)).
Comparing (6) and (7), we get
2dn log 4− 1
2d
(1 + o(1))n log n = O(1),
360 Omar Kihel, Florian Luca
which certainly implies that n is bounded. ut
Dabrowski (see [6]), showed that if P (x) = x2−A, where A is an integer
which is not a perfect square, then equation (2) has only finitely many
solutions. We consider the diophantine equation
(8) x2 −A =
n∏
k×n
k=1
k,
and prove the following result.
Theorem 3. If the integer A is not a perfect square, and n and x are
positive integers satisfying equation (8), then either
n ≤ p or n = 2p,
where p is the smallest prime such that (Ap ) = −1. Here, (
•
p) stands for the
Legendre symbol. In particular, equation (8) has only finitely many positive
integer solutions.
Before proving Theorem 3, we need the following Lemma.
Lemma 4. Every prime p ≤ n divides
∏n
k×n
k=1
k, except when n = p, 2p,
cases in which p is the only prime ≤ n which does not divide
∏n
k×n
k=1
k.
Proof. Suppose that p ≤ n and that n 6= p, 2p. If p ∈ (n/2, n), then p does
not divide n, therefore it divides
∏n
k×n
k=1
k. We now assume that p < n2 .
Hence, there exists a positive integer i such that
n
2
≤ 2ip < n.
(i) If n2 < 2
ip < n, then 2ip does not divide n, and so it divides∏n
k×n
k=1
k.
(ii) If n2 = 2
ip, then 3 · 2i−1p < n, and does not divide n, therefore it
divides
∏n
k×n
k=1
k.
ut
Proof of Theorem 3. Since A is not a perfect square, there exists a prime p
such that (Ap ) = −1. Then p does not divide
∏n
k×n
k=1
k. Lemma 4 now shows
that either n ≤ p or n = 2p. ut
In the general case in which A is any integer in equation (8), we have the
conditional result given in the following theorem.
Theorem 5. If the weak form of Hall’s conjecture is true, then equation
(8) has only finitely many solutions.
Brocard-Ramanujan 361
The weak form of Hall’s conjecture is a special case of the ABC-conjecture
and asserts that for every ε > 0, there exists a constant C(ε) depending only
on ε > 0, such that if x, y, and k are nonzero integers satisfying x2 = y3+k,
then
max
(
|x2|, |y3|
)
≤ C(ε)|k|6+ε.
Proof of Theorem 5. We assume that n ≥ 3. Let d and y be the two integers
with d cubefree such that
∏n
k×n
k=1
k = dy3. Then, from Chebyshev’s bound
we obtain that
d ≤
 ∏
p < n
p prime
p

2
< 42(n−1).
Equation (8) gives
dy3 + A = x2,
so
Y 3 + d2A = X2,
where X = dx and Y = dy. Taking ε = 1 in the weak form of Hall’s
conjecture we get that
d2
n∏
k×n
k=1
k = d3y3 = Y 3 ≤ C(1)|d2A|7.
Since
(n− 1)!1/2 ≤
n∏
k×n
k=1
k,
it follows, from Stirling’s formula, that
(4(n− 1)(n−1)e−(n−1))
1
2 ≤ (n− 1)!
1
2 ≤
n∏
k×n
k=1
k.
Hence,
(4(n− 1)(n−1)e−(n−1))
1
2 ≤
n∏
k×n
k=1
k  |d2|6|A|7  424(n−1)|A|7.
Thus, (
n− 1
448
)n−1
2
 |A|7.
This proves that n is bounded. ut
362 Omar Kihel, Florian Luca
We considered equation (8) with A = 1, namely
(9)
n∏
k×n
k=1
k + 1 = y2,
and did some computations. Except from the obvious solutions n = 4 and
n = 5, we didn’t find any other solution for equation (9) up to n = 105.
Finally, we look at yet another variant of the Brocard-Ramanujan dio-
phantine equation, namely
(10) 1 +
∏
k≤n
gcd(k,n)=1
k = y2.
Theorem 6. Suppose that there exist integers n > 4 and y satisfying equa-
tion (10). Then either n is equal to pα or 2pα for some prime p and positive
integer α, or all odd primes dividing n are ±1 (mod 8).
Proof. We know from Gauss generalization to Wilson’s Theorem (see [17])
that
∏
k≤n
gcd(k,n)=1
k =

−1 (mod n), if n = 4, pα, 2pα,
1 (mod n), otherwise.
Thus, if n 6= 4, pα, or 2pα, then Π
k≤n
gcd(k,n)=1
k + 1 ≡ 2 (mod n). This implies
that y2 ≡ 2 (mod n). In particular, y2 ≡ 2 (mod q) holds for all odd prime
factors q of n. Hence, (2q ) = 1, leading to the conclusion that q ≡ ±1
(mod 8). ut
We remark that results of Landau (see pages 668–669 in [10]), together with
the Prime Number Theorem, imply that if x is any positive real number,
then the number of positive integers n ≤ x such that n = pα, 2pα, or n
is free of prime factors ≡ ±3 (mod 8) is  x/
√
log x. In particular, the
set of n for which equation (10) can have a positive integer solution y is
of asymptotic density zero, which is an analogue of the result of Berend
and Osgood from [1] for the particular polynomial P (X) = X2− 1 and our
variant of the Brocard-Ramanujan equation.
Acknowledgements. We thank the referee for suggestions which im-
proved the quality of the paper. The first author was supported in part by
a grant from NSERC. Research of F. L. was supported in part by grants
PAPIIT IN104505, SEP-CONACyT 46755 and a Guggenheim Fellowship.
Brocard-Ramanujan 363
References
[1] D. Berend, C. Osgood, On the equation P (x) = n! and a question of Erdős. J. Number
Theory 42 (1992), no. 2, 189–193.
[2] D. Berend, J.E. Harmse, On polynomial-factorial diophantine equations. Trans. Amer.
Math. Soc. 358 (2005), no 4, 1741–1779.
[3] B.C. Berndt, W.F. Galway, On the Brocard-Ramanujan Diophantine equation n! + 1 =
m2. The Ramanujan Journal 4 (2000), 41–42.
[4] H. Brocard, Question 166. Nouv. Corresp. Math. 2 (1876), 287.
[5] H. Brocard, Question 1532. Nouv. Ann. Math. 4 (1885), 291.
[6] A. Dabrowski, On the diophantine equation n! + A = y2. Nieuw Arch. Wisk. 14 (1996),
321–324.
[7] P. Erdős, R. Obláth, Über diophantische Gleichungen der Form n! = xp±yp und n!±m! =
xp. Acta Szeged 8 (1937), 241–255.
[8] A. Gérardin, Contribution à l’étude de l’équation 1 · 2 · 3 · 4 · · · z + 1 = y2. Nouv. Ann.
Math. 6 (4) (1906), 222–226.
[9] H. Gupta, On a Brocard-Ramanujan problem. Math. Student 3 (1935), 71.
[10] E. Landau, Handbuch der Lehre von der verteilung der Primzahlen, 3rd Edition. Chelsea
Publ. Co., 1974.
[11] F. Luca, The Diophantine equation P (x) = n! and a result of M. Overholt. Glas. Mat. Ser.
III 37 (57) no. 2 (2002), 269–273.
[12] H.L. Montogomery, R.C. Vaughan, The large sieve. Mathematika 20 (1973), 119–134.
[13] M. Overholt, The diophantine equation n! + 1 = m2. Bull. London Math. Soc. 25 (1993),
104.
[14] R. M. Pollack, H. N. Shapiro, The next to last case of a factorial diophantine equation.
Comm. Pure Appl. Math. 26 (1973), 313–325.
[15] S. Ramanujan, Question 469. J. Indian Math. Soc. 5 (1913), 59.
[16] S. Ramanujan, Collected papers. New York, 1962.
[17] S. Wolfram, Math World. http://mathworld.wolfram.com/WilsonTheorem.html
Omar Kihel
Department of Mathematics
Brock University
500 Glenridge Avenue
St. Catharines, Ontario Canada L2S 3A1 00000
E-mail : okihel@brocku.ca
Florian Luca
Mathematical Institute UNAM,
Campus Morelia Apartado,
Postal 27-3 (Xangari),
C.P. 58089 Morelia, Michoacán, Mexico
E-mail : fluca@matmor.unam.mx


Variants of the Brocard-Ramanujan equation

Marc Deléglise

Jean-Louis Nicolas

Paul Zimmermann

Landau’s function for one million billions

Florent Jouve

Emmanuel Kowalski

David Zywina

An explicit integral polynomial whose splitting field has Galois group $W(\mathbf{E}_8)$

Marcin Mazur

Stephen V. Ullom

Unit indices and cohomology for biquadratic extensions of imaginary quadratic fields

The geometry of the third moment of exponential sums

Not a member yet

Logarithmic frequency in morphic sequences

Plongements ${\ell }$ -adiques et ${\ell }$ -nombres de Weil

On Elkies subgroups of $\ell$ -torsion points in elliptic curves defined over a finite field