Maths Olympiad Prep

Library / /70 of 155

Number theory Difficulty 6.0 AIME, harder Prove it Saudi Arabia

How many integers nn satisfy the following conditions?
i) 219n2019219 \leq n \leq 2019,
ii) there exist x,yZx, y \in \mathbb{Z} such that 1x<n<y1 \leq x < n < y and yy is divisible by all integers from 11 to nn, except two numbers xx and x+1x+1.

Solution

The answer is 292292.

We can see that if x=pqx = pq for some integers p,q>1p, q > 1 and gcd(p,q)=1\gcd(p, q) = 1 then 1<p,q<x1 < p, q < x which implies that pyp \mid y, qyq \mid y, then pqypq \mid y, contradiction.

Hence xx and x+1x+1 must be the powers of primes. But one of these numbers is even so one of them must be the power of 22. On the other hand, nn must be less than 2x2x, otherwise 2xy2x \mid y leads to xyx \mid y, contradiction. With the existence of xx we can easily choose yy.

Thus, number nn satisfies the given condition if and only if there exists an exponent of 22 less than nn and bigger than n/2n/2, namely xx such that x+1x+1 or x1x-1 is a power of some prime. We can check directly each range of numbers:

1. For each number 219n255219 \leq n \leq 255 we can choose x=1271x = 127^{1}, x+1=27x+1 = 2^{7}.

2. For each number 257n511257 \leq n \leq 511 we can choose x=28x = 2^{8} and x+1=2571x+1 = 257^{1}.

3. For each number from 513n1023513 \leq n \leq 1023 we cannot choose any xx since 511511 and 513513 are not the powers of prime.

4. For each number from 1025n20191025 \leq n \leq 2019 we cannot choose any xx since 10231023 and 10251025 are not powers of prime.

Therefore, the total number of integers we need to find is 37+255=29237 + 255 = 292. \square

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.