# 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 $B = 1$ or $D = 1$ then we are done. So assume that $B,D>1$. If $(*)$ has no solution we are done. Otherwise, let $(x_0,y_0)$ be a solution. Assume towards a contradiction that $S$ is the infinite set of solutions $(x,y)$ of $(*)$. For any $(x,y)\in S$, we have

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

i.e.

$\displaystyle\frac{B^{x-x_0}-1}{D^{y-y_0}-1} = \frac{CD^{y_0}}{AB^{x_0}}$.

This means that

$\displaystyle \frac{B^X-1}{D^Y-1}$

is equal to a constant for infinitely many $X,Y\in\mathbb N_0$. Since $\gcd(a^{X_1}-1,a^{X_2}-1) = a^{\gcd(X_1,X_2)}-1$, it follows that

\displaystyle \begin{aligned}&\frac{B^{X_1}-1}{D^{Y_1}-1} = \frac{B^{X_2}-1}{D^{Y_2}-1}\iff\\&\begin{cases}\displaystyle\frac{B^{X_1}-1}{B^{\gcd(X_1,X_2)}-1}=\frac{D^{Y_1}-1}{D^{\gcd(Y_1,Y_2)}-1}\\\displaystyle\frac{B^{X_2}-1}{B^{\gcd(X_1,X_2)}-1}=\frac{D^{Y_2}-1}{D^{\gcd(Y_1,Y_2)}-1}\end{cases}\end{aligned}

for infinitely many $X_1,X_2,Y_1,Y_2\in\mathbb N_0$. In particular,

$\displaystyle \frac{B^X-1}{B^x-1}=\frac{D^Y-1}{D^y-1}$

for infinitely many $X,Y,x,y\in\mathbb N_0$ with $x\mid X$ and $y\mid Y$. So by the corollary to Theorem 1 of [1],

$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.

### References

1 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 result.) 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.

Proof. Next post. $\square$

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.

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 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$.