Tag Archives: diophantine equation

Proof of a special case of Pillai’s conjecture

In the last post we conjectured that given fixed integers A, B, C, D, E>0 with BD>1, the equation

(*)\qquad\qquad\qquad\qquad\quad A\cdot B^x-C\cdot D^y=E

has only finitely many solutions (x,y) in integers. Let us prove this conjecture.

If (*) has no solution we are done. Otherwise suppose that (x_0,y_0) is a solution. Assume the contrary, and let S denote the infinite set of solutions (x,y). For any (x,y)\in S, we have

AB^x-AB^{x_0}=CD^y-CD^{y_0}.

So, if (*) has infinitely many solutions, then writing

\displaystyle u_x=AB^x-AB^{x_0},\quad v_y=CD^y-CD^{y_0}

gives that u_x=v_y for infinitely many x,y\in\mathbb N_0. So by Theorem 1.1 in this paper (or this one),

B^r=D^s

for some positive integers r,s. So \min\{B,D\}\mid\max\{B,D\} (exercise). But then \min\{B,D\}^{\min\{x,y\}} divides E for all (x,y)\in S, implying \min\{x,y\} is bounded over all (x,y)\in S. But then, by (*), \max\{x,y\} must also be bounded over all (x,y)\in S. Thus S is finite, a contradiction.

Leave a comment

Filed under Number theory

Catalan-type diophantine equations

Let’s say we want to find all integers x,y such that

2^x-5\cdot 3^y=1.

Suppose that x,y are sufficiently large. Having spotted the solution x=4,y=1, re-write the equation as

2^x-5\cdot 3^y=2^4-5\cdot 3\Leftrightarrow 16(2^{x-4}-1)=3\cdot 5(3^{y-1}-1).

So 16\mid 3^{y-1}-1. Checking the powers of 3 modulo 16 one deduces that 4\mid y-1. Writing y-1=4k therefore gives

16(2^{x-4}-1)=3\cdot 5\cdot 80(1+81+\cdots+81^{k-1}),

i.e.,

2^{x-4}-1=3\cdot 5^2(1+81+\cdots+81^{k-1}).

Hence 5^2=25\mid 2^{x-4}-1. As before, one deduces that 20\mid x-4. (A better way: since \hbox{ord}_5(2)=4, we have \hbox{ord}_{25}(2)=5\cdot 4=20 by this.) Writing x-4=20m gives

11\cdot 31\cdot 41(1+2^{20}+\cdots+2^{20(m-1)})=1+81+\cdots+81^{k-1}.

Using 81\equiv -1\pmod{41}, it follows that k must be even. Then 1+81=82 divides the left-hand side, which is impossible since the left-hand side is always odd. Thus we conclude that x=4,y=1 is the only solution.


This kind of approach usually works for many similar equations. The basic idea is the following:

  1. Guess an initial solution.
  2. Use the initial solution to group terms and factor them.
  3. Use congruence relations to restrict the variables.
  4. Eventually one side will likely have a prime factor that does not divide the other side.

This motivates the following:

Conjecture. Given integers A, B, C, D, E>0 with BD>1, the equation

A\cdot B^x-C\cdot D^y=E

has only finitely many solutions in integers.

This turns out to be a special case of a more general conjecture known as Pillai’s conjecture.

(All this arose when I was trying to make A,C as small as possible with respect to x,y, which range through the positive integers satisfying

A\cdot 2^x-C\cdot 3^y=1.)

1 Comment

Filed under Number theory

Sums of equal powers

Let k be a fixed positive integer. Let

S_k(n):=1^k+\cdots+n^k.

Let us consider expressions of the form

\pm 1^k\pm\cdots\pm n^k=\displaystyle\sum_{j=1}^nj^ke_j=: S(e_1,\dots,e_n)

where e_j=\pm 1\,\forall j.

Note that S takes 2^n possible values in [-S_k(n),S_k(n)] which are all congruent modulo 2. Hence the number of distinct values that S takes is at most

