Monthly Archives: September 2015

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

Chebyshev polynomials and algebraic values of the cosine function

Let p be an odd prime and let T_n(X) be the n-th Chebyshev polynomial of the first kind. By Lemma 1 on page 5 of this paper, T_p(X)/X is irreducible over \mathbb Q. Now

\displaystyle T_p(\cos\frac{\pi}{2p})=\cos\frac{\pi}{2}=0,

so the minimal polynomial of \cos(\pi/2p) over \mathbb Q is T_p(X)/X. (Note that we are slightly abusing terminology here. By definition, the minimal polynomial is a monic polynomial. But let us drop precision for the sake of brevity.)

By definition (and induction, if you may), \deg(T_n)=n. Hence we deduce the following:

Proposition 1. \cos(\pi/2p) is an algebraic number of degree p-1.

Since T_p(X)/X consists of only even powers of X, T_p(\cos(\pi/2p)) can be expressed as a polynomial in \cos(\pi/p)=2\cos^2(\pi/2p)-1. Therefore:

Proposition 2. \cos(\pi/p) is an algebraic number of degree (p-1)/2.

A nice corollary of this is Niven’s theorem:

Corollary (Niven’s theorem). If \theta\in (0,\pi/2) is a rational multiple of \pi such that \cos\theta is rational, then \theta=\pi/3.

Proof. Note that if \cos\theta is rational, then so is \cos(n\theta)=T_n(\cos\theta) for any positive integer n. So, (reduction 1) without loss of generality, \theta=k\pi/p for some odd prime p and positive integer k<p/2. (The case p=2 is dealt with trivially.)

Further, multiplying by the inverse of k\pmod p, (reduction 2) one may assume k=1 without any loss of generality.

Now being rational is the same as being algebraic of degree 1. Hence, by the above, we must have p=3 and the conclusion follows immediately. \square

Exercise. Find all rational multiples \theta\in(0,\pi/2) of \pi such that \cos\theta is a quadratic irrational.

Leave a comment

Filed under Algebra, Number theory