Diophantine Equation

Aayush Kumar
October 2024

Contents
§1 Prerequisites 2

§2 Introduction 2

§3 Factoring equations 2

§4 Simon’s Favorite Factorization Trick 2

§5 Modular Contradiction 4
§5.1 Some important relations: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

§6 Infinite Descent 5

§7 Vieta Jumping 7

§8 Pell’s Equations 9

§9 Brahmagupta’s √ idea of solving Pell’s Equation 11

§9.1 Representing d as a continued fraction . . . . . . . . . . . . . . . . . . . . . . . . . 11

§10 Recursive Solutions of Pell’s Equation 13

§11 Mixed Problems 13

1
Diophantine Equation Aayush Kumar

§1 Prerequisites
Nothing fancy as such, the reader is assumed to be comfortable with Modular Arithmetic. I would
highly encourage the reader to give the problems an honest attempt before looking at the solutions.

§2 Introduction
We will start with solving equations using factorization then we will move onto Modular Con-
tradiction and then we’ll end this with discussing Pell’s Equation.

§3 Factoring equations
We’ll start this with an easy example just to show how to get started on the basic questions, most
of you would have done this type anyway.

Q: Find all (x, y) ∈ Z such that

x2 − y 2 = 24

Solution: On factoring, we get (x + y)(x − y) = 24. So, we have two integers multiplying to give
24, so they can be ± (1, 24), ± (2, 12), ± (3, 8), ± (4, 6). Let us suppose that we get 24 by multiplying
(a, b), then without loss of generality, we have x + y = a and x − y = b. Adding both equations, we
get x = a+b2 . So, a+b must be even, so we are left with only ± (2, 12) and ± (4, 6) cases. We solve
these cases to get (x, y) = (7, 5) , (7, −5) , (−7, 5) , (−7, −5) , (5, 1) , (5, −1) , (−5, 1) , (−5, −1).
To get all the solutions, note that if (a,b) multiplies to give 24 then so does (b,a). ■

§4 Simon’s Favorite Factorization Trick

This is used to factorize expressions involving xy, ax, ay and ab terms. The key idea is to keep the
identity
(x + b) (y + a) = ax + by + xy + ab
in mind when solving equations involving terms ax, by, and xy. Sometimes, the ab term might be
missing from either one or both sides of the equation, so we will need to either add or subtract the
missing term to create the above identity. Let us see this using an introductory example, then we
will see a good application of this which has appeared on contest.

2
Diophantine Equation Aayush Kumar

Q: Find all positive integers m, n satisfying

m2 + 3m2 n2 = 30n2 + 517

Solution: Substitute m2 = x and n2 = y to get x+3xy = 30y +517 which gives x+3xy −30y =
517. Take 3y common to get 3y (x − 10) + x = 517. Now see that this can be easily factorized
into (x − 10) (3y + 1) = 507 after adding −10 to both side. Now we need to find two integers that
multiply to give 507 and then do some casework to get (x, y) and then ultimately get (m, n). So
the possible pairs of integer which can be multiplied to get 507 are (1, 507), (3, 169) and (13, 39)
but we don’t need to solve these many cases since observe that one of the integer is of the form
(3y + 1) and y ̸= 1 so the only possible pair of integers is (39, 13) which gives (x, y) to be (49, 4),
so (m, n) = (7, 2). ■

Now let’s see it’s application which appeared on a contest.

British Mathematical Olympiad Round 3 2005

Q: If n is positive and there are exactly 2005 ordered pairs (x, y) of positive integers satis-
fying:
1 1 1
+ =
x y n
then prove that n is a perfect square.

Solution: Simplify the equation to get xy − nx − ny = 0. We use SF F T to write it as

(x − n) (y − n) = n2 . Now again we need two
 integers
2
 which multiplies to give n , which are basi-
2
cally just factors of n2 . So (x − n, y − n) = d, nd is a solution to the equation which means the
number of solution to the equation is equal to the number of divisors of n2 .

Suppose, n = pα α2 αn 2 2α1 2α2 2αn

1 .p2 ...pn , then, n = p1 .p2 ...pn .
1

