Competition problem — Number theory

Library / /23 of 86

Number theory Difficulty 5.4 AIME, harder Prove it Estonia

We call positive integers $n, m$ an interesting pair if $n < m$ and the greatest prime factor of $n$ is equal to the greatest prime factor of $m$ .

a. For an interesting pair $n, m$ , will there always exist a prime $p$ such that $n < p < m$ ?

b. Among the first 25 positive integers, how many don't form an interesting pair with any smaller positive integer?

Solution

(a) The pair $24, 27$ is interesting, as the greatest prime factor of them both is $3$ . However, there are no primes between them.

(b) The number $1$ and prime numbers cannot form a pair with any smaller integers. However, each composite number forms a pair with its greatest prime factor, which is clearly smaller. Among the first $25$ positive integers, the primes are $2, 3, 5, 7, 11, 13, 17, 19$ and $23$ . Taking into account also the number $1$ , there are $10$ numbers among the first $25$ positive integers that don't form an interesting pair with any smaller positive integer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.