\displaystyle\left\lceil\frac{2S_k(n)+1}{2}\right\rceil=S_k(n)+1

Since this is O(n^{k+1}), it is eventually dominated by 2^n. Thus for all sufficiently large n, we can find e_j,e_j'\in\{\pm 1\} such that

\displaystyle\sum_{j=1}^nj^ke_j=\sum_{j=1}^nj^ke_j'\Leftrightarrow\sum_{j=1}^n(e_j-e_j')j^k=0

with e_j\neq e_j' for some j.

Note that e_j-e_j'\in\{0,\pm 2\}\,\forall j. Let A=\{j:e_j-e_j'=2\} and B=\{j:e_j-e_j'=-2\}. Then A and B are non-empty and disjoint, A\cup B\subseteq\{1,\dots,n\}, and

\displaystyle\sum_{j\in A}j^k=\sum_{j\in B}j^k.

Thus:

Proposition. Let k be a fixed positive integer. Then one can find distinct positive integers x_1,\dots, x_r,y_1,\dots,y_s such that

x_1^k+\cdots+x_r^k=y_1^k+\cdots+y_s^k.

In particular, one can choose x_i,y_j\le\min\{n\in\mathbb N: 2^n>S_k(n)+1\}\,\forall i,j.

Example. Let k=4. Note that 2^n>S_4(n)+1 for all n\ge 20. So there exist distinct integers 1\le x_i,y_j\le 20 such that \sum_ix_i^4=\sum_jy_j^4. In particular, one has

1^4+2^4+9^4=3^4+7^4+8^4

as well as

7^4+8^4+10^4+13^4=3^4+9^4+14^4.

Likewise, for fifth powers we can find such x_i‘s and y_j‘s in [1,26].

This wikipedia article contains many results related to sums of powers.

Leave a comment

Filed under Number theory

A ‘sum of squares’ problem

Recently I came to know from a friend that the only non-trivial value of n satisfying the Diophantine equation

1^2+2^2+\dots+n^2=m^2

is n=24. And apparently, although the problem looks fairly simple, especially since we have the formula for the left hand side

\displaystyle 1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}

the proof is hard. In fact, I was told that all proofs of this result use advanced machinery. Nevertheless, given the simple nature of the problem I was intrigued to give it a try.

So let us assume that

n(n+1)(2n+1)=6m^2.

Noting that 2n(n+1)-n(2n+1)=n, we have that n(n+1) and 2n+1 are coprime. Indeed, if g is a common factor, then g has to divide both n and 2n+1, forcing g=1. So we deduce that

\{n(n+1),2n+1\}=\{a^2,6b^2\} or \{2a^2,3b^2\}

for some integers a,b.

Note that 2n+1\not\in \{2a^2,6b^2\} so 2n+1\in\{a^2,3b^2\}. Hence the possibilities are:

(i) n(n+1)=2a^2, 2n+1=3b^2.

(ii) n(n+1)=6b^2, 2n+1=a^2.

First suppose that n(n+1)=2a^2. Then n(n+1)/2=a^2 is a square triangular number, so

n=\displaystyle\frac{H_{2k}-1}{2}

for some k, where P_0,P_1,\dots are the Pell numbers. and H_0,H_1,\dots are the half-companion Pell numbers, and they are given by (1+\sqrt 2)^k=H_k+P_k\sqrt 2 for each k. So we have to find all k such that

2n+1=\boxed{H_{2k}=3b^2}.

On the other hand, if 2n+1=a^2, then a=2c-1 for some integer c. Then n=2c(c-1). Hence n(n+1)=6b^2 implies

c(c-1)(2c^2-2c+1)=3b^2.

Now \gcd(c(c-1),2c^2-2c+1)=1, so \{c(c-1),2c^2-2c+1\}=\{u^2,3v^2\} for some integers u,v. Clearly c(c-1)\neq u^2, so

c(c-1)=3v^2 and 2c^2-2c+1=u^2.

So \{c,c-1,u\} is a near isosceles Pythagorean triple, i.e.