Therefore number of factors of n2 is

(2α1 + 1) (2α2 + 1) ... (2αn + 1)

which is equal to 2005. So,

(2α1 + 1) . (2α2 + 1) ... (2αn + 1) = 2005

and,
2005 = 1 × 2005
= 5 × 401
Hence, we find that either n = 1 and α1 = 1002 or n = 2 and (α1 , α2 ) = (2, 200). So, n is either =
p1002
1 or n = p21 .p200
2 and clearly in both cases n is a perfect square. ■

3
Diophantine Equation Aayush Kumar

§5 Modular Contradiction
This is one of the most important techniques you will learn to solve equations involving exponents
on a math contest. This is where your experience with Modular Arithmetic comes through. There’s
not much theory except for some relations which are stated below. Their proof is left as an exercise
for the reader.

§5.1 Some important relations:

• a2 ≡ {0, 1} (mod 3)
• a2 ≡ {0, 1} (mod 4)

• a2 ≡ {0, ±1} (mod 5)

2
• (odd) ≡ {1} (mod 8)
• a3 ≡ {0, ±1} (mod 7)
• a3 ≡ {0, ±1} (mod 9)

For their proof and creating other such relations I would suggest you to keep Fermat’s Little
Theorem and Euler’s Theorem in mind.
Let’s see some of it’s application now.

Q: Prove that every Pythagorean triple contains a multiple of 5.

Solution: Any Pythagorean triple (x, y, z) are integers satisfying the equation

x2 + y 2 = z 2

The only possible values of the equation (mod 5) are {0, 0, 0}, {0, 1, 1}, {0, −1, −1}, {1, 1, 1},
{−1, −1, −1} (why?) and their permutations. Clearly, last two cases don’t hold and in any
other cases at least one of the numbers is divisible by 5. ■

Regional Mathematical Olympiad 2023

Q: Let N be the set of all positive integers and let S = {(a, b, c, d) ∈ N4 : a2 + b2 + c2 =

d2 }. Find the largest positive integer m such that m divides abcd ∀ (a, b, c, d) ∈ S.

Solution: By relation (ii)

d2 ≡ {0, 1} (mod 4)
So, if d2 ≡ 1 (mod 4) then at least two of (a2 , b2 , c2 ) has to be 0 (mod 4) so, at least two of
(a, b, c) has to be even ⇒ 4 | abcd.
Now, if 4|d2 then clearly 4 divides each of {a, b, c, d} ⇒ 4|abcd.
Now, using relation (i)
d2 ≡ {0, 1} (mod 3)

4
Diophantine Equation Aayush Kumar

and in both cases it can be checked easily that 3|abcd.

So, clearly 12|abcd ⇒ m = 12k and m|abcd ∀ {a, b, c, d} ∈ S but notice that (1, 2, 2, 3) ∈ S.
So, k = 1 and m = 12. ■

USAMTS

Q: Find all (x, m, n) ∈ N satisfying:

3m + 3n + 1 = x2

Solution: Clearly x2 is odd so it is 1 (mod 8). Also notice that

3odd ≡ 3 (mod 8)

and
3even ≡ 1 (mod 8)
m n 2
So, 3 + 3 + 1 ≡ {3, 5, 7} (mod 8) whereas x ≡ 1 (mod 8).
Hence no solution is possible. Also note that there would’ve have been no solution even if x
was allowed to be any integer. ■

Balkan Mathematical Olympiad

Q: Prove that the equation

x5 − y 2 = 4
has no solution in integers.

Solution: Observe that x10 ≡ 0, 1 (mod 11) using Fermat’s Little Theorem. So we
have, x5 ≡ 0, 1, −1 (mod 11). So, we have x5 − 4 ≡ 6, 7, 8 (mod 11). But, y 2 is always
{0, 1, 3, 4, 5, 9} (mod 11). So, we have no solution to the given equation over integers. ■

Exercise

Q: Find all pairs of integers (x, y) that satisfy the equation

x2 − y! = 2001

§6 Infinite Descent
Infinite Descent is a classic method, famously used by F ermat, where we assume a solution
exist and then keep producing smaller and smaller ones which leads to contradiction, because
the positive integers can’t descend forever. Let’s see this technique in action using an easy
problem first and then we’ll do a few problems that has appeared on contests.

5
Diophantine Equation Aayush Kumar

Cambridge University STEP 1 2010

Q: Show that the only solution to the equation

a3 + 3b3 = 9c3

over non-negative integers is (0,0,0).

Solution: Clearly (0,0,0) works, now all we need to proof is there exist no solution over
positive integers and for that we’ll take the help of infinite descent. Clearly, 3|a3 which
implies that 3|a. So, a = 3k1 . Then

27k13 + 3b3 = 9c3

Dividing by 3 gives us
b3 + 9k13 = 3c3
Now clearly, 3|b as well so b = 3k2 which gives us

27k23 + 9k13 = 3c3

which implies c = 3k3 since 9|c3 . Then we get

9k13 + 27k23 = 81k33

which upon division by 9 reduces to

k13 + 3k23 = 9k33

which is similar to our original equation. So, if (a, b, c) satisfies the equation so does

(k1 , k2 , k3 )
where k1 = a3 , k2 = 3b , k3 = 3c . So we started with (a, b, c) and got to a3 , 3b , 3c and this will
continue forever and we’ll keep getting a chain of solutions
   
a b c a b c
(a, b, c) → , , → , , → ....
3 3 3 9 9 9
As we can see this will clearly descend forever but positive integers can’t, so it’s a contradiction
which implies we have no solution over positive integers. ■

Hungarian MO 2000

Q: Find all positive primes p for which there exist positive integers x, y and n such
that
p n = x3 + y 3

Solution: It could be easily checked that for p = 2 and 3 one can easily find n, x and y which
satisfies the given equation using casework and that is left for the reader to do.
Claim: There exist no such integers ∀ p ≥ 5.
Proof: For the sake of contradiction, let there exist a p ≥ 5 that satisfies the given equation,
then observe that at least one of x and y has to be greater than 1 (WLOG, say x). Also,

6
Diophantine Equation Aayush Kumar

pn = x3 + y 3 can be written as pn = (x + y)(x2 − xy + y 2 ). Observe that since x > 1, x + y ≥ 3

and x2 − xy + y 2 = (x − y)2 + xy ≥ 2 therefore, since both factors of pn > 1, p|x + y and
p|x2 −xy+y 2 (why?). Now since p|x+y, p|(x+y)2 which implies that p|(x+y)2 −(x2 −xy+y 2 )
⇒ p|2xy ⇒ p|xy, since p ≥ 5. But p also divides x + y ⇒ p|x and p|y. Now if we divide our
equation by p3 , we get
 3  3
n−3 x y
p = +
p p
Now since p|x and p|y this equation can be written as

pn−3 = k13 + k23

and this equation is identical to our original equation which means if n is a solution then so
is n − 3 so, we’ll again get a chain of solution

(n, x, y) → (n − 3, k1 , k2 ) → (n − 6, z1 , z2 ) → ...

Clearly this chain of solution also descends forever but again positive integers can’t, so it’s a
contradiction again. Hence, no prime ≥ 5 is possible.■

Exercise
Q:(PUTNAM,1973): Let a1 , a2 , ....a2n+1 be a set of integers such that, if any one of them
is removed, the remaining ones can be divided into two sets of n integers having equal sums.
Then, prove that a1 = a2 ..... = a2n+1 .

Q: (Fermat’s Last Theorem for n=4) Prove that there exists no integer solution for the
equation
a4 + b4 = c4

§7 Vieta Jumping
Vieta Jumping is a particular kind of descent technique. Let’s see how we can apply this on
contest problems. This is taught using a classic IMO problem from 1988 in almost all the
Maths Olympiads Classes even today in 2025. So, we’ll do the same as well.

IMO 1988 P6

Q: Let a and b be positive integers such that ab + 1 divides a2 + b2 . Show that

a2 + b2
ab + 1
is the square of an integer.

2 2
Solution: Let k = aab+1 +b
. Clearly, k is a positive integer(why?) but the problem asks us
to prove that it’s not just any integer, but it’s actually square of an integer. For the sake of

