Two distinct primes $p$ and $q$ are given.

  • a) Are there always two consecutive natural numbers such that one of them has the greatest prime divisor $p$, and the other has $q$?
  • b) Prove that there are two such natural numbers if $q<p<2q$.

a) Let $p=11$, $q=2$. If $n$ is divisible by $p$ and $n+1$ is divisible by $q$, where $p,q$ are the greatest prime divisors, then $n+1$ is a power of two. Modulo $11$, all nonzero remainders are observed for powers of two, that is, the period is $10$. This shows that $2^k-1$ is a multiple of $11$ <=> $k$ is a multiple of $10$. Thus, for $n+1=2^k$ we have $n=2^k-1$ is divisible by $11$ and $k$ is divisible by $10$, hence $2^k-1$ is divisible by $2^5-1=31$, so $11$ is not the greatest prime factor.

But I have difficulties with the b)... Can you help?


1 Answer 1


First, if $q=2$, we must have $p=3$. This case is trivial, since $p$ and $q$ are consecutive primes. From now on, assume that $q>2$.

Claim: There exist positive integers $a,b$ with $a$ even, $b<q$ and $aq-bp:=\varepsilon\in\{\pm 1\}$.

Proof: Find $x_0,y_0\in\mathbb{Z}$ such that $x_0q-y_0p=1$. Note that $(x_0+kp)q-(y_0+kq)p=1$ for all $k\in\mathbb{Z}$. Pick $k_0$ such that $0<y_0+k_0q<q$. If $x_0+k_0p$ is even, pick $a:=x_0+k_0p$ and $b:=y_0+k_0q$. If $x_0+k_0p$ is odd, pick $a=(1-k_0)p-x_0$ and $b:=(1-k_0)q-y_0$. $\square$

Now, let $a,b$ as in the claim and set $n:=aq$. It is trivial that $q\mid n$ and $p\mid n+\varepsilon$. We have to show that these are the largest prime divisors.

First, it is clear that $(n+\varepsilon)/p=b<q<p$, so $p$ is the largest prime factor of $n+\varepsilon$. Next, $2q\mid n$, and $$ \frac{n}{2q} = \frac{bp+\varepsilon}{2q}=\frac{p}{2q}\cdot\frac{bp}{p}+\frac{\varepsilon}{2q} <b+\frac{\varepsilon}{2q}, $$ so $n/2q<q$ and because $q>2$, the largest prime factor of $n$ is $q$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .