AoPS - Problem

Processing math: 100%

Problem

Source: St.Petersburg 2016 Grade 9 P4

Tags: number theory

tenplusten

07.04.2018 22:27

Two different prime numbers $p$ and $q$ differ in less than $2$ times. Prove that exists two consecutive natural numbers, such that largest prime divisor of first number is $p$ , and largest prime divisor of second number is $q$ .

suli

08.04.2018 02:35

Bezout tells us $qb - pa = \pm 1$ for some positive integers $a, b$ with $1 \le b \le \frac{p}{2}, 1 \le a \le \frac{q}{2}$ . The largest prime divisor of $qb$ is $q$ , and the largest prime divisor of $pa$ is $p$ .

We know

$qb - pa = 1$ for some positive integers

$a, b$ with

$1 \le b \le p, 1 \le a \le q$ ; this is straightforward Bezout and noticing that if

$(a, b)$ is solution, then so is

$(a - q, b - p)$ . If

$a \le \frac{q}{2}$ then

$b \le \frac{p}{2}$ , and the largest prime divisor of

$qb$ is

$q$ , and that of

$pa$ is

$p$ since

$p < \frac{q}{2}$ . If

$a > \frac{q}{2}$ then

$(q - a, p - b)$ satisfies

$px - qy = 1$ ; and repeat same argument, since

$q - a < \frac{q}{2}, p - b < \frac{p}{2}$ .