7
Diophantine Equation Aayush Kumar

contradiction, suppose that k is not a square number.Observe that if a = b, k = 1 which is

a perfect square which actually contradicts our assumption of k not being a perfect square,
so clearly a ̸= b. Now, assume without loss of generality, a > b. Now that our setup of
approaching the problem is almost done, we need to think of ways to apply our descent
method. To apply the descent method, we need an equation and then we can play around
with it’s solution. A very obvious step to get an equation from our problem is to actually
rearrange it and get a quadratic whose one of the roots is a. We get
a2 − (kb)a + b2 − k = 0
Define f (t) = t2 − kbt + b2 − k. Now, clearly f has two roots, one of them being a and the
other say x. Then,
x 2 + b2
=k
xb + 1
so we went from (a.b) satisfying our problem to (x, b) satisfying the exact same expression.
To perform descent, we now only need to show that x is a positive integer and x < a. The
first part is pretty obvious as k and b are positive integers and k is not a perfect square (due
to our assumption). To prove that x < a, notice that by Vieta relation, we have x = kb − a
2
and x = b a−k and we would want x < a but for the sake of contradiction assume x > a, then
we get
b2 − k
>a
a
⇒
b2 − k > a 2
⇒
b2 − a2 > k > 0
which is false since we assumed a > b. So there’s a contradiction, which suggests that x < a.
So, we started with (a, b) and constructed (x, b) as a solution with x + b < a + b. So we have
the first part of our chain of solutions of an Infinite descent, but we really got to show that
this chain will continue, which unfortunately for us is not really obvious. This is so because
now if we start with (x, b), we’ll get a quadratic in x and we’ll again get a as the other root,
which we’ll again give (a, b) as our solution, that is
(a, b) → (x, b) → (a, b)
and this is of course not what we want. So, to get a new pair we should make a quadratic in
b. The new quadratic would look like
f (t) = t2 − kxt + x2 − k
with one of roots being b and the other, say y.Therefore our original expression would be
converted to
y 2 + x2
k=
xy + 1
So, this time we started with (b, x) and got to (y, x). Again we can show that b > x just like
last time we had a > b.
b2 b2 − k
b> > =x
a a

8
Diophantine Equation Aayush Kumar

To get a descent we also need to prove that y < b. This can be proved just like how we showed
x < a, so this is left for the reader. Now, this is a infinite descent as our chain of solution is

(a, b) → (x, b) → (y, x) → ...

with a+b < x+b < y+x. Hence, we went from positive to ”smaller” positive pairs (how do you
really compare pairs??, that’s why we talk about the sum of the pairs) but this process can’t
go on forever, so this leads to a Contradiction which means k is in fact a perf ect square . ■

Exercise
Q:(Korean Mathematical Olympiad) Prove that x2 + y 2 + z 2 = 2xyz has no solution
over integers except (0, 0, 0).
Note: (Be careful that you can’t apply infinite descent directly here since x, y, z are not
necessarily only positive integers.)

Q:(stronger version of IMO 1988,P6.) Show that if ab + 1 divides a2 + b2 for posi-

tive integers a, b then
a2 + b2
= gcd(a, b)2
ab + 1

§8 Pell’s Equations
Any equation of the form of x2 − Dy 2 = 1 where D is a positive integer but not a perfect
square is called a Pell’s Equation. There’s actually a lot of controversy over the name as
Pell had nothing to do with the solution of these equations. The first mathematician known
to have done some significant work on these types of equations was Brahmagupta from India
when he found positive integer solutions to the equation x2 − 92y 2 = 1.

Theorem 8.1: There always exist a solution (x, y) to a Pell’s Equation. The proof
of this beautiful theorem actually comes from Continued Fractions which is out
of scope of this material (and you can use this theorem on contest without actually
proving it.) Even though, we won’t prove this theorem, We’ll still want to understand
how continued fractions help us find what’s called the Fundamental Solution.

Theorem 8.2: Given that there exists one solution (x0 , y0 ) to a Pell’s equation, we
can actually find an infinte number of solutions to the equation, with (x0 , y0 ) being
the smallest. The smallest solution is what we call as the Fundamental Solution.