c=\displaystyle\frac{H_{2k-1}+1}{2}.

Hence

\boxed{H_{2k-1}^2-1=12v^2\Leftrightarrow P_{2k-1}^2-1=6v^2\Leftrightarrow P_{2k}P_{2k-2}=6v^2}.

The two boxed cases are what only remain to check, and they show why this actually is a difficult problem! (Refer to the articles about Fibonacci numbers in the ‘Notes and Articles’ tab above to see how little information we have on divisors of sequences of this kind.) Nevertheless, I’ll leave it here and maybe come back to it another time.

1 Comment

Filed under Number theory

A generalisation of Pell’s equation

We want to find the solutions to

(*)\qquad x^2+mxy+ny^2=1

over the integers, where m,n\in\mathbb Z.

Let \alpha and \bar\alpha be the roots of x^2+mx+n=0. We can factorise (*) as (x-y\alpha)(x-y\bar\alpha)=1. If \alpha is rational, it must be an integer and then it is easy to find all solutions. So let us consider the more interesting case where \alpha is not rational (i.e. \sqrt{m^2-4n}\not\in\mathbb Z).

Now a solution in the form z=x-y\alpha to (*) is a unit in the ring \mathbb Z[\alpha]. For z=x-y\alpha\in\mathbb Z[\alpha], denote its conjugate by \bar z=x-y\bar\alpha. Then we have the multiplicative norm

N(z)=N(x-y\alpha)=z\bar z=x^2+mxy+ny^2.

It follows that the solutions to (*) form a subgroup S of the multiplicative group of units of \mathbb Z[\alpha].

Case 1: m^2< 4n. Then (*) defines an ellipse, so there are at most finitely many solutions, i.e. S is a finite subgroup of \mathbb C^\times. Hence S is cyclic and every solution is of the form

\displaystyle x-y\alpha=\cos\frac{2\pi t}{k}+i\sin\frac{2\pi t}{k},\quad x-y\bar\alpha=\cos\frac{2\pi t}{k}-i\sin\frac{2\pi t}{k}

\displaystyle \Rightarrow 2x+my=2\cos\frac{2\pi t}{k}\in [-2,2]\cap\mathbb Z\Rightarrow \cos\frac{2\pi t}{k}\in\{0,\pm\frac 12,\pm1\}

\displaystyle\Rightarrow x-y\alpha\in\{\pm 1,\pm i, \frac{1\pm i\sqrt 3}{2}, \frac{-1\pm i\sqrt 3}{2}\}.

Case 2: m^2>4n. Now \alpha is real, so S is a subgroup of \mathbb R^\times.

Claim. S is not dense.

Proof. WLOG S\neq\{\pm 1\}. Then for z=x-y\alpha\in S\backslash\{\pm 1\} we have

\displaystyle \left |z-\frac 1z\right |=|y(\alpha-\bar\alpha)|\ge |\alpha-\bar\alpha|=\sqrt{m^2-4n}=:\varepsilon> 1.

Suppose that 1<z<\varepsilon is a solution. Then

\displaystyle \left |z-\frac 1z\right |=z-\frac 1z<\varepsilon-\frac 1\varepsilon<\varepsilon,

impossible. Thus S\cap (1,\varepsilon)=\emptyset, i.e. S is not dense. \square

It follows that S is either \{\pm 1\} or \langle\delta\rangle\cup -\langle\delta\rangle for some \delta>1 (cf. ordering in groups, corollary 4). Therefore all solutions (x,y) to (*) are either just (\pm 1,0), or are given by

\boxed{x-y\alpha=\pm (x_0-y_0\alpha)^k,\; k\in\mathbb Z}

where x_0-y_0\alpha is the least solution >1.

Corollary. (Dirichlet’s unit theorem for a real quadratic field) If K is a real quadratic field, then \mathcal O_K^*=\{\pm\varepsilon^n: n\in\mathbb Z\} for some \varepsilon\ge 1.

Leave a comment

Filed under Algebra, Number theory