# Category Archives: Number theory

## Products of consecutive integers dividing one another

I’ve been working on a project lately and I find myself stuck with the following problem.

Problem. Given positive integers $a, what can be said about the least positive integer $t$ such that $a(a+1)\cdots (a+t)$ does not divide $b(b-1)\cdots (b-t)$?

Obviously $t$ is bounded above by $b-a+1$ but this is very weak. Probably the least $t$ should be close to $b/a$.

Filed under Number theory

## A nice divisibility result on binomial coefficients

I just came across this cute little result on Quora and generalised it to the following.

Proposition. For any integers $0,

$\displaystyle\frac{n}{(n,k)}$ divides $\displaystyle\binom{n}{k}$.

First proof. Note that

$\displaystyle \frac{k}{(n,k)}\binom nk=\frac{n}{(n,k)}\binom{n-1}{k-1}$.

Since $\displaystyle\left(\frac{n}{(n,k)},\frac{k}{(n,k)}\right)=1$, the result follows. $\square$

Second proof. Let $n=p_1^{a_1}\cdots p_r^{a_r}$ and $k=p_1^{b_1}\cdots p_r^{b_r}$ where $p_1,\dots,p_r$ are the prime factors of $nk$. For each $i$, the base $p_i$ representations of $n$ and $k$ have $a_i$ and $b_i$ trailing zeros respectively. Hence by Kummer’s theorem $p_i^{\max\{a_i-b_i,0\}}$ divides $\displaystyle\binom nk$. Hence

$\displaystyle k\prod_{i=1}^rp_i^{\max\{a_i-b_i,0\}}=\prod_{i=1}^rp_i^{\max\{a_i,b_i\}}=[n,k]$

divides $\displaystyle k\binom nk$. Now the result follows using $[n,k]/k=n/(n,k)$. $\square$

A nice corollary is the following property of Pascal’s triangle.

Corollary. For any integers $0,

$\displaystyle\gcd\left(n,\binom nk\right)>1$.

Using the identity

$\displaystyle\binom nk\binom kr=\binom nr\binom{n-r}{k-r}$

the argument in the first proof above can be adapted to prove the following generalisation:

Proposition. For any integers $0\le r\le k\le n$,

$\displaystyle\frac{\binom nr}{\left(\binom nr,\binom kr\right)}$ divides $\displaystyle\binom{n}{k}$.

Corollary. Any two entries $\neq 1$ in a given row of Pascal’s triangle have a common factor $>1$.

Filed under Number theory

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

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