Proof: Before starting with the proof,

√ we need to define some terms.
Norm: Let √ a number z = x + y d. Then, the conjugate of z, denoted by z̄, is given by
z̄ = x − y d. The Norm of z is given by

N (z) = z z̄ = x2 − dy 2

9
Diophantine Equation Aayush Kumar

Theorem 8.2.1: N (z1 z2 ) = N (z1 )N (z2 )

2 2
√ get back our original equation x −Dy =
The proof is simple and left for the reader. Now, let’s
1. Observe that if we define a number z = x + y D, then it satisfies that
N (z) = x2 − Dy 2 = 1
. Also notice that if N (z) = 1, then so is N (z 2 ) since
N (z 2 ) = N (z)N (z) = 1
, in fact we have
N (z k ) = N (z)N (z)... = 1
for any natural number k. Hence, if z satisfies the equation, then so does z k . So, we went
from one solution to infinitely many. ■

Theorem 8.3: Let√d be a positive integer which is not a perfect square. Then there
exists ϵ = x0 + y0 d with (x0 , y0 ) ∈ N such that every solution (x, y) to the Pell’s
Equation is found by √ √
x + y d = ϵn = (x0 + y0 d)n
for some integer n.

This theorem actually states that every solution to a Pell’s equation is given by some natural
power of the fundamental solution. √
Proof: Let α be the smallest √ real number of the form of x + y d greater than 1 with it’s
norm = 1. Now, let β = a+b d be another real number such that (a, b) satisfies the equation
X 2 − DY 2 = 1. Let k be such that
αk ≤ β < αk+1
Let
β √ √
γ= k
= (a + b d)(x − y d)k
α
√
Now, clearly N (γ) = 1 and on expanding γ comes out √ to be of the√form of r + s d. Note
that γ ≥ 1 which means γ̄ ≤ 1 (why?). Hence,
√ r − s d ≤ 1 ≤ r + s d, showing r and s are
non negative. Notice that since γ = r + s d with norm = 1, this also satisfies our original
equation X 2 − DY 2 = 1 and γ < α, so it contradicts the minimality of α unless γ = 1, which
implies β = αk . ■

Now, let’s do an example on how we find different solutions using the known fundamental
solution.

Q: Find (x,y) such that x2 − 3y 2 = 1 over positive integers.

10
Diophantine Equation Aayush Kumar

Solution: We need to either guess our fundamental solution or find it using continued frac-
tion, for smaller values of d like 3, I would recommend you to first at least try to guess the
smallest solution instead of using continued fraction as it gets very messy (by guessing, I √
ac-
tually mean checking by hit and trial). Clearly, (2, 1) is the smallest solution. So z = 2 + 3
works. Now we √ know other numbers that would actually work will all be of the form z k .
that √
2 2
So, z = (2 + 3) = 7 + 4 3 works. Hence, we get another solution (x, y) = (7, 4). Similarly
we can find other solutions by raising different natural powers of z. ■

§9 Brahmagupta’s idea of solving Pell’s Equation

He solved x2 − 92y 2 = 1 over positive integers and became first person known to work on
solution of Pell’s Equation. Since, d = 92 is a large number, we can get some ideas from
his solution and use it to find f undamental solution whenever d is large. Let’s solve this
equation using his idea but actually for d = 23 and hope that our y turns out to be even
(why?). So, we have
x2 − 23y 2 = 1
Divide by y 2 to get
 2
x 1
− 23 = 2
y y
1
Now since y is a positive integer, y2 ≈ 0, so we get
x √
≈ 23
y
√
So, we need a fraction which is approximately
√ equal to 23. This is where continued frac-
tions help. We try to represent 23 as an Infinite continued fraction to get approximate
values of x, y.

√
§9.1 Representing d as a continued fraction
Without getting into too much technical terms, we’ll just see how we actually do it else it
will get very messy and we’ll actually get off track of our main goal which is solving the Pell’s
Equation. Let’s see this with an example. We have,
√
[ 23] = 4

