Nagell Equation
Nagell Equation
Nagell Equation
Equations
N. Saradha and Anitha Srinivasan
1 Prelude
For any positive integer > 1, let P () and () denote the greatest prime
factor and the number of distinct prime factors of , respectively. Let P (1) =
1 and (1) = 0. Throughout the paper D1 , D2 and denote positive integers
such that gcd(D1 , D2 ) = 1. We are interested in the equation
D1 x2 + D2 = y n (1.1)
in positive integers x, y and n > 1. This equation has a rich history and it
has attracted the attention of several great mathematicians. Several papers
have been written on this topic, specially for particular values of D1 , D2 and
. Detailed surveys on this equation can be found in papers such as [Sh] and
[BMS].
x2 + D = k n . (2.1)
The following result of Siegel [Si] shows that the number of solutions (x, n)
of (2.1) is finite.
1
If f (x) Z[X] has at least two distinct roots then P (f (x)) as
| x | .
The famous Ramanujan-Nagell equation is a particular case of (2.1) when
D = 7, = 1 and k = 2. In 1913, Ramanujan [Ra] conjectured that all the
solutions (x, n) of the equation
x2 + 7 = 2n
are given by
(x, n) {(1, 3), (3, 4), (5, 5), (11, 7), (181, 15)}. (2.2)
Ljunggren posed the same problem in 1943 and Nagell solved it in 1948. His
proof in English was published in 1961, see [Na1]. Subsequently, alternative
proofs have been given by various authors. For instance Chowla, Lewis and
Skolem [CLS] used Skolems p-adic method in their proof.
In 1960, Apery [Ap] considered (2.1) with = 4 and k = 2. He showed
that
x2 + D = 2n+2 , D 6= 7 (2.3)
has at most two solutions. In particular,
(x, n) {(3, 5), (45, 11)} if D = 23 and
(2.4)
(x, n) {(1, m), (2m 1, 2m 1)} if D = 2m 1 with m 4.
Thus there are infinitely many D for which (2.3) has precisely two solu-
tions. In 1980, Beukers (see [Beu1] and [Beu2]) showed that apart from the
values of D given by (2.4), equation (2.3) has at most one solution, thereby
confirming a conjecture of Browkin and Schinzel. Apery also considered (2.1)
with = 1, k = p, an odd prime, i.e.,
x2 + D = pn , p - D. (2.5)
He showed that (2.5) has at most two solutions. Further Beukers proved
that (2.5) has at most one solution except when (p, D) = (3, 2) or (p, D) =
(4t2 + 1, 3t2 + 1) for a positive integer t. In these exceptional cases there are
exactly two solutions. Beukers used hyper-geometric methods for proving
these results.
In a series of papers, Le (see [Le1] to [Le5]) considered the following form
of equation (1.1) with y = p, a prime, namely
D1 x2 + D2 = 2 pn with {1, 2, 2}. (2.6)
2
He showed that (2.6) has at most two solutions except in the following four
cases :
x2 + 7 = 4 2n (x, n) as in (2.2),
3x2 + 5 = 4 2n (x, n) {1, 1), (3, 3), (13, 7)},
(2.7)
x2 + 11 = 4 3n (x, n) {(1, 1), (5, 2), (31, 5)},
x2 + 19 = 4 5n (x, n) {(1, 1), (9, 2), (559, 7)}.
We note here that the solution (x, n) = (11, 5) for the equation 2x2 + 1 = 3n
in (2.8) was found by Leu and Li [LL]. The last equation and its solutions
were added by Mollin [Mo2]. The three infinite families are
and
I = {(Fp2 , Lp+ , Fp ) | p 2, {1}, = 2},
where
F0 = 0, F1 = 1, Fk = Fk1 + Fk2 for k 2
and
L0 = 2, L1 = 1, Lk = Lk1 + Lk2 for k 2.
3
The two solutions in each case are given by
{(1, r), (2pr 1, 2r)} for G,
{(s, r), ( 3D1 s2 3s, 3r)} for H,
2
(x, n) 9F2p+1 F2p5 6
{(1, 1), ( 10
, 5)} for I if = 1,
{(1, 1), ( 9F2p1 F2p7 +6 , 5)} for I if = 1.
10
The results of Le, Bugeaud and Shorey mentioned above are based on the
work of Bilu, Hanrot and Voutier [BHV] on primitive divisors of Lucas and
Lehmer sequences. The relevance of these recurrence sequences was noted
by Beukers back in 1980, when he observed that distinct solutions of (2.5)
in positive integers (x, n) correspond to integers l 2 for which
l l
= 1 where Q( D).
Let D1 be odd and gcd(D1 D2 , k) = 1. Consider the equation
D1 x2 + D2 = 2 k n with {1, 2, 2}. (2.9)
In [BuS], some equations of the form (2.9) with k composite were solved. For
instance, it was shown that
The following result is obtained from the works of Le, Bugeaud and Shorey.
The solutions of (2.9) can be put into at most 2(k)1 classes. Suppose
that (2.9) is not any of the equations occurring in (2.7),(2.8) and (2.10).
Then in each class there is at most one solution except when (D1 , D2 , k)
belongs to G or H or I, in which case the equation has two solutions in one
class and at most one solution in any other class.
Bugeaud and Shorey applied their result to solve (2.9) for several values of
D1 , D2 and n a prime. Apart from the Ramanujan-Nagell equation, there are
values of D, , k for which equation (2.1) has many solutions. For example,
Stiller [St] showed that the equation
x2 + 119 = 15 2n
4
has six solutions given by
(x, n) {(1, 3), (11, 4), (19, 5), (29, 6), (61, 8), (701, 15)}.
x2 + 3 = 7 97n , n > 1
x2 + D = y n , (3.1)
where and D are fixed and a solution is given by a triple (x, y, n) of positive
integers. From Theorem 10.6 of [ST] it follows that the number of solutions
of (3.1) is finite. The following results were proved for = 1. In 1850,
Lebesgue [Leb] showed that equation (3.1) with D = 1 has no solution. In
1928, Nagell [Na2] solved the equation with D = 3, 5. Cohn [Co] solved
(3.1) for 77 values of D 100. For D = 74, 86 the equation was solved by
Mignotte and de Weger [MW] using linear forms in logarithms and Bennett
and Skinner [BeS] solved it for D = 55, 95. For the remaining 19 values
of D 100 equation (3.1) was solved by Bugeaud, Mignotte and Siksek
5
[BMS]. The proofs of their results depend heavily on the theory of Galois
representation of modular forms.
In the above results, D is fixed, (in fact D 100). Let the prime factor-
ization of D be written as
D = p1 1 . . . pr r , (3.2)
x2 + D = y n . (3.3)
Proposition 3.1 Let (3.2) and (3.3) hold with n > 2 and D 3(mod 4).
Suppose that each i is odd and each pi 3 (mod 4). Further assume that y
is odd if D 7(mod 8). Then n is odd and every prime divisor of n divides
3h0 . Also if gcd(n, h0 ) = 1 and 3 - h0 , then there exists an integer a such
that one of the following holds.
(a) D/27 = a2 + 8.
(b) D/32h+1 = a2 3h1 and h is even.
(c) D/32h+1 = a2 8 3h1 .
6
D for which equation (3.3) can be completely solved. As a consequence of
Proposition 3.1, we are able to show that the equation
By a result of Darmon and Granville [DG], equation (3.5) with ` > 6 has
only finitely many solutions. Arif & Murifah [AM] and Luca [Lu] solved (3.5)
with p = 3 without any gcd condition. They found two families of solutions
viz.,
(x, y, `, n) {(10 33t , 7 33t , 5 + 6t, 3), (46 33t , 13 32t , 4 + 6t, 3)}.
Bugeaud [Bu] proved that (3.5) with p = 7 and y = 2 has exactly six so-
lutions. Bennett and Skinner [BeS] have also made partial contributions on
(3.5). In [SA1], we showed the following result on (3.5).
Proposition 3.2 Suppose (3.5) holds with p {11, 19, 43, 67, 163} and ` is
odd. Then ` = 3 5 for some non-negative integers and . In particular if
` = 1, then the solutions are given by (x, y, p, n) S where S is as follows.
S = {(4, 3, 11, 3), (58, 15, 11, 3), (18, 7, 19, 3), (22434, 55, 19, 5), (110, 23, 67, 3)}.
7
hold with n > 2 and D 3(mod 4). Also let y be odd if D 7(mod 8).
Suppose that
D = Ds Dt2 E 2
where Ds and E are square free with gcd(E, Ds ) = 1 and Ds > 3. Assume
that
Ds Dt2 = p1 1 pr r
where each i is odd and each pi 3(mod 4). Further assume that each prime
q | E satisfies
Ds
q 6= 3, q = 2 3 + (4.2)
q
and every divisor e > 1 of E satisfies
for any prime p > 3 dividing Dt . Then every prime divisor of n divides 3h0 .
As a consequence of Theorem 4.1 we obtain the following result.
8
with
E {7, 31, 107}
has no solution. For every prime q|E for E in the above set, we observe that
3 11 19
= 1.
q
31119
Further q q
is of the form 2 3 for non-negative integers and .
Moreover (4.3) is satisfied. Hence by Theorem 4.1 every prime divisor of n
divides 3h0 = 12. Thus we may suppose that n = 3. By Theorem 4.2 part 2,
we have
112 193 E 2 = a2 8
or
112 193 = a2 8g E
since E is a prime. These equalities are excluded using congruence argument
modulo the primes 3,11 and 19.
Theorem 4.3 Suppose equation (3.5) holds with p {11, 19, 43, 67, 163}
and ` is odd. Then all the solutions of (3.5) are given in Proposition 3.2.
5 Lemmas
The following is [SA1, Lemma 4].
9
Proof. We refer to Mollin [Mo1] for the formula of h(4D) used in the proof
below. As in [SA1, Lemma 5], we see that
where
( D
!
Y p
s
)
= 1 .
p
p|Dt E
p6=2
Let p2q 1(mod f ) for some positive integer f. Then there exists an integer
h with 0 h < f such that
(
1(mod f ) if p2q 1(mod f )
pq h2 + 2a0 h + g
1(mod f ) if p2q 1(mod f ).
10
Proof. Suppose (5.4) holds. Then
a a0 (mod pq ).
which gives
0
pq h 2 2a0 h0 + g = p`q .
Since ` q 0 (mod 2q), we get for some h with 0 h < f,
(
1(mod f ) if p2q 1 (mod f )
pq h2 2a0 h + g
1(mod f ) if p2q 1(mod f )
6 Proofs of Theorems
p | Dt . (6.1)
Hence p|Ds . From Lemma 5.3 we see that b is odd and for any prime q,
Dt
ordq ( ) = ordq (b) and ordq (E) ordq (b).
p
Therefore 2pg Dt E = 2pg pbe for some divisor e of E. Thus
p1
pg p1 p p3 2 Ds p1
p1 Ds 2
2 e = a a b + . . . + (1) 2 b .
3 p p
Considering the above equality mod p and using (4.3), we see that the left
hand side is equal to 1. Thus g = 0, e = 1 and Dt E = pb. Now reducing the
11
equality mod 2 we conclude that a is an even integer with gcd(a, Ds ) = 1
such that p1
p1 p p3 D p1 D 2
1=a a + . . . + (1) 2 .
3 p3 pp
Hence p1
p1 p1 p1
(1) 2 Ds 2 (1) 2 D 2 p (mod 4).
As each pi 3(mod 4), we have
Ds 1(mod 4).
3a2 b2 Ds = 8g e (6.3)
and
b = Dt e0 ,
where E = ee0 . Therefore from (6.2),
8g e = 3a2 D/e2 ,
that is
D = e2 (3a2 8g e).
Suppose 3|D. By assumption 3 - E. If 3||D, then 3|Ds but 3 - Dt . This
contradicts (6.2). Hence ord3 (D) 3. Let D = 32h+1 Qs Q2t E 2 where Ds =
3Qs , Dt = 3h Qt , h 1 and 3 - Qs Qt . Then (6.2) gives
a2 b2 Qs = 8g 3 e and b = Qt e0 3 , (6.5)
12
where E = ee0 and , 0 with + = h 1. Moreover = 0 as 3 - a.
Combining the two equations in (6.5) we get
For h > 1 observe that parts 3(a) and 3(b) of Theorem 4.2 correspond to
= 0 and = 0 respectively.
First we consider
D/27 = a2 8g .
Reducing the above equation modulo 3 and modulo 8 and observing D/27
0(mod 3) and 1 or 5 (mod 8), we obtain
D/27 = a2 + 8. (6.8)
Next consider
D/32h+1 = a2 8g 3h1 . (6.9)
Let g = 0. Since each prime factor of D is congruent to 3(mod 4) and
occurs with an odd exponent, we have
13
This concludes the proof of part 3 of Proposition 3.1.
Proof of Theorem 4.3. Let p {11, 19, 43, 67, 163}. By Proposition 3.2
we have ` = 3 5 > 5. By Proposition 3.1, there exists an integer a such
that
3a2 1 = 11` or 3a2 + 8 = 11`
or
3a2 8 = p` with p {19, 43, 67, 163}.
Consider
3a2 1 = 11` or 3a2 + 8 = 11` . (6.11)
Reducing ` modulo 3, we obtain elliptic equations of the form
Y 2 = X3 + k (6.12)
3a2 8 = 43`
We have
3a2 8 = p` . (6.13)
We provide here a simple congruence argument based on Lemma 5.4 to rule
out these cases.
Let p = 19. Suppose 3 | `. We apply Lemma 5.4 with q = 3, = 3, =
8 and f = 27. We find that 196 1(mod 27) and a0 = 1466. Hence
g = 940. We check that
14
Suppose 5 | `. Then let q = 5, = 3, = 8 and f = 11. We have
1910 1(mod 11) and a0 = 2278654 and g = 6290860. We see that
3 195 h2 + 6 2278654h + 6290860 6 1(mod 11) for 0 h < 11.
Hence by Lemma 5.4,
3a2 8 6= 19` for any ` with 5 | `. (6.15)
We combine (6.14) and (6.15) to get the assertion of the theorem for p = 19.
For p = 67, 163, we give the necessary parameters for the application of
Lemma 5.4.
p = 67; q = 3, a0 = 203953, g = 414913, f = 7, if 3 | l.
q = 5, a0 = 620270116, g = 854887480, f = 25 if 5 | l.
15
correct as they relied upon an incomplete result which we have corrected in
Proposition 3.1 We list below a new set of values of D = Ds Dt2 = p1 p2 p3
where , and are odd integers. For these values of D equation (4.1) has
no solution by applying the three criteria in Proposition 3.1. and congruence
arguments modulo 8 or some suitable prime.
Let U1 be the set of values of D with (p1 , ) = (3, 3) and
(p2 , p3 ) {(7, 19), (7, 43), (7, 283), (11, 19), (11, 47), (11, 59), (11, 67),
(11, 71), (11, 83), (11, 107), (11, 131), (11, 179), (11, 227), (11, 251), (19, 31),
(19, 59), (19, 67), (19, 107), (19, 139), (19, 163), (31, 67), (43, 67)}.
Let U2 be the set of values of D with p1 = 3, > 3 and
(p2 , p3 ) {(7, 23), (7, 47), (7, 167), (7, 383), (23, 31).
(p1 , p2 , p3 ) {(3, 7, 59), (3, 7, 227), (3, 7, 251), (3, 7, 467), (3, 11, 31), (3, 11, 199),
(7, 11, 19), (7, 11, 23), (7, 11, 71), (7, 11, 107), (7, 19, 31), (7, 23, 43), (11, 23, 31), (11, 19, 43)}.
References
[Ap] R. Apery, Sur ue equation diophantienne, C.R. Acad. Sci. Paris Ser.
A 251 (1960), 12631264 and 14511452.
[AM] S.A. Arif and F.S. Abu Muriefah, The Diophantine equation x2 +3m =
y n , Int. J. Math. Sci 21 (1998), no.3, 619620.
16
[BHV] Y. Bilu, G. Hanrot and P. Voutier (with an appendix by M.
Mignotte), Existence of primitive divisors of Lucas and Lehmer num-
bers, J. reine angew. Math. 539 (2001), 75122.
[CLS] S. Chowla, D.J. Lewis and Th. Skolem, The Diophantine equation
2n+2 7 = x2 and related problems, Proc. Amer. Math. Soc. 10 (1959),
250-257.
17
[Le5] Maohua Le, The Diophantine equation x2 + 2m = y n , Chinese Sci.
Bull 42 (1997), 15151517.
[LL] Ming-Guang Leu and Guan-Wei Li, The Diophantine equation 2x2 +
1 = 3n , Proc. Amer. Math. Soc. 131 (2003), no.12, 3643-3645.
[Mo1] R.A. Mollin, Quadratics, CRC Press, New York, 1996, 387p.
[Ra] S. Ramanujan, Question 446, J. Indian Math. Soc.5 (1913), 120, Col-
lected papers, Cambridge University Press (1927), 327.
18
[Si] C. L. Siegel, Approximation algebraischer Zahlen, Math. Zeit. 10
(1921), 173-213.
19