where [x] = greatest integer ≤ x. See, that we can actually write

√
23 = 4 + x

where x < 1. To get x we actually use a clever technique

√ √
23 = 4 + ( 23 − 4)

11
Diophantine Equation Aayush Kumar

⇒
√ 1
23 = 4 +
√ 1
23−4

which upon rationalization gives

⇒
√ 1
23 = 4 + √
23+4
7
√ √
Now what we did with 23, we’ll do the same with 23+4
7 . So, we have
√
23 + 4
[ ]=1
7
⇒ √ √
23 + 4 23 + 4
=1+( − 1)
7 7
√
using this value in the expression of 23, we get
√ 1
23 = 4 + √
23+4
1+( 7 − 1)
⇒
√ 1 1
23 = 4 + √ =4+ 1
1+ 23−3 1+ √ 7
7 23−3

We can continue doing this to finally get

√ 1
23 = 4 + 1
1+ 3+ 1
1+ 1
8+....

√ x
Now that we have got the approximate expression for 23 we can compare this with y.
Suppose, we assume
1
≈0
3 + 1+ 1 1
8+....

then we get
x √ 1
= 23 = 4 + =5
y 1+0
so, we get x = 5, y = 1 now let’s see if this pair satisfies our equation

x2 − 23y 2 = 1

Substituting the value of x, y we get

25 − 23 = 2

which clearly doesn’t work. So, let’s try for a better approximation by taking
1
≈0
8 + ....

12
Diophantine Equation Aayush Kumar

then we get
x 1 4 24
=4+ =4+ =
y 1 + 3+1 1 5 5
1+0

So this time we get x = 24, y = 5 which upon substitution gives

242 − 23 ∗ 52 = 1

So, finally we get a pair which indeed works for the equation x2 − 23y 2 = 1. But, to actually
solve x2 − 92y 2 = 1, we wanted y to be even, but unfortunately for us, y = 5. But, we really
equation x2 −23y 2 = 1 since√we
shouldn’t be disappointed as we can find other solutions to the √
already have the fundamental solution. So, since z = 24+5 23 works, z 2 = 1151+240 23
also works. So, we get another solution as x = 1151, y = 240 and indeed, y is even. So, we
have
11512 − 92 ∗ 1202 = 1
Hence, we finally get a solution as x = 1151, y = 120 to the equation x2 − 92y 2 = 1. ■

Exercise
√
(Kurshak Competition) Q: Prove that if m = 2 + 2 28n2 + 1 is an integer for some
n ∈ N then m is a perfect square.

§10 Recursive Solutions of Pell’s Equation

Let x2 − Dy 2 = 1 be a Pell’s Equation with a fundamental solution (x0 , y0 ). Let (xn−1 , yn−1 )
be its nth solution. Then,

xn = 2x0 xn−1 − xn−2 , yn = 2y0 yn−1 − yn−2

We can solve this recursive relation to get a explicit form for xn−1 and yn−1 . Upon solving
we’ll get
√ n √ n √ n √ n
   
1 1
xn−1 = (x0 + y0 D) + (x0 − y0 D) , yn−1 = √ (x0 + y0 D) − (x0 − y0 D)
2 2 D

§11 Mixed Problems

√
1. Represent 5 as a continued fraction.

2
2. Find all pairs (a, b) of positive integers that satisfy the equation ab = ba .

3. (Romanian Mathematical Olympiad). Prove that there are infinitely many quadru-
ples (x, y, z, t) of positive integers with no common divisors such that

x3 + y 3 + +z 2 = t4

13
Diophantine Equation Aayush Kumar

4. (IMO Shortlist 2019 N2). Find all triples (a, b, c) of positive integers such that
2
a3 + b3 + c3 = (abc) .

5. Prove that 1919 cannot be written as a sum of a perf ect cube and a perf ect f ourth power.

6. (China TST 3 2018). Find all pairs of positive integers (x, y) such that (xy + 1)(xy +
x + y + 2) is a perfect square.

7. (IMO Shortlist 1991, P17). Find all positive integers (x, y, z) satisfying the equation

3x + 4y = 5z

14